  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.

Machine Learning