# Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph

arXiv: https://arxiv.org/abs/2403.17766 · HTML: https://mlsanity.com/paper/2403.17766/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2024.

## Built on by (most cited first, 2 of 2)

- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

We study the computational limits of the following general hypothesis testing problem. Let H=Hn be an arbitrary undirected graph on n vertices. We study the detection task between a ``null'' ErdHos-R'enyi 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=Hn. 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=Hn is any arbitrary graph and for any p=Omega(1). Perhaps surprisingly, we prove that the 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.