The feasibility of multi-graph alignment: A Bayesian approach

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ö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, which provides insight into a broader class of high-dimensional statistical problems.