The detection of planted subgraphs in Erdős-Rényi random graphs has been extensively studied, leading to a rich body of statistical and computational threshold results. However, most prior work assumes a purely random generative model, which makes the resulting algorithms potentially fragile in the face of real-world perturbations. This work initiates the study of semi-random models for the planted subgraph detection problem, where an adversary can remove edges outside the planted subgraph before the graph is revealed to the statistician. Crucially, the statistician remains unaware of which edges have been removed, introducing fundamental challenges to the inference task.
We establish fundamental statistical limits for detection under this semi-random model, revealing a sharp dichotomy. Specifically, for planted subgraphs with strongly sub-logarithmic maximum density, detection becomes information-theoretically impossible in the presence of an adversary, despite being possible for some planted subgraphs in the classical random model. In stark contrast, for subgraphs with super-logarithmic density, the statistical limits remain essentially unchanged; we prove that the optimal (albeit computationally intractable) likelihood ratio test remains robust.
Beyond these statistical boundaries, we design a new computationally efficient and robust detection algorithm, providing rigorous statistical guarantees for its performance. Our results establish the first robust framework for planted subgraph detection, opening new directions in the study of semi-random models, computational-statistical trade-offs, and robustness in graph inference problems.
Blogger's Review: This paper provides an innovative perspective on planted subgraph detection through semi-random models, addressing the vulnerabilities of traditional random models and demonstrating the statistical limits and algorithm robustness under adversarial interference. The proposed algorithm and theoretical results are likely to have a profound impact on the field of graph theory.