Impossibility of Partial Recovery in the Graph Alignment Problem
This work addresses a fundamental theoretical limit for recovering vertex correspondence in noisy graph alignment, relevant for researchers in graph theory and statistical inference.
This paper investigates the graph alignment problem for correlated Erdös-Rényi models, proving an impossibility result for partial recovery in the sparse regime with constant average degree and correlation. They establish a general bound on the maximal reachable overlap, which is tight in the noiseless case.
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.