2021-07-21-ganassali21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Impossibility of Partial Recovery in the Graph Alignment Problem	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	ganassali21a	0	Impossibility of Partial Recovery in the Graph Alignment Problem	2080	2102	2080-2102	2080	false	Ganassali, Luca and Massoulie, Laurent and Lelarge, Marc	given family Luca Ganassali given family Laurent Massoulie given family Marc Lelarge	2021-07-21		Proceedings of Thirty Fourth Conference on Learning Theory	134	inproceedings	date-parts 2021 7 21	http://proceedings.mlr.press/v134/ganassali21a/ganassali21a.pdf