# Seeded Graph Matching via Large Neighborhood Statistics

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2018.

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

- [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)
- [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)
- [Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphs](https://mlsanity.com/paper/2203.14573/) (2022)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [The Power of D-hops in Matching Power-Law Graphs](https://mlsanity.com/paper/2102.12975/) (2021)
- [Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator](https://mlsanity.com/paper/2302.05407/) (2023)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching](https://mlsanity.com/paper/2205.13679/) (2022)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Gaussian Database Alignment and Gaussian Planted Matching](https://mlsanity.com/paper/2307.02459/) (2023)
- [Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation](https://mlsanity.com/paper/2305.19666/) (2023)
- [Gotta match 'em all: Solution diversification in graph matching matched filters](https://mlsanity.com/paper/2308.13451/) (2023)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Statistical Limits for Testing Correlation of Hypergraphs](https://mlsanity.com/paper/2202.05888/) (2022)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm](https://mlsanity.com/paper/2412.16457/) (2024)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)
- [Covariate-assisted graph matching](https://mlsanity.com/paper/2512.11761/) (2025)
- [Matching and mixing: Matchability of graphs under Markovian error](https://mlsanity.com/paper/2601.20020/) (2026)

## Abstract (arXiv)

We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated ErdHos-R'enyi random graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. For seeded problems, our result provides a significant improvement over previously known results. We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices n. Moreover, we show the number of seeds needed for exact recovery in polynomial-time can be as low as n3ε in the sparse graph regime (with the average degree smaller than nε) and Omega(log n) in the dense graph regime. Our results also shed light on the unseeded problem. In particular, we give sub-exponential time algorithms for sparse models and an nO(log n) algorithm for dense models for some parameters, including some that are not covered by recent results of Barak et al.