Bipartite Stochastic Block Model

The bipartite stochastic block model is a generative model for random bipartite graphs with planted community structure, where rows and columns represent distinct sets of nodes (such as users and items, or genes and diseases) and the edge probabilities depend on the hidden community memberships of each node. The model generalizes the standard stochastic block model to asymmetric domains and serves as a theoretical framework for understanding matrix completion, recommendation systems, and biclustering. Under certain parameter regimes, the problem of recovering the planted communities in the bipartite stochastic block model is equivalent to sparse PCA, revealing that the statistical-computational gap is not unique to covariance estimation but arises across a broad class of structured inference problems.

The bipartite stochastic block model is not merely a generalization of a well-studied random graph model. It is a Rosetta stone: problems that appear distinct — sparse PCA, biclustering, matrix completion — reduce to the same structural question about how much signal is needed before communities become algorithmically recoverable.