The feasibility of multi-graph alignment: a Bayesian approach

Laurent Massouli\'e; Louis Vassaux

The feasibility of multi-graph alignment: a Bayesian approach

T0 review · 1 major / 0 minor · reviewed 2026-05-25 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Exact multi-graph alignment succeeds above a critical threshold in the Gaussian model but fails even partially below it.

desk verdict 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 →

arxiv 2502.17142 v4 pith:PYVDSWJ6 submitted 2025-02-24 math.ST math.PRstat.MLstat.TH

Louis Vassaux , Laurent Massoulié This is my paper

classification math.STmath.PRstat.MLstat.TH

keywords multi-graphalignmentBayesianestimationthresholdphenomenaGaussianmodelErdős-Rényigraphsexactrecoverypartialmetricspaces

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

Bayesian estimation framework 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.

Watch

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

assumptions (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.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The feasibility of multi-graph alignment: a Bayesian approach." pith.science (2026). https://pith.science/paper/PYVDSWJ6

@misc{pith2026250217142,
  author       = {Pith},
  title        = {Pith review of: The feasibility of multi-graph alignment: a Bayesian approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PYVDSWJ6}},
  note         = {Machine review of arXiv:2502.17142}
}

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.

Review history (2 revisions) →

Discussion (0). Sign in to comment.

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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Graph alignment in sparse inhomogeneous models via self-overlap
math.PR 2026-07 conditional novelty 7.0 of 10

Partial graph alignment is feasible exactly on vertices whose balanced load in the intersection graph exceeds the self-overlap of the union graph, giving sharp thresholds for Chung–Lu and stochastic block-model graphs.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · cited by 1 Pith paper

[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 Pith review 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

Show all 30 references

[10]

and Du, H

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

2022
[11]

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

1985
[12]

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

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

2015
[14]

, Quon, G

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

2017 arXiv
[15]

, Mao, C

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

2019 arXiv
[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

2019
[17]

, Lelarge, M

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

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

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

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

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

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

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

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

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

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

2023
[27]

, Zhu, L

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

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

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

2009
[30]

and Hajek, B

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

2025
[31]

and Hajek, B

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

2025

Pith tools

Reviewed May 25, 2026 · model on record in the stance chip above.

[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 Pith review 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