Spectral Thresholds in the Bipartite Stochastic Block Model

Abstract

We consider a bipartite stochastic block model on vertex sets $V_1$ and $V_2$, with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set. When $|V_2|\gg |V_1|$, multiple thresholds emerge. We first locate a sharp threshold for detection of the partition, in the sense of the results of \cite{mossel2012stochastic,mossel2013proof} and \cite{massoulie2014community} 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 \cite{feldman2014algorithm} 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.

updated version, will appear in COLT 2016

References in corpus (3)

• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Submatrix localization via message passing
• Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's

Cited by in corpus (4)

• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels