mlsanityData to 14 Oct 2026

The graph alignment problem: fundamental limits and efficient algorithms

arXiv 2404.12418 ↗First posted 18 Apr 2024cs.DS cs.LG math.PRcited by 2

Not on the map. Why?

Abstract (arXiv)

This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 26 of its 121 references that are in the map. First posted on arXiv 18 Apr 2024.

Builds on

26 of 121 references.

References · 26

  1. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  2. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  3. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  4. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  5. 2019Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universalitycited by 27
  6. 2020Testing correlation of unlabeled random graphscited by 26
  7. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  8. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  9. 2021Testing network correlation efficiently via counting treescited by 22
  10. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  11. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  12. 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
14 more
  1. 2017The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardnesscited by 20
  2. 2020Sharp threshold for alignment of graph databases with Gaussian weightscited by 16
  3. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  4. 2019Database Alignment with Gaussian Featurescited by 15
  5. 2014Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithmcited by 13
  6. 2019Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Modelcited by 13
  7. 2016Spectral Alignment of Graphscited by 12
  8. 2020Graph Matching with Partially-Correct Seedscited by 10
  9. 2019The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Propertycited by 9
  10. 2022Seeded graph matching for the correlated Gaussian Wigner model via the projected power methodcited by 4
  11. 2016On the Structure and Efficient Computation of IsoRank Node Similaritiescited by 3
  12. 2016Linear Regression with an Unknown Permutation: Statistical and Computational Limitscited by 3
  13. 2017DS++: A flexible, scalable and provably tight relaxation for matching problemscited by 2
  14. 2016Information-theoretic thresholds for community detection in sparse networkscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodingscited by 2
  2. 2026Sharp Statistical Thresholds for Attributed Gaussian Graph Matchingcited by 0