Recovering communities in the general stochastic block model without knowing the parameters

Emmanuel Abbe, Colin Sandon

Abstract

Community detection in networks is often modeled using the Stochastic Block Model (SBM). While theoretical thresholds for community recovery are well-established, most optimal algorithms require prior knowledge of model parameters, such as the number of communities and their connectivity probabilities. This paper presents the first "agnostic" algorithms capable of achieving information-theoretic optimal limits for both partial and exact recovery without such prior information. These algorithms operate in quasi-linear time, making them suitable for large-scale network analysis.

Introduction

The Stochastic Block Model (SBM) serves as a fundamental benchmark for community detection. In an SBM, nodes are assigned to one of $k$ communities, and the probability of an edge existing between two nodes is determined by their respective community memberships. Despite the model's popularity, a significant gap exists between theory and practice: most algorithms that achieve the sharp "phase transitions" for recovery require the connectivity matrix $W$ and the number of clusters $k$ to be known a priori. In real-world applications, these parameters are rarely available, necessitating a "fully agnostic" approach where the algorithm relies solely on the observed graph structure.

The Challenge of Agnostic Recovery

The difficulty in agnostic recovery lies in the interdependence of parameter estimation and community assignment. Traditional methods often treat these as separate steps, but errors in estimating $W$ or $k$ can propagate, leading to sub-optimal recovery. The authors address this by developing frameworks that learn the underlying structure of the graph—specifically the eigenvalues of the connectivity matrix—on the fly. This allows the algorithm to adapt to the specific characteristics of the network without external guidance.

Agnostic Algorithmic Frameworks

The paper introduces two primary algorithmic frameworks tailored to different recovery regimes:

1. Agnostic-Sphere-Comparison for Partial Recovery

Partial recovery involves detecting community structures better than random chance. The Agnostic-sphere-comparison algorithm achieves this by analyzing the "spheres" (neighborhoods) around individual vertices. The growth rate of these neighborhoods at distance $r$ is intrinsically linked to the eigenvalues of the connectivity matrix. By comparing these growth patterns across nodes, the algorithm can group similar nodes and estimate model parameters simultaneously.

2. Agnostic-Degree-Profiling for Exact Recovery

Exact recovery requires the correct labeling of every node in the graph. The authors propose a two-stage "classify and clean" approach:

  • Initial Clustering: A variation of the sphere-comparison method is applied to a sparsified version of the graph to generate a preliminary community structure.
  • Refinement: The algorithm uses the remaining edges to refine these labels. By examining a node's "degree profile"—the number of neighbors it has within each suspected community—the algorithm reassigns nodes to the most likely group.

A critical innovation here is the use of graph sparsification. By splitting the edges into two disjoint sets, the authors prevent "overfitting," ensuring that the edges used to refine a node's membership are independent of the edges used to define the initial community boundaries.

Performance and Theoretical Limits

The proposed algorithms are not only computationally efficient, running in quasi-linear time ($O(n^{1+\epsilon})$), but also reach the Chernoff-Hellinger (CH) limit. The CH-limit represents the fundamental information-theoretic barrier for exact recovery. The authors prove that their agnostic approach achieves this limit, matching the performance of the best possible algorithms that have full access to model parameters. This demonstrates that there is no "price to pay" for not knowing the parameters in the logarithmic degree regime.

Empirical Validation

The framework was validated using both synthetic and real-world datasets:

  • Synthetic SBMs: The algorithms were tested across various regimes, including constant, diverging, and logarithmic degrees, confirming the theoretical recovery thresholds.
  • Political Blogosphere: Using a dataset of 1,222 political blogs from the 2004 US election, a simplified version of the agnostic algorithm achieved high accuracy, resulting in only 56 to 67 errors. This performance is competitive with state-of-the-art spectral and regularized methods, despite the algorithm having no prior knowledge of the two-community (liberal vs. conservative) structure.

Conclusion and Future Work

This work bridges the gap between theoretical optimality and practical applicability in community detection. By demonstrating that parameters can be learned implicitly during the recovery process, the authors provide a robust framework for analyzing complex networks where underlying model parameters are unknown.

While the current proofs assume linear community sizes and a fixed number of clusters $k$, future research may extend these agnostic techniques to more complex variations. These include Degree-Corrected SBMs, which account for "hub" nodes, or models featuring overlapping communities and labeled edges.

Summary updated

BibTeX
@inproceedings{abbe2015recovering,
  author = {Emmanuel Abbe and Colin Sandon},
  title = {{Recovering communities in the general stochastic block model without knowing the parameters}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HyZi7DWOWr},
}
Figure