Planted Bipartite Graph Detection
Asaf Rotenberg, Wasim Huleihel, Ofer Shayevitz · IEEE Transactions on Information Theory · 2024
We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over n vertices with edge density q. Under the alternative, there exists a planted$k_{ \mathsf {R}} \times k_{ \mathsf {L}}$bipartite subgraph with edge density$p>q$. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where$p,q = \Theta \left ({1}\right)$, and the sparse regime where$p,q = \Theta \left ({n^{-\alpha }}\right), \alpha \in \left ({0,2}\right]$. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an “easy-hard-impossible” phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region.