Source-linked AI summary
Graph Clustering with Graph Neural Networks
Anton Tsitsulin, John Palowitch, Bryan Perozzi, Emmanuel Müller
TL;DR
The paper asks why GNN pooling methods often fail at unsupervised graph clustering despite effective simple baselines. It introduces DMoN, an end-to-end differentiable modularity-based pooling objective, and reports stronger clustering quality and ground-truth alignment than competing pooling methods.
Problem
Existing GNN pooling methods often fail to recover cluster structure, while unsupervised graph clustering remains insufficiently addressed despite its practical uses.
Method
DMoN bridges graph pooling and fully unsupervised clustering by optimizing modularity-inspired soft cluster assignments with an end-to-end differentiable GNN objective.
Results
DMoN better leverages graph structure and attributes than existing methods, producing clusters more likely to match ground-truth labels and with better conductance or modularity.
Takeaways & Limitations
DMoN provides a high-quality unsupervised pooling approach for attributed graph clustering across synthetic and real-world evaluations.
Takeaways & Limitations
MinCutPool’s orthogonality constraint can dominate its clustering term and trap optimization in local minima.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) have achieved state-of-the-art results on many graph analysis tasks such as node classification and link prediction. However, important unsupervised problems on graphs, such as graph clustering, have proved more resistant to advances in GNNs. Graph clustering has the same overall goal as node pooling in GNNs - does this mean that GNN pooling methods do a good job at clustering graphs? Surprisingly, the answer is no - current GNN pooling methods often fail to recover the cluster structure in cases where simple baselines, such as k-means applied on learned representations, work well. We investigate further by carefully designing a set of experiments to study different signal-to-noise scenarios both in graph structure and attribute data. To address these methods' poor performance in clustering, we introduce Deep Modularity Networks (DMoN), an unsupervised pooling method inspired by the modularity measure of clustering quality, and show how it tackles recovery of the challenging clustering structure of real-world graphs. Similarly, on real-world data, we show that DMoN produces high quality clusters which correlate strongly with ground truth labels, achieving state-of-the-art results with over 40% improvement over other pooling methods across different metrics.
1 Introduction
The paper frames unsupervised graph clustering as an important but underaddressed GNN problem, then introduces DMoN and evaluates pooling methods across synthetic and real-world settings.
- Unsupervised graph clustering remains underexplored despite applications in data exploration, visualization, genomic discovery, and anomaly detection.
- Existing unsupervised structure-aware methods can require multi-step optimization that prevents an end-to-end differentiable objective.
- DMoN is an unsupervised GNN clustering module that optimizes cluster assignments end-to-end differentiably.
- The study uses synthetic graphs to expose weaknesses in existing methods and evaluate DMoN across signal regimes.
- Real-world experiments show that many pooling methods poorly reflect hierarchical structure and fail to jointly use graph structure and node attributes.
2 Related Work
Related work spans GNN representation learning, graph pooling, and embedding methods, but existing approaches differ substantially in their suitability for unsupervised attributed graph clustering.
- GNNs support end-to-end differentiable losses on arbitrary graph structures and have been applied across social, recommender, and molecular graphs.
- Most GNN work uses semi-supervised node classification, while unsupervised methods often learn representations through mutual-information objectives.
- Graph pooling hierarchically coarsens graphs, but clustering-oriented evaluation requires properties including end-to-end training, unsupervised learning, node aggregation, sparsity, soft assignments, and stability.
- Several methods cannot scale to large graphs because their computational complexity is at least quadratic, whereas DMoN maintains subquadratic scalability without subsampling information.
- Graph embeddings can be viewed as restricted unsupervised GNNs using identity features, giving nodes positional representations.
3 Preliminaries
The preliminaries formulate attributed graph clustering, review differentiable cut and modularity objectives, and motivate spectral modularity as a scalable structure-based foundation for DMoN.
- Graph clustering formulation: The task partitions graph nodes into k clusters using adjacency structure together with node attributes X ∈ R^n×s.
- Clustering objectives: Classical clustering objectives are discrete, so differentiable methods rely on spectral approximations and must address shortcomings of cut-based and modularity criteria.
- Cut-based metrics: Plain graph cuts can produce unbalanced partitions, motivating ratio-cut and normalized-cut variants.
- Cut-based metrics: Real-network ground-truth communities may lack good cuts because nodes can participate in multiple clusters, such as family and work communities.
- Cut-based metrics: MinCutPool adapts normalized cut for pooling, but experiments show it does not optimize its own objective function.
- Modularity: Modularity compares within-cluster edges with expectations under a degree-preserving random-graph null model.
- Modularity: Positive modularity does not necessarily imply strong clustering structure, and modularity values are directly comparable only across graphs sharing the same degree distribution.
- Spectral modularity maximization: Relaxing discrete assignments makes the modularity maximizer the top-k eigenvectors of the modularity matrix B.
4 Method
DMoN performs attributed graph clustering by producing differentiable soft assignments with a GNN and optimizing modularity alongside collapse regularization. Its relaxed constraint avoids trivial clusters while theoretical results show consistency under a degree-corrected stochastic block model.
- 4.1 DMoN: Deep Modularity Networks: Its objective combines a modularity term based on a null model with collapse regularization to prevent trivial solutions.The modularity computation uses sparse matrix operations and degree normalization for efficient optimization on sparse graphs.
- 4.1 DMoN: Deep Modularity Networks: DMoN uses a GNN and softmax output to encode differentiable soft cluster assignments for each node.The assignment input can be any differentiable message-passing function; the paper specifically uses a graph convolutional network on a normalized adjacency matrix.
- 4.2 Collapse regularization: MinCutPool’s orthogonality constraint can dominate its clustering term and trap optimization in local minima, worsening graph clustering performance.On Cora, the soft orthogonality term becomes dominant after 200 epochs; a constraint-only variant performs better downstream but worse on graph metrics across most datasets.
- 4.2 Collapse regularization: Collapse regularization is a relaxed constraint that prevents the trivial partition without dominating optimization of the main objective.The regularizer is based on normalized soft cluster membership counts, reaching 0 for perfectly balanced clusters and its maximum when all clusters collapse into one.
- 4.3 Theoretical insights: The theoretical results show that collapse regularization avoids trivial clusters without preventing asymptotically consistent prediction of optimal class labels.The first theorem establishes a lower objective score than trivial clustering for any clustering solution with positive modularity.
- 4.3 Theoretical insights: Under equal cluster sizes in a degree-corrected stochastic block model, LDMoN is strongly consistent when λn/log(n) →∞ and weakly consistent when λn →∞.The analysis assumes node label/degree pairs drawn from a fixed discrete distribution and scales the edge probabilities by ρn = λn/n.
5 Experiments
The experiments evaluate DMoN and baseline methods on synthetic and real-world attributed graphs using graph-clustering and label-correlation metrics. DMoN consistently handles varied graph and feature signals, outperforming other neural pooling methods and scaling better on large graphs.
- Synthetic experiments: DMoN overwhelmingly outperforms neural pooling baselines across six synthetic scenarios, while DiffPool and MinCutPool are sensitive to graph density, degree homogeneity, and feature noise.MinCutPool is affected by weak graph or feature noise and by nested or grouped features; DMoN and DiffPool are less sensitive to these variations.
- Synthetic experiments: DMoN combines graph and attribute signals, maintaining strong clustering when either graph structure is near-random or features provide the stronger signal.Across synthetic scenarios, it outperforms stochastic block-model minimization and avoids the limitations of using only features or graph structure.
- Real-world experiments: DMoN achieves better clustering than neural counterparts on every real-world dataset and metric except two NMI comparisons against DGI+k-means on Cora and Citeseer.It remains within 3% of SBM in modularity while also clustering features, and exceeds SBM modularity on Citeseer and Pubmed.
- Real-world experiments: DMoN improves conductance, modularity, and NMI by over 40% on average relative to other pooling methods.It also beats MinCutPool in conductance on all datasets, while DiffPool is hindered by quadratic reconstruction and MinCutPool fails to converge on Amazon PC and Amazon Photo.
- Scalability: On large-scale datasets, DMoN performs 16% better on average across all metrics than other end-to-end learning methods, while several baselines cannot scale because of quadratic complexity.The experiments also report best-in-class scalability without subsampling away information.
6 Conclusion
The paper frames GNN pooling as attributed graph clustering and introduces DMoN as an unsupervised objective implemented with a GNN. Across synthetic and real-world experiments, DMoN better leverages graph structure and attributes, producing clusters that align more closely with ground-truth labels and score better on clustering metrics.
- DMoN applies an unsupervised objective to GNN-based attributed graph clustering and is compared with structure-, feature-, joint-information, and pooling baselines.The baselines include SBM, k-means, DGI+k-means, and MinCutPool.
- On synthetic graphs, DMoN better leverages both graph structure and node attributes than existing methods.
- On real-world datasets, DMoN clusters are more likely to correspond to ground-truth labels and have better conductance or modularity.