# Exact Matching of Random Graphs with Constant Correlation

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 44 references that are in the map.
- First posted on arXiv 11 Oct 2021.

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

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs](https://mlsanity.com/paper/1805.02349/) (2018)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universality](https://mlsanity.com/paper/1907.08883/) (2019)
- [From tree matching to sparse graph alignment](https://mlsanity.com/paper/2002.01258/) (2020)
- [Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignment](https://mlsanity.com/paper/1809.03553/) (2018)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Graph Isomorphism in Quasipolynomial Time](https://mlsanity.com/paper/1512.03547/) (2015)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Graph Matching with Partially-Correct Seeds](https://mlsanity.com/paper/2004.03816/) (2020)
- [Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphs](https://mlsanity.com/paper/1907.06334/) (2019)

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

- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [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)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphs](https://mlsanity.com/paper/2203.14573/) (2022)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator](https://mlsanity.com/paper/2302.05407/) (2023)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)
- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [Graph Matching via convex relaxation to the simplex](https://mlsanity.com/paper/2310.20609/) (2023)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Graph Alignment via Birkhoff Relaxation](https://mlsanity.com/paper/2503.05323/) (2025)
- [Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation](https://mlsanity.com/paper/2305.19666/) (2023)
- [Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein](https://mlsanity.com/paper/2311.13595/) (2023)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Testing Dependency of Weighted Random Graphs](https://mlsanity.com/paper/2409.14870/) (2024)
- [Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm](https://mlsanity.com/paper/2412.16457/) (2024)

## Abstract (arXiv)

This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. Let G and G' be G(n, p) ErdHos--R'enyi graphs marginally, identified with their adjacency matrices. Assume that G and G' are correlated such that mathbbE[Gij G'ij] = p(1-α). For a permutation π representing a latent matching between the vertices of G and G', denote by Gπ the graph obtained from permuting the vertices of G by π. Observing Gπ and G', we aim to recover the matching π. In this work, we show that for every varepsilon ∈ (0,1], there is n0>0 depending on varepsilon and absolute constants α0, R > 0 with the following property. Let n ≥ n0, (1+varepsilon) log n ≤ np ≤ n^frac1R log log n, and 0 < α < min(α0,varepsilon/4). There is a polynomial-time algorithm F such that mathbbPF(Gπ,G')=π=1-o(1). This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated ErdHos--R'enyi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.