Bipartite Stochastic Block Models with Tiny Clusters

Stefan NeumannNeurIPS 2018 · OpenReview

This paper tackles a long-standing limitation in graph clustering: the inability to find very small, "tiny" clusters in large bipartite datasets.

TL;DR

The author introduces pcv (Project, Cluster, Vote), a simple two-step algorithm that breaks the theoretical $\Omega(\sqrt{n})$ size barrier for finding clusters in bipartite graphs. By leveraging a smooth tradeoff between the sizes of clusters on both sides of the graph, the method can provably and practically recover clusters as small as $O(n^\epsilon)$, even in the presence of significant noise.

What Problem Does This Paper Address?

Bipartite graphs—which represent relationships between two distinct sets of entities, like customers and products or genes and biological samples—are ubiquitous. To model these, researchers use Bipartite Stochastic Block Models (SBMs).

The challenge lies in the "resolution limit." Previous algorithms typically required clusters to be at least as large as the square root of the number of vertices ($\sqrt{n}$). In a dataset with a million products, an algorithm that can only find clusters of 1,000 or more is often useless; real-world interest usually lies in much smaller, niche groups. This paper aims to bridge the gap between theoretical guarantees and the practical need to find these "tiny" clusters.

Methods

The author proposes a deceptively simple two-step algorithm called pcv:

  1. Project and Cluster: The algorithm first focuses on the "left" side of the graph (e.g., the customers). It projects the biadjacency matrix onto its first $k$ singular vectors (using SVD) and then runs $k$-means clustering. This step relies on the intuition that nodes in the same cluster should have similar neighborhoods.
  2. Vote (High-Degree Thresholding): Once the left-side clusters are identified, the algorithm "votes" to find the corresponding "right" side clusters (e.g., the products). A right-side node is added to a cluster if it has a significantly high number of connections to the previously identified left-side cluster, based on a calculated threshold $\theta$.

The core contribution is the theoretical analysis, which proves that this approach works for tiny clusters by demonstrating a "smooth tradeoff": if the clusters on one side are large and distinct, the clusters on the other side can be extremely small.

Datasets

The algorithm was evaluated using:

  • Synthetic Data: Randomly generated bipartite graphs where parameters like cluster size, noise levels ($p$ and $q$), and the number of clusters ($k$) were strictly controlled to test theoretical limits.
  • BookCrossing: A real-world dataset of users and book ratings. After preprocessing, it contained ~6,200 users and ~5,000 books.
  • 4News: A subset of the 20Newsgroups dataset, consisting of 400 posts and 800 words across four topics (cryptography, medicine, space, and Christianity).

Key Insights and Ideas

  • Breaking the $\sqrt{n}$ Barrier: The paper shows that the $\Omega(\sqrt{n})$ limit found in previous literature is not an absolute law for bipartite graphs. By considering the relationship between the two sides of the graph, we can bypass lower bounds that apply to general graphs.
  • The Smooth Tradeoff: The most important theoretical insight is that the difficulty of finding a cluster depends on the product of the cluster sizes on both sides. If your "customer" cluster is large, your "product" cluster can be tiny (and vice versa), and you can still recover both perfectly.
  • Heuristics vs. Theory: The paper provides a theoretical justification for why common heuristics—like applying $k$-means to singular vectors—actually work so well in practice for biclustering.

Key Results

  • Theoretical Recovery: The author proves that pcv can recover clusters of size $O(n^\epsilon)$ for any $\epsilon > 0$, provided the clusters on the opposite side are sufficiently large.
  • Superiority over Baselines: In synthetic tests, pcv outperformed popular Boolean Matrix Factorization (BMF) methods (like message and lfm) and spectral methods (like lim), especially when destructive noise was high.
Performance comparison of pcv against baselines across varying noise levels, cluster sizes, and dimensions.
  • Efficiency: As shown in the rightmost column of the figure above, pcv was consistently the fastest algorithm in the experiments, often finishing in seconds or minutes where other methods took significantly longer to converge.
  • Practical Performance: On the BookCrossing dataset, pcv successfully identified meaningful tiny clusters, such as specific groups of users interested only in the first three Harry Potter books or specific authors like John Grisham and Stephen King.

Limitations and Future Work

  • Parameter Sensitivity: The "Vote" step requires knowing (or estimating) the edge probabilities $p$ and $q$ to set the threshold $\theta$. While the author provides a heuristic for this, the algorithm's success is tied to the accuracy of these estimates.
  • Disjoint vs. Overlapping: The current theoretical framework assumes that clusters on the left side are disjoint. While the right side can overlap, many real-world datasets feature heavy overlaps on both sides, which may require further theoretical refinement.
  • Optimality Conjecture: The author conjectures that the tradeoff obtained between the sizes of the two sides is asymptotically optimal, but a formal lower-bound proof remains an open challenge for future research.

Summary updated

Abstract

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^\epsilon)$, where $n$ is the number of vertices in the graph and $\epsilon > 0$. Previous algorithms were only able to identify clusters of size $\Omega(\sqrt{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.
BibTeX
@inproceedings{neumann2018bipartite,
  author = {Stefan Neumann},
  title = {{Bipartite Stochastic Block Models with Tiny Clusters}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=ryV8NDbuZB},
}
Figure