Link Prediction Combining Motif Graph Neural Network and Auto-encoder

doi:10.3778/j.issn.1673-9418.2104085

Abstract

Abstract: Link prediction is a basic task of network data mining, and there are many related research results. Due to the in-depth development of graph neural network research, the related models can learn the important features of link prediction more effectively, and thus achieve better results. However, different from the CNN model in deep learning, the most existing graph neural network models only aggregate the first-order neighbor information of nodes, and do not fully consider the topology characteristics between neighbors. On this basis, this paper proposes a link prediction model based on motif graph neural network. The model adopts auto-encoder architecture. In the encoding process, the adjacent matrix of the node is constructed by the motif, and then the motif neighborhood of the node is obtained. According to the neighborhood of each kind of motif, the neighbor information is aggregated, and the representation of the node is obtained by nonlinear transformation. Finally, the representation of the node under each kind of motif is concatenated. However, owing to different importance of different motifs in the network, the attention weights of different motifs are given by using the attention network, and the vector representation of nodes is given by connecting the attention network. In the decoding process, the network is reconstructed by calculating the similarity between nodes. Experimental results on several citation networks show that the proposed method outperforms most benchmark algorithms in two indices, and effectively improves the accuracy of link prediction on networks.

Key words: link prediction, complex networks, motif, graph convolutional networks, graph auto-encoder

摘要： 链路预测是网络数据挖掘的一项基本任务，已有很多相关的研究成果。由于图神经网络研究的深入发展，使得相关的模型可以更加有效学习网络的重要特征，在链路预测等任务中取得了很好的预测效果。然而，不同于深度学习中CNN模型，已有的图神经网络模型中仅聚合了节点的一阶邻居信息，未充分考虑邻居节点之间的拓扑结构特性。在此基础上，提出了基于模体的图神经网络链路预测模型。该模型采用自编码器结构，在编码过程中，通过模体构建节点的邻接矩阵，进而得到节点的模体邻域，依照每一类模体的邻域聚合邻居信息，通过非线性变换得到节点的表示，最后拼接每一类模体下节点的表示。然而由于不同的模体结构在网络中重要度有所不同，利用注意力网络给出表达不同模体的注意力权重，连接注意力网络给出节点的向量表示。在解码过程中，通过计算节点间的相似性重构网络。在几个引文合作者网络上的实验结果表明，该方法在两个指标上优于大多数基准算法，有效地提高了网络链路预测的准确度。

关键词: 链路预测, 复杂网络, 模体, 图卷积网络, 图自编码器

LU Furong, YUAN Zhi'an, QIAN Yuhua. Link Prediction Combining Motif Graph Neural Network and Auto-encoder[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(1): 209-216.

鲁富荣, 原之安, 钱宇华. 融合模体图神经网络和自编码器的链路预测[J]. 计算机科学与探索, 2023, 17(1): 209-216.

References

[1] SINGH R, XU J B, BERGER B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences of the USA , 2008, 105(35): 12763-12768.
[2] NEWMAN M E J. Clustering and preferential attachment in growing networks[J]. Physical Review E, 2001, 2: 025102.
[3] KOSSINETS G. Effects of missing data in social networks[J]. Social Networks, 2006, 28(3): 247-268.
[4] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J].Nature, 2008, 453: 98-101.
[5] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230.
[6] ZHOU T, Lü L Y, ZHANG Y C. Predicting missing links via local information[J]. European Physical Journal B, 2009, 71: 623-630.
[7] WHITE H C, BOORMAN S A, BREIGER R L. Social struc-ture from multiple networks I: blockmodels of roles and positions[J]. American Journal of Sociology, 1976, 81(4): 730-780.
[8] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, Aug 24-27, 2014. New York: ACM, 2014: 701-710.
[9] GROVER A, LESKOVEC J. node2vec: scalable feature lear-ning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 855-864.
[10] TANG J, QU M, WANG M Z, et al. LINE: large-scale in-formation network embedding[C]//Proceedings of the 24th International Conference on World Wide Web, Florence,May 18-22, 2015. New York: ACM, 2015: 1067-1077.
[11] RIBEIRO L F, SAVERRSE P H, FIGUEIREDO D R. struc-2vec: learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, Aug 13-17, 2017. New York: ACM, 2017: 385-394.
[12] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[J]. arXiv:1609.02907, 2016.
[13] VELICKOVIC P, CUCURULL G, CASANOVA A, et al. Graph attention networks[J]. arXiv:1710.10903, 2017.
[14] XU K, HU W H, LESKOVEC J, et al. How powerful are graph neural networks?[C]//Proceedings of the 7th Interna-tional Conference on Learning Representations, New Orleans, May 6-9, 2019: 1-17.
[15] HAMILTON W L, YING Z T, LESKOVEC J. Inductive rep-resentation learning on large graphs[C]//Proceedings of the Annual Conference on Neural Information Processing Systems 2017, Long Beach, Dec 4-9, 2017. Red Hook: Curran Asso-ciates, 2017: 1024-1034.
[16] ZHANG M H, CHEN Y X. Link prediction based on graph neural networks[C]//Proceedings of the Annual Conference on Neural Information Processing Systems 2018, Montréal, Dec 3-8, 2018: 5171-5181.
[17] WANG L, REN J, XU B, et al. MODEL: motif-based deep feature learning for link prediction[J]. IEEE Transactions on Computational Social Systems, 2020, 7(2): 503-516.
[18] SANKAR A, ZHANG X Y, CHANG C C K. Meta-GNN: metagraph neural network for semi-supervised learning in attributed heterogeneous information networks[C]//Procee-dings of the 2019 International Conference on Advances in Social Networks Analysis and Mining, Vancouver, Aug 27-30, 2019. New York: ACM, 2019: 137-144.
[19] MILO R. Simple building blocks of complex networks[J]. Science, 2002, 298(5594): 824-827.
[20] KIPF T N, WELLING M. Variational graph auto-encoders [J]. arXiv:1611.07308, 2016.
[21] MATTHIEU L. Main-memory triangle computations for very large (sparse (power-law)) graphs[J]. Theoretical Computer Science, 2008, 407: 458-473.
[22] GU W, GAO F, LOU X, et al. Link prediction via graph attention network[J]. arXiv:1910.04807, 2019.