Matching recovery threshold for correlated random graphs (Q6183756): Difference between revisions

This paper studies a recovery-type problem for correlated (coupled) random graphs that are obtained as random subgraphs of the same Erdős-Rényi graph. More precisely, first we take an Erdős-Rényi graph \(G=(V, E)\) on \(n\) (labeled) vertices with edge probabilities \(p\). We keep each edge of \(G\) independently with probability \(s\) to obtain \(G_1=(V, E_1)\). Then we apply a randomly chosen permutation \(\pi^\ast: V\rightarrow V\) on the vertices of \(G\), this generates a labeled graph \(G^\ast\) (two vertices \(v\), \(w\) in \(G^\ast\) are connected to each other if and only if \((\pi^\ast)^{-1}(v)\) and \((\pi^\ast)^{-1}(w)\) are connected to each other in \(G\)). Finally, independently of \(G_1\) and each other, we keep each edge of \(G^\ast\) with probability \(s\) to get \(G_2=(V_2, E_2)\). The question is the following: given \(G_1\) and \(G_2\), how can we find the matching \(\hat\pi\) for which the overlap \((\pi^\ast, \hat \pi)=|\{v\in V: \pi^\ast(v)=\hat\pi(v)\}|\) is maximal? That is, given the two independent unlabeled copies of random subgraphs of the same Erdős-Rényi graph \(G\), the goal is to find the pairs of vertices that correspond to the same node in the original graph. The paper provides a sharp information-theoretic threshold for partial recovery, that is, determines \(\delta\) for which \((\pi^\ast, \hat \pi)\geq \delta n\) can be achieved for sequences of random graphs with \(p=p_n=n^{-\alpha}+o(1)\). It turns out that the threshold is the same as the threshold for detecting correlation (i.e.\ testing this correlated version against two completely independent copies of random graphs). The construction of the optimal matching also relies on the methods of \textit{J. Ding} and \textit{H. Hu} [IEEE Trans. Inf. Theory 69, No. 8, 5289--5298 (2023; \url{doi:10.1109/TIT.2023.3265009})]. Still, in order to obtain the precise threshold for partial recovery, the authors give strong bounds on quantities derived from edge orbits. As for the other direction, to show that partial recovery is not possible for large enough \(\delta\), the argument is based on a truncated version of the second-moment method.