Séminaire Probabilités et Statistiques
Aligning graphs via detecting correlation in trees
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.


All (past and future) events