# M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 63 references that are in the map.
- First posted on arXiv 27 Oct 2023.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels](https://mlsanity.com/paper/1711.08920/) (2017)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [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)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [Near-Optimal Joint Object Matching via Convex Relaxation](https://mlsanity.com/paper/1402.1473/) (2014)
- [A General Multi-Graph Matching Approach via Graduated Consistency-regularized Boosting](https://mlsanity.com/paper/1502.05840/) (2015)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [Distributed Consistent Data Association](https://mlsanity.com/paper/1609.07015/) (2016)
- [Multicuts and Perturb & MAP for Probabilistic Graph Clustering](https://mlsanity.com/paper/1601.02088/) (2016)
- [Distributable Consistent Multi-Object Matching](https://mlsanity.com/paper/1611.07191/) (2016)
- [Convex Joint Graph Matching and Clustering via Semidefinite Relaxations](https://mlsanity.com/paper/2110.11335/) (2021)

## Abstract (arXiv)

Existing graph matching methods typically assume that there are similar structures between graphs and they are matchable. However, these assumptions do not align with real-world applications. This work addresses a more realistic scenario where graphs exhibit diverse modes, requiring graph grouping before or along with matching, a task termed mixture graph matching and clustering. We introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence through the Minorize-Maximization framework and offers enhanced flexibility via relaxed clustering. Building on M3C, we develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Extensive experimental results on public benchmarks demonstrate that our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency. Source code will be made publicly available.