Bipartite Stochastic Block Models with Tiny Clusters

We study the problem of finding planted clusters in bipartite graphs. We present a simple two-step algorithm which provably finds even tiny clusters of size O(n^e), where n is the number of vertices in the graph and e > 0. Previous algorithms were only able to identify clusters of size Ω( sqrt(n) ). We evaluated 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.