# Inferring Hidden Structures in Random Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 60 references that are in the map.
- First posted on arXiv 5 Oct 2021.

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

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015)
- [Notes on computational-to-statistical gaps: predictions using statistical physics](https://mlsanity.com/paper/1803.11132/) (2018)
- [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering](https://mlsanity.com/paper/1610.02918/) (2016)
- [Universality of Computational Lower Bounds for Submatrix Detection](https://mlsanity.com/paper/1902.06916/) (2019)
- [Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix](https://mlsanity.com/paper/1502.01988/) (2015)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Community Detection in Sparse Random Networks](https://mlsanity.com/paper/1308.2955/) (2013)
- [Sum-of-Squares Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1507.06370/) (2015)
- [Average-case Hardness of RIP Certification](https://mlsanity.com/paper/1605.09646/) (2016)
- [Do semidefinite relaxations solve sparse PCA up to the information limit?](https://mlsanity.com/paper/1306.3690/) (2013)
- [Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems](https://mlsanity.com/paper/1502.06590/) (2015)
- [Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4](https://mlsanity.com/paper/1911.01411/) (2019)
- [Finding One Community in a Sparse Graph](https://mlsanity.com/paper/1502.05680/) (2015)
- [Hidden Hamiltonian Cycle Recovery via Linear Programming](https://mlsanity.com/paper/1804.05436/) (2018)

## Built on by (most cited first, 2 of 2)

- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)

## Abstract (arXiv)

We study the two inference problems of detecting and recovering an isolated community of general structure planted in a random graph. The detection problem is formalized as a hypothesis testing problem, where under the null hypothesis, the graph is a realization of an ErdHos-R'enyi random graph G(n,q) with edge density q∈(0,1); under the alternative, there is an unknown structure Gammak on k nodes, planted in G(n,q), such that it appears as an induced subgraph. In case of a successful detection, we are concerned with the task of recovering the corresponding structure. For these problems, we investigate the fundamental limits from both the statistical and computational perspectives. Specifically, we derive lower bounds for detecting/recovering the structure Gammak in terms of the parameters (n,k,q), as well as certain properties of Gammak, and exhibit computationally unbounded optimal algorithms that achieve these lower bounds. We also consider the problem of testing in polynomial-time. As is customary in many similar structured high-dimensional problems, our model undergoes an "easy-hard-impossible" phase transition and computational constraints can severely penalize the statistical performance. To provide an evidence for this phenomenon, we show that the class of low-degree polynomials algorithms match the statistical performance of the polynomial-time algorithms we develop.