Research map / Graph learning / Graph algorithms and clustering
M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering
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 M3C, a learning-free mixture graph matching and clustering solver with a convergence guarantee via a minorize-maximization framework and relaxed cluster indicator, and UM3C, an unsupervised extension with edge-wise affinity learning and relaxed-indicator pseudo-label selection.
Problem
Graph matching assumes graphs are of one category and matchable; real data mixes graph categories, so matching must be jointly done with clustering (mixture graph matching and clustering, MGMC) without labels.
Approach
Reformulates joint matching and clustering as an MM framework with a relaxed cluster indicator (global or local rank-based selection of graph pairs) that keeps discrete constraints and guarantees monotone convergence; UM3C trains edge-wise affinities with a cross-entropy affinity loss on pseudo-labels selected by the relaxed indicator.
Key results
- On Willow ObjectClass 3x8 with no outliers, M3C reaches 0.884 matching accuracy versus 0.879 for MGM-Floyd and 0.872 for DPMC, with 0.5 s runtime.
- UM3C reaches 0.955 matching accuracy on Willow 3x8 without outliers, above GANN (0.896) and the supervised BBGM (0.939) and NGMv2 (0.885).
- With 4 outliers, UM3C keeps 0.815 matching accuracy versus 0.461 for GANN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace M3C-hard's hard clustering with the relaxed indicator in M3C (ablation) | M3C · Willow ObjectClass, 3 clusters × 8 images, 0 outlier | MA: 0.838 -> 0.884 | Helped |
| replace M3C-hard's hard clustering with the relaxed indicator in M3C (ablation) | M3C · Willow ObjectClass, 3 clusters × 8 images, 2 outliers | CA: 0.576 -> 0.653 | Helped |
| replace M3C-hard's hard clustering with the relaxed indicator in M3C (ablation) | M3C · Willow ObjectClass, 3 clusters × 8 images, 4 outliers | CA: 0.587 -> 0.646 | Helped |
| use UM3C instead of GANN | unsupervised mixture graph matching and clustering · Willow ObjectClass, 3 clusters × 8 images, 0 outlier | MA: 0.896 -> 0.955 | Helped |
| use UM3C instead of GANN | unsupervised mixture graph matching and clustering · Willow ObjectClass, 3 clusters × 8 images, 2 outliers | MA: 0.610 -> 0.858 | Helped |
| use UM3C instead of GANN | unsupervised mixture graph matching and clustering · Willow ObjectClass, 3 clusters × 8 images, 4 outliers | MA: 0.461 -> 0.815 | Helped |
| use UM3C instead of GANN | unsupervised mixture graph matching and clustering · Pascal VOC, 3 clusters × 8 images | MA: 0.2774 -> 0.4979 | Helped |
| use UM3C instead of GANN | unsupervised mixture graph matching and clustering · Pascal VOC, 5 clusters × 10 images | MA: 0.2372 -> 0.4817 | Helped |
| add relaxed-indicator pseudo-label selection (ablation) | UM3C · Willow ObjectClass, early training (first 100 iterations) | pseudo-label MA: 5% improvement | Helped |
| add edge-wise affinity learning (ablation) | UM3C · Willow ObjectClass, 3 clusters × 8 images, 0 outlier | matching accuracy | Helped |
| add Spline CNN for feature refinement (ablation) | UM3C · Willow ObjectClass, 3 clusters × 8 images, 0 outlier | matching accuracy | Helped |
Surprising findings
- UM3C, trained without labels, outperforms supervised BBGM and NGMv2 on Willow ObjectClass matching accuracy.
Limitations
- Hard clustering converges to sub-optimal solutions, motivating the relaxation; relaxation parameter r and fusion hyperparameter alpha require tuning.
- Unsupervised learning still relies on hand-crafted affinities for early pseudo labels.
Experimental setup
Datasets: Willow ObjectClass Pascal VOC
Benchmarks: Willow ObjectClass Pascal VOC
Metrics: matching accuracy clustering accuracy clustering purity rand index time cost
Baselines: RRWM MatchLift MatchALS CAO-C MGM-Floyd DPMC M3C-hard NGMv2 BBGM GANN
Builds on: DPMC GANN RRWM MGM-Floyd BBGM
Closest papers by meaning
- Multiple Graph Matching and Clustering via Decayed Pairwise Matching Composition (AAAI 2020 · similarity 0.90)
- Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning (NeurIPS 2020 · similarity 0.90)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.87)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.86)
- THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (AAAI 2025 · similarity 0.86)
- Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective (NeurIPS 2024 · 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.