基于二阶图卷积自编码器的图表示学习

doi:10.3778/j.issn.1002-8331.2302-0097

摘要/Abstract

摘要： 图卷积自编码器是一类高效的图表示学习模型，在链路预测等任务中具有出色性能。然而现有模型大多依赖图卷积网络对邻接矩阵和属性矩阵进行编码，未充分利用二阶信息等高阶结构特征。针对上述问题，提出了基于二阶信息的图卷积自编码器模型SeVGAE。首先使用图卷积和二阶图卷积生成变分自编码器的均值和方差，然后学习嵌入向量表示原始图的混合概率分布，最后使用内积解码器恢复拓扑结构。在链接预测任务中，SeGVAE表现优于基线模型，Citeseer数据集上的AUC和AP相较原始的VGAE分别提升了3.26%和2.56%。实验结果表明，二阶信息的引入能够在低维嵌入中保留更丰富的图信息，提升模型性能。模型在处理属性信息不足、拓扑信息不准确的图数据时具有较为明显的优势，在边缘和属性均缺失40%的极端情况下，SeVGAE的AUC和AP相较VGAE提升4.79%和3.47%。

关键词: 图表示学习, 二阶图卷积网络, 链接预测

Abstract: Graph convolutional autoencoders emerged as powerful graph representation learning methods with promising performance on link prediction. However, existing methods typically rely on graph convolutional network to encode adjacency matrix and attribute matrix. This strategy ignores high-order features such as second-order information. This paper proposes a new SeVGAE model based on second-order graph convolutional autoencoders to tackle this problem. Firstly, graph convolutional network and second-order graph convolutional network are used to generate the mean and variance of the variational autoencoders. Then, the embeddings are learned to represent the mixed probability distribution of the original graph. Finally, the topology is recovered by the inner product decoder. SeVGAE performs better than the baselines in the link prediction. AUC and AP are raised by 3.26% and 2.56% respectively compared to the original VGAE on Citeseer dataset. The results show that the second-order information can retain richer graph information in low-dimensional embeddings. Besides, the proposed method has obvious advantages in insufficient attribute and inaccurate topology. In the extreme case where both edges and attributes are missing up to 40%, SeVGAE still improves AUC and AP by 4.79% and 3.47%respectively compared to VGAE.

Key words: graph representation learning, second-order graph convolutional network, link prediction

袁立宁, 蒋萍, 莫嘉颖, 刘钊. 基于二阶图卷积自编码器的图表示学习[J]. 计算机工程与应用, 2024, 60(10): 180-187.

YUAN Lining, JIANG Ping, MO Jiaying, LIU Zhao. Graph Representation Learning Using Second-Order Graph Convolutional Autoencoders[J]. Computer Engineering and Applications, 2024, 60(10): 180-187.

参考文献

[1] 袁立宁, 李欣, 王晓冬, 等.图嵌入模型综述[J].计算机科学与探索, 2022, 16(1): 59-87.
YUAN L N, LI X, WANG X D, et al. Graph embedding models: a survey[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(1): 59-87.
[2] 郑裕龙, 陈启买, 贺超波, 等.图卷积网络增强的非负矩阵分解社区发现方法[J].计算机工程与应用, 2022, 58(11): 73-83.
ZHENG Y L, CHEN Q M, HE C B, et al. Nonnegative matrix factorization community detection method enhanced by graph convolutional network[J]. Computer Engineering and Applications, 2022, 58(11): 73-83.
[3] ZHAO J, WEN T, JAHANSHAHI H, et al. The random walk-based gravity model to identify influential nodes in complex networks[J]. Information Sciences, 2022, 609: 1706-1720.
[4] 马帅, 刘建伟, 左信.图神经网络综述[J].计算机研究与发展, 2022, 59(1): 47-80.
MA S, LIU J W, ZUO X. Survey on graph neural network[J]. Journal of Computer Research and Development, 2022, 59(1): 47-80.
[5] 来杰, 王晓丹, 向前, 等.自编码器及其应用综述[J].通信学报, 2021, 42(9): 218-230.
LAI J, WANG X D, XIANG Q, et al. Review on autoencoder and its application[J]. Journal on Communications, 2021, 42(9): 218-230.
[6] KIPF T N, WELLING M. Variational graph auto-encoders[J]. arXiv:1611.07308v1, 2016.
[7] 翟正利, 梁振明, 周炜, 等.变分自编码器模型综述[J].计算机工程与应用, 2019, 55(3): 1-9.
ZHAI Z L, LIANG Z M, ZHOU W, et al. Research overview of variational auto-encoders models[J]. Computer Engineering and Applications, 2019, 55(3): 1-9.
[8] 徐冰冰, 岑科廷, 黄俊杰, 等.图卷积神经网络综述[J].计算机学报, 2020, 43(5): 755-780.
XU B B, CEN K T, HUANG J J, et al. A survey on graph convolutional neural network[J]. Chinese Journal of Computers, 2020, 43(5): 755-780.
[9] SALHA G, HENNEQUIN R, VAZIRGIANNIS M. Simple and effective graph autoencoders with one-hop linear models[C]//Proceedings of the 2020 Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer, 2020: 319-334.
[10] AHN S J, KIM M. Variational graph normalized autoencoders[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management. New York: ACM, 2021: 2827-2831.
[11] GUO L, DAI Q. Graph clustering via variational graph embedding[J]. Pattern Recognition, 2022, 122: 1-12.
[12] LEE N, LEE J, PARK C. Augmentation-free self-supervised learning on graphs[C]//Proceedings of the 2022 AAAI Conference on Artificial Intelligence. Menlo Park: AAAI, 2022: 7372-7380.
[13] 袁立宁, 刘钊.基于One-Shot聚合自编码器的图表示学习[J].计算机应用, 2023, 43(1): 8-14.
YUAN L N, LIU Z. Graph representation learning by autoencoder with one-shot aggregation[J]. Journal of Computer Applications, 2023, 43(1): 8-14.
[14] LI D, LI D, LIAN G. Variational graph autoencoder with mutual information maximization for graph representations learning[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2022, 36(9): 1-18.
[15] WANG D, CUI P, ZHU W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1225-1234.
[16] TANG J, QU M, WANG M, et al. LINE: large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. New York: ACM, 2015: 1067-1077.
[17] FIRTH J R. A synopsis of linguistic theory, 1930—1955[M]//Studies in linguistic analysis. Oxford: Philological Society, 1957: 1-32.
[18] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[19] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632.
[20] CAO S, LU W, XU Q. GraRep: learning graph representations with global structural information[C]//Proceedings of the 24th ACM International Conference on Information and Knowledge Management. New York: ACM, 2015: 891-900.
[21] DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems. New York: ACM, 2016: 3844-3852.
[22] GUO Z, WANG F, YAO K, et al. Multi-scale variational graph autoencoder for link prediction[C]//Proceedings of the 15th ACM International Conference on Web Search and Data Mining. New York: ACM, 2022: 334-342.
[23] 康世泽, 吉立新, 张建朋.一种基于图注意力网络的异质信息网络表示学习框架[J].电子与信息学报, 2021, 43(4): 915-922.
KANG S Z, JI L X, ZHANG J P. Heterogeneous information network representation learning framework based on graph attention network[J]. Journal of Electronics & Information Technology, 2021, 43(4): 915-922.
[24] HY T S, KONDOR R. Multiresolution equivariant graph variational autoencoder[J]. Machine Learning: Science and Technology, 2023, 4(1): 1-24.
[25] GOYAL P, FERRARA E. Graph embedding techniques, applications, and performance: a survey[J]. Knowledge Based Systems, 2018, 151: 78-94.
[26] WANG C, PAN S, HU R, et al. Attributed graph clustering: a deep attentional embedding approach[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. New York: ACM, 2019: 3670-3676.