Recovery thresholds for hidden weighted sparse graphs

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^* ∈ Hn 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 Pn; otherwise the weight is distributed independently according to Qn. The goal is to recover almost all of H from these edge weights. Assuming a local Lipschitzness of the R'enyi divergence between distributions Pn and Qn, and a mild density condition for the graphs Hn, 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 Pn and Qn to the logarithm of the first moment threshold of H in the ErdHos-R'enyi 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.