# Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 48 references that are in the map.
- First posted on arXiv 10 Jul 2026.

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

- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery](https://mlsanity.com/paper/2405.12293/) (2024)
- [Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing](https://mlsanity.com/paper/2504.02299/) (2025)
- [Attributed Network Alignment: Statistical Limits and Efficient Algorithm](https://mlsanity.com/paper/2604.04365/) (2026)

## Abstract (arXiv)

This paper studies graph matching under the correlated textErdHos-R'enyi (ER) graph pair model. This model first samples an ER(n,fracλns) base graph, whose edges are then independently subsampled twice with probability s to produce two correlated ER(n,fracλn) graphs. We propose a graph matching algorithm that has n2+o(1) time complexity and achieves almost exact recovery with high probability under the assumptions λ=(log n)α+o(1) for some α∈(0,1) and s∈(√COtter,1], where COtter≈ 0.338 is Otter's tree-counting constant. This is the first algorithm with almost quadratic time complexity in this regime of λ, while the best known result in this regime is the chandelier-counting algorithm with time complexity O(nc(s)), where c(s)rightarrow ∞ as s approaches √COtter from above. The proposed algorithm is based on local tree correlation tests. It uses a rank-based algorithm to match the vertex pairs instead of threshold-based rules in the literature. This avoids the need of computing an explicit threshold, which is computationally difficult to obtain. To prove the almost exact recovery result, we establish a new analysis of tree correlation tests in the diverging-degree regime, where both the mean degree and the tree depth grow with n. Based on this new result, we establish the existence of a threshold for a threshold-based graph matching algorithm via local tree correlation tests. Finally, we couple the performance of the rank-based algorithm with the threshold-based algorithm to show almost exact recovery.