Graph Matching via convex relaxation to the simplex
- 1 January 2025
- journal article
- research article
- Published by American Institute of Mathematical Sciences (AIMS) in Foundations of Data Science
- Vol. 7 (2) , 464-501
Abstract
This paper addresses the Graph Matching problem, which consists of finding the best possible alignment between two input graphs, and has many applications in computer vision, network deanonymization and protein alignment. A common approach to tackle this problem is through convex relaxations of the NP-hard Quadratic Assignment Problem (QAP). Here, we introduce a new convex relaxation onto the unit simplex and develop an efficient mirror descent scheme with closed-form iterations for solving this problem. Under the correlated Gaussian Wigner model, we show that the simplex relaxation admits a unique solution with high probability. In the noiseless case, this is shown to imply exact recovery of the ground truth permutation. Additionally, we establish a novel sufficiency condition for the input matrix in standard greedy rounding methods, which is less restrictive than the commonly used 'diagonal dominance' condition. We use this condition to show exact one-step recovery of the ground truth (holding almost surely) via the mirror descent scheme, in the noiseless setting. We also use this condition to obtain significantly improved conditions for the GRAMPA algorithm [ 26 ] in the noiseless setting. Our method is evaluated on both synthetic and real data, demonstrating superior statistical performance compared to existing convex relaxation methods with similar computational costs.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Spectral Graph Matching and Regularized Quadratic Relaxations IIFoundations of Computational Mathematics, 2022
- Spectral alignment of correlated gaussian matricesAdvances in Applied Probability, 2022
- Efficient random graph matching via degree profilesProbability Theory and Related Fields, 2020
- Random matrices have simple spectrumCombinatorica, 2017
- Fifty years of graph matching, network alignment and network comparisonInformation Sciences, 2016
- Near-optimal no-regret algorithms for zero-sum gamesGames and Economic Behavior, 2015
- On convex relaxation of graph isomorphismProceedings of the National Academy of Sciences, 2015
- Social structure of Facebook networksPhysica A: Statistical Mechanics and its Applications, 2012
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences, 2008
- Improved random graph isomorphismJournal of Discrete Algorithms, 2008