Scalable Deep Graph Clustering with Random-walk based Self-supervised Learning

Abstract

Web-based interactions can be frequently represented by an attributed graph, and node clustering in such graphs has received much attention lately. Multiple efforts have successfully applied Graph Convolutional Networks (GCN), though with some limits on accuracy as GCNs have been shown to suffer from over-smoothing issues. Though other methods (particularly those based on Laplacian Smoothing) have reported better accuracy, a fundamental limitation of all the work is a lack of scalability. This paper addresses this open problem by relating the Laplacian smoothing to the Generalized PageRank and applying a random-walk based algorithm as a scalable graph filter. This forms the basis for our scalable deep clustering algorithm, RwSL, where through a self-supervised mini-batch training mechanism, we simultaneously optimize a deep neural network for sample-cluster assignment distribution and an autoencoder for a clustering-oriented embedding. Using 6 real-world datasets and 6 clustering metrics, we show that RwSL achieved improved results over several recent baselines. Most notably, we show that RwSL, unlike all other deep clustering frameworks, can continue to scale beyond graphs with more than one million nodes, i.e., handle web-scale. We also demonstrate how RwSL could perform node clustering on a graph with 1.8 billion edges using only a single GPU.

References in corpus (11)

• Modularity and community structure in networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Pitfalls of Graph Neural Network Evaluation
• Structural Deep Clustering Network
• Predict then Propagate: Graph Neural Networks meet Personalized PageRank
• Diffusion Improves Graph Learning
• Scalable Graph Neural Networks via Bidirectional Propagation
• Efficient Estimation of Heat Kernel PageRank for Local Clustering
• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection