Aligning random graphs with a sub-tree similarity message-passing algorithm

Abstract

The problem of aligning Erdös-Rényi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through a random permutation of their vertices. We study a polynomial time message-passing algorithm devised to solve the inference problem of partially recovering the hidden permutation, in the sparse regime with constant average degrees. We perform extensive numerical simulations to determine the range of parameters in which this algorithm achieves partial recovery. We also introduce a generalized ensemble of correlated random graphs with prescribed degree distributions, and extend the algorithm to this case.

arXiv comment36 pages, 14 figures, submitted to Journal of Statistical Mechanics: Theory and Experiment. Corrected typos. Modified Figure 1 for clarity. Added references' titles in bibliography. Added definition of "quasi-aligned". Added clarifications about the significance of Nishimori experiments

References in corpus (13)

• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• Cross-species analysis of biological networks by Bayesian alignment
• Belief propagation, robust reconstruction and optimal recovery of block models
• Aligning graphs and finding substructures by a cavity approach
• Expressive Power of Invariant and Equivariant Graph Neural Networks
• Testing network correlation efficiently via counting trees
• Impossibility of Partial Recovery in the Graph Alignment Problem
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Sharp threshold for alignment of graph databases with Gaussian weights
• Exact Matching of Random Graphs with Constant Correlation
• Partial Recovery in the Graph Alignment Problem

Cited by in corpus (3)

• Statistical limits of correlation detection in trees
• Correlation detection in trees for planted graph alignment
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs