# Convex Joint Graph Matching and Clustering via Semidefinite Relaxations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 69 references that are in the map.
- First posted on arXiv 21 Oct 2021.

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

- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [Alternating Direction Graph Matching](https://mlsanity.com/paper/1611.07583/) (2016)
- [Multicuts and Perturb & MAP for Probabilistic Graph Clustering](https://mlsanity.com/paper/1601.02088/) (2016)
- [Spectral Clustering for Divide-and-Conquer Graph Matching](https://mlsanity.com/paper/1310.1297/) (2013)
- [ADMM for the SDP relaxation of the QAP](https://mlsanity.com/paper/1512.05448/) (2015)
- [Convex Optimisation for Inverse Kinematics](https://mlsanity.com/paper/1910.11016/) (2019)
- [Joint Cuts and Matching of Partitions in One Graph](https://mlsanity.com/paper/1711.09584/) (2017)

## Built on by (most cited first, 1 of 1)

- [M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering](https://mlsanity.com/paper/2310.18444/) (2023)

## Abstract (arXiv)

This paper proposes a new algorithm for simultaneous graph matching and clustering. For the first time in the literature, these two problems are solved jointly and synergetically without relying on any training data, which brings advantages for identifying similar arbitrary objects in compound 3D scenes and matching them. For joint reasoning, we first rephrase graph matching as a rigid point set registration problem operating on spectral graph embeddings. Consequently, we utilise efficient convex semidefinite program relaxations for aligning points in Hilbert spaces and add coupling constraints to model the mutual dependency and exploit synergies between both tasks. We outperform state of the art in challenging cases with non-perfectly matching and noisy graphs, and we show successful applications on real compound scenes with multiple 3D elements. Our source code and data are publicly available.