Graph Clustering with Graph Neural Networks
Anton Tsitsulin, John Palowitch, Bryan Perozzi, Emmanuel Müller; 24(127):1−21, 2023.
Abstract
Graph Neural Networks (GNNs) have achieved state-of-the-art results in various graph analysis tasks, such as node classification and link prediction. However, GNNs have faced challenges in solving unsupervised problems on graphs, particularly graph clustering. While GNN pooling methods have been successful in node pooling, they do not perform well in clustering graphs. This raises the question of whether GNN pooling methods are effective in clustering graphs. Surprisingly, the answer is no. Current GNN pooling methods often fail to recover the cluster structure, while simple baselines like k-means applied on learned representations work well. To investigate this further, we conducted a series of experiments to analyze different signal-to-noise scenarios in both graph structure and attribute data. To address the poor performance of existing methods in graph clustering, we propose Deep Modularity Networks (DMoN), an unsupervised pooling method inspired by the modularity measure of clustering quality. We demonstrate how DMoN effectively recovers the challenging clustering structure of real-world graphs. Additionally, we show that DMoN produces high-quality clusters on real-world data, which strongly correlate with ground truth labels. DMoN achieves state-of-the-art results, outperforming other pooling methods by over 40% across different metrics.
[abs]