mlsanityData to 7 Oct 2026

Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignment

arXiv 1809.03553 ↗First posted 10 Sep 2018cs.IT cs.LG math.ITcited by 25

Not on the map. Why?

Abstract (arXiv)

We determine information theoretic conditions under which it is possible to partially recover the alignment used to generate a pair of sparse, correlated ErdHos-R'enyi graphs. To prove our achievability result, we introduce the k-core alignment estimator. This estimator searches for an alignment in which the intersection of the correlated graphs using this alignment has a minimum degree of k. We prove a matching converse bound. As the number of vertices grows, recovery of the alignment for a fraction of the vertices tending to one is possible when the average degree of the intersection of the graph pair tends to infinity. It was previously known that exact alignment is possible when this average degree grows faster than the logarithm of the number of vertices.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Sep 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

25 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. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
  4. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  5. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  6. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  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. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
  12. 2022A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcited by 8
13 more
  1. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 8
  2. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  3. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  4. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 4
  5. 2025The feasibility of multi-graph alignment: a Bayesian approachcited by 3
  6. 2021Alignment and Comparison of Directed Networks via Transition Couplings of Random Walkscited by 2
  7. 2024The graph alignment problem: fundamental limits and efficient algorithmscited by 2
  8. 2025Exact Matching in Correlated Networks with Node Attributes for Improved Community Recoverycited by 1
  9. 2025Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodingscited by 1
  10. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0
  11. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  12. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  13. 2026Contextual Graph Matching with Correlated Gaussian Featurescited by 0