Research map / Graph learning / Graph algorithms and clustering
Discrete Cycle-Consistency Based Unsupervised Deep Graph Matching
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 CLUM, an unsupervised deep graph matching framework that trains keypoint matchers using a discrete cycle-consistency loss differentiated via black-box combinatorial solver differentiation.
Problem
Deep graph matching for keypoint correspondence normally requires ground-truth correspondences; the field of unsupervised deep graph matching is under-studied, and the discrete cycle-consistency signal is not differentiable.
Approach
Uses the discrete cycle-consistency loss over triples of images as a self-supervision signal, and makes it trainable by applying black-box differentiation of combinatorial solvers (Vlastelica et al.) with perturbed costs; compatible with arbitrary networks and LAP/QAP solvers.
Key results
- CLUM reaches 62.4% on Pascal VOC filtered, 43.5 F1 on unfiltered, 95.6% on Willow and 43.1% on SPair-71K, outperforming other unsupervised methods (GANN, SCGM).
- Even the baseline CL-BBGM outperforms all existing unsupervised methods (GANN and both SCGM variants) on all datasets except Willow.
- CLUM-L (LAP variant) performs significantly worse than CLUM but still beats all prior unsupervised methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a QAP solver instead of a LAP solver (ablation) | CLUM · PascalVOC Filtered | accuracy (%): 59.7 -> 62.4 | Helped |
| use a QAP solver instead of a LAP solver (ablation) | CLUM · PascalVOC Unfiltered | F1-score: 40.3 -> 43.5 | Helped |
| use a QAP solver instead of a LAP solver (ablation) | CLUM · Willow Object Class | accuracy (%): 93.4 -> 95.6 | Helped |
| use a QAP solver instead of a LAP solver (ablation) | CLUM · SPair-71K | accuracy (%): 41.6 -> 43.1 | Helped |
| pre-train CL-BBGM with SCGM | CL-BBGM · PascalVOC Filtered | accuracy (%): 58.4 -> 58.8 | Helped |
| pre-train CL-BBGM with SCGM | CL-BBGM · PascalVOC Unfiltered | F1-score: 38 -> 41.7 | Helped |
| pre-train CL-BBGM with SCGM | CL-BBGM · Willow Object Class | accuracy (%): 91.6 -> 93.2 | No clear effect |
| pre-train CL-BBGM with SCGM | CL-BBGM · SPair-71K | accuracy (%): 40.6 -> 41.2 | Helped |
| use CLUM instead of CL-BBGM (SCGM) | unsupervised graph matching · PascalVOC Filtered | accuracy (%): 58.8 -> 62.4 | Helped |
| use CLUM instead of CL-BBGM (SCGM) | unsupervised graph matching · PascalVOC Unfiltered | F1-score: 41.7 -> 43.5 | Helped |
| use CLUM instead of CL-BBGM (SCGM) | unsupervised graph matching · Willow Object Class | accuracy (%): 93.2 -> 95.6 | Helped |
| use CLUM instead of CL-BBGM (SCGM) | unsupervised graph matching · SPair-71K | accuracy (%): 41.2 -> 43.1 | Helped |
Surprising findings
- The unsupervised CL-BBGM beats the unsupervised baselines on most datasets but on Willow it is slightly worse than GANN.
Limitations
- Black-box differentiation adds computational cost since the solver runs twice per training iteration.
- LAP variant CLUM-L performs significantly worse than the QAP variant CLUM.
- SCGM is not suitable for direct training on incomplete matching, limiting comparisons on Pascal VOC unfiltered.
Experimental setup
Datasets: Pascal VOC with Berkeley annotations Willow Object Class SPair-71K
Benchmarks: Pascal VOC (filtered) Pascal VOC (unfiltered) Willow Object Class SPair-71K
Metrics: accuracy F1-score
Baselines: GANN SCGM BBGM NGMv2 CL-BBGM
Builds on: black-box differentiation of combinatorial solvers BBGM SplineCNN GANN SCGM
Closest papers by meaning
- Universe Points Representation Learning for Partial Multi-Graph Matching (AAAI 2023 · similarity 0.88)
- Deep Learning of Graph Matching (CVPR 2018 · similarity 0.88)
- D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching (ICML 2023 · similarity 0.88)
- Learning deep graph matching with channel-independent embedding and Hungarian attention (ICLR 2020 · similarity 0.87)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.86)
- Multi-Shape Matching with Cycle Consistency Basis via Functional Maps (AAAI 2025 · similarity 0.85)
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.