mlsanityData to 14 Oct 2026

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

arXiv 2506.02825 ↗First posted 3 Jun 2025stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

47 of 91 references.

References · 47

  1. 2024Nomic Embed: Training a Reproducible Long Context Text Embeddercited by 265
  2. 2017Statistical inference on random dot product graphs: a surveycited by 70
  3. 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
  4. 2017Tensor SVD: Statistical and Computational Limitscited by 53
  5. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  6. 2019Inference for multiple heterogeneous networks with a common invariant subspacecited by 39
  7. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  8. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  9. 2020Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decompositioncited by 30
  10. 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
  11. 2018Seeded Graph Matching via Large Neighborhood Statisticscited by 27
  12. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
35 more
  1. 2018On a 'Two Truths' Phenomenon in Spectral Graph Clusteringcited by 24
  2. 2013Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embeddingcited by 23
  3. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  4. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  5. 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
  6. 2017Two-sample Hypothesis Testing for Inhomogeneous Random Graphscited by 13
  7. 2017Network classification with applications to brain connectomicscited by 12
  8. 2017Joint Embedding of Graphscited by 12
  9. 2017Spectral clustering in the dynamic stochastic block modelcited by 12
  10. 2019Bootstrapping Networks with Latent Space Structurecited by 12
  11. 2016Cross: Efficient Low-rank Tensor Completioncited by 10
  12. 2016Information Recovery in Shuffled Graphs via Graph Matchingcited by 8
  13. 2018Out-of-sample extension of graph adjacency spectral embeddingcited by 8
  14. 2018Practical methods for graph two-sample testingcited by 7
  15. 2020On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Modelscited by 6
  16. 2021Estimating Graph Dimension with Cross-validated Eigenvaluescited by 6
  17. 2022Bilingual Lexicon Induction for Low-Resource Languages using Graph Matching via Optimal Transportcited by 6
  18. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  19. 2014Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurabilitycited by 5
  20. 2018Fast Randomized PCA for Sparse Datacited by 5
  21. 2019Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddingscited by 5
  22. 2020The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networkscited by 5
  23. 2021Network Recovery from Unlabeled Noisy Samplescited by 5
  24. 2021Hypothesis Testing for Equality of Latent Positions in Random Graphscited by 5
  25. 2013MIGRAINE: MRI Graph Reliability Analysis and Inference for Connectomicscited by 4
  26. 2021The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph matchcited by 4
  27. 2022Sparse Subspace Clustering in Diverse Multiplex Network Modelcited by 4
  28. 2020Correcting a Nonparametric Two-sample Graph Hypothesis Test for Graphs with Different Numbers of Vertices with Applications to Connectomicscited by 3
  29. 2022Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labelscited by 3
  30. 2024Statistical Inference for Low-Rank Tensors: Heteroskedasticity, Subgaussianity, and Applicationscited by 3
  31. 2018Unseeded low-rank graph matching by transform-based unsupervised point registrationcited by 2
  32. 2018Consistent polynomial-time unseeded graph matching for Lipschitz graphonscited by 2
  33. 2021A Practical Two-Sample Test for Weighted Random Graphscited by 2
  34. 2024Network two-sample test for block modelscited by 2
  35. 2015Network driven sampling; a critical threshold for design effectscited by 1

Built on by

Not cited yet.