# Learning Partial Graph Matching via Optimal Partial Transport

arXiv: https://arxiv.org/abs/2410.16718 · HTML: https://mlsanity.com/paper/2410.16718/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 19 of 19)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [SPair-71k: A Large-scale Benchmark for Semantic Correspondence](https://mlsanity.com/paper/1908.10543/) (2019)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Sliced Optimal Partial Transport](https://mlsanity.com/paper/2212.08049/) (2022)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [A Functional Representation for Graph Matching](https://mlsanity.com/paper/1901.05179/) (2019)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)
- [Graph Neural Networks for User Identity Linkage](https://mlsanity.com/paper/1903.02174/) (2019)
- [Universe Points Representation Learning for Partial Multi-Graph Matching](https://mlsanity.com/paper/2212.00780/) (2022)
- [Spectral Maps for Learning on Subgraphs](https://mlsanity.com/paper/2205.14938/) (2022)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (2022)
- [Subgraph Matching via Partial Optimal Transport](https://mlsanity.com/paper/2406.19767/) (2024)

## Built on by (most cited first, 2 of 2)

- [AutoSew: A Geometric Approach to Stitching Prediction with Graph Neural Networks](https://mlsanity.com/paper/2602.22052/) (2026)
- [Preserving Geometric Integrity in Graph Prompting via Measure-Constrained Optimal Transport](https://mlsanity.com/paper/2609.23547/) (2026)

## Abstract (arXiv)

Partial graph matching extends traditional graph matching by allowing some nodes to remain unmatched, enabling applications in more complex scenarios. However, this flexibility introduces additional complexity, as both the subset of nodes to match and the optimal mapping must be determined. While recent studies have explored deep learning techniques for partial graph matching, a significant limitation remains: the absence of an optimization objective that fully captures the problem's intrinsic nature while enabling efficient solutions. In this paper, we propose a novel optimization framework for partial graph matching, inspired by optimal partial transport. Our approach formulates an objective that enables partial assignments while incorporating matching biases, using weighted total variation as the divergence function to guarantee optimal partial assignments. Our method can achieve efficient, exact solutions within cubic worst case time complexity. Our contributions are threefold: (i) we introduce a novel optimization objective that balances matched and unmatched nodes; (ii) we establish a connection between partial graph matching and linear sum assignment problem, enabling efficient solutions; (iii) we propose a deep graph matching architecture with a novel partial matching loss, providing an end-to-end solution. The empirical evaluations on standard graph matching benchmarks demonstrate the efficacy of the proposed approach.