Three-Way Decision-Driven Adaptive Graph Convolution for Deep Clustering
Source abstract
Abstract
Graph clustering is an efficient method for deep clustering that utilizes graph convolution. Graph convolution effectively combines structure and content information, and lots of recent graph convolution-based methods have shown promising results in clustering performance on actual attribution networks. However, the established methods mainly employ a fixed graph convolution order, and limited studies have focused on the flexible choice of k-order graph convolution. When utilizing graph convolution with a fixed low order, only considering a few hops per node or neighbors within a set range of hops fails to maximize node relationships or account for the variations within the graphs. In this paper, we propose an adaptive method for graph clustering using a three-way decision idea. Our method enables the adaptive selection of k-order graph convolution for different graphs by searching for the k-order convolution kernel that best suits the subsequent clustering task. Additionally, our approach uses higher-order graph convolution to capture the global clustering structure. We assess the effectiveness of our approach through theoretical analysis and extensive experiments on benchmark datasets. Empirical evidence indicates that our method surpasses state-of-the-art techniques.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Graph Neural Networks · Complex Network Analysis Techniques · Recommender Systems and Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Software Engineering, South China University of Technology, Guangzhou 510006, China
State Key Laboratory of Pulp and Paper Engineering, South China University of Technology, Guangzhou 510006, China
References (46)
Show source-provided references
1. Kipf, T.N., and Welling, M. (2017, January 24–26). Semi-supervised classification with graph convolutional networks. Proceedings of the 5th International Conference on Learning Representations, Toulon, France.
2. Aljalbout, E., Golkov, V., Siddiqui, Y., Strobel, M., and Cremers, D. (2018). Clustering with Deep Learning: Taxonomy and New Methods. arXiv.
3. Zhou, S., Xu, H., Zheng, Z., Chen, J., Zhao, L., Bu, J., Wu, J., Wang, X., Zhu, W., and Martin, E. (2022). A Comprehensive Survey on Deep Clustering: Taxonomy, Challenges, and Future Directions. arXiv.
4. Wang, C., Pan, S., Long, G., Zhu, X., and Jiang, J. (2017, January 6–10). Mgae: Marginalized graph autoencoder for graph clustering. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, Singapore.10.1145/3132847.3132967 ↗
5. Adaptive graph convolution methods for attributed graph clustering10.1109/TKDE.2023.3278721 ↗
6. A survey of clustering with deep learning: From the perspective of network architecture10.1109/ACCESS.2018.2855437 ↗
7. Nasraoui, O., and Ben N’Cir, C.E. (2018). An Introduction to Deep Clustering. Clustering Methods for Big Data Analytics, Springer International Publishing.
8. Optimization of basic clustering for ensemble clustering: An information-theoretic perspective10.1109/ACCESS.2019.2950159 ↗
9. Finding community structure in networks using the eigenvectors of matrices10.1103/PhysRevE.74.036104 ↗
10. Cao, S., Lu, W., and Xu, Q. (2015, January 19–23). Grarep: Learning graph representations with global structural information. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Melbourne, Australia.10.1145/2806416.2806512 ↗
11. Nikolentzos, G., Meladianos, P., and Vazirgiannis, M. (2017, January 4–9). Matching node embeddings for graph similarity. Proceedings of the 31st AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.10.1609/aaai.v31i1.10839 ↗
12. Perozzi, B., Al-Rfou, R., and Skiena, S. (2014, January 24–27). Deepwalk: Online learning of social representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.10.1145/2623330.2623732 ↗
13. Grover, A., and Leskovec, J. (2016, January 13–17). node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.10.1145/2939672.2939754 ↗
14. Yang, C., Liu, Z., Zhao, D., Sun, M., and Chang, E.Y. (2015, January 25–31). Network representation learning with rich text information. Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina.
15. Wang, X., Jin, D., Cao, X., Yang, L., and Zhang, W. (2016, January 12–15). Semantic community identification in large attribute networks. Proceedings of the 2016 IEEE 16th International Conference on Data Mining (ICDM), Barcelona, Spain.
16. Cao, S., Lu, W., and Xu, G. (2016, January 12–17). Deep neural networks for learning graph representations. Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA.10.1609/aaai.v30i1.10179 ↗
17. Ye, F., Chen, C., and Zheng, Z. (2018, January 22–26). Deep autoencoder-like nonnegative matrix factorization for community detection. Proceedings of the 27th ACM International Conference on Information and Knowledge Management, Turin, Italy.10.1145/3269206.3271697 ↗
18. Chang, J., and Blei, D.M. (2009, January 16–18). Relational topic models for document networks. Proceedings of the 12th International Conference on Artificial Intelligence and Statistics, Clearwater Beach, FL, USA.
19. Bojchevski, A., and Günnemann, S. (2018, January 2–7). Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure. Proceedings of the 32nd AAAI Conference on Artificial Intelligence, New Orleans, LA, USA.10.1609/aaai.v32i1.11642 ↗
20. Xia, R., Pan, Y., Du, L., and Yin, J. (2014, January 27–31). Robust multi-view spectral clustering via low-rank and sparse decomposition. Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, QC, Canada.10.1609/aaai.v28i1.8950 ↗
21. Multivariate weather anomaly detection using dbscan clustering algorithm10.1088/1742-6596/1869/1/012077 ↗
22. Liu, F., Xue, S., Wu, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Yang, J., and Yu, P.S. (2021, January 7–15). Deep learning for community detection: Progress, challenges and opportunities. Proceedings of the 29th International Joint Conference on Artificial Intelligence, Yokohama, Japan.
23. Tang, H., Chen, K., and Jia, K. (2020, January 13–19). Unsupervised domain adaptation via structurally regularized deep clustering. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Seattle, WA, USA.10.1109/CVPR42600.2020.00875 ↗
24. Meng, Y., Zhang, Y., Huang, J., Zheng, Y., Zhang, C., and Han, J. (2020, January 6–10). Hierarchical topic mining via joint spherical tree and text embedding. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual Event.10.1145/3394486.3403242 ↗
25. Yang, J., Parikh, D., and Batra, D. (2016, January 27–30). Joint unsupervised learning of deep representations and image clusters. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA.10.1109/CVPR.2016.556 ↗
26. Wang, X., Shi, C., Wang, Z., Li, C., and Cheng, B. (2024, January 13–17). SIMPLE-GNN: A Simple and Efficient GNN for Large-scale Graph Learning. Proceedings of the ACM Web Conference 2024 (WWW ’24), Singapore.
27. Kipf, T.N., and Welling, M. (2016). Variational graph auto-encoders. arXiv.
28. Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., and Zhang, C. (2018, January 13–19). Adversarially regularized graph autoencoder for graph embedding. Proceedings of the 27th International Joint Conference on Artificial Intelligence, Stockholm, Sweden.10.24963/ijcai.2018/362 ↗
29. A novel anomaly detection algorithm using dbscan and svm in wireless sensor networks10.1007/s11277-017-4961-1 ↗
30. A comprehensive survey on community detection with deep learning
31. Hou, Z., Liu, Y., Wang, X., Wei, Y., Wang, P., Dong, Y., and Tang, J. (2024, January 21–27). GraphMAE2: A Decoding-Enhanced Masked Autoencoder for Self-Supervised Graph Learners. Proceedings of the 41st International Conference on Machine Learning (ICML), Vienna, Austria.
32. Cluster adaptation networks for unsupervised domain adaptation10.1016/j.imavis.2021.104137 ↗
33. Cai, X., Huang, X., Liang, H., and Wang, X. (2024, January 25–29). LightGCL: Simple and Effective Graph Contrastive Learning for Recommendation. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Barcelona, Spain.
34. Tixier, A.J., Nikolentzos, G., Meladianos, P., and Vazirgiannis, M. (2019). Graph classification with 2d convolutional neural networks. arXiv.10.1007/978-3-030-30493-5_54 ↗
35. Lin, Z., and Kang, Z. (2021, January 21–26). Graph filter-based multi-view attributed graph clustering. Proceedings of the 30th International Joint Conference on Artificial Intelligence, Montreal, QC, Canada.10.24963/ijcai.2021/375 ↗
36. Optimal estimation of low-rank factors via feature level data fusion of multiplex signal systems
37. Bo, D., Wang, X., Shi, C., Zhu, M., Lu, E., and Cui, P. (2020, January 20–24). Structural deep clustering network. Proceedings of the Web Conference 2020, Taipei, Taiwan.10.1145/3366423.3380214 ↗
38. A two-stage method for improving the decision quality of consensus-driven three-way group decision-making10.1109/TSMC.2022.3222026 ↗
39. A probabilistic linguistic three-way decision method with regret theory via fuzzy c-means clustering algorithm10.1109/TFUZZ.2023.3236386 ↗
40. A large-scale group decision-making method fusing three-way clustering and regret theory under fuzzy preference relations
41. Li, Q., Wu, X.M., Liu, H., Zhang, X., and Guan, Z. (2019, January 15–20). Label efficient semi-supervised learning via graph filtering. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Long Beach, CA, USA.10.1109/CVPR.2019.00981 ↗
42. Visualizing data using t-sne
43. Fettal, C., Labiod, L., and Nadif, M. (2022, January 18–23). Efficient graph convolution for joint node representation learning and clustering. Proceedings of the 2022 International Joint Conference on Neural Networks (IJCNN), Padua, Italy.10.1145/3488560.3498533 ↗
44. Fu, Y., Yuan, J., Song, G., Wang, X., and Pan, S. (2024, January 7–11). Towards a Deeper Understanding of the Hub-induced Dilemma in Graph Neural Networks. Proceedings of the Twelfth International Conference on Learning Representations (ICLR), Vienna, Austria.
45. Behrouz, A., and Al-Tahan, M. (2025, January 5–9). Graph Mamba: Towards Learning on Graphs with State Space Models. Proceedings of the Thirteenth International Conference on Learning Representations (ICLR), Vienna, Austria.
46. Feng, Y., Chen, K., Zhang, Y., Guo, J., Tang, S., Wang, Y., and Hooi, B. (2024, January 12–16). Large Language Models are Not Yet Effective Abstract Reasoners on Graphs. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing (EMNLP), Miami, FL, USA.