Bayesian Hierarchical Community Discovery

Charles Blundell, Yee Whye TehNeurIPS 2013 · OpenReview

Introduction

Most social networks are not just "flat" collections of groups; they are inherently hierarchical. For instance, a physicist belongs to a university, a physics department, and a specific research lab. Existing tools for finding these nested structures usually fall into two camps: greedy heuristics, which are fast but lack a formal probabilistic framework, and Bayesian Nonparametrics (like the Infinite Relational Model, or IRM), which are mathematically elegant but notoriously slow, often requiring thousands of MCMC iterations.

This paper introduces Bayesian Hierarchical Community Discovery (BHCD), a method that finds nested group structures in social networks with the speed of a greedy algorithm but the mathematical rigor of a Bayesian model. It achieves results comparable to or better than the gold-standard IRM while running two orders of magnitude faster, scaling quadratically with the number of nodes.

Methods: A Tree-Structured Mixture

The core of BHCD is a tree-structured mixture of stochastic blockmodels (SBMs). Instead of considering every computationally impossible way to partition a network, the authors restrict the search to partitions consistent with a tree. Each internal node in the tree represents a community, and the leaves are individual people (vertices).

Tree-structured mixture of stochastic blockmodels

Using a Beta-Bernoulli conjugate prior, the authors can "integrate out" the edge probabilities. This mathematical formulation results in a marginal likelihood that can be calculated recursively, bypassing the need for slow MCMC sampling.

Greedy Agglomerative Model Selection

To build this hierarchy, BHCD uses a greedy agglomerative algorithm. It starts with every person in their own "tree" and iteratively merges them based on a Bayes factor score derived from local connectivity.

Unlike standard clustering algorithms that only "join" two groups into a binary tree, BHCD considers three types of merges to allow for more flexible, non-binary hierarchies (often called "rose trees"):

  1. Join: Create a new parent node for two trees.
  2. Absorb A into B: Make tree A a child of a node in tree B.
  3. Absorb B into A: Make tree B a child of a node in tree A.
Join and Absorb merge operations

By caching "sufficient statistics" (counts of edges and non-edges), the algorithm can evaluate a potential merge in $O(1)$ time. The total complexity is $O(n^2 \log n)$, where $n$ is the number of vertices. The authors also introduced a "sparse" variant of BHCD that ignores pairs of communities with zero edges between them, significantly speeding up the process for real-world, sparse social networks.

Datasets and Evaluation

The authors evaluated BHCD on three primary datasets:

  1. Sampson’s Monastery Network: A classic small-scale dataset (18 monks) used to verify that the model captures known social factions.
  2. NIPS-234: A subset of the NIPS co-authorship network containing the 234 most connected researchers, used for quantitative benchmarking against the IRM.
  3. Full NIPS Dataset: A larger graph with 2,864 authors and 9,466 edges to demonstrate the algorithm's scalability on real-world data.

Key Results

  • Speed: BHCD is roughly 100x faster than a single iteration of the IRM. In the time it takes the IRM to perform one Gibbs sampling pass, BHCD has usually finished its entire run and produced a better model.
  • Predictive Accuracy: On the NIPS-234 dataset, BHCD achieved higher log-predictive probabilities and better Area Under the Curve (AUC) for link prediction than the standard IRM.
  • Qualitative Success: On the full NIPS dataset, BHCD successfully identified meaningful research clusters (e.g., a "Deep Learning/Vision" cluster featuring prominent researchers) within a massive, complex hierarchy.

Limitations and Future Work

While fast, the algorithm is still $O(n^2)$ in the worst case for dense graphs. The authors suggest that future work could improve this to $O(m)$ (where $m$ is the number of edges) for sparse networks.

Additionally, the current model uses a simple edge-counting likelihood. Incorporating more complex features, like the "sufficient statistics of triangles" (transitivity), could improve the discovery of tightly-knit cliques. Finally, while the model is nonparametric regarding the number of clusters, it still relies on hyperparameters that define what a "dense" vs. "sparse" community looks like. Automating the tuning of these parameters remains a suggested next step.

Summary updated

Abstract

We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms whose worst case scales quadratically in the number of vertices of the network, but independent of the number of communities. Our algorithms are two orders of magnitude faster than the infinite relational model, achieving comparable or better accuracy.
BibTeX
@inproceedings{blundell2013bayesian,
  author = {Charles Blundell and Yee Whye Teh},
  title = {{Bayesian Hierarchical Community Discovery}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=By4wsuWuZS},
}
Figure