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

arXiv: https://arxiv.org/abs/2112.15530 · HTML: https://mlsanity.com/paper/2112.15530/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 31 Dec 2021.

## Builds on (most cited first, 21 of 21)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [A Survey on Contrastive Self-supervised Learning](https://mlsanity.com/paper/2011.00362/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Adversarially Regularized Graph Autoencoder for Graph Embedding](https://mlsanity.com/paper/1802.04407/) (2018)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Efficient Estimation of Heat Kernel PageRank for Local Clustering](https://mlsanity.com/paper/1904.02707/) (2019)

## Built on by (most cited first, 2 of 2)

- [Impression-Informed Multi-Behavior Recommender System: A Hierarchical Graph Attention Approach](https://mlsanity.com/paper/2309.03169/) (2023)
- [Incremental Semi-supervised Federated Learning for Health Inference via Mobile Sensing](https://mlsanity.com/paper/2312.12666/) (2023)

## Abstract (arXiv)

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.