mlsanityData to 7 Oct 2026

Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator

arXiv 2302.05407 ↗First posted 10 Feb 2023math.ST cs.IT cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

We consider the task of estimating the latent vertex correspondence between two edge-correlated random graphs with generic, inhomogeneous structure. We study the so-called k-core estimator, which outputs a vertex correspondence that induces a large, common subgraph of both graphs which has minimum degree at least k. We derive sufficient conditions under which the k-core estimator exactly or partially recovers the latent vertex correspondence. Finally, we specialize our general framework to derive new results on exact and partial recovery in correlated stochastic block models, correlated Chung-Lu graphs, and correlated random geometric graphs.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 23 of its 37 references that are in the map. First posted on arXiv 10 Feb 2023.

Builds on

23 of 37 references.

References · 23

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2018Efficient random graph matching via degree profilescited by 48
  3. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  4. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 35
  5. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  6. 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
  7. 2018Seeded Graph Matching via Large Neighborhood Statisticscited by 27
  8. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  9. 2020From tree matching to sparse graph alignmentcited by 26
  10. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  11. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  12. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
11 more
  1. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  2. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  3. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  4. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  5. 2022Matching recovery threshold for correlated random graphscited by 16
  6. 2013An efficient reconciliation algorithm for social networkscited by 12
  7. 2020Correlated randomly growing graphscited by 12
  8. 2016Optimal De-Anonymization in Random Graphs with Community Structurecited by 11
  9. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
  10. 2021The Power of D-hops in Matching Power-Law Graphscited by 7
  11. 2021Phase transition in noisy high-dimensional random geometric graphscited by 6

Built on by

Cited by year

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

6 papers.

  1. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  2. 2024Harnessing Multiple Correlated Networks for Exact Community Recoverycited by 3
  3. 2025Exact Matching in Correlated Networks with Node Attributes for Improved Community Recoverycited by 1
  4. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0
  5. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  6. 2025Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)cited by 0