Variational Graph Autoencoder for Unsupervised Community Detection in Attributed Social Networks
Subject Areas : Neural networks and deep learningomid rashnodi 1 * , Maryam Rastgarpour 2 * , Azadeh Zamanifar 3 * , Parham Moradi 4 *
1 - Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
2 - Department of Computer, College of Engineering, Saveh Branch, Islamic Azad University, Saveh, Iran
3 - Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
4 - School of engineering, RMIT University Melbourne, Astralia
Keywords: Community Detection, Attributed Social Networks, Variational Graph Autoencoder, Graph Convolutional Networks, Deep Learning, Node Embeddings, Network Topology,
Abstract :
This paper introduces a novel approach named VGAEE (Variational Graph AutoEncoder Embedding), an innovative deep learning framework for detecting communities in attributed social networks. By synergistically integrating node content with network topology, the VGAEE aims to enhance the quality of community identification. Initially, we computed the modularity and Markov matrices of the input graph. These matrices were then concatenated and used as the input for the VGAEE to create a meaningful representation of the graph. In the decoder component of the VGAEE, two layers of Graph Convolutional Networks (GCN) are employed. Subsequently, a K-Nearest Neighbors (KNN) algorithm was used for clustering communities based on the embeddings generated previously. We performed several experiments on three benchmark datasets—Cora, Citeseer, and PubMed—to evaluate the proposed method. The results were compared with several baseline and state-of-the-art methods in terms of two key metrics: accuracy and Normalized Mutual Information (NMI). The findings demonstrate that the VGAEE accurately captures community structures and achieves superior accuracy and NMI. These results highlight the effectiveness of the VGAEE in identifying nuanced community structures within large, complex networks, surpassing existing algorithms in the field.
1. Wen, X., et al.) 2016). A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Transactions on Evolutionary Computation. 21(3): p. 363-377.
2. Lu, X., et al. (2018). Adaptive modularity maximization via edge weighting scheme. Information Sciences. 424: p. 55-68.
3. Wu, W., et al. (2018). Nonnegative matrix factorization with mixed hypergraph regularization for community detection. Information Sciences. 435: p. 263-281.
4. Altinoz, O.T., K. Deb, and A.E. Yilmaz. (2018). Evaluation of the migrated solutions for distributing reference point-based multi-objective optimization algorithms. Information Sciences. 467: p. 750-765.
5. Whang, J.J., D.F. Gleich, and I.S. Dhillon. (2016). Overlapping community detection using neighborhood-inflated seed expansion. IEEE Transactions on Knowledge and Data Engineering. 28(5): p. 1272-1284.
6. Fortunato, S. and D. Hric. (2016).Community detection in networks: A user guide. Physics reports. 2016. 659: p. 1-44.
7. Garza, S.E. and S.E. Schaeffer. (2019). Community detection with the label propagation algorithm: a survey. Physica A: Statistical Mechanics and its Applications. 534: p. 122058.
8. Cao, J., et al.(2018). Incorporating network structure with node contents for community detection on large networks using deep learning. Neurocomputing. 297: p. 71-81.
9. He, C., et al.(2019). Community detection method based on robust semi-supervised nonnegative matrix factorization. Physica A: Statistical Mechanics and its Applications. 523: p. 279-291.
10. Zhengdao Chen, X.L., Joan Bruna. (2020). Supervised Community Detection with Line Graph Neural Networks. International Conference on Learning Representations. p. 1-24.
11. Zhang, T., et al., CommDGI: Community Detection Oriented Deep Graph Infomax. 2020. p. 1843-1852.
12. Tang, J., et al. (2015). Line: Large-scale information network embedding. the 24th international conference on world wide web.
13. Grover, A. and J. Leskovec. (2016). node2vec: Scalable Feature Learning for Networks. p. 855-864.
14. Perozzi, B., R. Al-Rfou, and S. Skiena. (2014). Deepwalk: Online learning of social representations. in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.
15. Chen, S. and W. Guo. (2023). Auto-encoders in deep learning—a review with new perspectives. Mathematics. 11(8): p. 1777.
16. Zhao, S., et al. (2021). Hierarchical representation learning for attributed networks. IEEE Transactions on Knowledge and Data Engineering. 35(3): p. 2641-2656.
17. Lu, H.-Y., et al. (2024). Visual analytics of multivariate networks with representation learning and composite variable construction. IEEE Transactions on Visualization and Computer Graphics.
18. Wang, C., et al. (2017). Mgae: Marginalized graph autoencoder for graph clustering. Conference on Information and Knowledge Management.
19. Li, B., et al. (2020). Multi-source information fusion based heterogeneous network embedding. Information Sciences. 534: p. 53-71.
20. He, C., et al. (2021). Boosting nonnegative matrix factorization based community detection with graph attention auto-encoder. IEEE Transactions on Big Data. 8(4): p. 968-981.
21. Yang, C., et al. (2021). Network Embedding for Graphs with Node Attributes, in Network Embedding: Theories, Methods, and Applications. p. 29-38.
22. Zhang, Y., et al. (2022(. Spectral–spatial feature extraction with dual graph autoencoder for hyperspectral image clustering. IEEE Transactions on Circuits and Systems for Video Technology. 32(12): p. 8500-8511.
23. Jin, D., et al. (2021). A survey of community detection approaches: From statistical modeling to deep learning. IEEE Transactions on Knowledge and Data Engineering. 35(2): p. 1149-1170.
24. Liu, F., et al. (2020). Deep learning for community detection: progress, challenges and opportunities. arXiv preprint arXiv:2005.08225.
25. Zhou, J., et al. (2020). Graph neural networks: A review of methods and applications. AI Open. p. 57-81.
26. Su, X., et al. (2022). A comprehensive survey on community detection with deep learning. IEEE Transactions on Neural Networks and Learning Systems.
27. Jin, D., et al. (2019). Graph Convolutional Networks Meet Markov Random Fields: Semi-Supervised Community Detection in Attribute Networks. the AAAI Conference on Artificial Intelligence. 33(01): p. 152-159.
28. Sun, H., et al. (2020). Network embedding for community detection in attributed networks. ACM Transactions on Knowledge Discovery from Data (TKDD). 14(3): p. 1-25.
29. Jin, D., et al. (2019). Community detection via joint graph convolutional network embedding in attribute network. in International Conference on Artificial Neural Networks.
30. Luo, J. and Y. Du. (2020). Detecting community structure and structural hole spanner simultaneously by using graph convolutional network based Auto-Encoder. Neurocomputing. 410: p. 138-150.
31. Veličković, P., et al. (2017). Graph attention networks. arXiv preprint arXiv:1710.10903.
32. Goodfellow, I., et al. (2020). Generative adversarial networks. Communications of the ACM, 63(11): p. 139-144.
33. Chen, H., et al. (2019). Exploiting centrality information with graph convolutions for network representation learning. International Conference on Data Engineering.
34. Xin, X., et al. (2017). Deep community detection in topologically incomplete networks. Physica A: Statistical Mechanics and its Applications. 469: p. 342-352.
35. Cao, S., et al. (2023). LGNN: a novel linear graph neural network algorithm. Frontiers in Computational Neuroscience.
36. Zhang, T., et al. (2020). CommDGI: community detection oriented deep graph infomax. International Conference on Information & Knowledge Management.
37. Hu, R., et al. (2020). Going deep: Graph convolutional ladder-shape networks. the AAAI Conference on Artificial Intelligence.
38. Liu, Y., et al. (2020). Independence promoted graph disentangled networks. AAAI Conference on Artificial Intelligence.
39. Levie, R., et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing. 67(1): p. 97-109.
40. Geisler, S., D. Zügner, and S. Günnemann. (2020). Reliable graph neural networks via robust aggregation. Advances in neural information processing systems. 33: p. 13272-13284.
41. Cai, X. and B. Wang. (2023). A graph convolutional fusion model for community detection in multiplex networks. Data Mining and Knowledge Discovery. 37(4): p. 1518-1547.
42. Li, D., S. Zhang, and X. Ma. (2022). Dynamic Module Detection in Temporal Attributed Networks of Cancers. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 19(4): p. 2219-2230.
43. Li, D., Q. Lin, and X. Ma. (2021). Identification of dynamic community in temporal network via joint learning graph representation and nonnegative matrix factorization. Neurocomputing. 435: p. 77-90.
44. Li, D., et al. (2021). Detecting dynamic community by fusing network embedding and nonnegative matrix factorization. Knowledge-Based Systems. p. 106961.
45. Li, D., X. Ma, and M. Gong. (2023). Joint Learning of Feature Extraction and Clustering for Large-Scale Temporal Networks. IEEE Transactions on Cybernetics. 53(3): p. 1653-1666.
46. Huang, -.H., et al. (2023). Diverse Deep Matrix Factorization With Hypergraph Regularization for Multi-View Data Representation. IEEE/CAA Journal of Automatica Sinica.
47. Huang, H., et al. (2023). Exclusivity and consistency induced NMF for multi-view representation learning. Knowledge-Based Systems. 281: p. 111020.
48. Huang, H., et al. (2024). Comprehensive Multiview Representation Learning via Deep Autoencoder-Like Nonnegative Matrix Factorization. IEEE Trans Neural Netw Learn Syst. p. 5953-5967.
49. Amirfarhad Farhadi, M.M. (2024). Arash Sharifi, and Mohammad Teshnelab. Domaina daptation in reinforcement learning: a comprehensive and systematic study. Frontiers of Information Technology & Electronic Engineering.
50. Kanatsoulis, C.I., N.D. Sidiropoulos, and A.I. Claims. (2022). GAGE: Geometry Preserving Attributed Graph Embeddings. Fifteenth ACM International Conference on Web Search and Data Mining. p. 439–448.
51. Newman, M.E. (2006). Modularity and community structure in networks. Proceedings of the national academy of sciences. 103(23): p. 8577-8582.
52. Jianbo, S. and J. Malik. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 22(8): p. 888-905.
53. Liu, L., et al. (2015). Community detection based on structure and content: A content propagation perspective. IEEE international conference on data mining.
54. Shchur, O. and S. Günnemann. (2019). Overlapping Community Detection with Graph Neural Networks.
55. Zhang, X., et al. (2019). Attributed graph clustering via adaptive graph convolution. arXiv preprint arXiv:1906.01210.
56. Cui, G., et al. (2020). Adaptive Graph Encoder for Attributed Graph Embedding. p. 976-985.
57. Huang, W. (2021). Graph Auto-Encoders with Edge Reweighting. International Journal of Reconfigurable and Embedded Systems (IJRES).
58. Sen, P., et al. (2008). Collective classification in network data. AI magazine, 29(3): p. 93-93.
59. Namata, G., et al. (2012). Query-driven active surveying for collective classification. in 10th International Workshop on Mining and Learning with Graphs.
60. Rice, S.A. (1927). The identification of blocs in small political bodies. American Political Science Review. 21(3): p. 619-627.
61. Zhu, W., X. Wang, and P. Cui, (2020). Deep learning for learning graph representations, in Deep learning: concepts and architectures. p. 169-210.
62. Cao, S., W. Lu, and Q. Xu. (2016). Deep neural networks for learning graph representations. AAAI Conference on Artificial Intelligence.
63. Sun, F.-Y., et al. (2019). vGraph: a generative model for joint community detection and node representation learning, in Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc.
64. Tian, F., et al. (2014). Learning Deep Representations for Graph Clustering. Proceedings of the AAAI Conference on Artificial Intelligence. 28(1).
65. Kipf, T. and M. Welling. (2016). Variational Graph Auto-Encoders.
66. Pan, S., et al. (2019). Learning Graph Embedding With Adversarial Training Methods. IEEE Transactions on Cybernetics. p. 1-13.
67. Wang, C., et al. (2019). Attributed Graph Clustering: A Deep Attentional Embedding Approach. 3670-3676.
68. Zheng, S., et al. (2020). Distribution-Induced Bidirectional Generative Adversarial Network for Graph Representation Learning. p. 7222-7231.
69. Park, J., et al. (2019). Symmetric Graph Convolutional Autoencoder for Unsupervised Graph Representation Learning.
70. Guo, L. and Q. Dai. (2021). Graph Clustering via Variational Graph Embedding. Pattern Recognition. 122: p. 108334.
71. Yang, C., et al.(2015). Network representation learning with rich text information. in Twenty-fourth international joint conference on artificial intelligence.
72. Xia, R., et al. (2014). Robust Multi-View Spectral Clustering via Low-Rank and Sparse Decomposition. Proceedings of the AAAI Conference on Artificial Intelligence. 28(1).
73. Ahmadi, M., M. Safayani, and A. Mirzaei. (2022). Deep Graph Clustering via Mutual Information Maximization and Mixture Model. arXiv preprint arXiv:2205.05168.
74. Li, J., et al. (2020). Dirichlet Graph Variational Autoencoder.
75. Xie, H. and Y. Ning. (2023). Community detection based on BernNet graph convolutional neural network. Journal of the Korean Physical Society. 83(5): p. 386-395.
76. Deng, L., B. Guo, and W. Zheng. (2024). GCN-based weakly-supervised community detection with updated structure centres selection. Connection Science. 36(1): p. 2291995.
77. Ng, A., M. Jordan, and Y. Weiss. (2002). On Spectral Clustering: Analysis and an algorithm. Adv. Neural Inf. Process. Syst.
78. Tian, F., et al. (2014). Learning Deep Representations for Graph Clustering. Proceedings of the National Conference on Artificial Intelligence. p. 1293-1299.
79. Sun, F.-Y., et al. (2019). vGraph: A Generative Model for Joint Community Detection and Node Representation Learning.