融合社团信息的时序图链路预测算法

doi:10.3778/j.issn.1673-9418.2310022

摘要/Abstract

摘要： 时序图旨在表示现实世界中实体之间的时序交互关系，而时序图链路预测是建模这种关系的重要方法。现有基于表示学习的时序图链路预测方法通常基于时序图神经网络建模节点之间交互，并将时间信息融入到图神经网络的消息传递机制中以捕捉交互中的时序关联。时序图神经网络输出的节点嵌入作为时序图表示学习的结果被用于链路预测任务。然而，现有的方法仅考虑了节点之间的交互，而忽视了时序图中广泛存在的社团结构。为解决这一问题，提出一种融合社团信息的时序图链路预测算法（TLPC）。不同于传统社区划分的方法，该方法关注节点邻域社团的表示学习。在节点特征的基础上，引入对比学习技术，使用邻域结构特征采样出正样本和负样本进行对比学习约束，以编码节点所在邻域社团。所学习到的节点邻域社团编码可以有效提升节点嵌入的表示能力，从而提升链路预测的有效性。在四个真实数据集上的时序链路预测任务的实验结果表明，TLPC的准确率相比现有方法平均提升6.47%，F1平均提升6.77%，同时训练时间平均减少62.27%。

关键词: 时序图链路预测, 社团结构, 对比学习

Abstract: Temporal graphs aim to characterize the dynamic interactions among entities in real-world scenarios, while temporal link prediction is an essential method for modeling such relationships. Existing representation learning-based methods for temporal graph link prediction typically involve designing temporal graph neural networks to model interactions between nodes. The message-passing mechanisms of graph neural networks are incorporated with temporal information, enabling the models to generate time-specified embeddings for link prediction tasks. However, existing methods only consider interactions between nodes, neglecting the prevalent community structure in temporal graphs. To address this limitation, this paper proposes a temporal link prediction algorithm, TLPC (temporal link prediction enhanced by community-level information). Unlike traditional community detection methods, this paper focuses on representing the neighbor communities of a node. Leveraging contrastive learning techniques on top of node features, positive and negative samples are sampled based on neighborhood structural features for contrastive learning constraints, encoding the neighbor communities of nodes. The learnt encoding of node neighborhood communities effectively enhances the representation ability of node embeddings, thereby improving link prediction effectiveness. Experimental results on four real-life datasets for temporal link prediction tasks demonstrate that TLPC achieves an average accuracy increase of 6.47% and an average F1 score increase of 6.77% compared with existing methods, while simultaneously reducing training time by an average of 62.27%.

Key words: temporal link prediction, community structure, contrastive learning

吴翔, 高玉金, 李荣华, 王国仁. 融合社团信息的时序图链路预测算法[J]. 计算机科学与探索, 2024, 18(10): 2668-2677.

WU Xiang, GAO Yujin, LI Ronghua, WANG Guoren. Temporal Link Prediction with Community-Level Information[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(10): 2668-2677.

参考文献

[1] DU Z, WANG X, YANG H, et al. Sequential scenario-specific meta learner for online recommendation[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Anchorage, Aug 4-8, 2019. New York: ACM, 2019: 2895-2904.
[2] 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.
[3] 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, Chicago, Aug 21-24, 2005. New York: ACM, 2005: 177-187.
[4] GILMER J, SCHOENHOLZ S S, RILEY P F, et al. Neural message passing for quantum chemistry[C]//Proceedings of the 2017 International Conference on Machine Learning, Sydney, Aug 6-11, 2017: 1263-1272.
[5] PAREJA A, DOMENICONI G, CHEN J, et al. EvolveGCN: evolving graph convolutional networks for dynamic graphs[C]//Proceedings of the 2020 AAAI Conference on Artificial Intelligence, New York, Feb 7-12, 2020. Menlo Park: AAAI, 2020: 5363-5370.
[6] SANKAR A, WU Y, GOU L, et al. DySAT: deep neural representation learning on dynamic graphs via self-attention networks[C]//Proceedings of the 13th International Conference on Web Search and Data Mining, Houston, Feb 3-7, 2020. New York: ACM, 2020: 519-527.
[7] HOCHREITER S, SCHMIDHUBER J. Long short-term memory[J]. Neural Computation, 1997, 9(8): 1735-1780.
[8] 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, Siem Reap, Dec 13-16, 2018. Cham: Springer, 2018: 362-373.
[9] NGUYEN G H, LEE J B, ROSSI R A, et al. Continuous-time dynamic network embeddings[C]//Companion of the Web Conference 2018, Lyon, Apr 23-27, 2018. New York: ACM, 2018: 969-976.
[10] XU D, RUAN C, KORPEOGLU E, et al. Inductive representation learning on temporal graphs[C]//Proceedings of the 8th International Conference on Learning Representations, Addis Ababa, Apr 26-30, 2020.
[11] WANG Y, CHANG Y Y, LIU Y, et al. Inductive representation learning in temporal networks via causal anonymous walks[C]//Proceedings of the 9th International Conference on Learning Representations, Vienna, May 3-7, 2021.
[12] ZUO Y, LIU G, LIN H, et al. Embedding temporal network via neighborhood formation[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2857-2866.
[13] 朱小虎, 宋文军, 王崇骏，等. 用于社团发现的Girvan-Newman改进算法[J]. 计算机科学与探索, 2010, 4(12): 1101-1108.
ZHU X H, SONG W J, WANG C J, et al. Improved algorithm based on Girvan-Newman algorithm for community detection[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(12): 1101-1108.
[14] 陈洁, 张二明, 王倩倩，等. K阶图卷积属性网络社团检测方法[J]. 计算机科学与探索, 2022, 16(12): 2788-2796.
CHEN J, ZHANG E M, WANG Q Q, et al. Method of K-order graph convolution attribute network community detection[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(12): 2788-2796.
[15] LI T, WANG W, JIAO P, et al. Exploring temporal community structure via network embedding[J]. IEEE Transactions on Cybernetics, 2023, 53(11): 7021-7033.
[16] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Advances in Neural Information Processing Systems 30, Long Beach, Dec 4-9, 2017: 5998-6008.
[17] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C]//Proceedings of the 5th International Conference on Learning Representations, Toulon, Apr 24-26, 2017.
[18] ZHOU L, YANG Y, REN X, et al. Dynamic network embedding by modeling triadic closure process[C]//Proceedings of the 2018 AAAI Conference on Artificial Intelligence, New Orleans, Feb 2-7, 2018. Palo Alto: AAAI Press, 2018: 571-578.
[19] 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, Washington, Aug 14-18, 2022. New York: ACM, 2022: 2358-2366.
[20] WEN Z, FANG Y. TREND: temporal event and node dynamics for graph representation learning[C]//Proceedings of the ACM Web Conference 2022, Lyon, Apr 25-29, 2022. New York: ACM, 2022: 1159-1169.
[21] 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.
[22] SOUZA A, MESQUITA D, KASKI S, et al. Provably expressive temporal graph networks[C]//Proceedings of the 36th Conference on Neural Information Processing Systems, Nov 28-Dec 5, 2022: 32257-32269.
[23] XU K, HU W, LESKOVEC J, et al. How powerful are graph neural networks?[C]//Proceedings of the 11th International Conference on Learning Representations, May 6-9, 2019.
[24] HAWKES A G. Spectra of some self-exciting and mutually exciting point processes[J]. Biometrika, 1971, 58(1): 83-90.
[25] LU Y, WANG X, SHI C, et al. Temporal network embedding with micro-and macro-dynamics[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management, Beijing, Nov 3-7, 2019. New York: ACM, 2019: 469-478.
[26] YIN H, BENSON A R, LESKOVEC J, et al. Local higher-order graph clustering[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, Aug 13-17, 2017. New York: ACM, 2017: 555-564.
[27] 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.
[28] VELI?KOVI? P, FEDUS W, HAMILTON W L, et al. Deep graph infomax[C]//Proceedings of the 7th International Conference on Learning Representations, New Orleans, May 6-9, 2019.
[29] 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 and Data Mining, Anchorage, Aug 4-8, 2019. New York: ACM, 2019: 1269-1278.
[30] HAMILTON W, YING Z, LESKOVEC J. Inductive representation learning on large graphs[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, Long Beach, Dec 4-9, 2017. New York: ACM, 2017: 30.
[31] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of the 2013 International Conference on Neural Information Processing Systems, Lake Tahoe, Dec 5-8, 2013. New York: ACM, 2013: 3111-3119.
[32] KINGMA D P,?BA J. Adam: a method for stochastic optimization[C]//Proceedings of the 3th International Conference on Learning Representations, San Diego, May 7-9, 2015.