M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning
  of Mixture Graph Matching and Clustering
Jiaxin Lu Zetian Jiang Tianzhe Wang Junchi Yan
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.