Optimal recovery of correlated Erdős-Rényi graphs

Abstract

For two unlabeled graphs $G_1,G_2$ independently sub-sampled from an Erdős-Rényi graph $\mathbf{G}(n,p)$ by keeping each edge with probability $s$, we aim to recover \emph{as many as possible} of the corresponding vertex pairs. We establish a connection between the recoverability of vertex pairs and the balanced load allocation in the true intersection graph of $G_1$ and $G_2$. Using this connection, we analyze the partial recovery regime where $p=n^{-\alpha +o(1)}$ for some $\alpha \in (0,1]$ and $np{s}^2=\lambda =O(1)$. We derive upper and lower bounds for the recoverable fraction in terms of $\alpha$ and the limiting load distribution ${\mu }_{\lambda }$ (as introduced in \cite{AS16}). These bounds coincide asymptotically whenever ${\alpha }^{-1}$ is not an atom of ${\mu }_{\lambda }$. Therefore, for each fixed $\lambda$, our result characterizes the asymptotic optimal recovery fraction for all but countably many $\alpha \in (0,1]$.

41 pages