# Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator

arXiv: https://arxiv.org/abs/2302.05407 · HTML: https://mlsanity.com/paper/2302.05407/

## Key facts

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

## Builds on (most cited first, 23 of 23)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs](https://mlsanity.com/paper/1805.02349/) (2018)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2007.00533/) (2020)
- [From tree matching to sparse graph alignment](https://mlsanity.com/paper/2002.01258/) (2020)
- [Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignment](https://mlsanity.com/paper/1809.03553/) (2018)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [An efficient reconciliation algorithm for social networks](https://mlsanity.com/paper/1307.1690/) (2013)
- [Correlated randomly growing graphs](https://mlsanity.com/paper/2004.13537/) (2020)
- [Optimal De-Anonymization in Random Graphs with Community Structure](https://mlsanity.com/paper/1602.01409/) (2016)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [The Power of D-hops in Matching Power-Law Graphs](https://mlsanity.com/paper/2102.12975/) (2021)
- [Phase transition in noisy high-dimensional random geometric graphs](https://mlsanity.com/paper/2103.15249/) (2021)

## Built on by (most cited first, 6 of 6)

- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Harnessing Multiple Correlated Networks for Exact Community Recovery](https://mlsanity.com/paper/2412.02796/) (2024)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)

## 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.