Research map / Graph learning / Graph algorithms and clustering
Graph Alignment via Birkhoff Relaxation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes the Birkhoff (doubly stochastic) convex relaxation of the graph alignment QAP under the Gaussian Wigner model, proving its solution is close to the true permutation when noise sigma = o(1/n) and far when sigma = Omega(n^{-1/2}).
Problem
Graph alignment (QAP) between correlated Gaussian Wigner graphs: theoretical guarantees for the Birkhoff convex relaxation, which previously lacked analysis beyond sigma=0.
Approach
Constructs an approximately feasible dual certificate for the Birkhoff relaxation (handling nonnegativity constraints via n^2 dual variables) using GOE eigenvectors to bound off-diagonal mass of the optimal doubly stochastic solution; also proves a well-separation lower bound by comparing with the objective at J/n.
Key results
- Theorem: ||X*-Pi*||_F^2 = o(n) when sigma = o(1/n) and Omega(n) when sigma = Omega(n^{-1/2}), establishing a phase transition in the Birkhoff relaxation.
- Simulations at n=400 show Birkhoff relaxation exactly aligns all vertices for sigma up to 0.5, outperforming Simplex and GRAMPA which degrade at sigma=0.4 and 0.2.
- Empirical threshold scaling for ||X*-Pi*||_F/sqrt(n)=0.5 fits a log-log slope of -0.45, consistent with sigma = Theta(n^{-1/2}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase noise σ | Birkhoff relaxation · Gaussian Wigner Model | squared Frobenius distance to QAP optimum: o(n) when σ = o(n^{-1}); Ω(n) when σ = Ω(n^{-0.5}) | Mixed |
| use Birkhoff relaxation with row-wise argmax rounding | Birkhoff relaxation · Gaussian Wigner Model | fraction of vertices correctly matched: 1-o(1) fraction when σ = o(n^{-1}) | Helped |
| use Birkhoff relaxation with Hungarian projection | Birkhoff relaxation · Gaussian Wigner Model, n = 400 | fraction of correctly matched vertices: all vertices for σ up to 0.5 | Helped |
| use Simplex relaxation instead of Birkhoff relaxation | Graph alignment · Gaussian Wigner Model, n = 400 | fraction of correctly matched vertices: starts degrading for σ=0.4 | Hurt |
| use GRAMPA instead of Birkhoff relaxation | Graph alignment · Gaussian Wigner Model, n = 400 | fraction of correctly matched vertices: starts degrading for σ=0.2 | Hurt |
| increase σ | Birkhoff relaxation with Hungarian projection · Gaussian Wigner Model, n = 400 | fraction of correctly matched vertices: σ ∈ [0.3, 0.5] | Mixed |
| increase graph size n | Birkhoff relaxation with post-processing · Gaussian Wigner Model, n ∈ {100, 200, 300, 400 , 500} | fraction of correctly matched vertices | Hurt |
Surprising findings
- Birkhoff relaxation with rounding recovers the true permutation for sigma well above the threshold where X* itself is far from Pi*, since X* retains a slight bias toward Pi*.
- Population-level heuristic suggests the true threshold may be n^{-1/2} rather than n^{-1}, so the proven n^{-1} condition may be loose.
Limitations
- Small-perturbation guarantee only holds for sigma = o(1/n), a gap from the conjectured n^{-1/2} threshold.
- Analysis is restricted to the Gaussian Wigner (GOE) model; extension to general Wigner matrices is only sketched.
- Well-separation result does not imply failure of the relaxation after rounding.
Experimental setup
Datasets: synthetic Gaussian Wigner graphs
Benchmarks: synthetic Gaussian Wigner graphs
Metrics: fraction of correctly matched vertices ||X*-Pi*||_F/sqrt(n)
Baselines: GRAMPA Simplex relaxation EIG1
Builds on: GRAMPA simplex relaxation
Closest papers by meaning
- DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems (CVPR 2018 · similarity 0.87)
- Generalizing Graph Matching beyond Quadratic Assignment Model (NeurIPS 2018 · similarity 0.87)
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.87)
- OT4P: Unlocking Effective Orthogonal Group Path for Permutation Relaxation (NeurIPS 2024 · similarity 0.84)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.84)
- Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.