Recovery thresholds for hidden weighted sparse graphs (extended abstract)

摘要

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the information-theoretic recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph H^* ∈ℋ_n is chosen uniformly at random, and hidden in a complete graph of n vertices through edge weights: for an edge e ∈ H^*, its weight is distributed independently according to 𝒫_n; otherwise the edge weight is distributed independently according to 𝒬_n. The goal is to recover the hidden edge set from these noisy observations. Our primary focus on almost exact recovery, where all but a vanishing fraction of the edges of H^* must be identified. By choosing 𝒫 = Bern(1), 𝒬 = Bern(q), this model captures the well-studied planted Erdős-Rényi recovery setting, and other weighted formulations such as Gaussian and Exponential distributions. Assuming a local Lipschitzness of the Rényi divergence between distributions 𝒫_n and 𝒬_n, and a mild density condition for the graphs ℋ_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 uses the KL divergence D_KL(𝒫_n𝒬_n) as the signal-to-noise metric. We show that there is a critical threshold D_c governed by the logarithm of the first moment threshold of ℋ_n in the Erdős-Rényi random graph model G(n,p). For any constant η, if D_KL≥ (1+η)D_c, the maximum likelihood estimator (MLE) achieves almost exact recovery; conversely if D_KL≤ (1-η)D_c, almost exact recovery is information-theoretically impossible. Our MLE analysis is based on an extension of (Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang, 2020); While our lower bound involves deriving a distance-based Fano-type inequality based on Sibson’s α-mutual information, and it also extends to the task of partial recovery, in which only a constant λ-fraction of the hidden graph is required to be recovered. As a result, if D_KL≤ (λ-η)D_c, we also proved that the recovery of any λ-fraction must fail with high probability. Another interesting phenomenon exhibited by some of these models is the “All-or-Nothing” (AoN), where one can either recover almost all of the hidden graph or essentially nothing at all. For several natural distributional families, including certain Gaussian, Bernoulli and Exponential regimes, we establish an All-or-Nothing (AoN) threshold phenomenon at the exponential scale. For Gaussians, we obtained an AoN by lifting the sharp almost exact recovery threshold through the I-MMSE relation; For the others, we combine a second-moment argument inspired by planted subgraph recovery (Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik, 2023) with the second-order Rényi divergence. We also provide distributional examples where AoN is not universal at this level of generality, and our partial recovery lower bound is already the best possible.