Research map / Graph learning / Graph algorithms and clustering
Learning Partial Graph Matching via Optimal Partial Transport
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an optimal-partial-transport objective with weighted total variation divergence that reduces partial graph matching to a linear assignment problem solvable exactly by the Hungarian algorithm, and a deep end-to-end model (OPGM/OPGM-rs) with a partial matching loss.
Problem
Partial graph matching, where some nodes in each graph may remain unmatched and both the matched subset and the mapping must be determined; prior deep methods rely on ILP with dummy nodes or multi-stage k-estimation.
Approach
Uses weighted total variation as the divergence in optimal partial transport, with per-node matching biases, so that optimal partial assignments are guaranteed; this embeds partial matching into a linear sum assignment problem solvable exactly with the Hungarian algorithm in cubic time.
Key results
- On SPair-71k, OPGM-rs (GCAN backbone) reaches 57.7 mean matching F1 vs 55.7 for best GCAN+AFAT baselines.
- On IMCPT 100, OPGM-rs achieves 72.8 mean F1, above the best baseline GCAN+AFAT-I at 70.9.
- OPGM-rs inference time is 117.8 ms per pair vs 367.1 ms for AFAT-I and 561.1 ms for GCAN on IMCPT 100.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn matching biases instead of fixing them equal (ablation) | OPGM with GCAN · SPair-71K | matching F1-score: 56.5 ± 0.4 -> 57.7 ± 0.2 | Helped |
| Learn matching biases instead of fixing them equal (ablation) | OPGM with GCAN · IMCPT 50 | matching F1-score: 72.1±0.2 -> 72.7±0.1 | Helped |
| Learn matching biases instead of fixing them equal (ablation) | OPGM with GCAN · IMCPT 100 | matching F1-score: 72.3±0.4 -> 72.8±0.1 | Helped |
| Vary the unbalancedness parameter ρ (ablation) | OPGM-rs · SPair-71K and IMCPT 100 | matching F1-score | Mixed |
| Vary the regularization parameter λ (ablation) | OPGM-rs · SPair-71K and IMCPT 100 | matching F1-score | No clear effect |
| Use OPGM-rs instead of AFAT-I | IMCPT 100 inference · IMCPT 100 | inference time (ms): 367.1 -> 117.8 | Helped |
| Use OPGM-rs instead of AFAT-U | IMCPT 100 inference · IMCPT 100 | inference time (ms): 371.8 -> 117.8 | Helped |
| Use OPGM-rs instead of GCAN | IMCPT 100 inference · IMCPT 100 | inference time (ms): 561.1 -> 117.8 | Helped |
Surprising findings
- On IMCPT 50 the method performs only comparably to the best baselines rather than clearly better.
- The method's effectiveness diminishes on datasets with unreliable or ambiguous annotations such as Pascal VOC Keypoint.
Limitations
- Performance degrades with unreliable or ambiguous annotations.
- Performance degrades at higher noise levels on PPI, with the gap to StableGM narrowing.
- Requires a large unbalancedness parameter (rho=10^11) for PPI bijective matching, showing sensitivity to rho.
Experimental setup
Datasets: Pascal VOC Keypoint SPair-71k IMC PT SparseGM PPI network
Benchmarks: SPair-71k IMCPT 50 IMCPT 100 PPI network matching
Metrics: matching F1-score node correctness inference time
Baselines: NGM-v2 GCAN AFAT-U AFAT-I SIGMA StableGM
Builds on: optimal partial transport GCAN Sinkhorn normalization Hungarian algorithm
Closest papers by meaning
- Deep Learning of Partial Graph Matching via Differentiable Top-K (CVPR 2023 · similarity 0.91)
- From One to All: Learning to Match Heterogeneous and Partially Overlapped Graphs (AAAI 2022 · similarity 0.91)
- Deep Learning of Graph Matching (CVPR 2018 · similarity 0.90)
- Learning Combinatorial Solver for Graph Matching (CVPR 2020 · similarity 0.90)
- M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering (ICLR 2024 · similarity 0.87)
- Discrete Cycle-Consistency Based Unsupervised Deep Graph Matching (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.