# Spectral Thresholds in the Bipartite Stochastic Block Model

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2015.

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

- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Clustering Mixtures of Discrete Distributions: A Note on Mitra's Algorithm](https://mlsanity.com/paper/2405.19559/) (2024)

## Abstract (arXiv)

We consider a bipartite stochastic block model on vertex sets V1 and V2, with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set. When |V2| gg |V1|, multiple thresholds emerge. We first locate a sharp threshold for detection of the partition, in the sense of the results of citemossel2012stochastic,mossel2013proof and citemassoulie2014community for the stochastic block model. We then show that at a higher edge density, the singular vectors of the rectangular biadjacency matrix exhibit a localization / delocalization phase transition, giving recovery above the threshold and no recovery below. Nevertheless, we propose a simple spectral algorithm, Diagonal Deletion SVD, which recovers the partition at a nearly optimal edge density. The bipartite stochastic block model studied here was used by citefeldman2014algorithm to give a unified algorithm for recovering planted partitions and assignments in random hypergraphs and random k-SAT formulae respectively. Our results give the best known bounds for the clause density at which solutions can be found efficiently in these models as well as showing a barrier to further improvement via this reduction to the bipartite block model.