Impossibility of Partial Recovery in the Graph Alignment Problem

Abstract

Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For the correlated Erdös-Rényi model, we prove an impossibility result for partial recovery in the sparse regime, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.

arXiv comment23 pages, 8 figures. Accepted for publication at COLT21

References in corpus (9)

• Seeded graph matching for correlated Erdős-Rényi graphs
• Exact alignment recovery for correlated Erdős-Rényi graphs
• Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
• Efficient random graph matching via degree profiles
• Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
• DS++: A flexible, scalable and provably tight relaxation for matching problems
• Testing correlation of unlabeled random graphs
• Sharp threshold for alignment of graph databases with Gaussian weights
• Spectral Alignment of Correlated Gaussian matrices

Cited by in corpus (7)

• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Statistical limits of correlation detection in trees
• Correlation detection in trees for planted graph alignment
• Network Recovery from Unlabeled Noisy Samples
• Graph Matching via convex relaxation to the simplex
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs