Recovery thresholds for hidden weighted sparse graphs

Abstract

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph H^* H_n is chosen uniformly at random, and hidden in a complete graph of n vertices as follows: the weight of an edge e H is distributed independently according to P_n; otherwise the weight is distributed independently according to Q_n. The goal is to recover almost all of H from these edge weights. Assuming a local Lipschitzness of the Rényi divergence between distributions P_n and Q_n, and a mild density condition for the graphs H_n, we give a unified characterization of the information-theoretic limit for recovering almost all of H (also known as almost exact recovery). Our characterization connects the KL divergence between P_n and Q_n to the logarithm of the first moment threshold of H in the Erdős-Rényi random graph model G(n,p). Our lower bound also extends to the task of partial recovery, in which only a constant λ-fraction of H needs to be recovered. Last but not least, for certain Bernoulli and Exponential regimes, and for Gaussian distributions, we are able to show an All-or-Nothing (AoN) threshold phenomenon at the exponential scale.

Reproductions