Survey of Dynamic Graph Neural Network for Link Prediction

doi:10.3778/j.issn.1002-8331.2403-0308

Abstract

Abstract: Complex dynamic network data, such as social networks, protein interaction networks, and infectious disease transmission networks, are prevalent in the real world, consisting of numerous nodes and edges. Effective mining and utilization of such data for accurate prediction have become a key task. Dynamic graph neural network link prediction is an important branch of deep learning research, which aims to analyze the intrinsic laws of network evolution over time and predict potential future linkages, providing valuable information and basis for decision-making in various fields. This paper first reviews the development of dynamic graph neural networks, then introduces the modeling methods and training processes of dynamic graphs. Based on this, the paper categorizes dynamic graph neural network link prediction models into two main types according to the granularity of time: discrete dynamic graph models and continuous dynamic graph models, and provides an overview of the modeling methods used by current mainstream models in each category. In addition, it also introduces commonly used data sets, evaluation indicators and some application scenarios in dynamic graph link prediction research. Finally, the future development trends in this field are discussed prospectively.

Key words: graph neural network, deep learning, dynamic graph learning, link prediction, temporal graph

摘要： 在现实世界中，复杂的动态网络数据广泛存在，如社交网络、蛋白质相互作用网络和传染病传播网络，它们由大量的节点和边构成。针对这类数据的有效挖掘和利用，以进行精准预测，成为了一项关键任务。动态图神经网络链接预测是深度学习研究领域的一个重要分支，它旨在解析网络随时间演化的内在规律，并预测未来可能形成的链接，为各领域的决策提供有价值的信息和依据。回顾了动态图神经网络的发展历程，介绍动态图的建模方法和训练流程。在此基础上，根据时间粒度的不同，将动态图神经网络链接预测模型细分为离散动态图模型和连续动态图模型两大类，并综述了每一类别中当前主流模型所采用的建模方法；介绍了动态图链接预测研究中常用的数据集、评价指标和应用场景。最后，对该领域的未来发展趋势进行了前瞻性探讨。

关键词: 图神经网络, 深度学习, 动态图学习, 链接预测, 时间图

ZHANG Qi, CHEN Xu, WANG Shuyang, JING Yongjun, SONG Jifei. Survey of Dynamic Graph Neural Network for Link Prediction[J]. Computer Engineering and Applications, 2024, 60(20): 49-67.

张其, 陈旭, 王叔洋, 景永俊, 宋吉飞. 动态图神经网络链接预测综述[J]. 计算机工程与应用, 2024, 60(20): 49-67.

References

[1] BRONSTEIN M, BRUNA J, COHEN T, et al. Geometric deep learning: grids, groups, graphs, geodesics, and gauges[J]. arXiv:2104.13478, 2021.
[2] LIU Y, SHI X L, PIERCE L, et al. Characterizing and forecasting user engagement with in-app action graph: a case study of snapchat[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019: 2023-2031.
[3] FOUT A, BYRD J, SHARIAT B, et al. Protein interface prediction using graph convolutional networks[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 6533-6542.
[4] CHAMI I, YING Z, Ré C, et al. Hyperbolic graph convolutional neural networks[C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019: 4868-4879.
[5] SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80.
[6] PANG J, JIA L, DENG J. A survey on dynamic graph neural networks modeling[C]//Proceedings of the 2022 China Automation Congress, 2022: 2476-2481.
[7] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[J]. arXiv:1609.02907, 2016.
[8] VELI?KOVI? P, CUCURULL G, CASANOVA A, et al. Graph attention networks[J]. arXiv:1710.10903, 2017.
[9] HAMILTON W L, YING R, LESKOVEC J. Inductive representation learning on large graph[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 1025-1035.
[10] CHEN J, MA T, XIAO C. FastGCN: fast learning with graph convolutional networks via importance sampling[J]. arXiv:1801.10247, 2018.
[11] SCHLICHTKRULL M, KIPF T N, BLOEM P, et al. Modeling relational data with graph convolutional networks[C]//Proceedings of the 15th Extended Semantic Web Conference, 2018: 593-607.
[12] TAI K S, SOCHER R, MANNING C D. Improved semantic representations from tree-structured long short-term memory networks[C]//Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, 2015: 1556-1566.
[13] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 6000-6010.
[14] SKARDING J, GABRYS B, MUSIAL K. Foundations and modelling of dynamic net-works using dynamic graph neural networks: a survey[J]. IEEE Access, 2021, 9: 79143-79168.
[15] YANG L, CHATELAIN C, ADAM S. Dynamic graph representation learning with neural networks: a survey[J]. IEEE Access, 2024, 12: 43460-43484.
[16] LONGA A, LACHI V, SANTIN G, et al. Graph neural networks for temporal graphs: state of the art, open challenges, and opportunities[J]. arXiv:2302.01018, 2023.
[17] ZHU Y, LYU F, HU C, et al. Encoder-decoder architecture for supervised dynamic graph learning: a survey[J]. arXiv:2203.10480, 2022.
[18] ZHENG Y, YI L, WEI Z. A survey of dynamic graph neural networks[J]. arXiv:2404.18211, 2024.
[19] SKARDING J, HELLMICH M, GABRYS B, et al. A robust comparative analysis of graph neural networks on dynamic link prediction[J]. IEEE Access, 2022, 10: 64146-64160.
[20] FENG Z, LIU L, SHU J, et al. A survey of dynamic network link prediction[C]//Proceedings of the 2023 15th International Conference on Communication Software and Networks, 2023: 143-147.
[21] SANDRYHAILA A, MOURA J M F. Discrete signal processing on graphs: graph fourier transform[C]//Proceedings of the 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, 2013: 6167-6170.
[22] ZHOU J, CUI G, HU S, et al. Graph neural networks: a review of methods and applications[J]. AI Open, 2020, 1: 57-81.
[23] GORI M, MONFARDINI G, SCARSELLI F. A new model for learning in graph domains[C]//Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, 2005: 729-734.
[24] MICHELI A. Neural network for graphs: a contextual constructive approach[J]. IEEE Transactions on Neural Networks, 2009, 20(3): 498-511.
[25] BRUNA J, ZAREMBA W, SZLAM A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv:1312.6203, 2013.
[26] GILMER J, SCHOENHOLZ S, RILEY P F, et al. Neural message passing for quantum chemistry[C]//Proceedings of the International Conference on Machine Learning, 2017: 1263-1272.
[27] REHMAN A, AHMAD M, KHAN O. Exploring accelerator and parallel graph algorithmic choices for temporal graphs[C]//Proceedings of the 11th International Workshop on Programming Models and Applications for Multicores and Manycores, 2020: 1-10.
[28] HOLME P, SARAM?KI J. Temporal networks[J]. Physics Reports, 2012, 519(3): 97-125.
[29] HOLME P. Modern temporal network theory: a colloquium[J]. The European Physical Journal B, 2015, 88(9): 234.
[30] LI J, WANG P, LI H, et al. Enhanced time-expanded graph for space information network modeling[J]. Science China Information Sciences, 2022, 65(9): 192301.
[31] AZIMIFAR M, TODD T D, KHEZRIAN A, et al. Vehicle-to-vehicle forwarding in green roadside infrastructure[J]. IEEE Transactions on Vehicular Technology, 2016, 65(2): 780-795.
[32] MICHAIL O. An introduction to temporal graphs: an algorithmic perspective[J]. Internet Mathematics, 2016, 12(4): 239-280.
[33] QU L, ZHU H S, DUAN Q Q, et al. Continuous-time link prediction via temporal dependent graph neural network[C]//Proceedings of the Web Conference 2020, 2020: 3026-3032.
[34] KIPF T N, WELLING M. Variational graph auto-encoders[J]. arXiv:1611.07308, 2016.
[35] SEO Y, DEFFERRARD M, VANDERGHEYNST P, et al. Structured sequence modeling with graph convolutional recurrent networks[C]//Proceedings of the 25th International Conference on Neural Information Processing, 2018: 362-373.
[36] MANESSI F, ROZZA A, MANZO M. Dynamic graph convolutional networks[J]. Pattern Recognition, 2020, 97: 107000.
[37] GRAVES A. Long short-term memory[J]. Supervised Sequence Labelling with Recurrent Neural Networks, 2012, 385: 37-45.
[38] WANG Y, LI P, BAI C, et al. TEDIC: neural modeling of behavioral patterns in dynamic social interaction net-works[C]//Proceedings of the Web Conference 2021, 2021: 693-705.
[39] CAI L, CHEN Z, LUO C, et al. Structural temporal graph neural networks for anomaly detection in dynamic graphs[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021: 3747-3756.
[40] ZHOU F, XU X, LI C, et al. A heterogeneous dynamical graph neural networks approach to quantify scientific impact[J]. arXiv:2003.12042, 2020.
[41] BAI S, KOLTER J Z, KOLTUN V. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling[J]. arXiv:1803.01271, 2018.
[42] CHO K, MERRIENBOER V B, GULCEHRE C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation[J]. arXiv:1406.1078, 2014.
[43] NARAYAN A, O’N ROE P H. Learning graph dynamics using deep neural networks[J]. IFAC-PapersOnLine, 2018, 51(2): 433-438.
[44] NIEPERT M, AHMED M, KUTZKOV K. Learning convolutional neural networks for graphs[C]//Proceedings of the International Conference on Machine Learning, 2016: 2014-2023.
[45] WU J, CAO M, CHEUNG J C K, et al. TeMP: temporal message passing for temporal knowledge graph completion[C]//Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020: 5730-5746.
[46] KING I J, HUANG H. EULER: detecting network lateral movement via scalable temporal link prediction[J]. ACM Transactions on Privacy and Security, 2023, 26(3): 1-36.
[47] SHI X, CHEN Z, WANG H, et al. Convolutional LSTM network: a machine learning approach for precipitation nowcasting[C]//Proceedings of the 28th International Conference on Neural Information Processing Systems, 2015: 802-810.
[48] PAREJA A, DOMENICONI G, CHEN J, et al. EvolveGCN: evolving graph convolutional networks for dynamic graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2020: 5363-5370.
[49] CHEN J, WANG X, XU X. GC-LSTM: graph convolution embedded LSTM for dynamic network link prediction[J]. Applied Intelligence, 2022, 52(7): 7513-7528.
[50] LI J, HAN Z, CHENG H, et al. Predicting path failure in time-evolving graphs[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019: 1279-1289.
[51] JIN W, QU M, JIN X, et al. Recurrent event network: autoregressive structure inference over temporal knowledge graphs[C]//Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020: 6669-6683.
[52] BONNER S, ATAPOUR-ABARGHOUEI A, JACKSON P T, et al. Temporal neighbourhood aggregation: predicting future links in temporal graphs via re-current variational graph convolutions[C]//Proceedings of the 2019 IEEE International Conference on Big Data, 2019: 5336-5345.
[53] XU J, SUN X, ZHANG Z, et al. Understanding and improving layer normalization[C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019: 4381-4391.
[54] BAI L, YAO L, LI C. Adaptive graph convolutional recurrent network for traf?c forecasting[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020: 17804-17815.
[55] NIKNAM G, MOLAEI S, ZARE H, et al. DyVGRNN: dynamic mixture variational graph recurrent neural networks[J]. Neural Networks, 2023, 165: 596-610.
[56] QIN X, SHEIKH N, LEI C, et al. SEIGN: a simple and efficient graph neural network for large dynamic graphs[C]//Proceedings of the IEEE 39th International Conference on Data Engineering, 2023: 2850-2863.
[57] MIRZA M, OSINDERO S. Conditional generative adversarial nets[J]. arXiv:1411.1784, 2014.
[58] LEI K, QIN M, BAI B, et al. GCN-GAN: a non-linear temporal link prediction model for weighted dynamic networks[C]//Proceedings of the 2019 IEEE Conference on Computer Communications, 2019: 388-396.
[59] MAHESHWARI A, GOYAL A, HANAWAL M K, et al. DynGAN: generative adversarial networks for dynamic network embedding[C]//Proceedings of the Graph Representation Learning Workshop at NeurIPS, 2019.
[60] YANG M, ZHOU M, KALANDER M, et al. Discrete-time temporal network embedding via implicit hierarchical learning in hyperbolic space[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021: 1975-1985.
[61] YANG M, ZHOU M, XIONG H, et al. Hyperbolic temporal network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(11): 11489-11502.
[62] NICKEL M. Poincaré embeddings for learning hierarchical representations[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 6341-6350.
[63] BAI Q, NIE C, ZHANG H, et al. HGWaveNet: a hyperbolic graph neural network for temporal link prediction[C]//Proceedings of the ACM Web Conference 2023, 2023: 523-532.
[64] OORD V D A, DIELEMAN S, ZEN H, et al. WaveNet: a generative model for raw audio[J]. arXiv:1609.03499, 2016.
[65] WU Z, PAN S, LONG G, et al. Graph WaveNet for deep spatial-temporal graph modeling[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019: 1907-1913.
[66] LI H, JIANG H, YE D, et al. DHGAT: hyperbolic representation learning on dynamic graphs via attention networks[J]. Neurocomputing, 2024, 568: 127038.
[67] ORESHKIN B N, CARPOV D, CHAPADOS N, et al. Meta-learning framework with applications to zero-shot time-series forecasting[J]. arXiv:2002.02887, 2020.
[68] ORESHKIN B N, CARPOV D, CHAPADOS N, et al. N-BEATS: neural basis expansion analysis for interpretable time series forecasting[J]. arXiv:1905.10437, 2019.
[69] YANG C, WANG C, LU Y, et al. Few-shot link prediction in dynamic networks[C]//Proceedings of the 15th ACM International Conference on Web Search and Data Mining, 2022: 1245-1255.
[70] YOU J, DU T, LESKOVEC J. ROLAND: graph learning framework for dynamic graphs[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022: 2358-2366.
[71] ZHU Y, CONG F, ZHANG D, et al. WinGNN: dynamic graph neural networks with random gradient aggregation window[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023: 3650-3662.
[72] LIU M, WU J, LIU Y. Embedding global and local influences for dynamic graphs[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022: 4249-4253.
[73] SHI M, HUANG Y, ZHU X, et al. GAEN: graph attention evolving networks[C]//Proceedings of the 13th International Joint Conference on Artificial Intelligence, 2021: 1541-1547.
[74] ZANG X, TANG B. Self-supervised dynamic graph embedding with evolutionary neighborhood and community[J]. Expert Systems with Applications, 2023, 228: 120409.
[75] TIAN S, XIONG T, SHI L. Streaming dynamic graph neural networks for continuous-time temporal graph modeling[C]//Proceedings of the 2021 IEEE International Conference on Data Mining, 2021: 1361-1366.
[76] KUMAR S, ZHANG X, LESKOVEC J. Predicting dynamic embedding trajectory in temporal interaction networks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019: 1269-1278.
[77] TRIVEDI R, FARAJTABAR M, BISWAL P, et al. DyRep: learning representations over dynamic graphs[C]//Proceedings of the International Conference on Learning Representations, 2019.
[78] KNYAZEV B, AUGUSTA C, TAYLOR G W. Learning temporal attention in dynamic graphs with bilinear interactions[J]. Plos One, 2021, 16(3): 0247936.
[79] KIPF T, FETAYA E, WANG K C, et al. Neural relational inference for interacting systems[C]//Proceedings of the International Conference on Machine Learning, 2018: 2688-2697.
[80] XIA W, LI Y, LI S. Graph neural point process for temporal interaction prediction[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(5): 4867-4879.
[81] WEN Z, FANG Y. TREND: Temporal event and node dynamics for graph representation learning[C]//Proceedings of the ACM Web Conference 2022, 2022: 1159-1169.
[82] TIAN S, WU R, SHI L, et al. Self-supervised representation learning on dynamic graphs[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021: 1814-1823.
[83] JIANG L, CHEN K J, CHEN J. Self-supervised dynamic graph representation learning via temporal sub-graph contrast[J]. arXiv:2112.08733, 2021.
[84] ALOMRANI M A, BIPARVA M, ZHANG Y, et al. DyG2Vec: representation learning for dynamic graphs with self-supervision[J]. arXiv:2210.16906, 2022.
[85] LIU M, LIANG K, ZHAO Y, et al. Self-supervised temporal graph learning with temporal and structural intensity alignment[J]. arXiv:2302.07491, 2023.
[86] XU D, RUAN C, KORPEOGLU E, et al. Inductive representation learning on temporal graphs[J]. arXiv:2002.07962, 2020.
[87] YU L, SUN L, DU B, et al. Towards better dynamic graph learning: new architecture and unified library[C]//Proceedings of the 37th Conference on Neural Information Processing Systems, 2023.
[88] NGUYEN G H, LEE J B, ROSSI R A, et al. Continuous-time dynamic network embeddings[C]//Proceedings of the Web Conference 2018, 2018: 969-976.
[89] WANG Y, CHANG Y, LIU Y, et al. Inductive representation learning in temporal networks via causal anonymous walks[J]. arXiv:2101.05974, 2021.
[90] JIN M, LI Y F, PAN S. Neural temporal walks: motif-aware representation learning on continuous-time dynamic graphs[C]//Advances in Neural Information Processing Systems, 2022: 19874-19886.
[91] LI H, CHEN L. EARLY: efficient and reliable graph neural network for dynamic graphs[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 1-28.
[92] LI Y, SHEN Y, CHEN L, et al. Zebra: when temporal graph neural networks meet temporal personalized pagerank[J]. Proceedings of the VLDB Endowment, 2023, 16(6): 1332-1345.
[93] ROMERO R, BIE D T, LIJFFIJT J. New perspectives on the evaluation of link prediction algorithms for dynamic graphs[J]. arXiv:2311.18486, 2023.
[94] SHETTY J, ADIBI J. The enron email dataset[R]. Los Angeles: University of Southern California, 2004.
[95] PANZARASA P, OPSAHL T, CARLEY K M. Patterns and dynamics of users’ behavior and interaction: network analysis of an online community[J]. Journal of the American Society for Information Science and Technology, 2009, 60(5): 911-932.
[96] XIANG S, CHENG D, SHANG C, et al. Temporal and heterogeneous graph neural network for financial time series prediction[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022: 3584-3593.
[97] HUANG L, MA Y, LIU Y, et al. Position-enhanced and time-aware graph convolutional network for sequential recommendations[J]. ACM Transactions on Information Systems, 2023, 41(1): 1-32.
[98] LIU C, LI Y, LIN H, et al. GNNRec: gated graph neural network for session-based social recommendation model[J]. Journal of Intelligent Information Systems, 2022, 60(1): 137-156.
[99] ZHANG M, WU S, YU X, et al. Dynamic graph neural networks for sequential recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(5): 4741-4753.
[100] WAN S, WU Y, LIU Y, et al. A recommendation approach based on heterogeneous network and dynamic knowledge graph[J]. International Journal of Intelligent Systems, 2024, 2024: 1-19.
[101] HAN Z, MA Y, WANG Y, et al. Graph Hawkes neural network for forecasting on temporal knowledge graphs[J]. arXiv:2003.13432, 2020.
[102] XIONG S, YANG Y, PAYANI A, et al. TEILP: time prediction over knowledge graphs via logical reasoning[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2024: 16112-16119.
[103] HE Y, ZHANG P, LIU L, et al. HIP network: historical information passing network for extrapolation reasoning on temporal knowledge graph[C]//Proceedings of the 13th International Joint Conference on Artificial Intelligence, 2021: 1915-1921.
[104] PAN J, NAYYERI M, LI Y, et al. HGE: embedding temporal knowledge graphs in a product space of heterogeneous geometric subspaces[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2024: 8913-8920.
[105] XU H, BAO J, LI H, et al. A multi-view temporal knowledge graph reasoning framework with interpretable logic rules and feature fusion[J]. Electronics, 2024, 13(4): 742.
[106] JOBE A, KY R, LUO S, et al. Power grid anomaly detection via hybrid LSTM-GIN model[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2024: 23525-23527.
[107] ZHUANG W, JIANG W, XIA M, et al. Dynamic generative residual graph convolutional neural networks for electricity theft detection[J]. IEEE Access, 2024, 12: 42737-42750.
[108] HAO X, CHEN Y, YANG C, et al. From chaos to clarity: time series anomaly detection in astronomical observations[J]. arXiv:2403.10220, 2024.
[109] REN Z, LI X, PENG J, et al. Graph autoencoder with mirror temporal convolutional networks for traffic anomaly detection[J]. Scientific Reports, 2024, 14(1): 1247.
[110] LIU S, YAO D, FANG L, et al. AnomalyLLM: few-shot anomaly edge detection for dynamic graphs using large language models[J]. arXiv:2405.07626, 2024.
[111] CHEN J, XIONG H, ZHENG H, et al. Dyn-Backdoor: backdoor attack on dynamic link prediction[J]. IEEE Transactions on Network Science and Engineering, 2021, 11: 525-542.
[112] YUAN H, SUN Q, FU X, et al. Dynamic graph information bottleneck[J]. arXiv:2402.06716, 2024.
[113] MASCI J, BOSCAINI D, BRONSTEIN M, et al. Geodesic convolutional neural networks on Riemannian manifolds[C]//Proceedings of the IEEE International Conference on Computer Vision Workshops, 2015: 37-45.
[114] VLASSIS N, SUN W. Geometric learning for computational mechanics Part II: graph embedding for interpretable multiscale plasticity[J]. Computer Methods in Applied Mechanics and Engineering, 2023, 404: 115768.