mlsanityData to 14 Oct 2026

A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation

arXiv 2212.13677 ↗First posted 28 Dec 2022cs.DS math.PR math.STcited by 8

Not on the map. Why?

Abstract (arXiv)

Motivated by the problem of matching vertices in two correlated ErdHos-R'enyi graphs, we study the problem of matching two correlated Gaussian Wigner matrices. We propose an iterative matching algorithm, which succeeds in polynomial time as long as the correlation between the two Gaussian matrices does not vanish. Our result is the first polynomial time algorithm that solves a graph matching type of problem when the correlation is an arbitrarily small constant.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 27 of its 54 references that are in the map. First posted on arXiv 28 Dec 2022.

Builds on

27 of 54 references.

References · 27

  1. 2018Efficient random graph matching via degree profilescited by 48
  2. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  3. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
  4. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  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. 2019Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universalitycited by 27
  9. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  10. 2020From tree matching to sparse graph alignmentcited by 26
  11. 2020Testing correlation of unlabeled random graphscited by 26
  12. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
15 more
  1. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  2. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
  3. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  4. 2021Testing network correlation efficiently via counting treescited by 22
  5. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  6. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  7. 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
  8. 2022Matching recovery threshold for correlated random graphscited by 16
  9. 2021Correlation detection in trees for planted graph alignmentcited by 14
  10. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  11. 2020Correlated randomly growing graphscited by 12
  12. 2022Statistical limits of correlation detection in treescited by 12
  13. 2019Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphscited by 9
  14. 2022One-Way Matching of Datasets with Low Rank Signalscited by 5
  15. 2022A polynomial-time approximation scheme for the maximal overlap of two independent ErdHos-R'enyi graphscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 4; 2025: 2.

8 papers.

  1. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 9
  2. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 6
  3. 2024A computational transition for detecting correlated stochastic block models by low-degree polynomialscited by 6
  4. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  5. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 3
  6. 2024Testing Dependency of Weighted Random Graphscited by 0
  7. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  8. 2025Statistical-computational gap in multiple Gaussian graph alignmentcited by 0