Random Subgraph Detection Using Queries
arXiv:2110.00744
Abstract
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 vertices. Under the null hypothesis, the graph is a realization of an Erdős-Rényi graph with edge probability (or, density) . Under the alternative, there is a subgraph on vertices with edge probability . The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters and . 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.
arXiv comment27 pages
References in corpus (9)
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Computational barriers in minimax submatrix detection
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Finding One Community in a Sparse Graph
- Average-case Hardness of RIP Certification
- Query Complexity of Clustering with Side Information
- Universality of Computational Lower Bounds for Submatrix Detection
- On the subgraph query problem
- Finding Planted Cliques in Sublinear Time