Fundamental Limits of Query-Based Subgraph Detection
Information Theory
Summary
The authors study a problem where a special hidden subgraph is planted inside a random graph, but instead of seeing the whole graph, you can only check a limited number of edges. They explore how many edge checks (queries) you need to reliably detect this hidden structure. Their results provide both theoretical minimum query amounts and practical algorithms that work well for different types of hidden graphs, such as those with dense spots or important hub nodes. This work extends known results from specific cases like planted cliques to a much wider range of hidden graph types.
Authors
Wasim Huleihel
Abstract
The planted subgraph detection problem asks whether a random graph contains a hidden structured subgraph. In the classical formulation, the entire adjacency matrix is observed and one distinguishes between an Erdős--Rényi random graph and one obtained by planting a copy of a prescribed graph inside an Erdős--Rényi random graph. The statistical and computational limits of this problem under full observation are now well understood, even for arbitrary planted subgraphs. In this paper, we investigate an information-limited version of the problem in which the planted structure is an arbitrary sequence of graphs $Γ=(Γ_n)_{n\geq1}$, where $Γ_n$ is embedded in an ambient graph on $n$ vertices, but the observer does not have access to the full adjacency matrix. Instead, information is acquired through a limited number of non-adaptive edge queries. We study the minimum query complexity required for reliable detection. We derive general information-theoretic lower bounds and complementary algorithmic upper bounds on the query complexity as functions of the query budget and structural properties of the planted graph. The proposed algorithms exploit three distinct structural mechanisms: dense local motifs, high-degree vertices, and global edge density. We establish matching bounds, up to polylogarithmic factors, for several broad families of planted graphs, including clique-like, bounded-cover, and hub-dominated graph classes. Our framework substantially generalizes existing query-complexity results for planted clique and planted dense subgraph models, providing a unified treatment of arbitrary planted subgraphs under restricted graph access.