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^* \in \mathcal H_n$ is chosen uniformly at random, and hidden in a complete graph of $n$ vertices through edge weights: for an edge $e \in H^*$, its weight is distributed independently according to $\mathcal{P}_n$; otherwise the edge weight is distributed independently according to $\mathcal{Q}_n$. The goal is to recover the hidden edge set from these noisy observations. Our primary focus on \emph{almost exact recovery}, where all but a vanishing fraction of the edges of $H^*$ must be identified. By choosing $\mathcal{P} = \mathrm{Bern}(1), \mathcal{Q} = \mathrm{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 $\mathcal{P}_n$ and $\mathcal{Q}_n$, and a mild density condition for the graphs $\mathcal 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 uses the KL divergence $D_{\mathrm{KL}}(\mathcal{P}_n\|\mathcal{Q}_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 $\mathcal H_n$ in the Erdős-Rényi random graph model $G(n,p)$. For any constant $\eta$, if $D_{\mathrm{KL}} \ge (1+\eta)D_c$, the maximum likelihood estimator (MLE) achieves almost exact recovery; conversely if $D_{\mathrm{KL}} \le (1-\eta)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 d