# The feasibility of multi-graph alignment: a Bayesian approach

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 24 Feb 2025.

## Builds on (most cited first, 16 of 16)

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universality](https://mlsanity.com/paper/1907.08883/) (2019)
- [Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignment](https://mlsanity.com/paper/1809.03553/) (2018)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model](https://mlsanity.com/paper/1907.08880/) (2019)
- [Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphs](https://mlsanity.com/paper/2203.14573/) (2022)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Statistical limits of correlation detection in trees](https://mlsanity.com/paper/2209.13723/) (2022)
- [Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphs](https://mlsanity.com/paper/2311.15931/) (2023)
- [Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery](https://mlsanity.com/paper/2405.12293/) (2024)
- [Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem](https://mlsanity.com/paper/2405.14532/) (2024)

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

- [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025)
- [Sharp Statistical Thresholds for Attributed Gaussian Graph Matching](https://mlsanity.com/paper/2603.23305/) (2026)
- [Auditing Bayesian Graph Alignment: Diagnostic Comparisons and Reference Failure](https://mlsanity.com/paper/2609.23232/) (2026)

## Abstract (arXiv)

We establish thresholds for the feasibility of random multi-graph alignment in two models. In the Gaussian model, we demonstrate an "all-or-nothing" phenomenon: above a critical threshold, exact alignment is achievable with high probability, while below it, even partial alignment is statistically impossible. In the sparse ErdHos-R'enyi model, we rigorously identify a threshold below which no meaningful partial alignment is possible and conjecture that above this threshold, partial alignment can be achieved. To prove these results, we develop a general Bayesian estimation framework over metric spaces, which provides insight into a broader class of high-dimensional statistical problems.