Detecting Arbitrary Planted Subgraphs in Random Graphs

The problems of detecting and recovering planted structures/subgraphs in ErdHos-R'enyi random graphs, have received significant attention over the past three decades, leading to many exciting results and mathematical techniques. However, prior work has largely focused on specific ad hoc planted structures and inferential settings, while a general theory has remained elusive. In this paper, we bridge this gap by investigating the detection of an arbitrary planted subgraph Gamma = Gamman in an ErdHos-R'enyi random graph G(n, qn), where the edge probability within Gamma is pn. We examine both the statistical and computational aspects of this problem and establish the following results. In the dense regime, where the edge probabilities pn and qn are fixed, we tightly characterize the information-theoretic and computational thresholds for detecting Gamma, and provide conditions under which a computational-statistical gap arises. Most notably, these thresholds depend on Gamma only through its number of edges, maximum degree, and maximum subgraph density. Our lower and upper bounds are general and apply to any value of pn and qn as functions of n. Accordingly, we also analyze the sparse regime where qn = Theta(n-α) and pn-qn =Theta(qn), with α∈[0,2], as well as the critical regime where pn=1-o(1) and qn = Theta(n-α), both of which have been widely studied, for specific choices of Gamma. For these regimes, we show that our bounds are tight for all planted subgraphs investigated in the literature thus fartextemdashand many more. Finally, we identify conditions under which detection undergoes sharp phase transition, where the boundaries at which algorithms succeed or fail shift abruptly as a function of qn.