Convex Joint Graph Matching and Clustering via Semidefinite Relaxations

Graph matching and graph clustering are problems typically treated separately. A recent paper published on arXiv.org looks into joint graph matching and clustering.

The researchers show that graph matching can improve the accuracy of clustering in challenging scenarios, and vice versa, when both problems are considered jointly.

The non-learning-based method does not depend on the availability of labeled training data. In order to guarantee optimal solutions, the mutual dependency between the estimates is introduced. The solutions to both problems serve as additional mutual cues, either for clustering or for matching.

Experiments confirm that the proposed method achieves higher accuracy and more consistent results when compared to the current state of the art. The suggested approach enables to resolve cases that can be ambiguous for disjoint techniques.

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.

Research paper: Krahn, M., Bernard, F., and Golyanik, V., “Convex Joint Graph Matching and Clustering via Semidefinite Relaxations”, 2021. Link: https://arxiv.org/abs/2110.11335

You can offer your link to a page which is relevant to the topic of this post.