Parameter-Agnostic Deep Graph Clustering
Authors: 
Han Zhao, Xu Yang, Cheng DengAuthors Info & Claims
Article No.: 66, Pages 1 - 20
Abstract
Deep graph clustering, efficiently dividing nodes into multiple disjoint clusters in an unsupervised manner, has become a crucial tool for analyzing ubiquitous graph data. Existing methods have acquired impressive clustering effects by optimizing the clustering network under the parametric condition—predefining the true number of clusters (Ktr). However, Ktr is inaccessible in pure unsupervised scenarios, in which existing methods are incapable of inferring the number of clusters (K), causing limited feasibility. This article proposes the first Parameter-Agnostic Deep Graph Clustering method (PADGC), which consists of two core modules: K-guidence clustering and topological-hierarchical inference, to infer K efficiently and gain impressive clustering predictions. Specifically, K-guidence clustering is employed to optimize the cluster assignments and discriminative embeddings in a mutual promotion manner under the latest updated K, even though K may deviate from Ktr. In turn, such optimized cluster assignments are utilized to explore more accurate K in the topological-hierarchical inference, which can split the dispersive clusters and merge the coupled ones. In this way, these two modules are complementarily optimized until generating the final convergent K and discriminative cluster assignments. Extensive experiments on several benchmarks, including graphs and images, can demonstrate the superiority of our method. The mean values of our inferred K, in 11 out of 12 datasets, deviates from Ktr by less than 1. Our method can also achieve competitive clustering effects with existing parametric deep graph clustering.
References
[1]
Mohamed Abbas, Adel El-Zoghabi, and Amin Shoukry. 2021. DenMune: Density peak based clustering using mutual nearest neighbors. Pattern Recognit. 109 (2021), 107589.
[2]
Charles E. Antoniak. 1974. Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. Ann. Stat. 2, 6 (1974), 1152–1174.
[3]
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. 2020. Spectral clustering with graph neural networks for graph pooling. In Proc. Int. Conf. Mach. Learn. PMLR, 874–883.
[4]
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. 2020. Structural deep clustering network. In Proc. Web Conf.1400–1410.
[5]
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv:1312.6203. Retrieved from https://arxiv.org/abs/1312.6203
[6]
Avory Bryant and Krzysztof Cios. 2017. RNN-DBSCAN: A density-based clustering algorithm using reverse nearest neighbor density estimates. IEEE Trans. Knowl. Data Eng. 30, 6 (2017), 1109–1121.
[7]
Jason Chang. 2014. Sampling in Computer Vision and Bayesian Nonparametric Mixtures. Ph.D. Dissertation. Massachusetts Institute of Technology.
[8]
Jason Chang and John W. Fisher III. 2013. Parallel sampling of DP mixture models using sub-cluster splits. Proc. Adv. Neural Inf. Process. Syst. 26 (2013), 620–628.
[9]
Ching-Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka. 2020. Debiased contrastive learning. Proc. Adv. Neural Inf. Process. Syst. 33 (2020), 8765–8775.
[10]
Adam Coates, Andrew Ng, and Honglak Lee. 2011. An analysis of single-layer networks in unsupervised feature learning. In Proc. Int. Conf. Artif. Intell. Stat. JMLR Workshop and Conference Proceedings, 215–223.
[11]
George Bernard Dantzig and Delbert Ray Fulkerson. 1955. On the Max Flow Min Cut Theorem of Networks. Technical Report. RAND CORP SANTA MONICA CA.
[12]
Guowang Du, Lihua Zhou, Zhongxue Li, Lizhen Wang, and Kevin Lü. 2023. Neighbor-aware deep multi-view clustering via graph convolutional network. Inf. Fusion 93 (2023), 330–343.
[13]
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. Int. Conf. Knowl. Discov. Data Min. 226–231.
[14]
Shaohua Fan, Xiao Wang, Chuan Shi, Emiao Lu, Ken Lin, and Bai Wang. 2020. One2multi graph autoencoder for multi-view graph clustering. In Proc. Web Conf.3070–3076.
[15]
Lei Gong, Sihang Zhou, Wenxuan Tu, and Xinwang Liu. 2022. Attributed graph clustering with dual redundancy reduction. In Proc. Int. Jt. Conf. Artif. Intell. 3015–3021.
[16]
W. Keith Hastings. 2001. Monte carlo sampling methods using markov chains and their applications. Biometrika: One Hundred Years 57, 1 (2001), 97.
[17]
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Proc. Adv. Neural Inf. Process. Syst. 33 (2020), 22118–22133.
[18]
Michael C. Hughes, William T. Stephenson, and Erik Sudderth. 2015. Scalable adaptation of state complexity for nonparametric hidden Markov models. Proc. Adv. Neural Inf. Process. Syst. 28 (2015), 1198–1206.
[19]
Jonathan J. Hull. 1994. A database for handwritten text recognition research. IEEE Trans. Pattern Anal. Mach. Intell. 16, 5 (1994), 550–554.
[20]
Sonia Jain and Radford Neal. 2007. Splitting and merging components of a nonconjugate dirichlet process mixture model. Bayesian Anal. 2 (2007), 445–472.
[21]
Chaojie Ji, Hongwei Chen, Ruxin Wang, Yunpeng Cai, and Hongyan Wu. 2021. Smoothness sensor: Adaptive smoothness-transition graph convolutions for attributed graph clustering. IEEE Trans. Cybern. (2021).
[22]
Barakeel Fanseu Kamhoua, Lin Zhang, Kaili Ma, James Cheng, Bo Li, and Bo Han. 2023. GRACE: A general graph convolution framework for attributed graph clustering. ACM Trans. Knowl. Discov. Data 17, 3 (2023), 1–31.
[23]
Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In Proc. Int. Conf. Learn. Represent.
[24]
Thomas N. Kipf and Max Welling. 2016. Variational graph auto-encoders. NIPS Workshop Bayesian Deep Learn. (2016).
[25]
Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2, 1-2 (1955), 83–97.
[26]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11 (1998), 2278–2324.
[27]
Dongjie Li, Dong Li, and Guang Lian. 2023. Variational graph autoencoder with adversarial mutual information learning for network representation learning. ACM Trans. Knowl. Discov. Data 17, 3 (2023), 1–18.
[28]
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. 2019. Deepgcns: Can gcns go as deep as cnns?. In Proc. IEEE Int. Conf. Comput. Vis.9267–9276.
[29]
Hao Li, Xiaojie Liu, Tao Li, and Rundong Gan. 2020. A novel density-based clustering algorithm using nearest neighbor graph. Pattern Recognit. 102 (2020), 107206.
[30]
Mengran Li, Yong Zhang, Xiaoyong Li, Yuchen Zhang, and Baocai Yin. 2023. Hypergraph transformer neural networks. ACM Trans. Knowl. Discov. Data 17, 5 (2023), 1–22.
[31]
Zhuolin Liao, Xiaolin Zhang, Wei Su, and Kun Zhan. 2022. View-consistent heterogeneous network on graphs with few labeled nodes. IEEE Trans. Cybern. 53, 9 (2022), 5523–5532.
[32]
Chenghua Liu, Zhuolin Liao, Yixuan Ma, and Kun Zhan. 2022. Stationary diffusion state neural estimation for multiview clustering. In Proc. AAAI Conf. Artif. Intell.e. 7542–7549.
[33]
Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. 2022. Deep graph clustering via dual correlation reduction. In Proc. AAAI Conf. Artif. Intell.
[34]
Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Siwei Wang, Ke Liang, Wenxuan Tu, and Liang Li. 2023. Simple contrastive graph clustering. IEEE Trans. Neural Netw. Learn. Syst. (2023), 1–12.
[35]
Stuart Lloyd. 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theory 28, 2 (1982), 129–137.
[36]
Nairouz Mrabah, Mohamed Bouguessa, Mohamed Fawzi Touati, and Riadh Ksantini. 2022. Rethinking graph auto-encoder models for attributed graph clustering. IEEE Trans. Knowl. Data Eng. (2022).
[37]
Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. Proc. Adv. Neural Inf. Process. Syst. 14 (2001), 849–856.
[38]
Xi Peng, Zhenyu Huang, Jiancheng Lv, Hongyuan Zhu, and Joey Tianyi Zhou. 2019. COMIC: Multi-view clustering without parameter selection. In Proc. Int. Conf. Mach. Learn. PMLR, 5092–5101.
[39]
Zhihao Peng, Hui Liu, Yuheng Jia, and Junhui Hou. 2021. Attention-driven graph clustering network. In Proc. Int. Conf. Multimed.935–943.
[40]
Zhihao Peng, Hui Liu, Yuheng Jia, and Junhui Hou. 2023. Deep attention-guided graph clustering with dual self-supervision. IEEE Trans. Circuits Syst. Video Technol. 33, 7 (2023), 3296–3307.
[41]
Saquib Sarfraz, Vivek Sharma, and Rainer Stiefelhagen. 2019. Efficient parameter-free clustering using first neighbor relations. In Proc. IEEE Conf. Comput. Vis. Pattern Recognit.8934–8943.
[42]
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2022. Constant time graph neural networks. ACM Trans. Knowl. Discov. Data 16, 5 (2022), 1–31.
[43]
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008. Computational capabilities of graph neural networks. IEEE Trans. Neural Netw. 20, 1 (2008), 81–102.
[44]
Sohil Atul Shah and Vladlen Koltun. 2018. Deep continuous clustering. arXiv:1803.01449. Retrieved from https://arxiv.org/abs/1803.01449
[45]
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of graph neural network evaluation. arXiv:1811.05868. Retrieved from https://arxiv.org/abs/1811.05868
[46]
Michael C. Hughes and Erik Sudderth. 2013. Memoized online variational inference for dirichlet process mixture models. Proc. Adv. Neural Inf. Process. Syst. 26 (2013), 98–106.
[47]
Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tie-Yan Liu. 2014. Learning deep representations for graph clustering. In Proc. AAAI Conf. Artif. Intell.
[48]
Petar Velikovi, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li, and Yoshua Bengio. 2018. Graph attention networks. In Proc. Int. Conf. Learn. Represent.
[49]
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. 2019. Attributed graph clustering: a deep attentional embedding approach. In Proc. Int. Jt. Conf. Artif. Intell. 3670–3676.
[50]
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. 2017. Mgae: Marginalized graph autoencoder for graph clustering. In Proc. Conf. Inf. Knowl. Manag.889–898.
[51]
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. 2020. Microsoft academic graph: When experts are not enough. Quant. Science Stud. 1, 1 (2020), 396–413.
[52]
Tong Wang, Junhua Wu, Yaolei Qi, Xiaoming Qi, Juwei Guan, Yuan Zhang, and Guanyu Yang. 2023. Neighborhood contrastive representation learning for attributed graph clustering. Neurocomputing 562 (2023), 126880.
[53]
Joe H. Ward Jr. 1963. Hierarchical grouping to optimize an objective function. J. Am. Stat. Assoc. 58, 301 (1963), 236–244.
[54]
Sinead Williamson, Avinava Dubey, and Eric Xing. 2013. Parallel Markov chain Monte Carlo for nonparametric mixture models. In Proc. Int. Conf. Mach. Learn. PMLR, 98–106.
[55]
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying graph convolutional networks. In Proc. Int. Conf. Mach. Learn. PMLR, 6861–6871.
[56]
Man Wu, Shirui Pan, Lan Du, and Xingquan Zhu. 2021. Learning graph neural networks with positive and unlabeled nodes. ACM Trans. Knowl. Discov. Data 15, 6 (2021), 1–25.
[57]
Shunxin Xiao, Shide Du, Zhaoliang Chen, Yunhe Zhang, and Shiping Wang. 2023. Dual fusion- propagation graph neural network for multi-view clustering. IEEE Trans. Multimedia (2023), 1–13.
[58]
Yifan Xing, Tong He, Tianjun Xiao, Yongxin Wang, Yuanjun Xiong, Wei Xia, David Wipf, Zheng Zhang, and Stefano Soatto. 2021. Learning hierarchical graph neural networks for image clustering. In Proc. IEEE Int. Conf. Comput. Vis.3467–3477.
[59]
Kun Zhan and Chaoxi Niu. 2021. Mutual teaching for graph convolutional networks. Future Gener. Comput. Syst. 115 (2021), 837–843.
[60]
Kun Zhan, Changqing Zhang, Junpeng Guan, and Junsheng Wang. 2017. Graph learning for multiview clustering. IEEE Trans. Cybern. 48, 10 (2017), 2887–2895.
[61]
Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. 2021. Graph debiased contrastive learning with joint representation clustering. In Proc. Int. Jt. Conf. Artif. Intell.3434–3440.
Index Terms
- Parameter-Agnostic Deep Graph Clustering
Recommendations
Deep Adaptive Graph Clustering via von Mises-Fisher Distributions
Graph clustering has been a hot research topic and is widely used in many fields, such as community detection in social networks. Lots of works combining auto-encoder and graph neural networks have been applied to clustering tasks by utilizing node ...
Deep attributed graph clustering with self-separation regularization and parameter-free cluster estimation
AbstractDetecting clusters over attributed graphs is a fundamental task in the graph analysis field. The goal is to partition nodes into dense clusters based on both their attributes and structures. Modern graph neural networks provide ...
Highlights- We propose a novel method to learn highly separated clusters without cluster number.
Parameter-lite clustering algorithm based on MST and fuzzy similarity merging
ICACCI '12: Proceedings of the International Conference on Advances in Computing, Communications and InformaticsClustering is an unsupervised process of classifying data items or objects into meaningful groups and each group is called a cluster. There are several algorithms for clustering based on different approaches (hierarchical, partitional, density-based, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2024
663 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 January 2024
Online AM: 27 November 2023
Accepted: 10 November 2023
Revised: 30 July 2023
Received: 28 April 2023
Published in TKDD Volume 18, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Joint Fund of Ministry of Education of China
- Key Research and Development Program of Shaanxi
- National Natural Science Foundation of China
- Fundamental Research Funds for the Central Universities
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 330Total Downloads
- Downloads (Last 12 months)314
- Downloads (Last 6 weeks)40
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in