Skip to Main content Skip to Navigation
New interface
Conference papers

Impossibility of Partial Recovery in the Graph Alignment Problem

Luca Ganassali 1 Marc Lelarge 1 Laurent Massoulié 1 
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
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.
Complete list of metadata

https://hal.inria.fr/hal-03410038
Contributor : Luca Ganassali Connect in order to contact the contributor
Submitted on : Saturday, October 30, 2021 - 6:47:30 PM
Last modification on : Wednesday, June 8, 2022 - 12:50:03 PM
Long-term archiving on: : Monday, January 31, 2022 - 6:46:57 PM

File

ganassali21a.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03410038, version 1

Collections

Citation

Luca Ganassali, Marc Lelarge, Laurent Massoulié. Impossibility of Partial Recovery in the Graph Alignment Problem. COLT 2021 - 34th Annual Conference on Learning Theory, Aug 2021, Boulder / Virtual, United States. ⟨hal-03410038⟩

Share

Metrics

Record views

24

Files downloads

36