Planted Bipartite Graph Detection

arXiv:2302.03658v2 Announce Type: replace-cross
Abstract: 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\H{o}s-R\'{e}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 …

abstract arxiv cs.ds cs.it cs.lg detection edge graph hidden hypothesis math.it math.st null random stat.th testing type