Back

Dink-Net: Neural Clustering on Large Graphs

Yue LiuKe LiangJun XiaSihang ZhouXihong YangXinwang LiuStan Z. Li

article2023ICML84 citations

Proposes an end-to-end deep graph clustering framework that uses adversarial dilation and shrink loss functions with learnable cluster centers, enabling mini-batch training to scale effectively to graphs with over 100 million nodes.

Listen

Modern data applications across social networks, recommendation systems, and large-scale knowledge management rely heavily on grouping interconnected data into meaningful categories without human supervision. While deep learning methods that utilize graph structures have improved clustering accuracy, they fundamentally fail to scale to real-world datasets containing tens or hundreds of millions of entities. Most existing techniques require holding massive whole-graph relationship matrices in memory or separating feature extraction from the clustering step, resulting in prohibitive computational bottlenecks and out-of-memory system failures.

The article introduces and evaluates the Dilation Shrink Network (Dink-Net), an end-to-end deep graph clustering framework designed specifically to scale efficiently to massive graphs. The primary objective is to demonstrate that integrating representation learning with clustering optimization through mini-batch processing can resolve the memory and runtime limitations of existing methods while simultaneously achieving superior clustering accuracy.

The authors evaluate Dink-Net through extensive empirical benchmarking and theoretical complexity analyses across seven attribute graph datasets of varying scales, ranging from roughly 3,000 nodes up to 111 million nodes and 1.6 billion edges (specifically the ogbn-papers100M dataset). The proposed architecture combines a self-supervised node discrimination module with a neural clustering module. It optimizes cluster distributions using two adversarial objectives: a dilation loss that pushes separate cluster centers apart and a shrink loss that pulls data samples toward cluster centers. Both training and inference are designed to operate strictly on mini-batches of data rather than the entire graph at once.

The evaluation yields several key findings:

  1. Dink-Net outperforms existing state-of-the-art methods across all tested datasets, achieving a 9.62% improvement in Normalized Mutual Information on the 111-million-node benchmark compared to the leading alternative method (S3GC).
  2. The framework completely eliminates the out-of-memory failures that cause most conventional deep graph clustering methods to fail when scaling beyond small networks.
  3. The method demonstrates significant time and resource efficiency, completing both pre-training and fine-tuning on the 111-million-node dataset in approximately 12 hours on a single 40GB GPU (utilizing around 20GB of GPU memory), whereas traditional approaches require multiple days or fail entirely.
  4. Ablation experiments confirm that both the discriminative pre-training and the joint dilation-shrink clustering optimization are necessary to generate high-quality, clustering-friendly representations.

These results demonstrate that large-scale graph clustering can be unified into an efficient, end-to-end neural workflow without sacrificing cluster quality or requiring supercomputing infrastructure. For organizations managing massive network datasets, this approach significantly reduces infrastructure costs, prevents memory-related application crashes, and shortens end-to-end analytical pipelines from days to hours. It overcomes the historical trade-off between clustering quality and computational scalability.

Organizations handling large-scale network data should consider adopting mini-batch dilation and shrink optimization architectures to replace decoupled, multi-stage clustering pipelines. For immediate next steps, technical teams should conduct pilot implementations on their domain-specific graphs and explore extending the architecture to specialized graph structures, such as heterogeneous, temporal, or molecular networks.

Confidence in these findings is high given the broad range of dataset benchmarks and the underlying computational complexity proofs. However, practical deployment should account for boundary conditions: the model requires hyper-parameter tuning for learning rates and batch sizes, and its performance depends on standard mini-batch graph sampling strategies to handle dense edge connectivity during batch extraction.

bipartite graphsclustering algorithmsDink-Netscalable self-supervised graph clusteringlarge graphs
Liu et al (2023).pdf

No sufficiently relevant recommendations were found.

Cover for Dink-Net: Neural Clustering on Large Graphs

Topics

bipartite graphsclustering algorithms

Keywords

Dink-Netscalable self-supervised graph clusteringlarge graphs

Table of Contents

  • 1. Introduction
  • 2. Related Work
  • 2.1. Deep Graph Clustering
  • 2.2. Salable Graph Neural Network
  • 3. Methodology
  • 3.1. Basic Notation
  • 3.2. Problem Definition
  • 3.3. Challenge Analyses
  • 3.4. Proposed Solution
  • 3.5. Why Dink-Net Works Well on Large Graph?
  • 4. Experiment
  • 4.1. Experimental Setup
  • 4.1.1. Environment
  • 4.1.2. Dataset
  • 4.1.3. Evaluation Protocol
  • 4.1.4. Compared Baseline
  • 4.2. Superiority
  • 4.3. Effectiveness
  • 4.4. Scalability
  • 4.5. Efficiency
  • 5. Conclusion
  • 6. Acknowledgments
  • References
  • A. Notations & Datasets
  • B. Time and Space Analyses
  • C. Design Details & Hyper-parameter Settings
  • D. Additional Experimental Result
  • D.1. Compare Experiment
  • D.2. Sensitivity Analyses
  • D.3. Convergence Analyses
  • E. PyTorch-style Pseudo Code
  • F. Open Resource Supports
  • F.1. Awesome Deep Graph Clustering
  • F.2. A Unified Framework of Deep Graph Clustering
  • G. URLs of Used Datasets

Knowls

  1. Knowl 1 — Dink-Net unifies self-supervised representation learning and clustering

    model/method

    Dink-Net is an end-to-end method for clustering nodes in an attributed graph. A shared graph neural network encoder FF maps graph data to node embeddings; a projection head PP supports a self-supervised task that distinguishes original nodes from nodes in an augmented graph. After pre-training, KK cluster centers are initialized with K-means++ from the learned embeddings and then treated as trainable parameters. Fine-tuning jointly updates the encoder and centers using the discrimination, cluster-dilation, and cluster-shrink losses. At inference, each node is assigned to its nearest learned center. The method uses mini-batches for training and inference, and its clustering losses do not require estimating the assignments of all NN nodes simultaneously.

  2. Knowl 2 — A discrimination task trains node representations from original and augmented graph views

    equation

    For an attributed graph with NN nodes, Dink-Net creates an augmented graph view using graph or attribute augmentations, including edge dropout and attribute disturbance. The same encoder FF and projection head PP process the original and augmented views, yielding projected node representations Z,Z′∈RN×dZ,Z'\in\mathbb{R}^{N\times d}, where dd is the embedding dimension. For node ii, the scalar summaries are gi=∑r=1dZirg_i=\sum_{r=1}^{d}Z_{ir} and gi′=∑r=1dZir′g'_i=\sum_{r=1}^{d}Z'_{ir}. The discrimination loss treats original-view summaries as class 1 and augmented-view summaries as class 0:

    Ldis=1N∑i=1N[log⁡(1gi)+log⁡(11−gi′)].L_{\mathrm{dis}}=\frac{1}{N}\sum_{i=1}^{N}\left[\log\left(\frac{1}{g_i}\right)+\log\left(\frac{1}{1-g'_i}\right)\right].

    The summaries in this binary cross-entropy objective are interpreted as values in (0,1)(0,1). The loss is computed over nodes independently, so it can be optimized on mini-batches. During fine-tuning it is weighted by a trade-off parameter; the projection head supplies the discrimination task while the encoder also receives the clustering-loss gradients.

  3. Knowl 3 — Cluster dilation pushes learned centers apart

    equation

    Let K>1K>1 be the number of clusters, let dd be the embedding dimension, and let Ci∈RdC_i\in\mathbb{R}^{d} be the trainable embedding of cluster ii. Dink-Net defines the dilation loss as the negative mean squared distance over ordered pairs of distinct centers:

    Ldil=−1K(K−1)∑i=0K−1∑j=0j≠iK−1∥Ci−Cj∥22.L_{\mathrm{dil}}=-\frac{1}{K(K-1)}\sum_{i=0}^{K-1}\sum_{\substack{j=0\\j\ne i}}^{K-1}\lVert C_i-C_j\rVert_2^2.

    Minimizing this loss encourages different cluster centers to move farther apart. Its calculation depends on the number of centers and embedding dimension, not on the total number of graph nodes.

  4. Knowl 4 — Cluster shrink pulls each mini-batch embedding toward all centers

    equation

    For a mini-batch of BB node embeddings Hi∈RdH_i\in\mathbb{R}^{d} and KK trainable cluster centers Cj∈RdC_j\in\mathbb{R}^{d}, Dink-Net uses the following shrink loss:

    Lshrink=1BK∑i=0B−1∑j=0K−1∥Hi−Cj∥22.L_{\mathrm{shrink}}=\frac{1}{BK}\sum_{i=0}^{B-1}\sum_{j=0}^{K-1}\lVert H_i-C_j\rVert_2^2.

    The objective averages distances from every batch embedding to every center; it does not first assign each sample to its nearest center. The authors present this all-centers compromise as a way to avoid the confirmation bias that could arise from pulling each sample only toward a possibly incorrect nearest center. The loss is computed using the current mini-batch rather than all NN graph nodes.

  5. Knowl 5 — Fine-tuning combines center dilation, sample shrinkage, and discrimination

    equation

    Dink-Net fine-tunes its encoder and trainable cluster centers by minimizing

    L=Ldil+Lshrink+αLdis,L=L_{\mathrm{dil}}+L_{\mathrm{shrink}}+\alpha L_{\mathrm{dis}},

    where LdilL_{\mathrm{dil}} spreads cluster centers apart, LshrinkL_{\mathrm{shrink}} pulls mini-batch node embeddings toward the set of centers, LdisL_{\mathrm{dis}} distinguishes original from augmented graph views, and α\alpha is a nonnegative trade-off hyperparameter. The dilation and shrink terms act in opposing directions on the clustering distribution, while the discrimination term preserves the self-supervised representation objective. In the paper’s implementation, the centers and model parameters are updated together by Adam during mini-batch fine-tuning.

  6. Knowl 6 — The clustering losses give Dink-Net mini-batch scaling costs

    theoretical result

    Ignoring the cost of producing embeddings and counting the loss calculations, Dink-Net’s pre-training discrimination loss takes O(Bd)O(Bd) time and space for a mini-batch of BB nodes with embedding dimension dd. During fine-tuning, the dilation, shrink, and discrimination losses together take O(BKd+K2d)O(BKd+K^2d) time and O(BK+Bd+Kd)O(BK+Bd+Kd) space, where KK is the number of cluster centers. Given embeddings, assigning a batch to its nearest centers at inference takes O(BKd)O(BKd) time and O(BK+Bd+Kd)O(BK+Bd+Kd) space. These bounds avoid terms proportional to the full node count NN in the clustering-loss calculations and do not require an N×NN\times N dense graph-diffusion matrix. They are the paper’s stated loss/inference costs, not the cost of the graph encoder itself.

  7. Knowl 7 — Dink-Net reports strong clustering scores across seven graph scales

    data/table

    The table gives Dink-Net’s reported clustering scores (percent) on seven attributed-graph benchmarks, from Cora with 2,708 nodes to ogbn-papers100M with 111,059,956 nodes and 1,615,685,872 edges. The four metrics are accuracy (ACC), normalized mutual information (NMI), adjusted Rand index (ARI), and F1-score. The evaluation maps predicted clusters to ground-truth labels with the Kuhn–Munkres algorithm; results were obtained using three random seeds. The scores show that the method produces clustering results across the full range of graph sizes, including the 111-million-node benchmark. On ogbn-papers100M, its NMI of 54.92% is 9.62 percentage points above the reported runner-up S3GC score of 45.30%.

    Dataset ACC (%) NMI (%) ARI (%) F1 (%)
    Cora 78.10 62.28 61.61 72.66
    CiteSeer 70.36 45.87 46.96 65.96
    Amazon-Photo 81.71 74.36 68.40 73.92
    ogbn-arXiv 43.68 46.30 35.22 26.92
    ogbn-products 41.09 53.60 23.00 25.15
    Reddit 76.03 80.70 74.50 67.95
    ogbn-papers100M 26.67 54.92 18.01 19.48

  8. Knowl 8 — The method runs on ogbn-papers100M within the reported GPU budget

    empirical result

    On ogbn-papers100M, which has 111,059,956 nodes and 1,615,685,872 edges, Dink-Net completed training using approximately 20 GB of GPU memory. The reported training took about 9 hours for pre-training and 3 hours for fine-tuning. The experiments used a server with one 40 GB NVIDIA A100 GPU, four Intel Xeon Platinum 8358 CPUs, and PyTorch. The authors report that most compared baseline methods ran out of memory on the 40 GB GPU; they also report that K-means took about five days on CPU for this dataset. These measurements support the feasibility of Dink-Net at this graph scale, but the paper does not give a uniform wall-clock comparison for every baseline on this benchmark.

  9. Knowl 9 — Ablations support both Dink-Net modules

    empirical result

    Ablations on Cora, CiteSeer, Amazon-Photo, and ogbn-arXiv compare the full Dink-Net with versions lacking the node-discrimination module (NDM) or the neural-clustering module (NCM). The complete method achieved the best clustering performance among these variants on the reported metrics. Removing NDM reduced performance, which the authors attribute to weaker representation learning. Removing NCM produced the runner-up variant: discrimination alone could learn representations, but without joint clustering optimization it did not provide equally clustering-friendly features. The results support the roles of both modules; the paper presents these ablations graphically rather than reporting exact values in the text.

  10. Knowl 10 — Sensitivity and convergence checks show stable training behavior

    empirical result

    The paper evaluates hyperparameter sensitivity and optimization behavior in additional experiments. On Cora and CiteSeer, clustering performance remained good across the tested values of the loss trade-off parameter α\alpha. On ogbn-papers100M, performance was not sensitive to the tested mini-batch sizes, although larger batches produced some ACC improvement. On Cora and CiteSeer, the recorded loss values decreased and tended toward convergence across training epochs, while NMI increased. These observations are empirical findings on the tested datasets and settings; they do not establish convergence for every graph or hyperparameter choice.

Coverage note — The extended per-baseline comparison tables, embedding visualizations, and detailed dataset-specific hyperparameter settings are omitted because they provide additional evaluation detail but do not add distinct method mechanisms beyond the results and procedures summarized here.

References

  1. 1.Bianchi, F. M., Grattarola, D., and Alippi, C. Spectral clustering with graph neural networks for graph pooling. In Proc. of ICML, 2020.
  2. 2.Bo, D., Wang, X., Shi, C., Zhu, M., Lu, E., and Cui, P. Structural deep clustering network. In Proc. of WWW, 2020.
  3. 3.Bojchevski, A., Klicpera, J., Perozzi, B., Blais, M., Kapoor, A., Lukasik, M., and Gunnemann, S. Is pagerank all you need for scalable graph neural networks? In ACM KDD, MLG Workshop, 2019.
  4. 4.Bojchevski, A., Klicpera, J., Perozzi, B., Kapoor, A., Blais, M., Rozemberczki, B., Lukasik, M., and G ́ unnemann, S. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464–2473, 2020.
  5. 5.Cao, S., Lu, W., and Xu, Q. Deep neural networks for learning graph representations. In Proc. of AAAI, 2016.
  6. 6.Chen, J., Ma, T., and Xiao, C. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247, 2018.
  7. 7.Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.-J. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257–266, 2019.
  8. 8.Cui, G., Zhou, J., Yang, C., and Liu, Z. Adaptive graph encoder for attributed graph embedding. In Proc. of KDD, 2020.
  9. 9.Devvrit, F., Sinha, A., Dhillon, I., and Jain, P. S3gc: Scalable self-supervised graph clustering. 2022.
  10. 10.Ding, M., Rabbani, T., An, B., Wang, E. Z., and Huang, F. Sketch-gnn: Scalable graph neural networks with sublinear training complexity. In NeurIPS 2022 Workshop: New Frontiers in Graph Learning.
  11. 11.Gong, L., Zhou, S., Liu, X., and Tu, W. Attributed graph clustering with dual redundancy reduction. In Proc. of IJCAI, 2022.
  12. 12.Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855–864, 2016.
  13. 13.Guo, X., Gao, L., Liu, X., and Yin, J. Improved deep embedded clustering with local structure preservation. In Proc. of IJCAI, 2017.
  14. 14.Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
  15. 15.Hartigan, J. A. and Wong, M. A. Algorithm as 136: A k-means clustering algorithm. Journal of the royal statistical society. series c (applied statistics), 1979.
  16. 16.Hassani, K. and Khasahmadi, A. H. Contrastive multi-view representation learning on graphs. In Proc. of ICML, 2020.
  17. 17.Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020.
  18. 18.Kipf, T. N. and Welling, M. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.
  19. 19.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In Proc. of ICLR, 2017.
  20. 20.Klicpera, J., Weißenberger, S., and Gunnemann, S. Diffusion improves graph learning. arXiv preprint arXiv:1911.05485, 2019.
  21. 21.Lee, N., Lee, J., and Park, C. Augmentation-free self-supervised learning on graphs. arXiv preprint arXiv:2112.02472, 2021.
  22. 22.Li, G., Muller, M., Thabet, A., and Ghanem, B. Deepgcns: Can gcns go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9267–9276, 2019.
  23. 23.Li, G., Xiong, C., Thabet, A., and Ghanem, B. Deep-ergcn: All you need to train deeper gcns. arXiv preprint arXiv:2006.07739, 2020.
  24. 24.Li, G., Muller, M., Ghanem, B., and Koltun, V. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437–6449. PMLR, 2021a.
  25. 25.Li, M., Zhang, T., Chen, Y., and Smola, A. J. Efficient mini-batch training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 661–670, 2014.
  26. 26.Li, X., Zhang, H., and Zhang, R. Adaptive graph auto-encoder for general data clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021b.
  27. 27.Liang, K., Liu, Y., Zhou, S., Liu, X., and Tu, W. Relational symmetry based knowledge graph contrastive learning. arXiv preprint arXiv:2211.10738, 2022a.
  28. 28.Liang, K., Meng, L., Liu, M., Liu, Y., Tu, W., Wang, S., Zhou, S., Liu, X., and Sun, F. Reasoning over different types of knowledge graphs: Static, temporal and multimodal. arXiv preprint arXiv:2212.05767, 2022b.
  29. 29.Liang, K., Meng, L., Zhou, S., Wang, S., Tu, W., Liu, Y., Liu, M., and Liu, X. Message intercommunication for inductive relation reasoning. arXiv preprint arXiv:2305.14074, 2023a.
  30. 30.Liang, K., Tan, J., Zeng, D., Huang, Y., Huang, X., and Tan, G. Abslearn: a gnn-based framework for aliasing and buffer-size information retrieval. Pattern Analysis and Applications, pp. 1–19, 2023b.
  31. 31.Linder, E. V. Exploring the expansion history of the universe. Physical review letters, 90(9):091301, 2003.
  32. 32.Liu, M., Gao, H., and Ji, S. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 338–348, 2020.
  33. 33.Liu, M., Liang, K., Xiao, B., Zhou, S., Tu, W., Liu, Y., Yang, X., and Liu, X. Self-supervised temporal graph learning with temporal and structural intensity alignment. arXiv preprint arXiv:2302.07491, 2023a.
  34. 34.Liu, M., Liu, Y., Liang, K., Wang, S., Zhou, S., and Liu, X. Deep temporal graph clustering. arXiv preprint arXiv:2305.10738, 2023b.
  35. 35.Liu, Y., Jin, M., Pan, S., Zhou, C., Zheng, Y., Xia, F., and Philip, S. Y. Graph self-supervised learning: A survey. IEEE Transactions on Knowledge and Data Engineering, 35(6):5879–5900, 2022a.
  36. 36.Liu, Y., Tu, W., Zhou, S., Liu, X., Song, L., Yang, X., and Zhu, E. Deep graph clustering via dual correlation reduction. In Proc. of AAAI, 2022b.
  37. 37.Liu, Y., Xia, J., Zhou, S., Wang, S., Guo, X., Yang, X., Liang, K., Tu, W., Li, Z. S., and Liu, X. A survey of deep graph clustering: Taxonomy, challenge, and application. arXiv preprint arXiv:2211.12875, 2022c.
  38. 38.Liu, Y., Zheng, Y., Zhang, D., Lee, V., and Pan, S. Beyond smoothing: Unsupervised graph representation learning with edge heterophily discriminating. arXiv preprint arXiv:2211.14065, 2022d.
  39. 39.Liu, Y., Zhou, S., Liu, X., Tu, W., and Yang, X. Improved dual correlation reduction network. arXiv preprint arXiv:2202.12533, 2022e.
  40. 40.Liu, Y., Yang, X., Zhou, S., and Liu, X. Simple contrastive graph clustering. IEEE Transactions on Neural Networks and Learning Systems, 2023c.
  41. 41.Liu, Y., Yang, X., Zhou, S., Liu, X., Wang, Z., Liang, K., Tu, W., Li, L., Duan, J., and Chen, C. Hard sample aware network for contrastive deep graph clustering. In Proc. of AAAI, 2023d.
  42. 42.Meng, L., Liang, K., Xiao, B., Zhou, S., Liu, Y., Liu, M., Yang, X., and Liu, X. Sarf: Aliasing relation assisted self-supervised learning for few-shot relation reasoning. arXiv preprint arXiv:2304.10297, 2023.
  43. 43.Mo, Y., Peng, L., Xu, J., Shi, X., and Zhu, X. Simple unsupervised graph representation learning. In AAAI, pp. 7797–7805, 2022.
  44. 44.Mo, Y., Chen, Y., Lei, Y., Peng, L., Shi, X., Yuan, C., and Zhu, X. Multiplex graph representation learning via dual correlation reduction. IEEE Transactions on Knowledge and Data Engineering, 2023.
  45. 45.Nickerson, R. S. Confirmation bias: A ubiquitous phenomenon in many guises. Review of general psychology, 2(2):175–220, 1998.
  46. 46.Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., and Zhang, C. Adversarially regularized graph autoencoder for graph embedding. In Proc. of IJCAI, 2018.
  47. 47.Pan, S., Hu, R., Fung, S.-f., Long, G., Jiang, J., and Zhang, C. Learning graph embedding with adversarial training methods. IEEE transactions on cybernetics, 2019.
  48. 48.Peng, Z., Liu, H., Jia, Y., and Hou, J. Attention-driven graph clustering network. In Proc. of ACM MM, 2021.
  49. 49.Plummer, M. D. and Lovasz, L. Matching theory. Elsevier, 1986.
  50. 50.Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205.12454, 2022.
  51. 51.Rong, Y., Huang, W., Xu, T., and Huang, J. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903, 2019.
  52. 52.Rossi, E., Frasca, F., Chamberlain, B., Eynard, D., Bronstein, M., and Monti, F. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198, 7:15, 2020.
  53. 53.Thakoor, S., Tallec, C., Azar, M. G., Munos, R., Velickovic, P., and Valko, M. Bootstrapped representation learning on graphs. In ICLR 2021 Workshop on Geometrical and Topological Representation Learning, 2021.
  54. 54.Tian, F., Gao, B., Cui, Q., Chen, E., and Liu, T.-Y. Learning deep representations for graph clustering. In Proc. of AAAI, 2014.
  55. 55.Tu, W., Zhou, S., Liu, X., Guo, X., Cai, Z., Cheng, J., et al. Deep fusion clustering network. arXiv preprint arXiv:2012.09600, 2020.
  56. 56.Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 2008.
  57. 57.Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Li o, P., and Bengio, Y. Graph attention networks. In Proc. of ICLR, 2018.
  58. 58.Velickovic, P., Fedus, W., Hamilton, W. L., Lio, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. ICLR (Poster), 2019.
  59. 59.Von Luxburg, U. A tutorial on spectral clustering. Statistics and computing, 2007.
  60. 60.Wang, C., Pan, S., Long, G., Zhu, X., and Jiang, J. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017.
  61. 61.Wang, C., Pan, S., Hu, R., Long, G., Jiang, J., and Zhang, C. Attributed graph clustering: A deep attentional embedding approach. arXiv preprint arXiv:1906.06532, 2019.
  62. 62.Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861–6871. PMLR, 2019.
  63. 63.Wu, Q., Zhao, W., Li, Z., Wipf, D., and Yan, J. Nodeformer: A scalable graph structure learning transformer for node classification. In Advances in Neural Information Processing Systems, 2022.
  64. 64.Xia, J., Wu, L., Wang, G., Chen, J., and Li, S. Z. Progcl: Rethinking hard negative mining in graph contrastive learning. In Proc. of ICML, 2022.
  65. 65.Xia, J., Zhao, C., Hu, B., Gao, Z., Tan, C., Liu, Y., Li, S., and Li, S. Z. Mole-bert: Rethinking pre-training graph neural networks for molecules. In The Eleventh International Conference on Learning Representations, 2023.
  66. 66.Xie, J., Girshick, R., and Farhadi, A. Unsupervised deep embedding for clustering analysis. In Proc. of ICML, 2016.
  67. 67.Yang, B., Fu, X., Sidiropoulos, N. D., and Hong, M. Towards k-means-friendly spaces: Simultaneous deep learning and clustering. In Proc. of ICML, 2017.
  68. 68.Yang, X., Liu, Y., Zhou, S., Liu, X., and Zhu, E. Interpolation-based correlation reduction network for semi-supervised graph learning. arXiv preprint arXiv:2206.02796, 2022a.
  69. 69.Yang, X., Liu, Y., Zhou, S., Wang, S., Liu, X., and Zhu, E. Contrastive deep graph clustering with learnable augmentation. arXiv preprint arXiv:2212.03559, 2022b.
  70. 70.Yang, X., Liu, Y., Zhou, S., Wang, S., Tu, W., Zheng, Q., Liu, X., Fang, L., and Zhu, E. Cluster-guided contrastive graph clustering network. In Proc. of AAAI, 2023.
  71. 71.Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931, 2019.
  72. 72.Zhang, T., Wu, Q., Yan, J., Zhao, Y., and Han, B. Scalegcn: Efficient and effective graph convolution via channel-wise scale transformation. IEEE Transactions on Neural Networks and Learning Systems, 2022.
  73. 73.Zhao, H., Yang, X., Wang, Z., Yang, E., and Deng, C. Graph debiased contrastive learning with joint representation clustering. In Proc. of IJCAI, 2021.
  74. 74.Zhao, L. and Akoglu, L. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv:1909.12223, 2019.
  75. 75.Zheng, Y., Lee, V. C., Wu, Z., and Pan, S. Heterogeneous graph attention network for small and medium-sized enterprises bankruptcy prediction. In Advances in Knowledge Discovery and Data Mining: 25th Pacific-Asia Conference, PAKDD 2021, Virtual Event, May 11–14, 2021, Proceedings, Part I, pp. 140–151. Springer, 2021.
  76. 76.Zheng, Y., Jin, M., Pan, S., Li, Y.-F., Peng, H., Li, M., and Li, Z. Toward graph self-supervised learning with contrastive adjusted zooming. IEEE Transactions on Neural Networks and Learning Systems, 2022a.
  77. 77.Zheng, Y., Pan, S., Lee, V. C., Zheng, Y., and Yu, P. S. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. arXiv preprint arXiv:2206.01535, 2022b.
  78. 78.Zheng, Y., Zheng, Y., Zhou, X., Gong, C., Lee, V. C., and Pan, S. Unifying graph contrastive learning with flexible contextual scopes. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 793–802. IEEE, 2022c.
  79. 79.Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., and Wang, L. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
  80. 80.Bo, D., Wang, X., Shi, C., Zhu, M., Lu, E., and Cui, P. Structural deep clustering network. In Proc. of WWW, 2020.
  81. 81.Devvrit, F., Sinha, A., Dhillon, I., and Jain, P. S3gc: Scalable self-supervised graph clustering. 2022.
  82. 82.Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855–864, 2016.
  83. 83.Guo, X., Gao, L., Liu, X., and Yin, J. Improved deep embedded clustering with local structure preservation. In Proc. of IJCAI, 2017.
  84. 84.Hartigan, J. A. and Wong, M. A. Algorithm as 136: A k-means clustering algorithm. Journal of the royal statistical society. series c (applied statistics), 1979.
  85. 85.Hassani, K. and Khasahmadi, A. H. Contrastive multi-view representation learning on graphs. In Proc. of ICML, 2020.
  86. 86.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In Proc. of ICLR, 2017.
  87. 87.Li, X., Zhang, H., and Zhang, R. Adaptive graph auto-encoder for general data clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
  88. 88.Liu, Y., Xia, J., Zhou, S., Wang, S., Guo, X., Yang, X., Liang, K., Tu, W., Li, Z. S., and Liu, X. A survey of deep graph clustering: Taxonomy, challenge, and application. arXiv preprint arXiv:2211.12875, 2022.
  89. 89.Pal, S. K. and Mitra, S. Multilayer perceptron, fuzzy sets, classifiaction. 1992.
  90. 90.Pan, S., Hu, R., Fung, S.-f., Long, G., Jiang, J., and Zhang, C. Learning graph embedding with adversarial training methods. IEEE transactions on cybernetics, 2019.
  91. 91.Thakoor, S., Tallec, C., Azar, M. G., Munos, R., Velickovic, P., and Valko, M. Bootstrapped representation learning on graphs. In ICLR 2021 Workshop on Geometrical and Topological Representation Learning, 2021.
  92. 92.Tsitsulin, A., Palowitch, J., Perozzi, B., and Muller, E. Graph clustering with graph neural networks. arXiv preprint arXiv:2006.16904, 2020.
  93. 93.Tu, W., Zhou, S., Liu, X., Guo, X., Cai, Z., Cheng, J., et al. Deep fusion clustering network. arXiv preprint arXiv:2012.09600, 2020.
  94. 94.Velickovic, P., Fedus, W., Hamilton, W. L., Lio, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. ICLR (Poster), 2019.
  95. 95.Von Luxburg, U. A tutorial on spectral clustering. Statistics and computing, 2007.
  96. 96.Wang, C., Pan, S., Long, G., Zhu, X., and Jiang, J. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017.
  97. 97.Wang, C., Pan, S., Hu, R., Long, G., Jiang, J., and Zhang, C. Attributed graph clustering: A deep attentional embedding approach. arXiv preprint arXiv:1906.06532, 2019.
  98. 98.Xie, J., Girshick, R., and Farhadi, A. Unsupervised deep embedding for clustering analysis. In Proc. of ICML, 2016.
  99. 99.Zhao, H., Yang, X., Wang, Z., Yang, E., and Deng, C. Graph debiased contrastive learning with joint representation clustering. In Proc. of IJCAI, 2021.
  100. 100.Zheng, Y., Pan, S., Lee, V. C., Zheng, Y., and Yu, P. S. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. arXiv preprint arXiv:2206.01535, 2022.
  101. 101.Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., and Wang, L. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.

Citation

MLA
Liu, Y., et al. “Dink-Net: Neural Clustering on Large Graphs”. International Conference on Machine Learning, vol. 202, 2023, pp. 21794–812, https://proceedings.mlr.press/v202/liu23v.html.
APA
Liu, Y., Liang, K., Xia, J., Zhou, S., Yang, X., Liu, X., & Li, S. Z. (2023). Dink-Net: Neural Clustering on Large Graphs. International Conference on Machine Learning, 202, 21794–21812. https://proceedings.mlr.press/v202/liu23v.html
Chicago
Liu, Y., K. Liang, J. Xia, et al. 2023. “Dink-Net: Neural Clustering on Large Graphs”. International Conference on Machine Learning 202: 21794–812. https://proceedings.mlr.press/v202/liu23v.html.
Harvard
Liu, Y. et al. (2023) “Dink-Net: Neural Clustering on Large Graphs”, International Conference on Machine Learning. PMLR, pp. 21794–21812. Available at: https://proceedings.mlr.press/v202/liu23v.html.
Vancouver
1. Liu Y, Liang K, Xia J, Zhou S, Yang X, Liu X, Li SZ (2023) Dink-Net: Neural Clustering on Large Graphs. In: International Conference on Machine Learning. PMLR, pp 21794–21812

BibTeX

@InProceedings{pmlr-v202-liu23v,
  title = 	 {Dink-Net: Neural Clustering on Large Graphs},
  author =       {Liu, Yue and Liang, Ke and Xia, Jun and Zhou, Sihang and Yang, Xihong and Liu, Xinwang and Li, Stan Z.},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {21794--21812},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/liu23v/liu23v.pdf},
  url = 	 {https://proceedings.mlr.press/v202/liu23v.html},
  abstract = 	 {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 centers 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: https://github.com/yueliu1999/Dink-Net. Besides, a collection (papers, codes, and datasets) of deep graph clustering is shared on GitHub https://github.com/yueliu1999/Awesome-Deep-Graph-Clustering.}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/