Phase Transition in Convex Relaxations for Graph Alignment

摘要

We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symmetric Gaussian matrices (A,B) with correlation 1/√(1+σ^2). While the maximum likelihood estimator is information-theoretically optimal, its computation, which reduces to a quadratic assignment problem, is intractable. Motivated by this, we analyze convex relaxations based on minimizing AX - XB_F over the set of doubly stochastic matrices and the unit hypercube. We show that when the correlation parameter satisfies σ = o(n^-1/2/log^4 n), the solution of either relaxation (X^⋆) concentrates around the ground-truth permutation matrix (Π^⋆), i.e., X^⋆ - Π^⋆_F^2 = o(n), implying recovery of all but a vanishing fraction of vertices after simple post-processing. Combined with existing lower bounds, our results precisely characterize that X^⋆ - Π^⋆_F^2 transitions from o(n) for σ = õ(n^-1/2) to Ω(n) for σ = Ω̃(n^-1/2). In doing so, our analysis significantly tightens prior results and extends them beyond doubly stochastic relaxations.