Matching recovery threshold for correlated random graphs

DOI10.1214/23-AOS2305MaRDI QIDQ6183756zbMATH OpenFDO

Authors

Publication date 4 January 2024

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.14650, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-4/Matching-recovery-threshold-for-correlated-random-graphs/10.1214/23-AOS2305.full

zbMATH Keywords

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: For two correlated graphs which are independently sub-sampled from a common ErdH{o}s-R'enyi graph

m a t h b f G (n, p)

, we wish to recover their emph{latent} vertex matching from the observation of these two graphs emph{without labels}. When

p = n^{- a l p h a + o (1)}

for

a l p h a i n (0, 1]

, we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.

Review text

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Matching recovery threshold for correlated random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183756)