# Optimal Bipartite Network Clustering

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2018.

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

- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [A simpler spectral approach for clustering in directed networks](https://mlsanity.com/paper/2102.03188/) (2021)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Sparse Partial Least Squares for Coarse Noisy Graph Alignment](https://mlsanity.com/paper/2104.02810/) (2021)
- [Exact Community Recovery in Bipartite Networks](https://mlsanity.com/paper/2609.12445/) (2026)

## Abstract (arXiv)

We study bipartite community detection in networks, or more generally the network biclustering problem. We present a fast two-stage procedure based on spectral initialization followed by the application of a pseudo-likelihood classifier twice. Under mild regularity conditions, we establish the weak consistency of the procedure (i.e., the convergence of the misclassification rate to zero) under a general bipartite stochastic block model. We show that the procedure is optimal in the sense that it achieves the optimal convergence rate that is achievable by a biclustering oracle, adaptively over the whole class, up to constants. This is further formalized by deriving a minimax lower bound over a class of biclustering problems. The optimal rate we obtain sharpens some of the existing results and generalizes others to a wide regime of average degree growth, from sparse networks with average degrees growing arbitrarily slowly to fairly dense networks with average degrees of order √n. As a special case, we recover the known exact recovery threshold in the log n regime of sparsity. To obtain the consistency result, as part of the provable version of the algorithm, we introduce a sub-block partitioning scheme that is also computationally attractive, allowing for distributed implementation of the algorithm without sacrificing optimality. The provable algorithm is derived from a general class of pseudo-likelihood biclustering algorithms that employ simple EM type updates. We show the effectiveness of this general class by numerical simulations.