Time-constrained walk fused memory enhanced temporal graph neural network

doi:10.11918/202406018

融合时间约束游走的记忆增强时序图神经网络

doi: 10.11918/202406018

金志刚¹ ，张浩¹ ，苏仁鋆² ，赵晓芳³

1. 天津大学电气自动化与信息工程学院，天津 300072

2. 天津大学党委宣传部，天津 300072

3. 天津城建大学计算机与信息工程学院，天津 300072

基金项目: 国家自然科学基金(52171337)

详细信息

作者简介

金志刚（1972—），男，教授，博士生导师

通讯作者

金志刚，zgjin@tju.edu.cn

中图分类号: TP183

文献标识码: A

文章编号: 0367-6234(2025)09-0029-10

Time-constrained walk fused memory enhanced temporal graph neural network

JIN Zhigang¹ ， ZHANG Hao¹ ， SU Renjun² ， ZHAO Xiaofang³

1. School of Electrical and Information Engineering, Tianjin University, Tianjin 300072 , China

2. Publicity Department, Tianjin University, Tianjin 300072 , China

3. School of Computer and Information Engineering, Tianjin Chengjian University, Tianjin 300072 , China

摘要

为解决现有时序图表示学习方法难以充分挖掘网络结构特征和依赖关系的问题，提出了一种融合时间约束游走的记忆增强时序图神经网络(time-constrained walk fused memory enhanced temporal graph neural network，TWMTGN)。首先，从交互节点出发构造特定类型的时间约束游走序列,采用记忆模块捕获网络的长期依赖关系，并将游走序列特征融合至节点记忆状态，在事件发生时进行动态更新；其次，根据节点类型和时间间隔设计特征衰减层，建模短期依赖关系，提高模型对关键历史交互节点的识别能力；最后，将目标节点聚合后的历史交互特征输入因果卷积网络，进一步挖掘特征之间的潜在关联。在真实数据集上的实验结果表明：所提网络能够提升时间链路预测任务的效果，且复杂度较小；时间约束游走长度和次数等参数会影响模型的性能。研究提出的时间约束游走序列能够捕捉网络结构特征，节点记忆和特征衰减层有助于捕获网络依赖关系。

关键词

时序网络 / 游走 / 记忆 / 特征衰减 / 因果卷积

Abstract

To address the challenges faced by existing temporal graph representation learning methods in fully exploiting structural features and dependencies of the network, a time-constrained walk fused memory enhanced temporal graph neural network (TWMTGN) is proposed. Firstly, a specific type of temporal constraint walk sequence is constructed for the interaction node, and the memory module is used to capture the long-term dependence of the network. The walk sequence features are fused into the memory of interaction node, which is dynamically updated upon the occurance of events. Secondly, a feature attenuation layer is designed according to the node type and time interval to model short-term dependencies, which improves the model′s ability to identify key historical interaction nodes. Finally, the aggregated historical interaction features of the target node are fed into a causal convolutional network to further uncover the potential association between them. Experimental results on real datasets show that the proposed network can improve the performance of temporal link prediction tasks while maintaining relatively low complexity. Parameters such as the length and frequency of time-constrained walks affect the mode′s performance. The proposed time-constrained walk sequences can effectively capture the structural features of the network, while the node memory and feature attenuation layers help to capture the network dependencies.

Keywords

temporal network / walk / memory / feature attenuation / causal convolution

1 融合时间约束游走的记忆增强时序图神经网络 1.1 相关定义 1.2 TWMTGN 1.2.1 构造时间约束游走序列 1.2.2 记忆模块 1.2.3 消息函数 1.2.4 消息聚合和记忆更新 1.2.5 节点嵌入表示 1.2.6 特征衰减和因果卷积 1.2.7 模型训练 2 实验结果与分析 2.1 评价指标和数据集 2.2 基线模型 2.3 对比实验 2.4 复杂度分析 2.5 消融实验 2.6 参数灵敏度分析 3 结论

随着图数据应用的日益广泛，如何对图数据进行建模，并将节点表示为下游任务的低维嵌入向量已成为研究人员关注的重要问题。图神经网络是一种图数据的深度学习方法^[1]，是解决图表示学习问题的有效方法。现实世界的图网络一般都是动态的，拓扑结构随着时间不断变化。对动态网络进行表示学习具有挑战性，但意义重大。动态网络描述了网络如何交互和演化，有助于理解和预测系统的行为^[2]，相关研究成果已应用于欺诈检测^[3]、网络安全^[4]和推荐系统^[5]等领域。

动态图表示学习算法分为离散网络嵌入和连续网络嵌入两大类。离散网络嵌入一般将图分解为几个静态快照，利用静态方法对每个快照进行编码，但这种方法往往忽略了同一快照内的时间信息，无法捕捉复杂的时间动态。连续网络也被称为时序网络，可以表示为交互事件的有序序列，每个事件均与一个连续的时间相关联。时序网络通过在不同交互作用之间传递信息或利用连续时间函数生成嵌入表示来捕捉时间动态^[6]，其动态性往往表现在微观和宏观两个层面^[7]。网络的微观变化是一种短期的变化规律，通常体现在节点的交互事件直接对其他节点产生的影响，其会随时间不断衰减；网络的宏观变化是一种长期、稳定的演变规律，表现在网络的拓扑结构遵循一定的变化模式。因此，时序图表示学习模型需要建模短期和长期依赖关系，并进一步挖掘网络演变规律。

在时序网络的相关研究中，Kumar等^[8]利用循环神经网络（recurrent neural network，RNN）和依赖于时间的投影嵌入模块学习用户-项目交互网络的节点表示；Xu等^[9]将自注意力应用于时序图的归纳表示学习，设计了一种时间编码器，将连续时间投影为时间向量；Rossi等^[10]提出一种编码时序图的通用框架，将节点记忆引入时序图注意力网络的时间特征聚合阶段，允许模型学习数据的顺序性。然而，这些方法未明确利用图的拓扑结构信息。Luo等^[11]设计了一种新的邻域结构特征表示方法，该方法从节点的联合领域中提取关键结构信息；Wang等^[12]提出了一种因果关系匿名游走策略，该策略通过隐藏节点身份捕捉网络变化规律，采用RNN对游走序列进行编码；Zhou等^[13]将元路径实例抽象为语义单元，考虑其相互作用来挖掘更深层次的语义信息，并利用霍克斯过程（Hawkes process）建模时序信息。但这些方法缺乏对长期依赖关系的捕获。Trivedi等^[14]考虑网络拓扑结构和节点交互的变化进行网络的表示学习，在事件发生后更新节点表示，对于长期没有交互的节点存在嵌入过时问题。

鉴于此，本文提出了一种融合时间约束游走的记忆增强时序图神经网络（time-constrained walk fused memory enhanced temporal graph neural network，TWMTGN），以挖掘网络的结构特征和依赖关系，联合建模网络异质性和动态性，提高节点表示性能。模型采用采样—更新—聚合机制，考虑图结构特征更新节点记忆状态，聚合历史交互节点特征，获得目标节点嵌入表示。具体来说，对于每一条新边，从两个交互节点出发，考虑时间约束对邻居节点进行采样，构造特定类型的游走序列，并对其进行编码，在全局视角下捕捉网络拓扑结构的演变模式，学习网络的长期变化规律；采用记忆模块保存节点历史状态，当事件发生时，更新节点记忆，捕捉网络长期依赖关系；依据节点类型和时间间隔设计特征衰减层，降低时间间隔较远节点的影响，建模网络短期依赖关系；利用因果卷积网络捕获历史交互节点时序特征的潜在关联，最终获得交互节点嵌入表示，应用于时间链路预测任务。

1 融合时间约束游走的记忆增强时序图神经网络

1.1 相关定义

1）时序图。时序图可以表示为带有时间的边集合，记作G={（u，v，t）|u，v∈X，t∈T}，其中，u与v表示交互节点，t表示对应边的时间，X为节点集合，T为时间集合。每条边表示一个事件，具有对应的特征向量。

2）元路径。时序图的丰富语义可以由元路径获取。元路径是通过节点类型和边类型定义的序列，可以表示一组连接多种类型节点的复合关系^[15]。元路径实例是按照元路径定义，从图中抽取的连续节点序列。

3）时间链路预测。给定一个时序图G，利用t之前的历史信息{（u′，v′，t′）}∈G学习一种揭示网络随时间变化关系和模式的映射函数

X \to R^{d} ， d ≪

|X|，将网络中的节点映射到低维向量空间，利用低维稠密向量预测两个节点在时间t是否会有新的边建立。

1.2 TWMTGN

TWMTGN采用记忆模块存储节点状态，并将图的拓扑结构信息融合至节点记忆的更新过程，框架如图1所示。模型利用时间约束游走序列捕获网络的拓扑结构特征，将节点的记忆状态作为节点过去交互的压缩表征。为了更有效地聚合历史交互节点特征，基于节点类型和交互时间间隔设计特征衰减层，提取目标节点的关键历史交互特征，并利用因果卷积网络挖掘其潜在关联；最终形成节点的嵌入向量表示，应用于时间链路预测任务。

图1TWMTGN框架

Fig.1Framework of TWMTGN

1.2.1 构造时间约束游走序列

时间约束游走序列可以确定每个交互节点的影响范围。图1中②、③分别给出了在边（u₁，v₃，t₁₃）出现时，以不同类型节点为起点，构造时间约束游走序列的过程。在时间t₁₃分别从交互节点u₁和v₃出发构造两个路径子集：

p_{u}^{t} = \{p_{u}^{t, 1}, p_{u}^{t, 2}, \dots, p_{u}^{t, k}\}

(1)

p_{v}^{t} = \{p_{v}^{t, 1}, p_{v}^{t, 2}, \dots, p_{v}^{t, k}\}

(2)

式中k为游走序列数量。子集中的游走序列长度均相同，满足相应的元路径定义关系。

游走序列的本质是抽取网络子结构，更全面地利用网络的拓扑结构信息。表1为在LastFM数据集上，以用户（user，U）和物品（item，I）两种类型节点为起点，构造不同长度游走序列的结果。

表1LastFM不同游走长度结果

Tab.1Results of different walk lengths for LastFM

1.2.2 记忆模块

节点记忆由一组向量组成，是节点历史交互特征的压缩表示。对于时间t的节点i，其记忆向量s_i（t）在事件发生时利用RNN进行更新，反映这一事件的影响，使模型持续学习新出现的节点和边特征。该机制使得模型能够捕获网络长期依赖关系，对于理解和预测时序图中的复杂行为至关重要^[10]。

1.2.3 消息函数

消息函数是记忆更新的主要机制。给定时间t节点u和v之间的交互（u，v，t），消息函数计算出两条消息用于更新u和v的节点记忆。当事件发生时，将事先构造的、分别以节点u和v为起点的时间约束游走序列输入一个可训练的嵌入层进行编码，然后将获得的游走序列特征应用至消息函数中。

m_{u, v} (t) = f_{m s g} (w_{u} (t), s_{u} (t), s_{v} (t), ϕ (t - t_{u}), e_{v}^{t})

(3)

m_{v, u} (t) = f_{m s g} (w_{v} (t), s_{v} (t), s_{u} (t), ϕ (t - t_{v}), e_{u}^{t})

(4)

式中：

m_{u ， v} （ t ）

、

m_{v ， u} （ t ）

分别为节点u、v的消息向量；w_u（t）、w_v（t）为编码后的游走序列特征向量； s_u（t）、s_v（t）分别为节点u、v的记忆向量；

e_{u}^{t}

、

e_{v}^{t}

分别为节点u、v用于更新消息的边特征向量；t_u、t_v分别为节点u、v上次更新记忆的时间；φ（·）为一种通用时间编码^[9]，用于捕捉时间依赖关系； f_msg（·）为可学习的消息函数。为减少计算量，仅将输入的多特征向量进行拼接。

1.2.4 消息聚合和记忆更新

为提高训练效率，采用批处理的方式训练模型。同一批次中涉及节点i的事件可能出现多次，每个涉及节点i的事件均会生成一条消息。因此，需要对消息进行聚合并更新节点记忆。

m_{i} (t) = f_{agg} (\{m_{i, p} (t_{n}) ∣ (i, p, t_{n}) \in J (i, t), t_{n} ⩽ t\})

(5)

s_{i} (t^{+}) = f_{u p d} (s_{i} (t), m_{i} (t))

(6)

式中：m_i（t）为聚合后的消息向量；J（i，t）为在时间t涉及节点i的事件集；s_i（t）、s_i（t⁺）分别为节点i更新前后的状态向量；f_agg（·）为消息聚合函数，用于聚合时间t同一批次内涉及节点i的最新事件消息，生成节点新的记忆状态；f_upd（·）为记忆更新函数，采用门控循环网络实现。

1.2.5 节点嵌入表示

由于节点记忆仅在涉及该节点的事件发生时才被更新，当长时间没有事件发生时（例如，社交平台用户在某段时间突然停止使用该平台），节点记忆存在过时问题^[10]。为解决该问题，在与目标节点时空邻近的节点上执行图聚合操作，计算任意时间目标节点的嵌入表示。即使一个节点在一段时间内处于非活动状态，但与其邻近的一些节点可能处于活动状态。因此，通过聚合时空邻近节点的特征，并结合时间衰减特性和因果卷积网络，计算目标节点的最新嵌入表示。

与节点u在时间t及之前产生交互的最近N个历史交互节点集可以表示为

N (u, t) = \{(v_{j}, e_{v_{j}}^{t_{j}}, t_{j}) ∣ j \in [1, N], t_{j} ⩽ t, (u, v_{j}, t_{j}) \in G\}

(7)

式中

(v_{j} ， e_{v_{j}}^{t_{j}} ， t_{j}) \in N （ u ， t ）

。下文将

(v_{j} ， e_{v_{j}}^{t_{j}} ， t_{j})

简写为（v，e，t′）。

TWMTGN通过递归计算节点u在第l层的嵌入过程表示为:

{\tilde{h}}_{u}^{l} (t) = f_{A G G} ({\tilde{h}}_{v}^{(l - 1)} (t), ϕ (t - t^{'}), e)

(8)

h_{u}^{l} (t) = f_{U P D} (h_{u}^{(l - 1)} (t), {\tilde{h}}_{u}^{l} (t))

(9)

式中：

{\tilde{h}}_{u}^{l} （ t ）

、

{\tilde{h}}_{v}^{（ l - 1 ）} （ t ）

分别为第l层和第l-1层历史交互节点聚合后的特征表示；

h_{u}^{l} （ t ）

、

h_{u}^{（ l - 1 ）} （ t ）

分别为第l层和l-1层目标节点的嵌入表示；t′为上次交互的时间；φ（t-t′）为编码后的时间；f_UPD（·）为更新函数，采用多层感知机实现；f_AGG（·）为聚合函数，聚合历史交互节点特征。目标节点的初始表示采用其记忆状态，即

h_{u}^{0} （ t ） = S_{u} (t^{+})

。

聚合函数f_AGG（·）采用多头注意力机制实现，表示为:

{\tilde{h}}_{u}^{l} (t) = f_{A T T} (Q^{l} (t), K^{l} (t), V^{l} (t))

(10)

Q^{l} (t) = h_{u}^{(l - 1)} (t) ‖ ϕ (0)

(11)

\begin{matrix} K^{l} (t) = V^{l} (t) = \\ [h_{v_{1}}^{(l - 1)} (t) ‖e_{v_{1}}^{t_{1}}‖ ϕ (t - t_{1}), \dots, \\ h_{v_{N}}^{(l - 1)} (t) ‖e_{v_{N}}^{t_{N}}‖ ϕ (t - t_{N})] \end{matrix}

(12)

式中：f_ATT（·）为多头注意力网络，{t₁，···，t_N}为每个历史交互节点对应的时间，

\{e_{v_{1}}^{t_{1}} ， \dots ， e_{v_{N}}^{t_{N}}\}

为对应的边特征，

\{h_{v_{1}}^{（ l - 1 ）} （ t ） ， \dots ， h_{v_{N}}^{（ l - 1 ）} （ t ）\}

为截至时间t与节点u产生交互的最近N个历史交互节点的表示，

Q^{l} （ t ）

为聚合了目标节点自身特征的向量，

K^{l} （ t ）

和

V^{l} （ t ）

为聚合了目标节点历史交互特征的向量。

1.2.6 特征衰减和因果卷积

从时序图学习的网络嵌入不仅应该捕捉网络结构特征，而且要反映网络演化过程。为了模拟过去事件对现在产生的影响，更准确地建模网络演化过程，本文考虑节点类型和时间衰减特性设计了特征衰减层，以捕捉目标节点关键历史交互节点的特征。

h_{v_{n}}^{*} (t) = h_{v_{n}} (t) \cdot f_{d e} (σ (α_{ψ (n)}) \cdot (t - t_{n}))

(13)

式中：n∈{1，···，N}；f_de（·）为衰减函数，定义为f_de（x）=1/log（e+x）；α_ψ_（_n_）为特定于节点类型的可训练参数；σ（·）为激活函数，σ=1/（1+e^-x）是为了约束（t-t_n）的系数在（0，1）内。更新后的

K^{l} （ t ）

和

V^{l} （ t ）

计算式为

\begin{matrix} K^{l} (t) = V^{l} (t) = \\ [h_{v_{1}}^{* (l - 1)} (t) ‖e_{v_{1}}^{t_{1}}‖ ϕ (t - t_{1}), \dots, \\ h_{v_{N}}^{* (l - 1)} (t) ‖e_{v_{N}}^{t_{N}}‖ ϕ (t - t_{N})] \end{matrix}

(14)

式中

h_{v_{1}}^{* （ l - 1 ）} （ t ） ， \dots ， h_{v_{N}}^{* （ l - 1 ）} （ t ）

为节点u最近N个历史交互节点经过特征衰减层后的表示。

因果卷积网络结合了因果卷积和膨胀卷积技术，能够有效捕捉时间序列数据中的因果关系和时间序列中的潜在依赖关系^[16]。在时序图中，节点之间的交互也可以被看作是一种时间序列数据，节点的特征可能随着时间的推移而变化。在进行多头注意力计算时，将因果卷积网络应用至

K^{l} （ t ）

和

V^{l} （ t ）

的计算中，得到因果卷积网络输出后的值：

K^{* l} (t) = V^{* l} (t) = f_{causal} (K^{l} (t))

(15)

式中f_causal（·）为因果卷积网络。

聚合历史交互节点特征的过程如图2所示。将历史交互节点经过特征衰减层和时间编码层后获得的特征表示与边特征进行拼接，输入因果卷积网络，获得聚合后的历史交互节点特征。

图2聚合目标节点历史交互特征

Fig.2Aggregate the historical interaction features for target node

1.2.7 模型训练

对于时间链路预测任务，通过构造正负样本将其转化为二分类任务。将给定时序图中存在的边均视为正样本（即正边），不存在的边均视为负样本（即负边），利用负采样策略^[17]解决数据不平衡问题，并利用二元交叉熵损失（BCE-loss，L_BCE）函数训练。L_BCE表达式为

(16)

式中：F为负样本数量，P_n（v）为节点空间中的负采样分布，

F E_{v_{q} \sim P_{n} （ v ）}

为期望值。

TWMTGN的训练过程见算法1。

算法1 TWMTGN的训练过程:

input:时序图G={（u，v，t）}; 边特征{e}; 历史交互节点数量N; 网络层数L

output:正负样本得分S_pos，S_neg

1. for (u, v, t) in G do

2. Generate p^t_u and p^t_v % 为u和v构造时间约束游走序列

3 . end for

4. for each batch (u, v, t) in G do

5. m_u_，_v（t）← f_msg（p^t_u，s_u（t），t，t_u，e）% 计算消息

6. m_u（t）← f_agg（m_u_，_v（t））% 聚合同一节点消息

7. s_u（t⁺）← f_upd（s_u（t），m_u（t））% 更新节点记忆

8 . for l=1, ···, L do

h_{v_{n}}^{* （ l - 1 ）} （ t ） \leftarrow h_{v_{n}}^{（ l - 1 ）} （ t ） ， n \in {1 ， \dots ， N}

% 特征衰减层

10.

K^{l} （ t ） ， V^{l} （ t ） \leftarrow f_{causal} (h_{v_{n}}^{* （ l - 1 ）} （ t ） ， e_{v_{n}}^{t_{n}} ， t - t_{n}) ， n \in {1 ， \dots ， N}

%因果卷积层

11.

{\tilde{h}}_{u}^{l} （ t ） \leftarrow f_{A T T} (Q^{l} （ t ） ， K^{l} （ t ） ， V^{l} （ t ）)

% 聚合目标节点和历史交互节点特征

12.

h_{u}^{l} （ t ） \leftarrow f_{U P D} (h_{u}^{（ l - 1 ）} （ t ） ， {\tilde{h}}_{u}^{l} （ t ）)

% 更新目标节点特征

13 . end for

14 . end for

15. Calculate L_BCE, do back-propagation and update parameters

16. return S_pos, S_neg

2 实验结果与分析

采用时间链路预测任务评估模型的有效性，具体采用直推式和归纳式两种实验设置全面评估模型在预测未知链路方面的能力。直推式设置即利用训练集中的数据预测那些已知的节点在未来的链接情况；归纳式设置即基于模型所学习到的网络特性，预测那些在训练集中未曾出现过的节点的未来链接。实验在Intel（R）Core（TM）i5-12600KF CPU和NVIDIA GeForce RTX 3060 GPU上运行。

2.1 评价指标和数据集

参考文献^[6，18]，实验采用受试者工作特征曲线下面积A和平均准确率P作为评价指标。A衡量模型在不同阈值下对正负样本的区分能力，P衡量模型在不同召回率下的平均准确率。A、P值越大代表性能越好。

选取LastFM、MOOC、UCI和Enron 4个数据集进行实验，详细信息见表2。

1）LastFM。该数据集记录了用户听歌的历史数据信息，包含1 000名用户和1 000首最常听的歌曲，产生了1 293 103次互动。

2）MOOC。该数据集记录了用户点击在线课程或回答的数据，包含7 047名用户（user）和97个项目（item，包括video、answer等），共有411 749次互动。

3）UCI。该数据集记录了大学生在论坛上发表的帖子，包含1 899名用户，产生了59 834次互动。

4）Enron。该数据集记录了公司员工之间发送的电子邮件，包含184名用户，产生了125 235次互动。

表2数据集统计

Tab.2Statistics of datasets

2.2 基线模型

为评估TWMTGN的有效性，采用时序图注意力网络（temporal graph attention network，TGAT）^[9]、时序图网络（temporal graph network，TGN）^[10]、邻居感知时序网络（neighborhood-aware temporal network，NAT）^[11]、基于因果匿名游走的网络（causal anonymous walk，CAW）^[12]、位置编码映射时序图网络（position-encoding injective temporal graph net，PINT）^[19]5种先进的时序图网络模型作为基线比较模型。其中，TGAT和TGN通过聚合事件触发的时间子图建模节点动态；CAW和NAT是构造邻域结构特征的模型；PINT在TGN基础上进行优化，探索了时序图的表达能力。

1）TGAT设计一种时间感知图注意力网络，用于时序图上的归纳表示学习，采用新的时间编码方法，结合自注意力机制处理连续时间，捕捉节点和拓扑结构的时序特征。

2）TGN提出一种对以时间事件序列表示的动态图进行深度学习的通用框架，利用一种新的训练策略允许模型从数据的顺序性中学习，并保持高效的并行处理能力。

3）CAW提出一种因果关系匿名游走策略，通过时间随机游走自动提取并表示时序网络中的动态模式，采用新颖的匿名化策略保持方法的归纳性，建立网络模式之间的相关性。

4）NAT提出一种邻域感知的时序网络模型，采用基于字典类型的邻域表示，允许快速构建多个节点联合邻域的结构特征，并设计一种N-缓存（N-cache）数据结构支持并行访问和更新邻域表示。

5）PINT提出一种新的时序图网络架构，采用注入式时序信息聚合和更新函数捕捉时间优先级，引入相对位置特征增强模型对图结构的理解，在图的表达能力方面得到强化。

2.3 对比实验

TWMTGN利用PyTorch框架实现，模型参数设置参考文献^[10]。采用早停法以避免过拟合，并设置耐心值为5，训练轮次为50，批大小为200，注意力头数为2，学习率为0.000 1，随机失活率为0.1。为公平地进行比较，所有数据预处理后的输入格式一致，多次运行取平均值得到对比实验结果，见表3。由表3可以看出，TWMTGN在4个数据集上的指标优于绝大多数基线模型，说明TWMTGN在不同数据集上均有很好的泛化能力。

在捕获邻域特征方面，TWMTGN在直推式设置下，A和P在4个数据集上比CAW分别平均提高了11.55%和9.39%，比NAT分别平均提高了4.38%和2.40%；在归纳式设置下，A和P在4个数据集上比CAW分别平均提高了11.35%和9.48%，比NAT分别平均提高了4.84%和2.68%。虽然CAW和NAT分别通过因果匿名游走和获得一定跳数内的邻域表示捕获网络拓扑结构特征，但二者没有明确地区分挖掘出的语义类型，主要关注网络的局部结构，并且忽略了节点之间的长期依赖关系。因此，与TWMTGN相比，CAW和NAT在时间链路预测任务上显现出不足。

在建模节点动态方面，TWMTGN在直推式设置下，A和P在4个数据集上比TGN分别平均提高了6.64%和7.27%；在归纳式设置下，A和P在4个数据集上比TGN分别平均提高了8.43%和8.44%。虽然TGN和TWMTGN均通过记录节点记忆建模节点动态，但TGN没有明确利用网络的拓扑结构特征，并且忽略了事件发生时间间隔的影响，也未进一步挖掘历史交互节点不同特征的内部关联。因此，TGN与TWMTGN相比表现出劣势。

在LastFM、Enron等交互密集的时序图上，聚合事件触发的时间子图建模节点动态的方法不如构建邻域结构特征的方法，这是由于后者为每个节点的邻居保存一种单独的表示，旧的交互不会被新的交互压缩成一个单一的表示。TWMTGN结合二者优势，进行时间约束游走构建邻域结构特征，结合记忆模块建模长期依赖关系，考虑事件影响随时间衰减的特性，挖掘历史交互特征的潜在关联，更好地捕捉时间动态。

TWMTGN在不同类型数据集上的表现有所差异。不同数据集的实体和关系类型有所差异，其通常会以不同的模式影响当前的各种交互^[20]。因此，语义特征对不同数据集上时间链路预测任务的重要性有所差异。通常，异质图包含的语义信息更丰富，TWMTGN能够有效应对网络的异质性，在同质图上也能取得良好的效果。

2.4 复杂度分析

为比较模型的复杂度，统计模型参数量的大小，在批大小为200的情况下，对UCI数据集上的训练、推理阶段的速度进行比较，结果见表4。由表4可知，虽然NAT在训练和推理速度上具有优势，但其以牺牲精度为代价，且NAT参数量为TWMTGN的8倍左右，所需存储空间更大。TWMTGN与CAW、PINT等模型相比具有显著优势，因为构造邻域结构特征或计算相对位置特征的开销较高。总体来看，TWMTGN具有良好的预测性能和可接受的开销。

表3时间链路预测任务对比实验结果

Tab.3Comparative experimental results for temporal link prediction tasks

表4复杂度对比

Tab.4Complexity comparison

2.5 消融实验

为进一步验证TWMTGN引入网络拓扑结构特征和设计历史交互节点特征聚合方法的有效性，设置3种变体进行消融实验：1）TWMTGN w/o walk，即去除时间约束的随机游走过程；2）TWMTGN w/o decay，即去除特征衰减层；3）TWMTGN w/o causal，即去除因果卷积网络。

图3为消融实验结果。与原始模型相比，3种变体的性能指标均有不同程度的下降，在不同数据集上的表现也有所差异。在LastFM数据集上，去除时间约束随机游走后模型效果下降最多，原因是LastFM是异质数据集，时间约束随机游走策略能有效提取不同类型的异质信息，更好地利用网络的结构特征。在Enron数据集上，去除特征衰减层后模型效果下降幅度较大，这说明时间衰减特性对聚合历史交互节点特征具有重要影响。去除因果卷积层后，实验指标在4个数据集上均有所下降，证明了其对挖掘历史交互特征潜在时序关联的有效性。

图3消融实验结果

Fig.3Ablation experiment results

2.6 参数灵敏度分析

为了对不同时间约束随机游走序列进行聚合，在UCI数据集上选取平均值、标准差、最小值、最大值4种编码方式进行测试，结果如图4所示。由图4可知，均值编码方式效果最好。在聚合历史交互节点特征获得更新后的目标节点嵌入表示时，历史交互节点的数量是重要的影响因素。因此，在UCI数据集上测试了历史交互节点数量对模型效果的影响，结果如图5所示。由图5可知，随着节点数量的增加，P先提升后下降。原因是随着目标节点的信息感受野扩大，模型获取的有效信息增加，但当历史交互节点数量进一步扩大时，出现了更多噪声和冗余信息，干扰模型对关键特征的学习，导致性能下降。

图4游走序列编码方式的影响

Fig.4Effect of walk sequence encoding methods

图5历史交互节点数量的影响

Fig.5Effect of the number of historical interaction nodes

时间约束游走的长度和次数对于捕获网络拓扑结构特征有重要影响。游走长度的增加能够更好地捕捉网络全局结构信息，然而过长的游走长度可能会导致冗余信息的产生。过多的游走次数也会增加模型的计算负担。因此，在UCI数据集上测试了不同游走长度和次数对模型效果的影响，结果如图6所示。在直推式设置下，当游走长度和次数均为4时，结果最优；在归纳式设置下，当游走长度为2、游走次数为6时，结果最优。因此，可以通过平衡实验精度要求和计算复杂度来选取游走长度和次数。

为检验超参数对模型的影响，在UCI数据集上选取批大小和注意力头数进行实验，结果如图7、8所示。结果显示，最优的批大小为200，最优的注意力头数为2。

图6游走长度和次数对指标P的实验结果

Fig.6Experimental results of walk length and frequency on P

图7批大小实验结果

Fig.7Experimental results for batch size

图8注意力头数实验结果

Fig.8Experimental results of attention head count

3 结论

本文针对时序图表示学习提出了一种融合时间约束游走的记忆增强时序图神经网络，联合提取网络的异质性和演化模式，主要结论如下：

1）构造的时间约束游走序列可以有效捕捉时序网络邻域结构特征。

2）记录节点记忆状态能够捕获网络长期依赖关系。将编码后的游走序列融合至节点记忆的更新过程，能够利用网络拓扑结构信息学习网络长期演变规律。

3）利用节点类型和时间衰减特性设计特征衰减层，能够提高模型对关键历史交互节点的识别能力，降低发生时间较长的历史事件对目标节点产生的影响，有效聚合了历史交互节点特征。

4）因果卷积网络能够有效捕获历史交互节点特征的潜在关联。

图1TWMTGN框架

Fig.1Framework of TWMTGN

下载: 全尺寸图片

图2聚合目标节点历史交互特征

Fig.2Aggregate the historical interaction features for target node

下载: 全尺寸图片

图3消融实验结果

Fig.3Ablation experiment results

下载: 全尺寸图片

图4游走序列编码方式的影响

Fig.4Effect of walk sequence encoding methods

下载: 全尺寸图片

图5历史交互节点数量的影响

Fig.5Effect of the number of historical interaction nodes

下载: 全尺寸图片

图6游走长度和次数对指标P的实验结果

Fig.6Experimental results of walk length and frequency on P

下载: 全尺寸图片

图7批大小实验结果

Fig.7Experimental results for batch size

下载: 全尺寸图片

图8注意力头数实验结果

Fig.8Experimental results of attention head count

下载: 全尺寸图片

表1LastFM不同游走长度结果

Tab.1Results of different walk lengths for LastFM

下载: 全尺寸图片

表2数据集统计

Tab.2Statistics of datasets

下载: 全尺寸图片

表3时间链路预测任务对比实验结果

Tab.3Comparative experimental results for temporal link prediction tasks

下载: 全尺寸图片

表4复杂度对比

Tab.4Complexity comparison

下载: 全尺寸图片

图1TWMTGN框架

Fig.1Framework of TWMTGN

图2聚合目标节点历史交互特征

Fig.2Aggregate the historical interaction features for target node

图3消融实验结果

Fig.3Ablation experiment results

图4游走序列编码方式的影响

Fig.4Effect of walk sequence encoding methods

图5历史交互节点数量的影响

Fig.5Effect of the number of historical interaction nodes

图6游走长度和次数对指标P的实验结果

Fig.6Experimental results of walk length and frequency on P

图7批大小实验结果

Fig.7Experimental results for batch size

图8注意力头数实验结果

Fig.8Experimental results of attention head count

表1LastFM不同游走长度结果

Tab.1Results of different walk lengths for LastFM

表2数据集统计

Tab.2Statistics of datasets

表3时间链路预测任务对比实验结果

Tab.3Comparative experimental results for temporal link prediction tasks

表4复杂度对比

Tab.4Complexity comparison

图1TWMTGN框架

Fig.1Framework of TWMTGN

图2聚合目标节点历史交互特征

Fig.2Aggregate the historical interaction features for target node

图3消融实验结果

Fig.3Ablation experiment results

图4游走序列编码方式的影响

Fig.4Effect of walk sequence encoding methods

图5历史交互节点数量的影响

Fig.5Effect of the number of historical interaction nodes

图6游走长度和次数对指标P的实验结果

Fig.6Experimental results of walk length and frequency on P

图7批大小实验结果

Fig.7Experimental results for batch size

图8注意力头数实验结果

Fig.8Experimental results of attention head count

表1LastFM不同游走长度结果

Tab.1Results of different walk lengths for LastFM

表2数据集统计

Tab.2Statistics of datasets

表3时间链路预测任务对比实验结果

Tab.3Comparative experimental results for temporal link prediction tasks

表4复杂度对比

Tab.4Complexity comparison

王天保, 刘昱, 郭继昌, 等. 图卷积神经网络行人轨迹预测算法[J]. 哈尔滨工业大学学报,2021,53(2):53. WANG Tianbao, LIU Yu, GUO Jichang,et al. Pedestrian trajectory prediction algorithm based on graph convolutional network[J]. Journal of Harbin Institute of Technology,2021,53(2):53. DOI:10.11918/202006051

YANG Menglin, ZHOU Min, KALANDER M,et al. Discrete-time temporal network embedding via implicit hierarchical learning in hyperbolic space[C]//Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Singapore: ACM,2021:1975. DOI:10.1145/3447548.3467422

LI Xiaoxiao, SAUDE J, REDDY P,et al. Classifying and understanding financial data using graph neural network[C]//AAAI Workshop on Knowledge Discovery from Unstructured Data in Financial Services. New York: AAAI,2020

KING I J, HUANG H H. Euler:detecting network lateral movement via scalable temporal link prediction[J]. ACM Transactions on Privacy and Security,2023,26(3):35. DOI:10.1145/3588771

WU Cheng, WANG Chaokun, XU Jingcao,et al. Instant representation learning for recommendation over large dynamic graphs[C]//39th IEEE International Conference on Data Engineering, ICDE 2023. Anaheim: IEEE,2023:82. DOI:10.1109/ICDE55515.2023.00014

LI Longhai, DUAN Lei, WANG Junchen,et al. Memory-enhanced transformer for representation learning on temporal heterogeneous graphs[J]. Data Science and Engineering,2023,8(2):98. DOI:10.1007/s41019-023-00207-w

LU Yuanfu, WANG Xiao, SHI Chuan,et al. Temporal network embedding with micro-and macro-dynamics[C]//28th ACM International Conference on Information and Knowledge Management. Beijing: ACM,2019:469. DOI:10.1145/3357384.3357943

KUMAR S, ZHANG Xikun, 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: ACM,2019:1269. DOI:10.1145/3292500.3330895

XU Da, RUAN Chuanwei, KORPEOGLU E,et al. Inductive representation learning on temporal graphs[C]//8th International Conference on Learning Representations, ICLR 2020. Addis Ababa: ICLR,2020

ROSSI E, CHAMBERLAIN B, FRASCA F,et al. Temporal graph networks for deep learning on dynamic graphs[EB/OL].(2020-06-18)[2024-06-02].https://arxiv.org/pdf/2006.10637

LUO Yuhong, LI Pan. Neighborhood-aware scalable temporal network representation learning[C]//1st Learning on Graphs Conference. Mountain View: PMLR,2022:1

WANG Yanbang, CHANG Yenyu, LIU Yunyu,et al. Inductive representation learning in temporal networks via causal anonymous walks[C]//9th International Conference on Learning Representations. Vienna: ICLR,2021

ZHOU Wei, HUANG Hong, SHI Ruize,et al. Temporal heterogeneous information network embedding via semantic evolution[J]. IEEE Transactions on Knowledge and Data Engineering,2023,35(12):13031. DOI:10.1109/TKDE.2023.3287260

TRIVEDI R, FARAJTABAR M, BISWAL P,et al. Representation learning over dynamic graphs[EB/OL].(2018-03-12)[2024-06-02].https://arxiv.org/pdf/1803.04051

杨应修, 陈红梅, 周丽华, 等. 基于数据增强的异质图注意力网络[J/OL]. 计算机科学.(2024-05-28)[2024-06-02].https://link.cnki.net/urlid/50.1075.tp.20240527.1600.015. YANG Yingxiu, CHEN Hongmei, ZHOU Lihua,et al. Heterogeneous graph attention network based on data augmentation[J/OL]. Computer Science.(2024-05-28)[2024-06-02].https://link.cnki.net/urlid/50.1075.tp.20240527.1600.015

BAI Shaojie, KOLTER J Z, KOLTUN V. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling[EB/OL].(2018-03-04)[2024-06-02].https://arxiv.org/pdf/1803.01271

MIKOLOV T, SUTSKEVER I, CHEN Kai,et al. Distributed representations of words and phrases and their compositionality[C]//27th Conference on Neural Information Processing Systems. Nevada: Morgan Kaufmann Publishers,2013:3111

ZHANG Lin, GUO Jiawen, BAI Qijie,et al. Dynamic heterogeneous graph representation learning with neighborhood type modeling[J]. Neurocomputing,2023,533:46. DOI:10.1016/j.neucom.2023.02.060

SOUZA A H, MESQUITA D, KASKI S,et al. Provably expressive temporal graph networks[C]//36th Conference on Neural Information Processing Systems. New Orleans: Morgan Kaufmann Publishers,2022:32257

JI Yugang, JIA Tianrui, FANG Yuan,et al. Dynamic heterogeneous graph embedding via heterogeneous hawkes process[C]//European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Bilbao: Springer,2021:388. DOI:10.1007/978-3-030-86486-6_24

Publication Statement

Journal Subscription

1 融合时间约束游走的记忆增强时序图神经网络

2 实验结果与分析

3 结论