Global and Local Information in Clustering Labeled Block Models

Varun Kanade, Elchanan Mossel, Tselil Schramm

Abstract

This paper investigates the Labeled Stochastic Block Model (LSBM), where a vanishingly small fraction of node labels is revealed to a clustering algorithm. We demonstrate that while a tiny amount of information does not aid recovery in the two-cluster case below the standard Kesten-Stigum threshold, it significantly lowers the recovery barrier in the "many-cluster" regime. This allows simple local algorithms to succeed where global ones previously failed, effectively bridging the gap between local and global information in network science.

Introduction

In network science, the Stochastic Block Model (SBM) is the standard framework for studying community detection. It generates random graphs where nodes in the same community are more likely to be connected than nodes in different communities. A major focus in recent years has been the "sparse case," where the average degree of a node remains constant regardless of network size. In this regime, a fundamental phase transition exists: below the Kesten-Stigum bound, it is mathematically impossible to recover clusters better than random guessing.

However, real-world networks often include metadata—a few known labels, such as a handful of users on a social network who have listed their affiliations. This paper asks: Does a vanishingly small amount of node information (e.g., knowing the labels of 0.01% of nodes) change the fundamental limits of cluster recovery? Specifically, can simple "local" algorithms—which only examine a node's immediate neighborhood—now perform as well as complex "global" ones?

Methodology

The authors analyze the Labeled Stochastic Block Model, adding a parameter $p$ representing the probability that a node's true label is revealed. To study this, they employ Information Flow on Trees. Because sparse random graphs look like trees locally, clustering a node in a graph can be mapped to reconstructing the label of a root node in a Galton-Watson tree based on the labels of its leaves and randomly revealed internal nodes.

The paper introduces a simple local algorithm that propagates revealed labels from a neighborhood of radius $r$ back to a target node using "first common ancestor" logic. They also utilize Belief Propagation (BP) simulations to test conjectures regarding the limits of local versus global information.

Key Insights and Phase Transitions

Symmetry Breaking

In an unlabeled SBM, local algorithms cannot outperform random guessing because they lack a reference frame to distinguish between clusters. Revealing even a tiny fraction of labels breaks this symmetry, providing the local algorithm with a necessary "anchor."

The "Many Clusters" Advantage

The most striking finding is that if the number of clusters ($k$) is large, the threshold for recovery drops significantly. Even if edge information is too weak for standard algorithms, a tiny bit of node information allows local algorithms to "stitch together" the community structure.

Recovery probability as a function of signal strength for different cluster counts k. Plot (a) shows the continuous transition for k=2, while (b) and (c) show the discontinuous jumps and lowered thresholds in the many-cluster regime.

The Limit of Global Information

For the two-cluster case, the authors conjecture that once local node labels are available, the "global" structure of the entire graph provides no additional benefit over the local neighborhood. This suggests that in the presence of metadata, local algorithms may become optimal.

Key Results

  • Theorem 1 (The Power of Large $k$): If the number of clusters $k$ is large enough relative to the fraction of revealed labels, recovery is possible even below the conjectured algorithmic threshold for the unlabeled model.
  • Theorem 2 (The Limit of Small Info): For a fixed $k$, if the signal is below the "tree reconstruction threshold," a vanishingly small fraction of labels provides zero help for recovery. The phase transition remains a hard wall.
  • Proposition 3: In the two-cluster case, if the signal is strong enough, a local algorithm with minimal node info can achieve the same accuracy as the best possible global algorithm for the unlabeled problem.

Limitations and Future Work

The current model assumes revealed labels are 100% accurate; the "many-cluster" results do not yet easily extend to noisy label models. Additionally, while the $k=2$ and very large $k$ regimes are well-defined, the "middle ground" (e.g., $k=5$) remains complex. Proving the conjecture that global information becomes redundant in the presence of local labels remains a significant open challenge that would deeply link spatial processes on trees with graph clustering theory.

Summary updated

Abstract

The stochastic block model is a classical cluster-exhibiting random graph model that has been widely studied in statistics, physics and computer science. In its simplest form, the model is a random graph with two equal-sized clusters, with intra-cluster edge probability p, and inter-cluster edge probability q. We focus on the sparse case, i.e. p, q = O(1/n), which is practically more relevant and also mathematically more challenging. A conjecture of Decelle, Krzakala, Moore and Zdeborova, based on ideas from statistical physics, predicted a specific threshold for clustering. The negative direction of the conjecture was proved by Mossel, Neeman and Sly (2012), and more recently the positive direction was proven independently by Massoulie and Mossel, Neeman, and Sly. In many real network clustering problems, nodes contain information as well. We study the interplay between node and network information in clustering by studying a labeled block model, where in addition to the edge information, the true cluster labels of a small fraction of the nodes are revealed. In the case of two clusters, we show that below the threshold, a small amount of node information does not affect recovery. On the other hand, we show that for any small amount of information efficient local clustering is achievable as long as the number of clusters is sufficiently large (as a function of the amount of revealed information).
BibTeX
@article{kanade2016global,
  author = {Varun Kanade and Elchanan Mossel and Tselil Schramm},
  title = {{Global and Local Information in Clustering Labeled Block Models}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  url = {https://openreview.net/forum?id=NdZ1QCWE5Mm},
}
Figure