Impossibility of Partial Recovery in the Graph Alignment Problem

Luca Ganassali, Laurent Massoulie, Marc Lelarge
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2080-2102, 2021.

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 the first impossibility result for partial recovery in the sparse regime (with constant average degree). 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-ganassali21a, title = {Impossibility of Partial Recovery in the Graph Alignment Problem}, author = {Ganassali, Luca and Massoulie, Laurent and Lelarge, Marc}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {2080--2102}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/ganassali21a/ganassali21a.pdf}, url = {https://proceedings.mlr.press/v134/ganassali21a.html}, 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 the first impossibility result for partial recovery in the sparse regime (with constant average degree). 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.} }
Endnote
%0 Conference Paper %T Impossibility of Partial Recovery in the Graph Alignment Problem %A Luca Ganassali %A Laurent Massoulie %A Marc Lelarge %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-ganassali21a %I PMLR %P 2080--2102 %U https://proceedings.mlr.press/v134/ganassali21a.html %V 134 %X 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 the first impossibility result for partial recovery in the sparse regime (with constant average degree). 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.
APA
Ganassali, L., Massoulie, L. & Lelarge, M.. (2021). Impossibility of Partial Recovery in the Graph Alignment Problem. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:2080-2102 Available from https://proceedings.mlr.press/v134/ganassali21a.html.

Related Material