# Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 47 of its 91 references that are in the map.
- First posted on arXiv 3 Jun 2025.

## Builds on (most cited first, 30 of 47)

- [Nomic Embed: Training a Reproducible Long Context Text Embedder](https://mlsanity.com/paper/2402.01613/) (2024)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [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)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [(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)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [On a 'Two Truths' Phenomenon in Spectral Graph Clustering](https://mlsanity.com/paper/1808.07801/) (2018)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [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)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Two-sample Hypothesis Testing for Inhomogeneous Random Graphs](https://mlsanity.com/paper/1707.00833/) (2017)
- [Network classification with applications to brain connectomics](https://mlsanity.com/paper/1701.08140/) (2017)
- [Joint Embedding of Graphs](https://mlsanity.com/paper/1703.03862/) (2017)
- [Spectral clustering in the dynamic stochastic block model](https://mlsanity.com/paper/1705.01204/) (2017)
- [Bootstrapping Networks with Latent Space Structure](https://mlsanity.com/paper/1907.10821/) (2019)
- [Cross: Efficient Low-rank Tensor Completion](https://mlsanity.com/paper/1611.01129/) (2016)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Out-of-sample extension of graph adjacency spectral embedding](https://mlsanity.com/paper/1802.06307/) (2018)
- [Practical methods for graph two-sample testing](https://mlsanity.com/paper/1811.12752/) (2018)
- [On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models](https://mlsanity.com/paper/2003.14250/) (2020)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Bilingual Lexicon Induction for Low-Resource Languages using Graph Matching via Optimal Transport](https://mlsanity.com/paper/2210.14378/) (2022)
- [Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator](https://mlsanity.com/paper/2302.05407/) (2023)

## Abstract (arXiv)

We present the OmniMatch algorithm for seeded multiple graph matching. In the setting of d-dimensional Random Dot Product Graphs (RDPG), we prove that under mild assumptions, OmniMatch with s seeds asymptotically and efficiently perfectly aligns O(sα) unseeded vertices -- for α<2wedge d/4 -- across multiple networks even in the presence of no edge correlation. We demonstrate the effectiveness of our algorithm across numerous simulations and in the context of shuffled graph hypothesis testing. In the shuffled testing setting, testing power is lost due to the misalignment/shuffling of vertices across graphs, and we demonstrate the capacity of OmniMatch to correct for misaligned vertices prior to testing and hence recover the lost testing power. We further demonstrate the algorithm on a pair of data examples from connectomics and machine translation.