Séminaire Probabilités et Statistiques
Aligning graphs via detecting correlation in trees
12
jan. 2023
jan. 2023
| Intervenant : | Luca Ganassali |
| Institution : | EPFL |
| Heure : | 14h00 - 17h00 |
| Lieu : | Amphithéatre Yoccoz |
Graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This problem can be viewed as an average-case and noisy version of the well-known graph isomorphism problem.
For correlated Erdős-Rényi random graphs, we will first give insights on the fundamental limits for the planted formulation of this problem, establishing statistical thresholds for partial recovery.
Then, motivated by designing an efficient (polynomial-time) algorithm to recover the underlying alignment in a sparse regime, a message-passing algorithm based on testing correlation in trees is proposed.
We study this related correlation detection problem in trees and identify a phase transition in the limit of large degrees for the existence of suitable tests, hence giving insights on the performance of the above method for our initial problem on graphs.
Based on joint works with Laurent Massoulié, Marc Lelarge and Guilhem Semerjian.