# Recovery thresholds for hidden weighted sparse graphs

arXiv: https://arxiv.org/abs/2606.14335 · HTML: https://mlsanity.com/paper/2606.14335/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 31 references that are in the map.
- First posted on arXiv 12 Jun 2026.

## Builds on (most cited first, 9 of 9)

- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [The Planted Matching Problem: Phase Transitions and Exact Results](https://mlsanity.com/paper/1912.08880/) (2019)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [Hidden Hamiltonian Cycle Recovery via Linear Programming](https://mlsanity.com/paper/1804.05436/) (2018)
- [Almost-Linear Planted Cliques Elude the Metropolis Process](https://mlsanity.com/paper/2204.01911/) (2022)
- [Consistent recovery threshold of hidden nearest neighbor graphs](https://mlsanity.com/paper/1911.08004/) (2019)
- [Low-degree Security of the Planted Random Subgraph Problem](https://mlsanity.com/paper/2409.16227/) (2024)

## Abstract (arXiv)

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.