mlsanityData to 7 Oct 2026

Matching recovery threshold for correlated random graphs

arXiv 2205.14650 ↗First posted 29 May 2022math.ST math.PR stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

For two correlated graphs which are independently sub-sampled from a common ErdHos-R'enyi graph G(n, p), we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p = n-α+o(1) for α∈ (0, 1], we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 20 of its 44 references that are in the map. First posted on arXiv 29 May 2022.

Builds on

20 of 44 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. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  8. 2020From tree matching to sparse graph alignmentcited by 26
  9. 2020Testing correlation of unlabeled random graphscited by 26
  10. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  11. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
  12. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
8 more
  1. 2021Testing network correlation efficiently via counting treescited by 22
  2. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  3. 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
  4. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  5. 2020Correlated randomly growing graphscited by 12
  6. 2019Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphscited by 9
  7. 2021The planted matching problem: Sharp threshold and infinite-order phase transitioncited by 9
  8. 2022One-Way Matching of Datasets with Low Rank Signalscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 3; 2024: 6; 2025: 3; 2026: 1.

16 papers.

Sort:

  1. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  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 polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 8
  5. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  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. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0
  12. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
4 more
  1. 2024Testing Dependency of Weighted Random Graphscited by 0
  2. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  3. 2025Chaining 2-FWL GNNs for Combinatorial Graph Alignmentcited by 0
  4. 2026Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failurecited by 0