# Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 47 references that are in the map.
- First posted on arXiv 28 Mar 2022.

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

- [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)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [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)
- [Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2007.00533/) (2020)
- [From tree matching to sparse graph alignment](https://mlsanity.com/paper/2002.01258/) (2020)
- [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)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [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)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Correlated randomly growing graphs](https://mlsanity.com/paper/2004.13537/) (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, 13 of 13)

- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [Statistical limits of correlation detection in trees](https://mlsanity.com/paper/2209.13723/) (2022)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (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)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [The feasibility of multi-graph alignment: a Bayesian approach](https://mlsanity.com/paper/2502.17142/) (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)

The problem of detecting edge correlation between two ErdHos-R'enyi random graphs on n unlabeled nodes can be formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are sampled independently; under the alternative, the two graphs are independently sub-sampled from a parent graph which is ErdHos-R'enyi G(n, p) (so that their marginal distributions are the same as the null). We establish a sharp information-theoretic threshold when p = n-α+o(1) for α∈ (0, 1] which sharpens a constant factor in a recent work by Wu, Xu and Yu. A key novelty in our work is an interesting connection between the detection problem and the densest subgraph of an ErdHos-R'enyi graph.