  Deep graph clustering, which aims to group the nodes of a graph into disjoint
clusters with deep neural networks, has achieved promising progress in recent
years. However, the existing methods fail to scale to the large graph with
million nodes. To solve this problem, a scalable deep graph clustering method
(Dink-Net) is proposed with the idea of dilation and shrink. Firstly, by
discriminating nodes, whether being corrupted by augmentations, representations
are learned in a self-supervised manner. Meanwhile, the cluster centres are
initialized as learnable neural parameters. Subsequently, the clustering
distribution is optimized by minimizing the proposed cluster dilation loss and
cluster shrink loss in an adversarial manner. By these settings, we unify the
two-step clustering, i.e., representation learning and clustering optimization,
into an end-to-end framework, guiding the network to learn clustering-friendly
features. Besides, Dink-Net scales well to large graphs since the designed loss
functions adopt the mini-batch data to optimize the clustering distribution
even without performance drops. Both experimental results and theoretical
analyses demonstrate the superiority of our method. Compared to the runner-up,
Dink-Net achieves 9.62% NMI improvement on the ogbn-papers100M dataset with 111
million nodes and 1.6 billion edges. The source code is released at
https://github.com/yueliu1999/Dink-Net. Besides, a collection (papers, codes,
and datasets) of deep graph clustering is shared at
https://github.com/yueliu1999/Awesome-Deep-Graph-Clustering.
