mlsanityData to 7 Oct 2026

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

arXiv 2203.14573 ↗First posted 28 Mar 2022math.PR math.ST stat.MLcited by 13

Not on the map. Why?

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.

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

Builds on

20 of 47 references.

References · 20

  1. 2018Efficient random graph matching via degree profilescited by 48
  2. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  3. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 35
  4. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  5. 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
  6. 2018Seeded Graph Matching via Large Neighborhood Statisticscited by 27
  7. 2019Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universalitycited by 27
  8. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  9. 2020From tree matching to sparse graph alignmentcited by 26
  10. 2020Testing correlation of unlabeled random graphscited by 26
  11. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  12. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
8 more
  1. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  2. 2021Testing network correlation efficiently via counting treescited by 22
  3. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  4. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  5. 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
  6. 2016Spectral Alignment of Graphscited by 12
  7. 2020Correlated randomly growing graphscited by 12
  8. 2019Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphscited by 9

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 3; 2024: 5; 2025: 2.

13 papers.

Sort:

  1. 2022Matching recovery threshold for correlated random graphscited by 16
  2. 2022Statistical limits of correlation detection in treescited by 12
  3. 2022A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcited by 8
  4. 2023A Survey on the Densest Subgraph Problem and Its Variantscited by 8
  5. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 8
  6. 2024A computational transition for detecting correlated stochastic block models by low-degree polynomialscited by 6
  7. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  8. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 4
  9. 2025The feasibility of multi-graph alignment: a Bayesian approachcited by 3
  10. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 2
  11. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  12. 2024Testing Dependency of Weighted Random Graphscited by 0
1 more
  1. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0