Spectral Thresholds in the Bipartite Stochastic Block Model
From MaRDI portal
Abstract: We consider a bipartite stochastic block model on vertex sets and , with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set. When , 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 -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.
This page was built for publication: Spectral Thresholds in the Bipartite Stochastic Block Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6262917)
