Adaptive Product Space Discrete Dynamic Graph Link Prediction Model

doi:10.3778/j.issn.1673-9418.2408023

Abstract

Abstract: With the widespread application of complex network analysis in many fields, such as recommendation systems, social networks, disease transmission networks, and financial transaction networks, the analysis of dynamic graphs has become a key challenge in the study of graph neural networks. To address the issue of embedding distortion caused by single-space embeddings in dynamic graph neural networks for link prediction, an adaptive product space discrete dynamic graph link prediction model (APSDG) is proposed. This model aims to resolve embedding distortion and enhance the performance of discrete dynamic graph link prediction. By integrating Euclidean space, hyperbolic space and hypersphere space, a product space is constructed as the embedding space to better fit the complex structure of dynamic graph data. To achieve adaptive adjustment of the product space, a reinforcement learning mechanism is designed to dynamically optimize the dimensional proportions and curvature parameters of each space. Experimental results demonstrate that APSDG outperforms baseline models using single-space embeddings across five real-world datasets. In tasks of dynamic link prediction and dynamic new link prediction, APSDG achieves average gains in AUC and AP metrics of 2.24% and 1.90%, 2.12% and 1.43%, respectively. APSDG effectively solves the embedding distortion problem of single space embedding methods, can better capture the hierarchical structure and regular structure of complex networks, and significantly improves the dynamic link prediction effect.

Key words: discrete dynamic graphs, representation learning, link prediction, product space, geometric deep learning, reinforcement learning

摘要： 随着复杂网络分析在诸多领域的广泛应用，如推荐系统、社交网络、疾病传播网络和金融交易网络，动态图的分析成为图神经网络研究的一个关键挑战。针对动态图神经网络在链接预测时因单一空间嵌入导致的嵌入扭曲问题，提出了自适应积空间离散动态图链接预测模型（APSDG），拟解决嵌入扭曲问题，提高离散动态图链接预测性能。通过结合欧几里德空间、双曲空间和超球面空间，构建积空间作为嵌入空间，以更好地拟合动态图数据的复杂结构。为实现积空间的自适应调整，设计了一种强化学习机制，动态优化各空间的维度比例和曲率参数。实验结果表明，APSDG在五个真实世界数据集上优于使用单一空间的基准模型，在动态链接预测和动态新链接预测任务中，AUC和AP指标上的平均增益分别为2.24%和1.90%、2.12%和1.43%，APSDG有效解决了单一空间嵌入方法的嵌入扭曲问题，能够更好地捕捉复杂网络的层次结构和规则结构，显著提升了动态链接预测效果。

关键词: 离散动态图, 表示学习, 链接预测, 积空间, 几何深度学习, 强化学习

CHEN Xu, ZHANG Qi, WANG Shuyang, JING Yongjun. Adaptive Product Space Discrete Dynamic Graph Link Prediction Model[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(7): 1820-1831.

陈旭, 张其, 王叔洋, 景永俊. 自适应积空间离散动态图链接预测模型[J]. 计算机科学与探索, 2025, 19(7): 1820-1831.

References

[1] ZHANG J N, SHI X J, ZHAO S L, et al. STAR-GCN: stacked and reconstructed graph convolutional networks for recommender systems[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. Palo Alto: AAAI, 2019: 4264-4270.
[2] WANG H, LIAN D F, TONG H H, et al. HyperSoRec: exploiting hyperbolic user and item representations with multi-ple aspects for social-aware recommendation[J]. ACM Trans-actions on Information Systems, 2022, 40(2): 1-28.
[3] LIAO L Z, HE X N, ZHANG H W, et al. Attributed social network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(12): 2257-2270.
[4] 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: ACM, 2014: 701-710.
[5] CHAMI I, YING R, Ré C, et al. Hyperbolic graph convolutional neural networks[C]//Advances in Neural Information Processing Systems 32, 2019: 4869-4880.
[6] WEBER M, DOMENICONI G, CHEN J, et al. Anti-money laundering in bitcoin: experimenting with graph convolutional networks for financial forensics[C]//Proceedings of the 2019 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2019.
[7] DOU Y T, LIU Z W, SUN L, et al. Enhancing graph neural network-based fraud detectors against camouflaged fraudsters[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management. New York: ACM, 2020: 315-324.
[8] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[EB/OL]. [2024-06-26]. https:// arxiv.org/abs/1609.02907.
[9] VELI?KOVI? P, CUCURULL G, CASANOVA A, et al. Graph attention networks[C]//Proceedings of the 6th International Conference on Learning Representations, 2018.
[10] SCHLICHTKRULL M, KIPF T N, BLOEM P, et al. Modeling relational data with graph convolutional networks[C]//Proceedings of the 15th International Conference on the Semantic Web. Cham: Springer, 2018: 593-607.
[11] PAREJA A, DOMENICONI G, CHEN J, et al. EvolveGCN: evolving graph convolutional networks for dynamic graphs[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(4): 5363-5370.
[12] CHEN J Y, WANG X K, XU X H. GC-LSTM: graph convolution embedded LSTM for dynamic network link prediction[J]. Applied Intelligence, 2022, 52(7): 7513-7528.
[13] ZHU Y F, CONG F P, 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. New York: ACM, 2023: 3650-3662.
[14] BAI Q J, NIE C L, ZHANG H W, et al. HGWaveNet: a hyper-bolic graph neural network for temporal link prediction[C]//Proceedings of the ACM Web Conference 2023. New York: ACM, 2023: 523-532.
[15] ZHANG K K, CAO Q, FANG G L, et al. DyTed: disentangled representation learning for discrete-time dynamic graph[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2023: 3309-3320.
[16] YAO H Y, YU Y L, ZHANG C Y, et al. Fuzzy representation learning on dynamic graphs[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2024, 54(2): 878-890.
[17] CONG W, ZHANG S, KANG J, et al. Do we really need complicated model architectures for temporal networks?[C]//Proceedings of the 11th International Conference on Learning Representations, 2023.
[18] CHEN C, GENG H Y, YANG N Z, et al. EasyDGL: encode, train and interpret for continuous-time dynamic graph learning[EB/OL]. [2024-06-26]. https://arxiv.org/abs/2303.12341.
[19] XIA W W, LI Y C, LI S H. Graph neural point process for temporal interaction prediction[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(5): 4867-4879.
[20] GRAVES A. Long short-term memory[M]//Supervised sequence labelling with recurrent neural networks. Berlin, Heidelberg: Springer, 2012: 37-45.
[21] CHO K, VAN MERRIENBOER B, GULCEHRE C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation[C]//Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing. Stroudsburg: ACL, 2014: 1724-1734.
[22] CUI X, SONTHALIA R. Hyperbolic and mixed geometry graph neural network[C]//Proceedings of the NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations, 2022.
[23] GULCEHRE C, DENIL M, MALINOWSKI M, et al. Hyper-bolic attention networks[C]//Proceedings of the 6th International Conference on Learning Representations, 2018: 6527-6533.
[24] LEI H, AKHTAR N, MIAN A. Spherical kernel for efficient graph convolution on 3D point clouds[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(10): 3664-3680.
[25] GU A, SALA F, GUNEL B, et al. Learning mixed-curvature representations in products of model spaces[C]//Proceedings of the 7th International Conference on Learning Representations, 2019.
[26] GANEA O E, BéCIGNEUL G, HOFMANN T. Hyperbolic neural networks[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018: 5350-5360.
[27] WANG Y B, LI P, BAI C Y, et al. TEDIC: neural modeling of behavioral patterns in dynamic social interaction networks[C]//Proceedings of the Web Conference 2021. New York: ACM, 2021: 693-705.
[28] CAI L, CHEN Z 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. New York: ACM, 2021: 3747-3756.
[29] ZHOU F, XU X, LI C, et al. A heterogeneous dynamical graph neural networks approach to quantify scientific impact[EB/OL]. [2024-06-26]. https://arxiv.org/abs/2003.12042.
[30] BAI S, KOLTER J Z, KOLTUN V. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling[EB/OL]. [2024-06-26]. https://arxiv.org/abs/1803.01271.
[31] NARAYAN A, O??N ROE P H. Learning graph dynamics using deep neural networks[J]. IFAC-PapersOnLine, 2018, 51(2): 433-438.
[32] YANG M L, 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 and Data Mining. New York: ACM, 2021: 1975-1985.
[33] LI H, JIANG H, YE D S, et al. DHGAT: hyperbolic representation learning on dynamic graphs via attention networks[J]. Neurocomputing, 2024, 568: 127038.
[34] GODINHO L, NATáRIO J. An introduction to Riemannian geometry: with applications to mechanics and relativity[M]. Berlin, Heidelberg: Springer, 2012.
[35] YANG M L, ZHOU M, LI Z H, et al. Hyperbolic graph neural networks: a review of methods and applications[EB/OL]. [2024-06-29]. https://arxiv.org/abs/2202.13852.
[36] PENG W, VARANKA T, MOSTAFA A, et al. Hyperbolic deep neural networks: a survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44(12): 10023-10044.
[37] YANG C T. On maps from spheres to Euclidean spaces[J]. American Journal of Mathematics, 1957, 79(4): 725.
[38] SHIN H Y, OH H S. Robust geodesic regression[J]. International Journal of Computer Vision, 2022, 130(2): 478-503.
[39] UNGAR A A. The hyperbolic square and mobius transformations[J]. Banach Journal of Mathematical Analysis, 2007, 1(1): 101-116.
[40] FU X C, LI J X, WU J, et al. ACE-HGNN: adaptive curvature exploration hyperbolic graph neural network[C]//Proceedings of the 2021 IEEE International Conference on Data Mining. Piscataway: IEEE, 2021: 111-120.
[41] CUI Q, WU S, HUANG Y, et al. A hierarchical contextual attention-based network for sequential recommendation[J]. Neurocomputing, 2019, 358: 141-149.
[42] KRIOUKOV D, PAPADOPOULOS F, KITSAK M, et al. Hyperbolic geometry of complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2010, 82: 036106.
[43] WATKINS C J C H, DAYAN P. Q-learning[J]. Machine Learning, 1992, 8(3): 279-292.
[44] PETERS J. Policy gradient methods[J]. Scholarpedia, 2010, 5(11): 3698.
[45] ZHANG Y D, WANG X, SHI C, et al. Hyperbolic graph attention network[J]. IEEE Transactions on Big Data, 2022, 8(6): 1690-1701.
[46] 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. Cham: Springer, 2018: 362-373.
[47] BENSON A R, ABEBE R, SCHAUB M T, et al. Simplicial closure and higher-order link prediction[J]. Proceedings of the National Academy of Sciences of the United States of America, 2018, 115(48).
[48] HAJIRAMEZANALI E, HASANZADEH A, DUFFIELD N, et al. Variational graph recurrent neural networks[EB/OL]. [2024-06-29]. https://arxiv.org/abs/1908.09710.
[49] LESKOVEC J, KLEINBERG J, FALOUTSOS C. Graphs over time: densification laws, shrinking diameters and possible explanations[C]//Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York: ACM, 2005: 177-187.
[50] ROSSI R, AHMED N. The network data repository with inter-active graph analytics and visualization[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2015, 29(1): 4292-4293.