  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.
