The feasibility of multi-graph alignment: a Bayesian approach

Laurent Massouli\'e; Louis Vassaux

arxiv: 2502.17142 · v4 · pith:PYVDSWJ6new · 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-25 07:54 UTC · model grok-4.3

classification 🧮 math.ST math.PRstat.MLstat.TH

keywords multi-graph alignmentBayesian estimationthreshold phenomenaGaussian modelErdős-Rényi graphsexact recoverypartial recoverymetric spaces

0 comments

The pith

Exact multi-graph alignment succeeds above a critical threshold in the Gaussian model but fails even partially below it.

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

The paper determines feasibility thresholds for aligning several random graphs drawn from the same underlying structure. In the Gaussian model it proves an all-or-nothing transition: above the threshold exact recovery of the alignment occurs with high probability, while below the threshold no algorithm can recover even a positive fraction of the correct matches. In the sparse Erdős-Rényi model it proves a lower threshold below which partial alignment is impossible and conjectures that partial alignment becomes possible above it. Both results rest on a Bayesian estimation procedure defined directly on metric spaces that yields posterior concentration at the true alignment when the signal is strong enough.

Core claim

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ős-Rényi 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.

What carries the argument

Bayesian estimation framework over metric spaces, whose posterior concentrates at the true alignment above the identified thresholds.

If this is right

Above the Gaussian threshold any procedure that samples from the posterior will output the exact alignment with high probability.
Below the Gaussian threshold every procedure, including those that optimize any objective, fails to recover a positive fraction of matches.
In the sparse Erdős-Rényi model the identified threshold is a hard impossibility barrier for partial recovery.
The same metric-space Bayesian construction supplies concentration arguments for a wider family of high-dimensional estimation tasks.

Where Pith is reading between the lines

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

The metric-space formulation may allow direct transfer of the same threshold analysis to related matching problems such as point-cloud registration or database deduplication.
Finite-n simulations with the posterior sampler could reveal how sharply the transition occurs for moderate graph sizes.
The all-or-nothing result suggests that computational methods need only target the regime above the threshold rather than attempting graceful degradation.

Load-bearing premise

The multi-graph alignment task can be faithfully captured as a Bayesian estimation problem over metric spaces whose posterior concentrates at the true alignment above the identified thresholds.

What would settle it

An algorithm that recovers a positive fraction of correct matches with high probability below the Gaussian-model threshold, or failure of every algorithm to achieve exact recovery above the same threshold.

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.

Desk Editor's Note private letter to a colleague

The paper sets up a Bayesian metric-space framework that yields an all-or-nothing threshold for exact multi-graph alignment in the Gaussian model plus an impossibility threshold in sparse ER graphs.

read the letter

The main point is that they extend alignment from pairs of graphs to multiple graphs and use a Bayesian posterior over metric spaces to get sharp feasibility thresholds. In the Gaussian case they claim exact recovery becomes possible above a critical value and impossible even partially below it. In the sparse ER model they prove the negative direction and leave the positive direction as a conjecture. The framework is positioned as a general tool for other high-dimensional estimation tasks as well. This is new relative to the pairwise results in the literature they cite, and the all-or-nothing statement is a strong form of result if the arguments hold. The approach directly targets information-theoretic limits rather than algorithm design, which is useful for guiding work in network inference. The ER conjecture is stated plainly, which is honest. The main soft spot is that the abstract supplies the claims but not the derivations or error bounds, so it is not yet possible to check how the posterior concentration is established or whether the metric-space reduction preserves the essential structure of the alignment problem. The Gaussian proofs are asserted to be rigorous, but that still needs verification in the body. No circular dependence on prior self-citations appears in the description. This is for people working on statistical limits for graph problems who want precise thresholds rather than heuristics. A reader focused on Bayesian methods in high dimensions might also extract something from the framework. It deserves peer review because the claims are concrete and the multi-graph setting is a natural next step; referees can test the proofs and see whether the conjecture can be settled or tightened.

Referee Report

1 major / 0 minor

Summary. The paper claims to establish feasibility thresholds for random multi-graph alignment. In the Gaussian model it asserts an all-or-nothing phenomenon (exact alignment achievable w.h.p. above a critical threshold, impossible even partially below it). In the sparse ER model it rigorously identifies a threshold below which no meaningful partial alignment is possible and conjectures achievability above it. Both results are obtained via a newly developed general Bayesian estimation framework over metric spaces whose posterior is claimed to concentrate at the true alignment.

Significance. If the claimed thresholds and the supporting posterior-concentration arguments hold, the work supplies a unified Bayesian lens for a class of high-dimensional alignment and estimation problems, potentially clarifying phase transitions that appear in multiple related settings.

major comments (1)

[Abstract] Abstract: the central claims rest on 'rigorous proofs' for the Gaussian case and a 'rigorous identification' of the ER threshold, yet the provided text contains neither model definitions, the metric-space posterior, error bounds, nor any proof sketch. Without these elements the all-or-nothing statement and the partial-alignment threshold cannot be verified and are therefore load-bearing gaps.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. The single major comment is addressed below. The full manuscript contains the model definitions, framework, bounds, and proofs referenced in the abstract; the abstract itself is a conventional high-level summary.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims rest on 'rigorous proofs' for the Gaussian case and a 'rigorous identification' of the ER threshold, yet the provided text contains neither model definitions, the metric-space posterior, error bounds, nor any proof sketch. Without these elements the all-or-nothing statement and the partial-alignment threshold cannot be verified and are therefore load-bearing gaps.

Authors: The full manuscript supplies all requested elements. Section 2 defines the Gaussian multi-graph model and the sparse ER model. Section 3 develops the general Bayesian estimation framework over metric spaces, including the posterior and its concentration properties. Section 4 contains the rigorous proof of the all-or-nothing threshold for the Gaussian case, with explicit error bounds. Section 5 rigorously identifies the partial-alignment impossibility threshold in the sparse ER model (with the achievability direction stated as a conjecture). The abstract summarizes these results without reproducing the technical content, which is standard practice; the complete definitions, framework, bounds, and proofs appear in the body of the paper. revision: no

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The abstract and reader's summary present a Bayesian estimation framework over metric spaces as a newly developed tool to derive all-or-nothing thresholds for multi-graph alignment in Gaussian and Erdős-Rényi models. No equations, self-citations, or fitted parameters are quoted that reduce the claimed predictions or impossibility results to inputs by construction. The derivation chain is therefore self-contained against external benchmarks, with the framework providing independent insight rather than renaming or fitting prior quantities. This matches the expected honest non-finding for papers without visible load-bearing reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, invented entities, or non-standard axioms are stated. The framework implicitly relies on standard properties of metric spaces and Bayesian posterior concentration.

axioms (1)

standard math Standard properties of metric spaces and concentration of Bayesian posteriors in high dimensions
Invoked to support the general estimation framework described in the abstract.

pith-pipeline@v0.9.0 · 5629 in / 1214 out tokens · 34387 ms · 2026-05-25T07:54:31.622156+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We develop a general Bayesian estimation framework over metric spaces... posterior concentrates at the true alignment above the identified thresholds.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

all-or-nothing phenomenon... exact alignment achievable with high probability

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

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

[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]

, 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]

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
[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
[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
[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
[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
[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
[10]

and Du, H

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

work page 2022
[11]

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

work page 1985
[12]

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

work page 2001
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[31]

and Hajek, B

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

work page arXiv 2025

[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