# The Algorithmic Phase Transition of Random Graph Alignment Problem

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2023.

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

- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We study the graph alignment problem over two independent ErdHos-R'enyi graphs on n vertices, with edge density p falling into two regimes separated by the critical window around pc=√log n/n. Our result reveals an algorithmic phase transition for this random optimization problem: polynomial-time approximation schemes exist in the sparse regime, while statistical-computational gap emerges in the dense regime. Additionally, we establish a sharp transition on the performance of online algorithms for this problem when p lies in the dense regime, resulting in a √8/9 multiplicative constant factor gap between achievable and optimal solutions.