pith. sign in

arxiv: 2502.17142 · v3 · submitted 2025-02-24 · 🧮 math.ST · math.PR· stat.ML· stat.TH

The feasibility of multi-graph alignment: a Bayesian approach

Louis Vassaux , Laurent Massouli\'e This is my paper

Pith reviewed 2026-05-23 02:45 UTC · model grok-4.3

classification 🧮 math.ST math.PRstat.MLstat.TH
keywords multi-graph alignmentBayesian estimationinformation-theoretic thresholdsGaussian modelErdős-Rényi modelphase transitionmetric spaces
0
0 comments X

The pith

Above a critical threshold exact multi-graph alignment is achievable with high probability in the Gaussian model

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the conditions under which it becomes possible to align multiple random graphs and recover their hidden correspondences. In the Gaussian model it proves a sharp threshold where exact alignment succeeds with high probability above the line but even recovering a positive fraction of matches is impossible below it. In the sparse Erdős-Rényi model it proves that no meaningful partial alignment exists below a threshold and conjectures that partial alignment becomes possible above it. A sympathetic reader would care because these are the fundamental statistical limits on a task that appears in network comparison, biology, and data integration. The results are obtained by constructing a Bayesian estimation procedure defined over metric spaces.

Core claim

In the Gaussian model, above a critical threshold, exact alignment is achievable with high probability, while below it, even partial alignment is statistically impossible. In the sparse Erdős-Rényi model, a threshold is rigorously identified below which no meaningful partial alignment is possible and it is conjectured that partial alignment can be achieved above this threshold. These statements are proved by developing a general Bayesian estimation framework over metric spaces.

What carries the argument

Bayesian estimation framework over metric spaces that directly computes information-theoretic feasibility thresholds for alignment

If this is right

  • Exact alignment is achievable with high probability above the threshold in the Gaussian model
  • Even partial alignment is statistically impossible below the threshold in the Gaussian model
  • No meaningful partial alignment is possible below the threshold in the sparse Erdős-Rényi model
  • Partial alignment is conjectured to be possible above the threshold in the sparse Erdős-Rényi model
  • The metric-space Bayesian framework applies to a broader class of high-dimensional estimation problems

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The framework may be used to derive thresholds for other matching problems such as record linkage or community detection
  • Practical alignment tasks should first verify that the observed signal exceeds the derived threshold before expecting recovery
  • Proving the conjecture for the sparse model would require explicit algorithms that achieve partial alignment above the threshold
  • Similar impossibility lines may exist when the underlying graphs are generated from real data rather than the assumed random models

Load-bearing premise

The random multi-graph generative models with Gaussian weights and sparse Erdős-Rényi edges correctly capture the statistical setting of the alignment problem

What would settle it

A simulation or calculation showing that below the predicted critical threshold in the Gaussian model some procedure achieves partial alignment with non-vanishing probability

read the original abstract

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 Erd\H{o}s-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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper develops a general Bayesian estimation framework over metric spaces and applies it to establish feasibility thresholds for random multi-graph alignment. In the Gaussian model it proves an all-or-nothing phenomenon: exact recovery is possible with high probability above a critical threshold and even partial alignment is impossible below it. In the sparse Erdős-Rényi model it rigorously identifies a threshold below which no meaningful partial alignment is possible and conjectures that partial alignment becomes feasible above the threshold.

Significance. If the derivations are correct, the work supplies sharp information-theoretic thresholds for a multi-graph alignment problem that arises in network analysis and high-dimensional statistics. The metric-space Bayesian framework is presented as a general tool that may extend to other estimation problems; the explicit separation of rigorous impossibility results from the conjecture in the ER case is a strength.

minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly flag that the ER-model result above the threshold remains a conjecture while the impossibility statement is rigorous, to avoid any ambiguity for readers.
  2. Notation for the metric-space posterior and the definition of partial vs. exact alignment should be introduced with a short self-contained paragraph early in the paper, as the framework is new.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper develops a general Bayesian estimation framework over metric spaces and applies it to standard generative models (Gaussian weights, sparse ER graphs) to derive information-theoretic thresholds. No load-bearing step reduces by construction to a fitted parameter, self-citation, or renamed input; the all-or-nothing claims follow from the framework's analysis of the models without internal redefinition or smuggling of ansatzes. The derivation is externally falsifiable via the stated random-graph models and does not rely on prior self-citations for its core thresholds.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the validity of the two random-graph generative models and on the correctness of the newly introduced Bayesian estimation framework; no free parameters or invented entities are indicated in the abstract.

axioms (2)
  • domain assumption The multi-graph data are generated exactly according to the stated Gaussian or sparse Erdős-Rényi distributions.
    These generative assumptions define the statistical setting in which the thresholds are derived.
  • standard math Standard axioms of probability theory and metric-space geometry hold.
    Required for the Bayesian estimation framework and threshold statements.

pith-pipeline@v0.9.0 · 5629 in / 1277 out tokens · 35698 ms · 2026-05-23T02:45:07.717673+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 3 internal anchors

  1. [1]

    Exact alignment recovery for correlated Erd\H{o}s-R\'enyi graphs

    Cullina, D. and Kiyavash, N. (2017). Exact alignment recovery for correlated Erdős–Rényi graphs. arXiv:1711.06783

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  2. [2]

    , Massoulié, L

    Ganassali, L. , Massoulié, L. and Lelarge, M. (2021). Impossibility of Partial Recovery in the Graph Alignment Problem. In Proceedings of the Thirty-Fourth Conference on Learning Theory, 134, 2080--2102. PMLR

    work page 2021

  3. [3]

    and Du, H

    Ding, J. and Du, H. (2023). Detection Threshold for Correlated Erdős–Rényi Graphs via Densest Subgraph. IEEE Trans.\ Inf.\ Theory 69(8) 5289--5298

    work page 2023

  4. [5]

    Ganassali, L. (2022). Sharp threshold for alignment of graph databases with Gaussian weights. In Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, 145, 314--335. PMLR

    work page 2022

  5. [6]

    and Vershynin, R

    Rudelson, M. and Vershynin, R. (2013). Hanson–Wright inequality and sub-gaussian concentration. Electron.\ Commun.\ Probab. 18 1--9

    work page 2013

  6. [7]

    , Lugosi, G

    Boucheron, S. , Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Non Asymptotic Theory of Independence, 481 pp. Oxford University Press

    work page 2013

  7. [8]

    Wu, Y. , Xu, J. and Yu, S.\!H. (2022). Settling the Sharp Reconstruction Thresholds of Random Graph Matching. IEEE Trans.\ Inf.\ Theory 68(8) 5391--5417

    work page 2022

  8. [9]

    , Kiyavash, N

    Cullina, D. , Kiyavash, N. , Mittal, P. and Poor, H.\!V. (2019). Partial Recovery of Erdős–Rényi Graph Alignment via k -Core Alignment. Proc.\ ACM Meas.\ Anal.\ Comput.\ Syst. 3(3) Article 54, 21 pp

    work page 2019

  9. [10]

    and Du, H

    Ding, J. and Du, H. (2022). Matching recovery threshold for correlated random graphs. Ann.\ Statist. (to appear)

    work page 2022

  10. [11]

    Berger, J.\!O. (1985). Statistical Decision Theory and Bayesian Analysis, 2nd ed. Springer, New York

    work page 1985

  11. [12]

    Bollobás, B. (2001). Random Graphs, 2nd ed. Cambridge University Press, Cambridge

    work page 2001

  12. [13]

    , Grama, I

    Fan, X. , Grama, I. and Liu, Q. (2015). Sharp large deviation results for sums of independent random variables. Sci.\ China Math. 58 1939--1958

    work page 2015

  13. [14]

    Spectral Alignment of Graphs

    Feizi, S. , Quon, G. , Recamonde-Mendoza, M. , Medard, M. , Kellis, M. and Jadbabaie, A. (2017). Spectral Alignment of Graphs. arXiv:1602.04181

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  14. [15]

    Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model

    Fan, Z. , Mao, C. , Wu, Y. and Xu, J. (2019). Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model. arXiv:1907.08880

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  15. [16]

    , Mao, C

    Fan, Z. , Mao, C. , Wu, Y. and Xu, J. (2019). Spectral Graph Matching and Regularized Quadratic Relaxations II. Found.\ Comput.\ Math. 23 1567--1617

    work page 2019

  16. [17]

    , Lelarge, M

    Ganassali, L. , Lelarge, M. and Massoulié, L. (2019). Spectral alignment of correlated Gaussian random matrices. arXiv:1912.00231

    work page arXiv 2019

  17. [18]

    Ding, J. , Ma, Z. , Wu, Y. and Xu, J. (2018). Efficient random graph matching via degree profiles. Probab.\ Theory Relat.\ Fields 179 29--115

    work page 2018

  18. [19]

    and Maron, H

    Dym, N. and Maron, H. (2017). DS++: A flexible, scalable and provably tight relaxation for matching problems. ACM Trans.\ Graph. 36

    work page 2017

  19. [20]

    Mao, C. , Wu, Y. , Xu, J. and Yu, S.\!H. (2022). Random Graph Matching at Otter’s Threshold via Counting Chandeliers. In Proc.\ 55th ACM Symp.\ Theory Comput

    work page 2022

  20. [21]

    , Ganassali, L

    Even, M. , Ganassali, L. , Maier, J. and Massoulié, L. (2024). Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes–Wasserstein Problem. arXiv:2405.14532

    work page arXiv 2024

  21. [22]

    and Shmatikov, V

    Narayanan, A. and Shmatikov, V. (2009). De-anonymizing Social Networks. In Proc.\ 2009 IEEE Symp.\ Security Privacy, 173--187. IEEE

    work page 2009

  22. [23]

    , Gleich, D.\!F

    Bayati, M. , Gleich, D.\!F. , Saberi, A. and Wang, Y. (2013). Message-Passing Algorithms for Sparse Network Alignment. ACM Trans.\ Knowl.\ Discov.\ Data 7(1) Article 3, 31 pp

    work page 2013

  23. [24]

    , Hassani, H

    Kazemi, E. , Hassani, H. , Grossglauser, M. and Pezeshgi Modarres, H. (2016). PROPER: Global protein interaction network alignment through percolation matching. BMC Bioinformatics 17

    work page 2016

  24. [25]

    , Massoulié, L

    Ganassali, L. , Massoulié, L. and Semerjian, G. (2024). Statistical limits of correlation detection in trees. Ann.\ Appl.\ Probab. 34(4) 3701--3734

    work page 2024

  25. [26]

    Ding, J. , Du, H. and Li, Z. (2023). Low-Degree Hardness of Detection for Correlated Erdős–Rényi Graphs. arXiv:2311.15931

    work page arXiv 2023

  26. [27]

    , Zhu, L

    Zhu, X. , Zhu, L. and Geng, X. (2024). k -wise multi-graph matching. IET Image Process. 18 4760--4777

    work page 2024

  27. [28]

    and Milenković, T

    Vijayan, V. and Milenković, T. (2016). Multiple Network Alignment via MultiMAGNA++. IEEE/ACM Trans.\ Comput.\ Biol.\ Bioinform. 15 1669--1682

    work page 2016

  28. [29]

    Liao, C.-S. , Lu, K. , Baym, M. , Singh, R. and Berger, B. (2009). IsoRankN: Spectral Methods for Global Alignment of Multiple Protein Networks. Bioinformatics 25 i253--i258

    work page 2009

  29. [30]

    and Hajek, B

    Ameen, T. and Hajek, B. (2025). Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery. arXiv:2405.12293

    work page arXiv 2025

  30. [31]

    and Hajek, B

    Ameen, T. and Hajek, B. (2025). Detecting Correlation between Multiple Unlabeled Gaussian Networks. arXiv:2504.16279

    work page arXiv 2025