# Exact Community Recovery in Bipartite Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 11 Sep 2026.

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

- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Impact of regularization on Spectral Clustering](https://mlsanity.com/paper/1312.1733/) (2013)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Analysis of spectral clustering algorithms for community detection: the general bipartite setting](https://mlsanity.com/paper/1803.04547/) (2018)
- [Spectral Algorithms for Community Detection in Directed Networks](https://mlsanity.com/paper/2008.03820/) (2020)
- [Optimal Bipartite Network Clustering](https://mlsanity.com/paper/1803.06031/) (2018)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Strong Consistency of Spectral Clustering for Stochastic Block Models](https://mlsanity.com/paper/1710.06191/) (2017)
- [Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2309.10416/) (2023)

## Abstract (arXiv)

Community detection in bipartite networks is a fundamental problem in modern data analysis, with applications in recommendation systems, biological networks, and social network analysis. Unlike conventional unipartite graphs, bipartite networks consist of two distinct types of nodes with edges only connecting across types, so recovering latent communities requires estimating labels on the two node types. The stochastic co-blockmodel is a classical probabilistic framework for such networks, yet theoretical guarantees for exact community recovery in this setting remain limited, especially when the number of communities grows, the community sizes are unbalanced, or the degrees are heterogeneous. In this work, we prove that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters. We further extend the result to the degree-corrected stochastic co-blockmodel, where each node carries its own degree heterogeneity parameter, and show that a row-normalized version of the same algorithm maintains the exact recovery guarantee. Extensive experiments validate our theoretical findings.