Graph Matching via convex relaxation to the simplex

Araya, Ernesto; Tyagi, Hemant

Document type :

Article dans une revue scientifique: Article original

DOI :

10.3934/fods.2024034

Title :

Graph Matching via convex relaxation to the simplex

Author(s) :

Araya, Ernesto [Auteur]
Ludwig Maximilian University [Munich] = Ludwig Maximilians Universität München [LMU]
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]

Journal title :

Foundations of Data Science

Pages :

464-501

Publisher :

American Institute of Mathematical Sciences

Publication date :

2023-11-01

HAL domain(s) :

Mathématiques [math]
Statistiques [stat]

English abstract : [en]

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. ...
Show more >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 \emph{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 [Fan et al. 2019] 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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Files

document
Open access
Access the document

2310.20609.pdf
Open access
Access the document

2310.20609
Open access
Access the document

Graph Matching via convex relaxation to ... BibTeX CSV Excel RIS

Files

Graph Matching via convex relaxation to ...

BibTeX

CSV

Excel

RIS