Graph clustering is one of the fundamental tasks in graph data mining, with significant applications in social networks and recommendation systems. Traditional methods for clustering heterogeneous graphs typically involve obtaining node representations as a preliminary step, followed by the application of clustering algorithms to achieve the final clustering results. However, this two-step approach leads to a disconnection between the optimization of node representation and the clustering process, making it challenging to achieve optimal results. In this paper, we propose a graph clustering approach specifically designed for heterogeneous graphs that unifies the optimization of node representation and the clustering process for nodes in a heterogeneous graph. We assume that the relationships between different meta-paths in the heterogeneous graph are mutually independent. By maximizing the joint probability of meta-paths and nodes, we derive the optimization objective through variational methods. Finally, we employ backpropagation and reparameterization techniques to optimize this objective and thereby achieve the desired clustering results. Experiments conducted on multiple real heterogeneous datasets demonstrate that the proposed method is competitive with existing methods.
Citation: Chuang Ma, Helong Xia. A one-step graph clustering method on heterogeneous graphs via variational graph embedding[J]. Electronic Research Archive, 2024, 32(4): 2772-2788. doi: 10.3934/era.2024125
Graph clustering is one of the fundamental tasks in graph data mining, with significant applications in social networks and recommendation systems. Traditional methods for clustering heterogeneous graphs typically involve obtaining node representations as a preliminary step, followed by the application of clustering algorithms to achieve the final clustering results. However, this two-step approach leads to a disconnection between the optimization of node representation and the clustering process, making it challenging to achieve optimal results. In this paper, we propose a graph clustering approach specifically designed for heterogeneous graphs that unifies the optimization of node representation and the clustering process for nodes in a heterogeneous graph. We assume that the relationships between different meta-paths in the heterogeneous graph are mutually independent. By maximizing the joint probability of meta-paths and nodes, we derive the optimization objective through variational methods. Finally, we employ backpropagation and reparameterization techniques to optimize this objective and thereby achieve the desired clustering results. Experiments conducted on multiple real heterogeneous datasets demonstrate that the proposed method is competitive with existing methods.
| [1] | N. Park, R. Rossi, E. Koh, I. A. Burhanuddin, S. Kim, F. Du, et al., CGC: Contrastive graph clustering for community detection and tracking, in Proceedings of the ACM Web Conference 2022, (2022), 1115–1126. https://doi.org/10.1145/3485447.3512160 |
| [2] |
L. Guo, Q. Dai, Graph clustering via variational graph embedding, Pattern Recognit., 122 (2022), 108334. https://doi.org/10.1016/j.patcog.2021.108334 doi: 10.1016/j.patcog.2021.108334
|
| [3] | R. A. Khan, M. Kleinsteuber, Cluster-aware heterogeneous information network embedding, in Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, (2022), 476–486. https://doi.org/10.1145/3488560.3498385 |
| [4] |
C. Song, Y. Teng, Y. Zhu, S. Wei, B. Wu, Dynamic graph neural network for fake news detection, Neurocomputing, 505 (2022), 362–374. https://doi.org/10.1016/j.neucom.2022.07.057 doi: 10.1016/j.neucom.2022.07.057
|
| [5] | H. Bo, R. McConville, J. Hong, W. Liu, Social influence prediction with train and test time augmentation for graph neural networks, in Proceedings of 2021 International Joint Conference on Neural Networks (IJCNN), (2021), 1–8. https://doi.org/10.1109/IJCNN52387.2021.9533437 |
| [6] | H. Bo, R. McConville, J. Hong, W. Liu, Social network influence ranking via embedding network interactions for user recommendation, in Proceedings of WWW'20: The Web Conference, (2020), 379–384. https://doi.org/10.1145/3366424.3383299 |
| [7] |
W. Peng, J. Wang, Z. Zhang, F. X. Wu, Applications of random walk model on biological networks, Curr. Bioinf., 11 (2016), 2111–220. https://doi.org/10.2174/1574893611666160223200823 doi: 10.2174/1574893611666160223200823
|
| [8] | W. Fan, Y. Ma, Q. Li, Y. He, E. Zhao, J. Tang, et al., Graph neural networks for social recommendation, in Proceedings of WWW'19: The World Wide Web Conference, (2019), 417–426. https://doi.org/10.1145/3308558.3313488 |
| [9] | C. Huang, H. Xu, Y. Xu, P. Dai, L. Xia, M. Lu, et al., Knowledge-aware coupled graph neural network for social recommendation, in Proceedings of the AAAI Conference on Artificial Intelligence, (2021), 4115–4122. https://doi.org/10.1609/aaai.v35i5.16533 |
| [10] | C. Huang, J. Chen, L. Xia, Y. Xu, P. Dai, Y. Chen, et al., Graph-enhanced multi-task learning of multi-level transition dynamics for session-based recommendation, in Proceedings of the AAAI Conference on Artificial Intelligence, (2021), 4123–4130. https://doi.org/10.1609/aaai.v35i5.16534 |
| [11] | D. Yuxiao, N. Chawla, A. Swami, Metapath2vec: Scalable representation learning for heterogeneous networks, in KDD'17: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2017), 135–144. https://doi.org/10.1145/3097983.3098036 |
| [12] | X. Wang, H. Ji, C. Shi, B. Wang, Y. Ye, P. Cui, et al., Heterogeneous graph attention network, in Proceedings of WWW '19: The World Wide Web Conference, (2019), 2022–2032. https://doi.org/10.1145/3308558.3313562 |
| [13] | X. Fu, J. Zhang, Z. Meng, I. King, MAGNN: Metapath aggregated graph neural network for heterogeneous graph embedding, in Proceedings of WWW '20: The Web Conference, (2020), 2331–2341. https://doi.org/10.1145/3366423.3380297 |
| [14] | C. Zhang, D. Song, C. Huang, A. Swami, N. Chawla, Heterogeneous graph neural network, in KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, (2019), 793–803. https://doi.org/10.1145/3292500.3330961 |
| [15] | C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, et al., Do transformers really perform bad for graph representation?, Adv. Neural Inf. Process. Syst., 34 (2021), 28877–28888. |
| [16] | B. Perozzi, R. Al-Rfou, S. Skiena, DeepWalk: Online learning of social representations, in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2014), 701–710. https://doi.org/10.1145/2623330.2623732 |
| [17] | A. Grover, J. Leskovec, Node2vec: Scalable feature learning for networks, in KDD: Proceedings of International Conference on Knowledge Discovery & Data Mining, (2016), 855–864. https://doi.org/10.1145/2939672.2939754 |
| [18] | M. Defferrard, X. Bresson, P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering, inProceedings of the 30th International Conference on Neural Information Processing Systems, (2016), 3844–3852. https://doi.org/10.5555/3157382.3157527 |
| [19] | P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, Y. Bengio, Inductive representation learning on large graphs, in Proceedings of International Conference on Learning Representations, (2017). |
| [20] | W. Hamilton, R. Ying, J. Leskovec, Inductive representation learning on large graphs, in Proceedings of the 31st International Conference on Neural Information Processing Systems, (2017), 1025–1035. https://doi.org/10.5555/3294771.3294869 |
| [21] | T. Kipf, M. Welling, Variational graph auto-encoders, preprint, arXiv: 1611.07308. |
| [22] | A. Salehi, H. Davulcu, Graph attention auto-encoders, in Proceedings of IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), (2020), 989–996. https://doi.org/10.1109/ICTAI50040.2020.00154 |
| [23] | P. Veličković, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, R. D. Hjelm, Deep Graph Infomax, in Proceedings of International Conference on Learning Representations, (2019). |
| [24] | C. Wang, S. Pan, R. Hu, G. Long, J. Jiang, C. Zhang, Attributed graph clustering: A deep attentional embedding approach, in Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, (2019), 3670–3676. https://doi.org/10.24963/ijcai.2019/509 |
| [25] | D. Bo, X. Wang, C. Shi, M. Zhu, E. Lu, P. Cui, Structural deep clustering network, in Web Conference 2020: Proceedings of the World Wide Web Conference (WWW 2020), (2020), 1400–1410. https://doi.org/10.1145/3366423.3380214 |
| [26] | H. Liu, B. Hu, X. Wang, C. Shi, Z. Zhang, J. Zhou, Confidence may cheat: Self-training on graph neural networks under distribution shift, in Proceedings of the ACM Web Conference, (2022), 1248–1258. https://doi.org/10.1145/3485447.3512172 |
| [27] |
C. Shi, B. Hu, W. Zhao, P. Yu, Heterogeneous information network embedding for recommendation, IEEE Trans. Knowl. Data Eng., 31 (2017), 357–370. https://doi.org/10.1109/TKDE.2018.2833443 doi: 10.1109/TKDE.2018.2833443
|
| [28] | T. Fu, W. C. Lee, Z. Lei, HIN2Vec: Explore meta-paths in heterogeneous information networks for representation learning, in Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, (2017), 1797–1806. https://doi.org/10.1145/3132847.3132953 |
| [29] |
W. Wang, X. Wei, X. Suo, B. Wang, H. Wang, H. N. Dai, et al., HGATE: heterogeneous graph attention auto-encoders, IEEE Trans. Knowl. Data Eng., 35 (2021), 3938–3951. https://doi.org/10.1109/TKDE.2021.3138788 doi: 10.1109/TKDE.2021.3138788
|
| [30] | X. Fu, J. Zhang, Z. Meng, I. King, MAGNN: Metapath aggregated graph neural network for heterogeneous graph embedding, in Proceedings of The Web Conference 2020, (2020), 2331–2341. https://doi.org/10.1145/3366423.3380297 |
| [31] |
S. Zheng, D. Guan, W. Yuan, Semantic-aware heterogeneous information network embedding with incompatible meta-paths, World Wide Web, 25 (2022), 1–21. https://doi.org/10.1007/s11280-021-00903-5 doi: 10.1007/s11280-021-00903-5
|
| [32] | Y. Ren, B. Liu, C. Huang, P. Dai, L. Bo, J. Zhang, Heterogeneous deep graph infomax, preprint, arXiv: 1911.08538. |
| [33] | C. Park, D. Kim, J. Han, H. Yu, Unsupervised attributed multiplex network embedding, in Proceedings of the AAAI Conference on Artificial Intelligence, (2020), 5371–5378. |
| [34] | C. Mavromatis, G. Karypis, HeMI: Multi-view embedding in heterogeneous graphs, preprint, arXiv: 2109.07008. |
| [35] | J. Macqueen, Some methods for classification and analysis of multivariate observations, in Proceedings of Symposium on Mathematical Statistics and Probability, (1967). |
| [36] | X. Wang, N. Liu, H. Han, C. Shi, Self-supervised heterogeneous graph neural network with co-contrastive learning, in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, (2021), 1726–1736. https://doi.org/10.1145/3447548.3467415 |
| [37] | Q. Zhu, W. Bi, X. Liu, X. Ma, X. Li, D. Wu, A batch normalized inference network keeps the KL vanishing away, in Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, (2020), 2636–2649. https://doi.org/10.18653/v1/2020.acl-main.235 |
| [38] | Z. Jiang, Y. Zheng, H. Tan, B. Tang, H. Zhou, Variational deep embedding: An unsupervised and generative approach to clustering, in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, (2017), 1965–1972. https://doi.org/10.24963/ijcai.2017/273 |
Figures(6) / Tables(1)
Chuang Ma, Helong Xia. A one-step graph clustering method on heterogeneous graphs via variational graph embedding[J]. Electronic Research Archive, 2024, 32(4): 2772-2788. doi: 10.3934/era.2024125
DownLoad: