Graph Matching via convex relaxation to the simplex

Araya, Ernesto; Tyagi, Hemant

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.3934/fods.2024034

Titre :

Graph Matching via convex relaxation to the simplex

Auteur(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]

Titre de la revue :

Foundations of Data Science

Pagination :

464-501

Éditeur :

American Institute of Mathematical Sciences

Date de publication :

2023-11-01

Discipline(s) HAL :

Mathématiques [math]
Statistiques [stat]

Résumé en anglais : [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. ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

2310.20609.pdf
Accès libre
Accéder au document

2310.20609
Accès libre
Accéder au document

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

Fichiers

Graph Matching via convex relaxation to ...

BibTeX

CSV

Excel

RIS