# Optimal community detection in dense bipartite graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 63 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 28 of 28)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1601.02658/) (2016)
- [Optimal hypothesis testing for stochastic block models with growing degrees](https://mlsanity.com/paper/1705.05305/) (2017)
- [Community Detection in Sparse Random Networks](https://mlsanity.com/paper/1308.2955/) (2013)
- [Minimax rates in sparse, high-dimensional changepoint detection](https://mlsanity.com/paper/1907.10012/) (2019)
- [Phase Transitions for Detecting Latent Geometry in Random Graphs](https://mlsanity.com/paper/1910.14167/) (2019)
- [Phase transition in noisy high-dimensional random geometric graphs](https://mlsanity.com/paper/2103.15249/) (2021)
- [Testing Network Structure Using Relations Between Small Subgraph Probabilities](https://mlsanity.com/paper/1704.06742/) (2017)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Random Geometric Graph: Some recent developments and perspectives](https://mlsanity.com/paper/2203.15351/) (2022)
- [Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs](https://mlsanity.com/paper/2406.15957/) (2024)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Minimax rates for sparse signal detection under correlation](https://mlsanity.com/paper/2110.12966/) (2021)
- [Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates](https://mlsanity.com/paper/2211.08580/) (2022)
- [Detecting Arbitrary Planted Subgraphs in Random Graphs](https://mlsanity.com/paper/2503.19069/) (2025)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Sparsity meets correlation in Gaussian sequence model](https://mlsanity.com/paper/2312.09356/) (2023)

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

- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

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.