The feasibility of multi-graph alignment: a Bayesian approach

2025/02/24 by Louis Vassaux, Vassaux, Louis, Laurent Massoulié +1 · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2502.17142

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.

Cited by

• Statistical-computational gap in multiple Gaussian graph alignment

Related

• Statistical-computational gap in multiple Gaussian graph alignment
• Graph alignment in sparse inhomogeneous models via self-overlap
• The Algorithmic Phase Transition of Random Graph Alignment Problem
• Random Graph Matching with Improved Noise Robustness
• The graph alignment problem: fundamental limits and efficient algorithms