Journal of Frontiers of Computer Science and Technology ›› 2024, Vol. 18 ›› Issue (10): 2668-2677.DOI: 10.3778/j.issn.1673-9418.2310022

• Theory·Algorithm • Previous Articles     Next Articles

Temporal Link Prediction with Community-Level Information

WU Xiang, GAO Yujin, LI Ronghua, WANG Guoren   

  1. School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China
  • Online:2024-10-01 Published:2024-09-29

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

吴翔,高玉金,李荣华,王国仁   

  1. 北京理工大学 计算机学院,北京 100081

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

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

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