Attentive Clustering Processes

Ari Pakman, Yueqi Wang, Yoonho Lee, Pallab Basu, Juho Lee, Yee Whye Teh, Liam Paninski

Abstract

Learning community structures in graphs has broad applications across scientific domains. While graph neural networks (GNNs) have been successful in encoding graph structures, existing GNN-based methods for community detection are limited by requiring knowledge of the number of communities in advance, in addition to lacking a proper probabilistic formulation to handle uncertainty. We propose a simple framework for amortized community detection, which addresses both of these issues by combining the expressive power of GNNs with recent methods for amortized clustering. Our models consist of a graph representation backbone that extracts structural information and an amortized clustering network that naturally handles variable numbers of clusters. Both components combine into well-defined models of the posterior distribution of graph communities and are jointly optimized given labeled graphs. At inference time, the models yield parallel samples from the posterior of community labels, quantifying uncertainty in a principled way. We evaluate several models from our framework on synthetic and real datasets and demonstrate superior performance to previous methods. As a separate contribution, we extend recent amortized probabilistic clustering architectures by adding attention modules, which yield further improvements on community detection tasks.

Introduction

Community detection—identifying groups of densely connected nodes—is a cornerstone of network analysis, used in applications ranging from social media mapping to protein interaction studies. However, current deep learning approaches face three major hurdles: the requirement to specify the number of communities ($K$) beforehand, a lack of principled uncertainty estimation, and the computational inefficiency of iterative unsupervised models.

This research addresses these challenges by framing community detection as a problem of amortized probabilistic inference. By combining Graph Neural Networks (GNNs) with amortized clustering, the proposed framework naturally handles variable numbers of clusters and provides rapid, parallelized inference with built-in uncertainty quantification.

Methodology

The proposed framework follows a two-stage pipeline designed to translate raw graph data into probabilistic community assignments.

The high-level framework for amortized community detection, showing the flow from input graph to final clusters via a GNN encoder and clustering module.

1. The Graph Backbone

A GNN (such as GatedGCN or GraphSAGE) acts as an encoder. It processes the graph structure and node features (e.g., Laplacian eigenvectors) to produce compact node embeddings that capture both local and global topology.

2. The Amortized Clustering Module

These embeddings are fed into a clustering model that treats community assignment as a sequence of probabilistic decisions. The paper evaluates several variants:

  • Neural Clustering Process (NCP): Assigns nodes to clusters sequentially.
  • Clusterwise Clustering Process (CCP): Forms clusters by selecting an "anchor" node and iteratively deciding which other nodes should join its community.
  • Deep Amortized Clustering (DAC): A non-probabilistic baseline.

The "Secret Sauce": Attention Modules

A key contribution of this work is the enhancement of these models using Set Transformers. By replacing standard mean-pooling with multi-head attention modules—specifically Induced Set Attention Blocks (ISAB), Multihead Attention Blocks (MAB), and Pooling by Multihead Attention (PMA)—the model can better capture complex, permutation-invariant dependencies between nodes within a community.

Comparison of the standard CCP architecture and the proposed CCP-Attn, highlighting the integration of attention modules (ISAB, MAB, PMA) to improve community representation.

Experimental Evaluation

The framework was rigorously tested on both synthetic and real-world datasets:

  • Stochastic Block Models (SBM): Synthetic benchmarks with known ground truths, containing between 1 and 16 communities.
  • SNAP Datasets (DBLP and YouTube): Real-world social and collaboration networks where the models' ability to generalize to messy, large-scale structures was evaluated.
  • Log-Degree SBM: A regime used to test performance against the theoretical "recovery threshold" where communities become mathematically distinguishable from noise.

Key Results and Insights

Superior Accuracy and Calibration

The GCN-CCP-Attn model consistently outperformed existing methods. On the DBLP dataset ($K=3$), it achieved an Adjusted Mutual Information (AMI) of 89.2, significantly higher than the 52.8 achieved by DMoN. Furthermore, CCP-based models demonstrated lower Expected Calibration Error (ECE), indicating that the model's predicted confidence closely aligns with its actual accuracy.

Efficiency and Scalability

By using exchangeable clustering priors, the framework is naturally invariant to label permutations, avoiding the combinatorial explosion ($O(K!)$) that plagues standard supervised node classification. Once trained, inference is a simple forward pass, making these models over 10x faster than state-of-the-art unsupervised models like DMoN.

Principled Uncertainty

Because the model outputs a posterior distribution, researchers can draw multiple samples to visualize ambiguity. If samples vary significantly, it indicates a high degree of uncertainty in the community structure—a vital feature for high-stakes applications like biological research.

Conclusion and Future Work

While the framework demonstrates significant advances in speed and accuracy, it currently relies on labeled data for training. Future research will explore extending this to fully unsupervised or semi-supervised regimes. Additionally, while the current model assumes disjoint communities, many real-world networks feature overlapping groups, representing a promising avenue for further development in amortized probabilistic inference.

Summary updated

Abstract

Learning community structures in graphs has broad applications across scientific domains. While graph neural networks (GNNs) have been successful in encoding graph structures, existing GNN-based methods for community detection are limited by requiring knowledge of the number of communities in advance, in addition to lacking a proper probabilistic formulation to handle uncertainty. We propose a simple framework for amortized community detection, which addresses both of these issues by combining the expressive power of GNNs with recent methods for amortized clustering. Our models consist of a graph representation backbone that extracts structural information and an amortized clustering network that naturally handles variable numbers of clusters. Both components combine into well-defined models of the posterior distribution of graph communities and are jointly optimized given labeled graphs. At inference time, the models yield parallel samples from the posterior of community labels, quantifying uncertainty in a principled way. We evaluate several models from our framework on synthetic and real datasets and demonstrate superior performance to previous methods. As a separate contribution, we extend recent amortized probabilistic clustering architectures by adding attention modules, which yield further improvements on community detection tasks.
BibTeX
@inproceedings{pakman2020attentive,
  author = {Ari Pakman and Yueqi Wang and Yoonho Lee and Pallab Basu and Juho Lee and Yee Whye Teh and Liam Paninski},
  title = {{Attentive Clustering Processes}},
  booktitle = {SPIGM @ ICML},
  year = {2020},
  doi = {10.48550/arxiv.2010.15727},
}
Figure