Counting stars is constant-degree optimal for detecting any planted subgraph

Abstract

We study the computational limits of the following general hypothesis testing problem. Let $H=H_n$ be an arbitrary undirected graph. We study the detection task between a “null” Erdős–Rényi random graph $G(n,p)$ and a “planted” random graph which is the union of $G(n,p)$ together with a random copy of $H=H_n$. Our notion of planted model is a generalization of a plethora of recently studied models initiated with the study of the planted clique model (Jerrum, 1992), which corresponds to the special case where $H$ is a $k$-clique and $p=1/2$.
Over the last decade, several papers have studied the power of low-degree polynomials for limited choices of $H$’s in the above task. In this work, we adopt a unifying perspective and characterize the power of constant degree polynomials for the detection task, when $H=H_n$ is any arbitrary graph and for any $p=\Omega (1)$. Perhaps surprisingly, we prove that an optimal constant degree polynomial is always given by simply counting stars in the input random graph. As a direct corollary, we conclude that the class of constant-degree polynomials is only able to “sense” the degree distribution of the planted graph $H$, and no other graph theoretic property of it.