# Random Subgraph Detection Using Queries

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

## Key facts

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

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

- [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)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [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)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [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)
- [Community Detection in Sparse Random Networks](https://mlsanity.com/paper/1308.2955/) (2013)
- [Average-case Hardness of RIP Certification](https://mlsanity.com/paper/1605.09646/) (2016)
- [Finding One Community in a Sparse Graph](https://mlsanity.com/paper/1502.05680/) (2015)
- [Finding a planted clique by adaptive probing](https://mlsanity.com/paper/1903.12050/) (2019)
- [Finding Planted Cliques in Sublinear Time](https://mlsanity.com/paper/2004.12002/) (2020)
- [Clustering Evolving Networks](https://mlsanity.com/paper/1401.3516/) (2014)
- [Finding Planted Subgraphs with Few Eigenvalues using the Schur-Horn Relaxation](https://mlsanity.com/paper/1605.04008/) (2016)

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

- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)

## Abstract (arXiv)

The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on n vertices. Under the null hypothesis, the graph is a realization of an ErdHos-R'enyi graph with edge probability (or, density) q. Under the alternative, there is a subgraph on k vertices with edge probability p>q. The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters p and q. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph. We also propose a polynomial-time algorithm which is able to detect the planted subgraph, albeit with more queries compared to the above lower bound. We conjecture that in the leftover regime, no polynomial-time algorithms exist. Our results resolve two open questions posed in the past literature.