Spectral thresholds in the bipartite stochastic block model

We consider a bipartite stochastic block model on vertex sets V1V1 and V2V2, with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set.

When |V2|≫|V1||V2|≫|V1|, multiple thresholds emerge. We first locate a sharp threshold for detection of the partition, in the sense of the results of Mossel, Neeman and Sly and Massoulie 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 Feldman, Perkins, Vempala to give a unified algorithm for recovering planted partitions and assignments in random hypergraphs and random kk-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.