Optimal community detection in dense bipartite graphs

We consider the problem of detecting a community of densely connected vertices in a high-dimensional bipartite graph of size n1 × n2. Under the null hypothesis, the observed graph is drawn from a bipartite ErdHos-Renyi distribution with connection probability p0. Under the alternative hypothesis, there exists an unknown bipartite subgraph of size k1 × k2 in which edges appear with probability p1 = p0 + δ for some δ > 0, while all other edges outside the subgraph appear with probability p0. Specifically, we provide non-asymptotic upper and lower bounds on the smallest signal strength δ^* that is both necessary and sufficient to ensure the existence of a test with small enough type one and type two errors. We also derive novel minimax-optimal tests achieving these fundamental limits when the underlying graph is sufficiently dense. Our proposed tests involve a combination of hard-thresholded nonlinear statistics of the adjacency matrix, the analysis of which may be of independent interest. In contrast with previous work, our non-asymptotic upper and lower bounds match for any configuration of n1,n2, k1,k2.