Provable Estimation of the Number of Blocks in Block Models

Bowei Yan, Purnamrita Sarkar, Xiuyuan ChengAISTATS 2018 · OpenReview

Abstract

Community detection is a fundamental unsupervised learning problem for unlabeled networks with broad applications. Most existing algorithms require the number of clusters ($r$) as a pre-set input, which is rarely known in real-world scenarios. This paper introduces SPUR, a semi-definite programming (SDP) approach that simultaneously estimates $r$ and recovers community memberships. We provide theoretical guarantees for exact recovery under "weak assortativity," a more realistic condition than the standard strong assortativity.

Introduction

In network analysis, community detection aims to group nodes based on their connectivity patterns. While spectral clustering and other state-of-the-art methods perform well when the number of communities $r$ is known, their performance drops significantly if $r$ is misspecified. Existing methods to estimate $r$ often involve complex two-stage processes or difficult-to-tune penalty terms that require prior knowledge of model parameters.

The SPUR Method

The researchers propose a convex relaxation approach formulated as a semi-definite program: $$\max \text{trace}(AX) - \lambda \text{trace}(X)$$ subject to $X \succeq 0, X \geq 0, X\mathbf{1} = \mathbf{1}$.

In this formulation, the term $\text{trace}(AX)$ encourages the solution to fit the observed adjacency matrix $A$, while $\lambda \text{trace}(X)$ acts as a penalty on the number of clusters. Since the trace of a normalized clustering matrix corresponds to the number of clusters, varying $\lambda$ allows the model to explore different granularities of community structure.

Hierarchical community discovery as the penalty parameter $\lambda$ varies. Higher $\lambda$ values (c) result in coarser clusters, while lower values (e) reveal finer sub-communities.

To automate the selection of $\lambda$, the SPUR algorithm performs a grid search and selects the value that maximizes the "low-rankness" of the solution $X$, specifically by looking at the proportion of leading eigenvalues. This data-driven approach removes the need for manual tuning or prior knowledge of $r$.

Key Insights: Weak Assortativity and Hierarchy

A significant contribution of this work is the proof of exact recovery under weak assortativity. Unlike strong assortativity, which requires nodes to be more connected to their own group than to the rest of the network combined, weak assortativity only requires a node to be more connected to its own group than to any other single group. This is a much more common characteristic of real-world networks.

Furthermore, the method naturally handles hierarchical structures. As shown in the figures, a large $\lambda$ might identify broad "meta-clusters," whereas decreasing $\lambda$ progressively reveals finer sub-communities. This multi-resolution property allows for a more nuanced understanding of network topology.

Experimental Results

The authors validated SPUR on both synthetic Stochastic Block Models (SBM) and real-world benchmarks:

  • Synthetic Data: SPUR demonstrated superior robustness in estimating $r$ as the number of clusters increased, outperforming methods like USVT and the Bethe-Hessian.
  • Real-World Networks:
    • College Football: SPUR estimated 13 clusters (ground truth is 12 conferences), whereas spectral methods estimated only 10.
  • Karate Club & Political Books: The algorithm achieved exact recovery of the ground truth clusters.

Conclusion and Future Work

SPUR provides a theoretically grounded and practically effective way to perform community detection without pre-specifying the number of clusters. While the computational cost of SDP is higher than spectral methods, the simultaneous estimation of $r$ and memberships offers a significant advantage in accuracy and interpretability. Future work may focus on improving the scalability for massive networks and providing a formal theoretical framework for the observed multi-resolution properties.

Summary updated

Abstract

Community detection is a fundamental unsupervised learning problem for unlabeled networks which has a broad range of applications. Many community detection algorithms assume that the number of clus...
BibTeX
@inproceedings{yan2018provable,
  author = {Bowei Yan and Purnamrita Sarkar and Xiuyuan Cheng},
  title = {{Provable Estimation of the Number of Blocks in Block Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=-HrYHh_ANRd},
}
Figure