# The graph alignment problem: fundamental limits and efficient algorithms

arXiv: https://arxiv.org/abs/2404.12418 · HTML: https://mlsanity.com/paper/2404.12418/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 121 references that are in the map.
- First posted on arXiv 18 Apr 2024.

## Builds on (most cited first, 26 of 26)

- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universality](https://mlsanity.com/paper/1907.08883/) (2019)
- [Testing correlation of unlabeled random graphs](https://mlsanity.com/paper/2008.10097/) (2020)
- [Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignment](https://mlsanity.com/paper/1809.03553/) (2018)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Database Alignment with Gaussian Features](https://mlsanity.com/paper/1903.01422/) (2019)
- [Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm](https://mlsanity.com/paper/1403.7721/) (2014)
- [Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model](https://mlsanity.com/paper/1907.08880/) (2019)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Graph Matching with Partially-Correct Seeds](https://mlsanity.com/paper/2004.03816/) (2020)
- [The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property](https://mlsanity.com/paper/1904.07174/) (2019)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [On the Structure and Efficient Computation of IsoRank Node Similarities](https://mlsanity.com/paper/1602.00668/) (2016)
- [Linear Regression with an Unknown Permutation: Statistical and Computational Limits](https://mlsanity.com/paper/1608.02902/) (2016)
- [DS++: A flexible, scalable and provably tight relaxation for matching problems](https://mlsanity.com/paper/1705.06148/) (2017)
- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1607.01760/) (2016)

## Built on by (most cited first, 2 of 2)

- [Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings](https://mlsanity.com/paper/2505.13087/) (2025)
- [Sharp Statistical Thresholds for Attributed Gaussian Graph Matching](https://mlsanity.com/paper/2603.23305/) (2026)

## Abstract (arXiv)

This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail.