Bipartite Stochastic Block Models with Tiny Clusters
We study the problem of finding clusters in random bipartite graphs. We present a simple two-step algorithm which provably finds even tiny clusters of size O(n ε ), where n is the number of vertices in the graph and ε > 0. Previous algorithms were only able to identify clusters of size Ω( √ n). We evaluate the algorithm on synthetic and on real-world data; the experiments show that the algorithm can find extremely small clusters even in presence of high destructive noise.
This paper introduces and analyzes a simple algorithm for bipartite block model clustering in which clusters can be very small.  The model in which the work is situated is a natural variation of a blockmodel for bipartite random graphs which allows the clusters on the "right" to overlap. The model involves a bijection between the clusters on the left and the clusters on the right. Two probabilities must be specified: the probability that an edge exists between two nodes whose blocks are in bijection, and the probability that an edge is generated between two nodes whose blocks are not in bijection (though it is likely that this constraint can be relaxed).  The algorithm is simple: first, cluster the nodes on the left by applying a mixture model approach to the rows of the biadjacency matrix. Next, having determined the clusters on the left, assign to each the nodes on the right which have sufficiently many edges to it. To analyze the first part of the algorithm, the authors make use of the results of Mitra concerning mixture models.  The authors prove that -- quite interestingly -- the algorithm is able to recover right clusters which are O(n^eps) small, which represents a significant improvement over previous analyses. This is perhaps surprising due to previous analyses which proved a sqrt(n) lower bound on cluster size, however (as the authors note) those analyses assumed that the bipartite clusters were square. In contrast, the current paper allows the left cluster and right cluster to be of vastly different sizes. This relaxation is quite natural and provides for a smooth tradeoff -- very small right clusters can be recovered, provided that the left cluster is correspondingly large.  Ultimately, I found the paper clear and interesting. The fact that such small clusters can be recovered is intriguing, though it would be interesting to investigate whether the smooth tradeoff mentioned is indeed optimal.