Fonctionne avec Indico
v3.2.9
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 sharp phase transition in the limit of large degrees for the existence of suitable tests.
As a byproduct, this result gives insights on the performance of the message-passing algorithm for our initial problem on graphs.
Based on joint works with Laurent Massoulié, Marc Lelarge and Guilhem Semerjian.