Optimal Sampling and Clustering in the Stochastic Block Model

Se-Young Yun, Alexandre ProutièreNeurIPS 2019 · OpenReview

Overview

This paper introduces a novel approach to finding hidden communities (clusters) within a network by intelligently choosing which connections to "test" or sample, rather than relying on a pre-existing, static graph. The authors derive the fundamental mathematical limit for the misclassification rate and present the Adaptive Spectral Partition (ASP) algorithm. This algorithm achieves the theoretical limit by learning and subsequently applying an optimal sampling strategy.

The Challenge: Active Learning in Networks

In the classic Stochastic Block Model (SBM), a graph is provided where nodes belong to hidden groups, and the probability of an edge existing depends entirely on these group memberships. Traditionally, researchers attempt to recover these groups from a single, static observation of the graph.

However, in many practical fields—such as biology, where testing protein-protein interactions is expensive and time-consuming—gathering data is a bottleneck. This paper shifts the focus to active learning: given a limited budget of $T$ samples, which pairs of nodes should be tested to identify the clusters most accurately? The primary challenge is that neither the cluster memberships nor the connection probabilities are known beforehand, requiring the algorithm to learn them on the fly to inform future sampling decisions.

The Adaptive Spectral Partition (ASP) Algorithm

To solve this, the authors propose a three-stage approach:

  1. Initial Exploration: The algorithm uses a small fraction of the sampling budget to sample edges uniformly at random. It then applies standard spectral clustering to generate a "rough draft" of the clusters.
  2. Parameter Estimation: Using this initial clustering, the algorithm estimates the underlying SBM parameters, specifically the relative sizes of the clusters ($\alpha$) and the connection probabilities ($p_{ij}$).
  3. Optimal Exploitation: The algorithm solves an optimization problem to determine the optimal sampling strategy ($x^*$). This strategy dictates exactly how many samples to allocate to pairs of nodes between different clusters to maximize the "divergence" (a measure of cluster distinguishability). The remaining budget is spent following this targeted strategy to refine the final cluster assignments.

The core theoretical contribution is the derivation of a necessary and sufficient condition for "exact recovery" (misclassifying a vanishingly small number of nodes), expressed through an information-theoretic divergence metric $D(p, \alpha)$.

Theoretical Insights

  • Budget-Independent Strategy: Surprisingly, the optimal distribution of samples between clusters depends only on the SBM parameters (the "shape" of the problem) and not on the total sampling budget.
  • Enlarging the Feasible Region: There are specific SBM configurations where recovering clusters from a static graph via random sampling is mathematically impossible. The authors prove that adaptive sampling successfully recovers clusters in these previously "impossible" regions.
  • Information-Theoretic Tightness: The ASP algorithm is proven to be optimal; it exactly matches the theoretical upper bound of the recovery rate, meaning no other algorithm can achieve a better asymptotic performance.

Key Results & Performance

The paper evaluates its findings using synthetic datasets generated according to a binary symmetric SBM ($K=2$ clusters) with $n=20,000$ nodes. By varying the sampling budget $T$ and the edge probabilities (parametrized by $a$ and $b$), the authors compared their adaptive method against traditional random sampling.

Theoretical Limit: For any $s = o(n)$ (a vanishing fraction of nodes), a joint adaptive algorithm can misclassify fewer than $s$ nodes if and only if: $$ \lim \inf_{n \to \infty} \frac{2T D(p, \alpha)}{n \log(n/s)} \geq 1 $$

Phase diagram of recovery feasibility and error rate comparison between adaptive and random sampling.

Empirical Gains: As illustrated in the figure above, the phase diagram (left) shows that the region of parameters $(a, b)$ where exact recovery is feasible is significantly larger for adaptive sampling compared to non-adaptive sampling. Furthermore, the error rate comparison (right) demonstrates that the ASP algorithm (blue) achieves near-zero error rates with a budget of roughly 450,000 samples. In contrast, the optimal non-adaptive algorithm (red) still exhibits significant errors even with 650,000 samples.

Limitations and Future Directions

  • SBM Assumptions: The theoretical guarantees rely heavily on the network strictly following the Stochastic Block Model. Real-world networks frequently exhibit more complex behaviors, such as overlapping communities or degree-corrected structures. It remains unclear how well this specific optimal strategy translates to those broader models.
  • Initial Phase Sensitivity: The ASP algorithm requires the initial random sampling phase to be successful enough for spectral clustering to provide a viable starting point. If the graph is extremely sparse or noisy, this first step might fail, causing the subsequent parameter estimation and exploitation phases to collapse.
  • Future Work: The authors suggest investigating more complex online optimization problems, such as scenarios where the graph structure evolves over time or where sampling costs vary significantly between different types of nodes.

Summary updated

Abstract

This paper investigates the design of joint adaptive sampling and clustering algorithms in networks whose structure follows the celebrated Stochastic Block Model (SBM). To extract hidden clusters, the interaction between edges (pairs of nodes) may be sampled sequentially, in an adaptive manner. After gathering samples, the learner returns cluster estimates. We derive information-theoretical upper bounds on the cluster recovery rate. These bounds actually reveal the optimal sequential edge sampling strategy, and interestingly, the latter does not depend on the sampling budget, but on the parameters of the SBM only. We devise a joint sampling and clustering algorithm matching the recovery rate upper bounds. The algorithm initially uses a fraction of the sampling budget to estimate the SBM parameters, and to learn the optimal sampling strategy. This strategy then guides the remaining sampling process, which confers the optimality of the algorithm. We show both analytically and numerically that adaptive edge sampling yields important improvements over random sampling (traditionally used in the SBM analysis). For example, we prove that adaptive sampling significantly enlarges the region of the SBM parameters where asymptotically exact cluster recovery is feasible.
BibTeX
@inproceedings{yun2019optimal,
  author = {Se-Young Yun and Alexandre Proutière},
  title = {{Optimal Sampling and Clustering in the Stochastic Block Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=tJHx8shS5a},
}
Figure