Graph Alignment via Birkhoff Relaxation

We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard in the worst case even to approximately solve. In this paper, we analyze Birkhoff relaxation, a tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices are correlated Gaussian Orthogonal Ensemble with correlation 1/√1+σ2. Denote the optimal solutions of the QAP and Birkhoff relaxation by Pi^star and X^star respectively. We show that |X^star-Pi^star|F2 = o(n) when σ = o(n-1.25) and |X^star-Pi^star|F2 = Omega(n) when σ = Omega(n-0.5). Thus, the optimal solution X^star transitions from a small perturbation of Pi^star for small σ to being well separated from Pi^star as σ becomes larger than n-0.5. This result allows us to guarantee that simple rounding procedures on X^star align 1-o(1) fraction of vertices correctly whenever σ = o(n-1.25). This condition on σ to ensure the success of the Birkhoff relaxation is state-of-the-art.