Detecting Arbitrary Planted Subgraphs in Random Graphs

The problems of detecting and recovering planted structures and subgraphs in Erdős–Rényi 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. We bridge this gap by investigating the detection of an arbitrary planted subgraph in an Erdős–Rényi random graph. We examine both the statistical and computational aspects of this problem and establish tight bounds on the detection risk, across several regimes of interest, as a function of the planted and underlying graph edge probabilities. Most notably, these bounds depend on the planted subgraph only through its number of edges, maximum degree, and maximum subgraph density.