Analysis of Graph Data Structure from the Perspective of Clustering
Authors: 
Peng Lv, Yan LiuAuthors Info & Claims
Pages 414 - 419
Abstract
Deep graph clustering is a fundamental task that partitions graph nodes into distinct clusters based on their similarity features, without using human-annotated data. Graph representation learning methods are widely used for deep graph clustering, as they can learn node embeddings that capture the similarity features within each cluster. However, the existing methods have not clearly defined what kind of similarity they capture, and how it varies across different node categories. In this paper, we propose a novel approach for deep graph clustering that addresses these issues. We use a combination of qualitative and quantitative methods to analyze the attribute vectors and structure of graph data, and explore the sources of similarity captured by graph representation learning. We also investigate how the attribute and structure features of graph data affect the clustering performance, and identify the specific challenges faced by deep graph clustering tasks. Our approach provides insights and guidance for the future development of deep graph clustering.
References
[1]
Lada A. Adamic, Thomas M. Lento, Eytan Adar, and Pauline C. Ng. 2016. Information Evolution in Social Networks. Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, 473–482. https://doi.org/10.1145/2835776.2835827
[2]
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. 2020. Structural Deep Clustering Network. Proceedings of The Web Conference 2020, 1400–1410. https://doi.org/10.1145/3366423.3380214
[3]
Yu Chen, Lingfei Wu, Mohammed Zaki, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. 2020. Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings. Proceedings of the 34th International Conference on Neural Information Processing Systems, 19314–19326. https://proceedings.neurips.cc/paper/2020/file/e05c7ba4e087beea9410929698dc41a6-Paper.pdf
[4]
Shaohua Fan, Xiao Wang, Chuan Shi, Emiao Lu, Ken Lin, and Bai Wang. 2020. One2Multi Graph Autoencoder for Multi-view Graph Clustering. Proceedings of The Web Conference 2020, 3070–3076. https://doi.org/10.1145/3366423.3380079
[5]
William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. Proceedings of the 31st International Conference on Neural Information Processing Systems, 1025–1035.
[6]
Kaveh Hassani and Amir Hosein Khasahmadi. 2020. Contrastive Multi-View Representation Learning on Graphs, Hal Daumé III and Aarti Singh (Eds.). Proceedings of the 37th International Conference on Machine Learning, 4116–4126. https://proceedings.mlr.press/v119/hassani20a.html
[7]
Thomas N Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. Proceedings of the 5th International Conference on Learning Representations. https://openreview.net/forum?id=SJU4ayYgl
[8]
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. 2021. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Proceedings of the 35th Conference on Neural Information Processing Systems 34, 20887–20902. https://proceedings.neurips.cc/paper-files/paper/2021/file/ae816a80e4c1c56caa2eb4e1819cbb2f-Paper.pdf
[9]
Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. 2022. Deep Graph Clustering via Dual Correlation Reduction. Proceedings of the AAAI Conference on Artificial Intelligence 36 (28 6 2022), 7603–7611. https://doi.org/10.1609/aaai.v36i7.20726
[10]
Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Zhen Wang, Ke Liang, Wenxuan Tu, Liang Li, Jingcan Duan, and Cancan Chen. 2023. Hard Sample Aware Network for Contrastive Deep Graph Clustering. Proceedings of the AAAI Conference on Artificial Intelligence 37, 7 (26 6 2023), 8914–8922. https://doi.org/10.1609/aaai.v37i7.26071
[11]
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. 2022. Towards Unsupervised Deep Graph Structure Learning. Proceedings of the ACM Web Conference 2022, 1392–1403. https://doi.org/10.1145/3485447.3512186
[12]
Zhiyuan Liu and Jie Zhou. 2020. Introduction to Graph Neural Networks. Springer International Publishing, Cham. https://link.springer.com/10.1007/978-3-031-01587-8
[13]
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-GCN: Geometric graph convolutional networks. Proceedings of the 8th International Conference on Learning Representations. https://openreview.net/forum?id=S1e2agrFvS
[14]
Khyaati Shrikant, Vaishnavi Gupta, Anand Khandare, and Palak Furia. 2022. A Comparative Study of Clustering Algorithm. In Intelligent Computing and Networking. Vol. 301. Springer Nature Singapore, Singapore, 219–235. https://link.springer.com/10.1007/978-981-16-4863-2-19
[15]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. Proceedings of the 6th International Conference on Learning Representations. https://openreview.net/forum?id=rJXMpikCZ
[16]
Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. 2021. Graph Structure Estimation Neural Networks. Proceedings of the Web Conference 2021, 342–353. https://doi.org/10.1145/3442381.3449952
[17]
Xihong Yang, Yue Liu, Sihang Zhou, Siwei Wang, Wenxuan Tu, Qun Zheng, Xinwang Liu, Liming Fang, and En Zhu. 2023. Cluster-Guided Contrastive Graph Clustering Network. Proceedings of the AAAI Conference on Artificial Intelligence 37, 9 (26 6 2023), 10834–10842. https://doi.org/10.1609/aaai.v37i9.26285
[18]
Hongyuan Zhang, Pei Li, Rui Zhang, and Xuelong Li. 2022. Embedding Graph Auto-Encoder for Graph Clustering. IEEE Transactions on Neural Networks and Learning Systems (2022), 1–11. https://doi.org/10.1109/TNNLS.2022.3158654
[19]
Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. 2021. Graph Debiased Contrastive Learning with Joint Representation Clustering. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 3434–3440. https://doi.org/10.24963/ijcai.2021/473
[20]
Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, and Philip S. Yu. 2022. Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination. Proceedings of the 36th International Conference on Neural Information Processing Systems. http://arxiv.org/abs/2206.01535
[21]
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du, Jieyu Zhang, Qiang Liu, Carl Yang, and Shu Wu. 2022. A Survey on Graph Structure Learning: Progress and Opportunities. (14 2 2022). http://arxiv.org/abs/2103.03036
Recommendations
CGC: Contrastive Graph Clustering forCommunity Detection and Tracking
WWW '22: Proceedings of the ACM Web Conference 2022Given entities and their interactions in the web data, which may have occurred at different time, how can we find communities of entities and track their evolution? In this paper, we approach this important task from graph clustering perspective. ...
Deep graph clustering via aligning representation learning
AbstractDeep graph clustering is a fundamental yet challenging task for graph data analysis. Recent efforts have witnessed significant success in combining autoencoder and graph convolutional network to explore graph-structured data. However, we observe ...
Highlights- A novel contrastive deep graph clustering method termed Aligning Representation Learning Network (ARLN) to avoid representation collapse problem.
- ARLN selects positive/negative pairs in the original view without data augmentation, thus ...
Deep graph clustering by integrating community structure with neighborhood information
AbstractDeep graph clustering approaches employ deep graph neural networks to encode node embeddings and subsequently partition nodes based on these representations. Recent one-step methods have demonstrated progress; however, they often encounter issues ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2023
563 pages
ISBN:9798400708688
DOI:10.1145/3638584
Copyright © 2023 ACM.
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: 14 March 2024
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
CSAI 2023
CSAI 2023: 2023 7th International Conference on Computer Science and Artificial Intelligence
December 8 - 10, 2023
Beijing, China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 20Total Downloads
- Downloads (Last 12 months)20
- Downloads (Last 6 weeks)5
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format