Spectral thresholds in the bipartite stochastic block model

Laura Florescu, Will Perkins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)
56 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationCOLT 2016 Proceedings
PublisherJMLR
Volume49
Publication statusPublished - 2016
EventConference on Learning Theory 2016 - New York, United States
Duration: 23 Jun 201626 Jun 2016

Publication series

NameThe JMLR: Workshop and Conference Proceedings series
Volume49
ISSN (Electronic)1938-7228

Conference

ConferenceConference on Learning Theory 2016
Country/TerritoryUnited States
Period23/06/1626/06/16

Fingerprint

Dive into the research topics of 'Spectral thresholds in the bipartite stochastic block model'. Together they form a unique fingerprint.

Cite this