mlsanityData to 14 Oct 2026

Exact alignment recovery for correlated ErdHos-R'enyi graphs

arXiv 1711.06783 ↗First posted 18 Nov 2017cs.IT cs.LG math.ITcited by 38

Not on the map. Why?

Abstract (arXiv)

We consider the problem of perfectly recovering the vertex correspondence between two correlated ErdHos-R'enyi (ER) graphs on the same vertex set. The correspondence between the vertices can be obscured by randomly permuting the vertex labels of one of the graphs. We determine the information-theoretic threshold for exact recovery, i.e. the conditions under which the entire vertex correspondence can be correctly recovered given unbounded computational resources.

Key facts. Cited by 38 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 9; 2023: 6; 2024: 6; 2025: 6; 2026: 5.

38 papers.

Sort:

  1. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  2. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  3. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  4. 2021Testing network correlation efficiently via counting treescited by 22
  5. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  6. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  7. 2022Matching recovery threshold for correlated random graphscited by 16
  8. 2021Correlation detection in trees for planted graph alignmentcited by 14
  9. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  10. 2022Statistical limits of correlation detection in treescited by 12
  11. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 9
  12. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
26 more
  1. 2022A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcited by 8
  2. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  3. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 6
  4. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  5. 2024Efficient Graph Matching for Correlated Stochastic Block Modelscited by 5
  6. 2022Seeded graph matching for the correlated Gaussian Wigner model via the projected power methodcited by 4
  7. 2023Gaussian Database Alignment and Gaussian Planted Matchingcited by 3
  8. 2023Graph Matching via convex relaxation to the simplexcited by 3
  9. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 3
  10. 2025The feasibility of multi-graph alignment: a Bayesian approachcited by 3
  11. 2021Alignment and Comparison of Directed Networks via Transition Couplings of Random Walkscited by 2
  12. 2022Clustered Graph Matching for Label Recovery and Graph Classificationcited by 2
  13. 2024The graph alignment problem: fundamental limits and efficient algorithmscited by 2
  14. 2025Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodingscited by 2
  15. 2023Gotta match 'em all: Solution diversification in graph matching matched filterscited by 1
  16. 2025Exact Matching in Correlated Networks with Node Attributes for Improved Community Recoverycited by 1
  17. 2026Attributed Network Alignment: Statistical Limits and Efficient Algorithmcited by 1
  18. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  19. 2024Testing Dependency of Weighted Random Graphscited by 0
  20. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  21. 2025Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)cited by 0
  22. 2025Covariate-assisted graph matchingcited by 0
  23. 2026Matching and mixing: Matchability of graphs under Markovian errorcited by 0
  24. 2026Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Boundscited by 0
  25. 2026Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Testscited by 0
  26. 2026Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failurecited by 0