基于双层时序的动态社交网络链路预测

Dynamic Social Network Link Prediction Based on Bi-Layer Temporal Modeling

摘要: 现实世界中存在大量网络图信息，其中社交网络实体间交互的动态性和复杂性使得动态图链路预测成为了一项更具有挑战性的任务。传统基于图神经网络的动态链路方法由于过平滑性往往只关注图中局部特征，难以获取图中实体的全面性信息，并且发现在社交网络中的连通接近性对未来链路预测是有利的。为了解决以上挑战，本文设计了双层时序模型Bi-GTGNN。首先提取每个快照的子图，并将每个快照的子图集抽象为时序序列，然后设计全局时序图神经网络提取图的全局信息并生成快照表示。其次，将每个时间戳的快照表示输入到LSTM中进一步提取时序信息，并设计了新颖的损失函数训练具有连通接近性的图嵌入。最后将具有时序信息的图嵌入用于链路预测。在五个数据集上进行了大量实验，结果表示Bi-GTGNN性能优于其它先进的baseline模型。

Abstract: In the real world, there is a plethora of network graph information, where the dynamism and complexity of interactions among entities in social networks have made dynamic graph link prediction a more challenging task. Traditional methods based on graph neural networks for dynamic links often focus only on local features of the graph due to over-smoothing, making it difficult to acquire comprehensive information about entities in the graph. Additionally, we observe that the connectivity proximity in social networks is advantageous for future link prediction. To address these challenges, we propose a bi-layer temporal model. Firstly, we extract subgraphs for each snapshot and abstract the subgraph set of each snapshot into a temporal sequence. Then, we design a global temporal graph neural network to extract the global information of the graph and generate snapshot representations. Secondly, we input the snapshot representations of each timestamp into an LSTM to further extract temporal information and design a novel loss function to train graph embeddings with connectivity proximity. Finally, the graph embeddings with temporal information are utilized for link prediction. We conduct extensive experiments on five social network datasets, and the results demonstrate that our model outperforms other state-of-the-art baseline models.

1. 引言

现实世界的网络图数据通常会随着时间的推移而演变，社交网络平台每个月都有成千上万用户之间的链接演变，因此这些数据在社交网络 [1] 中得到了很好的表达。动态链路预测旨在预测节点之间未来的关系，对于理解动态图 [2] 的演变至关重要。现有基于图嵌入的链路预测方法可以分为传统图嵌入 [3] 和图神经网络图嵌入 [4] 。

传统的图嵌入方法包括矩阵分解和随机游走，在基于矩阵分解的技术中，节点嵌入是通过分解图表示矩阵 [5] 和图邻接矩阵 [6] 来学习的。但是，矩阵分解方法消耗大量内存空间，并且由于存储大型矩阵而需要高计算需求。因此通常通过随机游走来获取节点的邻域连通性信息。流行的基于随机行走的方法包括deepWalk [3] 和node2vec [7] 。随机行走方法侧重于保留节点接近信息，但是牺牲了网络结构信息 [8] ，并且高度节点可能比低度节点的样本更多 [9] ，因此难以广泛适用于各种网络。上述方法主要应用于静态图嵌入，目前大量研究将图嵌入技术应用于动态网络链路预测。例如，GraphLP [10] 利用深度学习模型的特征学习能力，自动从图中提取结构模式，以改进链路预测。为了捕捉时间的演化信息，DynamicTriad [11] 采用三元闭合的概念作为指导原则来捕捉各种快照的演化模式。DynGEM [12] 从初始化开始逐步更新节点嵌入。但是难以捕获长期动态，从而限制了它们的准确性。

基于图神经网络的图嵌入方法主要通过使用图神经网络提取图中节点信息来进行链路预测。此方法最初应用于静态图，自GCN [13] 以来，许多图神经网络被提出。例如，GAT [4] 、GraphSAGE [14] 、FastGCN [15] 、图同构网络(GIN) [16] 和位置感知图神经网络(P-GNNs) [17] 等。还有一些变体用于解决时空问题，通过将GCN变体和循环架构进行结合。例如，GCRN (Graph Convolutional recurrent Network) [18] 结合了图卷积和循环神经网络的模型，在图卷积层之后引入循环神经网络层，使得模型能够在图的时间序列上进行信息传递和更新，从而捕捉快照的演化过程。AddGraph [19] 结合了注意力机制和时间感知的图卷积网络，利用注意力机制来对节点的邻居进行加权，然后通过时间感知的GCN来聚合邻居节点的信息。但是对于复杂的图结构和时间序列数据，可能无法充分利用到演化过程中的细节信息。EvolveGCN [20] 通过引入图演化机制来建模时间演化过程，图演化机制用于动态地更新图结构和节点特征。从而能够自适应地学习图的演化规律并充分利用演化过程中的丰富信息。

上述的图神经网络由于自身架构限制，只能通过聚合低阶邻居节点信息，导致无法获取图的全局结构特征。图1是数据集Enron的部分图，如图1左侧红色框节点为例，当GCN [13] 行处理时，第一层GCN会聚合绿色填充部分的一阶邻居，此时绿色的节点也会聚合橙色节点信息。第二层GCN聚合时，红框节点可以通过绿色节点获取到橙色节点的信息。也就是说，红色节点想要获取二阶邻域信息必须要通过一阶邻域节点。理想情况下，当GCN层数无限大时，可以获取到全图信息。但是由于过平滑特性，一般情况下，当GCN层数达到3以上时，性能会极大降低。因此，传统图神经网络是无法捕获全图信息的。此外，如图1右侧表示时间t与时间t+1的快照变化，其中红色实线表示新增的链接，绿色虚线表示消失的链接。可以发现对于邻近的节点，在未来进行交互的可能性较大。这说明关联接近性可以帮助揭示未来社交网络中的链接变化。

Figure 1. Problem statement

图1. 问题阐述

为了解决以上挑战，本文提出了双层时序模型(Bi-GTGNN)，双层时序分为子图层时序以及快照层时序。子图层时序是全局时序图神经网络(Global Temporal Graph Neural Network, GTGNN)。与传统图神经网络架构不同，它不需要与低阶邻居信息聚合更新，而是对每个快照提取抽象时序子图，通过全局时序聚合获取单个快照的图嵌入表示。进一步将所有快照的图嵌入输入快照层时序捕获快照时序信息。此外，本文设计了损失函数将关联接近的用户生成相似的嵌入，以保持关联接近性。最终的嵌入用于链路预测。本文的贡献总结如下：

1) 提出了双层时序架构，子图层捕获单个快照的抽象时序子图集的时序信息，快照层捕获快照间的时序信息。

2) 传统的图神经网络只能聚合低阶邻居，难以捕获全局结构信息。本文提出的GTGNN模型每层都可以聚合全局信息，从而获取更丰富的隐藏特征。

3) 设计了新颖的损失函数将关联接近的用户生成相似的嵌入，从而提高预测精度。

4) 在五个真实动态社交网络数据集上进行大量实验，证明了模型的有效性。

2. 模型设计

本章介绍了提出的双层时序模型，双层时序分为子图层时序以及快照层时序。子图层时序是全局时序图神经网络，与传统图神经网络架构不同，它不需要与低阶邻居信息聚合更新。首先提取每个时间节点快照的子图，并将这些子图抽象为一个时序演变子图集合，然后使用一个时序网络捕获抽象时序信息，这些抽象时序信息进行聚合并更新图嵌入。因此这也是一种聚合与更新的过程。快照层时序将每个时间节点快照嵌入作为LSTM网络的输入，获取快照时序信息。最终的嵌入用于下游链路预测任务，模型框架如图2所示。

Figure 2. Bi-layer temporal framework structure

图2. 双层时序框架结构

2.1. 定义

定义一：定义动态图为 $G\left(t\right)=\left(V,E\right)$ ，其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 代表 $n$ 个节点集合， $E=\left\{E_1,E_2,\cdots ,E_t\right\}$ 代表在t个时间的所有边集合。动态图可以通过一系列快照 $\left(G_1,G_2,\cdots ,G_t\right)$ 来表示， $G_t$ 代表图在时间点t的快照状态。每个时间点的快照邻接矩阵表示为 $A_t$ ，如果节点 $v_i$ 和 $v_j$ 之间无连接，则邻接矩阵 $A_{i,j}=0$ ，否则为 $A_{i,j}>0$ 。图嵌入方法学习映射 $F=\left\{f_1,f_2,\cdots ,f_t\right\}$ ，其中 $f^t\in F$ 将图 $G_t$ 中的每个节点 $v_n$ 映射到向量空间 $R^d$ ，d表示节点表示维度，节点嵌入可以表示为X。映射后的节点表示可以保留节点的拓扑信息以及动态图的时序信息。

定义二：将每一个快照生成子图集，子图集可以表示为 $\tilde{G}=\left\{{\tilde{G}}^1,{\tilde{G}}^2,\cdots ,{\tilde{G}}^n\right\}$ 。 ${\tilde{G}}^n$ 表示当前子图每个节点度大于等于n，因此 ${\tilde{G}}^1$ 也表示原图。子图的生成过程可以表示为，给定图 $G=\left(V,E\right)$ ，通过递归移除度小于n的节点直到所有节点的度都至少为n。

2.2. 子图层时序

2.2.1. 子图提取

子图层时序需要先提取快照子图，本文中的子图提取可视为一种图划分方法，类似的方法已在ClusterGCN [21] 中使用。ClusterGCN通过图聚类算法将图划分为多个子图，以限制GCN层中的邻域扩展，从而解决GCN中的过度平滑问题。本文目标是增强图神经网络，以保留局部连接近似，并在动态图中捕获全局结构信息。如图3所示，这是一个简单的子图提取示例，可以发现， ${\tilde{G}}^3$ 、 ${\tilde{G}}^2$ 和 ${\tilde{G}}^1$ 中节点数量相同，但是边不同。并且由于是通过对原图的边进行移除，它们之间存在着一种抽象时序关系。如： ${\tilde{G}}^3\to {\tilde{G}}^2\to {\tilde{G}}^1$ 。

Figure 3. Example of subgraph extraction process

图3. 子图提取过程示例

2.2.2. 全局时序图神经网络

图卷积网络(GCNs)在各种任务中取得了较好的表现。形式上，一个单层的普通GCN被定义为：

$H^{\left(l+1\right)}=\sigma \left({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{\left(l\right)}{W}^{\left(l\right)}\right)$ (1)

其中X是输入特征矩阵， $\tilde{A}=A+I$ 表示具有自环的邻接矩阵，I是单位矩阵， $\tilde{D}$ 是对角矩阵，其元素 ${\tilde{D}}_{ij}={\displaystyle {\sum }_j{\tilde{A}}_{ij}}$ ，W是可学习的权重矩阵， $\sigma (\cdot )$ 是非线性激活函数，H表示学习到的输出嵌入。

显然，图卷积层类似于全连接层，除了扩散矩阵 ${\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$ 外，它将节点的邻居特征传播到该节点。

本质上，图卷积是一种特殊形式的拉普拉斯平滑，它计算一个节点的新特征作为自身及其邻居的加权平均。单层GCN可以保留一阶接近性，而多层GCN在实践中经常使用，因为它可以捕获高阶接近性信息。然而，由于图神经网络架构的过平滑性，当图的卷积层增加时，GCN会出现过平滑和过拟合现象。这些问题反映了GCN无法探索全局图结构。因此，在实践中，一个GCN通常最多包含3个图卷积层。

受此启发，本文将图神经网络分为特征变换和特征聚合，可以如下表达：

$Z=f\left(X\right)$ (2)

$H=h\left(g\left(A\right),Z\right)$ (3)

其中，X为输入特征矩阵，f为将X映射到潜空间的特征变换函数，A为邻接矩阵，g为定义传播规则的A的函数，h为根据传播规则g对每个节点的特征进行聚合的特征聚合函数，h是融合了特征变换和图结构信息的嵌入矩阵。

许多以前的工作都是不同的f和g组合，但它们都选择H的输出作为实际的最终嵌入。本文将f和H的输出都用作节点表示，这将在后面讨论。通过将传统的图卷积运算推广到特征变换和特征聚合，为设计不同类型的GCNs提供了更大的灵活性。接下来介绍GTGNN，结构如图4所示。

前面介绍的抽象时序子图集可以表示为时间序列 ${\tilde{G}}^{\text{n}}\to {\tilde{G}}^{\text{n}-1}\to \cdots \to {\tilde{G}}^2\to {\tilde{G}}^1$ 。本文使用的是每个子图的邻接矩阵作为输入，然后与初始节点嵌入进行特征变换，如公式(4)

$X^n=\sigma \left({\tilde{A}}^{n}X\right)$ (4)

其中， ${\tilde{A}}^n$ 是 ${\tilde{G}}^n$ 子图的自环邻接矩阵，也就是在邻接矩阵上增加了一个单位矩阵。由于将子图集抽象为时间序列，因此特征聚合将在提取了时间信息后进行。由于时间序列 ${\tilde{G}}^n\to {\tilde{G}}^{n-1}\to \cdots \to {\tilde{G}}^2\to {\tilde{G}}^1$ 的表示是从 $n\to 1$ ，为了后续表达清晰，本文在后续将其表示为 ${\tilde{G}}^1\to {\tilde{G}}^2\to \cdots \to {\tilde{G}}^{n-1}\to {\tilde{G}}^n$ ，例如 ${\tilde{G}}^1$ 的真实含义是 ${\tilde{G}}^n$ ，就是节点度大于等于n的图。 ${\tilde{G}}^n$ 的真实含义是 ${\tilde{G}}^1$ ，就是节点度大于等于1的图，等同于原图。在图4中，也是进行了相关调整。

Figure 4. GTGNN structure

图4. GTGNN结构

现有的RNN架构是比较常见的时序方法，但是这些方法难以捕获长序列信息并且受限于对前一个时间序列数据的依赖，因此时间复杂度较大并且性能不佳。本文使用了时间混合方法调整了RNN架构，因为RNN依赖于前一个时间片的数据信息和隐层表示。将前一个时间片 $t-1$ 的数据信息与当前时间片t的数据信息进行混合操作，并将隐层嵌入使用线性表示，则可以直接获取长序列信息并减少时间复杂度。

时序混合如公式(5) (6) (7)所示， ${\mu }_r$ ， ${\mu }_k$ ， ${\mu }_v$ 用于 $X^n$ 和 $X^{n-1}$ 的线性组合中，以实现简单的时间混合，这种混合在当前和前一时间步的输入之间进行插值。前一步和当前步的组合通过块内的投影矩阵进行线性投影。

$r_n=W_r\cdot \left({\mu }_r\odot X^n+\left(1-{\mu }_r\right)\odot X^{n-1}\right)$ (5)

$k_n=W_k\cdot \left({\mu }_k\odot X^n+\left(1-{\mu }_k\right)\odot X^{n-1}\right)$ (6)

$v_n=W_v\cdot \left({\mu }_v\odot X^n+\left(1-{\mu }_v\right)\odot X^{n-1}\right)$ (7)

进一步设计一个类似于注意力机制的操作器，它具有线性时间和空间复杂度。也可以认为是对隐层嵌入的操作器。公式如下：

$o{p}_n=diag\left(u\right)\cdot k_n^T\cdot v_n+{\displaystyle {\sum }_{i=1}^{n-1}diag{\left(w\right)}^{n-1-i}\cdot k_i^T\cdot v_i}$ (8)

其中 ${\displaystyle {\sum }_{i=1}^{n-1}diag{\left(w\right)}^{n-1-i}\cdot k_i^T\cdot v_i}$ 可以认为是上一层的隐层嵌入，w和u是两个可训练参数。参数u是一个奖励参数，首次遇到一个token，特别是当前token的奖励。这有助于模型更加关注当前token。另一个重要的参数是w，它是每个时间片隐藏表示的时间衰减向量。为了确保对前面每个时序通道的隐藏表示进行惩罚，需要将w表示在(0, 1)范围，因此对w的处理如公式(9)。

$w=\exp \left(-\exp \left(w\right)\right)$ (9)

由于可以直接获取 $k_n^T\cdot v_n$ ，因此每个时序通道可以直接进行计算。每个时序通道的输出表示如公式(10)

$o_n=\left(SiLU\left(r_n\right)\odot o{p}_n\right)W_{op}$ (10)

上述过程可以以RNN循环形式进行表达，如公式(11) (12)：

$o{p}_n=s_{t-1}+diag\left(u\right)\cdot k_n^T\cdot v_n$ (11)

$s_t=diag\left(w\right)\cdot s_{t-1}+k_n^T\cdot v_n$ (12)

其中 为当前时间步隐层状态， $s_{t-1}$ 为上一时间步隐层状态， $s_0$ 为零矩阵。最终获得了具有时序信息的输出 $O=\left\{o_1,o_2,\cdots ,o_n\right\}$ 。

完成对子图集中每个子图的嵌入工作后，接下来需要将每个子图的嵌入表示进行聚合，如公式(13)，由此完成一次完整的特征变换与聚合。对于下一层的输入，则由上一层的输出H与子图集的自环邻接矩阵进行特征变换并重复上述操作。

$H=\underset{l=1}{\overset{n}{{\displaystyle \sum }}}{o}_l$ (13)

2.3. 快照层时序

将每个单一快照使用GTGNN进行两次处理后。会得到每个快照的节点特征矩阵集合 $\left\{H_1,H_2,\cdots ,H_t\right\}$ 。然后将这t个节点特征矩阵作为序列输入到LSTM模型中。就可以获取到具有快照层时态信息的最新的 个节点特征矩阵。具体公式如下：

$C_t=\text{LSTM}\left({\text{GTGNN}}^t\left(A_t,X\right),C_{t-1}\right)$ (14)

其中 $C_0$ 为零矩阵， $A_t$ 为 $G_t$ 的邻接矩阵，X为G的节点特征矩阵。每个GTGNN对LSTM单元产生静态节点嵌入，LSTM单元决定下一个时间戳层保留多少信息。节点特征矩阵 $C_1,C_2,\cdots ,C_t$ 是t个快照的最终嵌入。

2.4. 损失函数

在引言部分已经阐述了连通接近性对于链路预测的影响。为了在动态图中保持连接的接近性，本文遵循前面的GCNs来利用h函数的输出作为最终的嵌入。模型训练采用无监督方式，损失函数如下：

$L_c=\underset{t=1}{\overset{T}{{\displaystyle \sum }}}\underset{u\in V}{{\displaystyle \sum }}{L}_u^t$ (15)

$L_u^t=\underset{v\in N_w^t\left(u\right)}{{\displaystyle \sum }}-\log \left\{1-\sigma \left[D_{(h_v,h_u)}\right]\right\}-Q\cdot \underset{v^{\prime }\in P_n^t\left(u\right)}{{\displaystyle \sum }}-\log \left\{\sigma \left[D_{\left(h_{v^{\prime }},h_u\right)}\right]\right\}$ (16)

$D_{(h_v,h_u)}=\sqrt{\underset{i=1}{\overset{d}{{\displaystyle \sum }}}{\left(h_v{}_i-h_u{}_i\right)}^2}$ (17)

其中 $D_{(h_v,h_u)}$ 表示欧式距离，d是嵌入维度， $N_w^t\left(u\right)$ 是与u在定长随机游动上同时出现的节点集合， $P_n^t$ 表示负样本集合。Q是用于平衡正、负样本的超参数。通过这个无监督的损失函数，在固定长度的随机游动中发生的节点被鼓励有相似的表示。因此，学习后的节点表示可以在动态图中保持局部连接的邻近性。

3. 实验结果与分析

3.1. 数据集与评估指标

实验中使用了五个社交网络数据集。包括加州大学欧文分校的一个学生信息网络UCI；来自Autonomous systems的一个通信网络AS；来自Facebook公司的Facebook数据集；一个来自安然公司的电子邮件联系网络Enron和一个来自堆栈交换网站Math overflow的用户交互网络Math。在实践中按月分割数据集。数据集信息如下表1。

Table 1. Dataset information

表1. 数据集信息

评估指标使用的是曲线下面积(Area Under The Curve, AUC)，ROC曲线(Receiver Operating Characteristic curve)下方的面积就是AUC。因为最终的链路预测任务是二分类问题，而AUC的优点在于它对类别不平衡和阈值选择不敏感，因此被广泛应用于评估各种分类任务的性能。

3.2. 对比模型和实施细节

对比baseline分为静态图方法和动态图方法，静态图方法选择GCN [13] 、GAT [4] 和GIN [16] ，动态图方法选择DynGEM [12] 、Dyngraph2vec [22] 、GCRN [18] 和EvolveGCN [20] 。其中Dyngraph2vec有三种变体，分别是dynAE、dynRNN和dynAERNN。

对于基于静态GCN的方法，在GCN、GAT、GIN、GCRN和EvolveGCN中使用了2层。对于DynGEM，将α设为10⁻⁵，β设为10， ${\gamma }_1$ 设为10⁻⁴， ${\gamma }_2$ 设为10⁻⁴。对于dynAE、dynRNN和dynAERNN，设β为5，向后看为3， ${\gamma }_1$ 为 ${10}^{-6}$ ， ${\gamma }_2$ 为 ${10}^{-6}$ 。对于本文所提出的方法Bi-GTGNN，为了公平对比，也保持两层GTGNN。优化器使用Adam [23] ，学习率设置为0.001。为了方便比较，所有方法的嵌入维度都设置为128。

给定一系列动态图，链接预测根据当前时间步长t的嵌入信息，预测下一个时间步长t + 1中存在一条边。为了构建带标记的边集，本文从图G_t中随机采样边作为正样本，从未连接的节点对中生成负样本。然后采用 [7] 的方法，使用标记的边集中节点对的嵌入向量执行Hadamard运算以生成边特征向量。训练一个逻辑回归(Logistic Regression, LR)分类器来区分正和负边样本。所有静态图嵌入方法都在每个图快照上重新训练以生成节点嵌入，而所有动态图嵌入方法都结合了历史图信息以生成当前时间戳的节点嵌入。

3.3. 对比实验结果分析

如表2所示，实验结果是所有时间戳的平均AUC分数，“-”表示GPU内存不足。实验结果表示静态图方法整体性能低于动态图方法，因为常规的图嵌入方式提取的动态图信息存在缺陷。说明时序信息在动态图链路预测中是不可或缺的。动态嵌入方法中，Bi-GTGNN性能优于其它方法，这表明Bi-GTGNN可以捕获全局图结构信息，从而生成的节点表示有助于预测链路的形成和消失。其它动态图嵌入方法表现最优的是EvolveGCN，这是因为它引入了图演化机制，能够根据当前时刻的图数据动态地更新节点表示。这使得模型能够更好地捕捉动态图的时间演化规律，从而提高了嵌入质量。

Table 2. Comparative experimental results

表2. 对比实验结果

3.4. 消融实验

消融实验继续在5个社交网络数据集上进行，Baseline模型使用GCN、GAT、GIN。在之前的对比实验中，对于这三个baseline的操作方式是分别对每个快照生成节点表示，然后进行链路预测。在消融实验中，在分别生成节点表示后，再输入到快照层时序进一步生成新的表示，损失函数如公式(15)，最后进行链路预测。调整后的模型表示为GCN++、GAT++和GIN++。此外，本文增加了GTGNN的实验，并且训练方式与未融合快照层的GCN相同。

如表3所示，GCN、GAT和GIN融合快照层时序后，在5个数据集上都有了一定提升，这说明快照层时序是有效的。其中，在AS数据集上各个模型提升较大，这是因为AS数据集中快照数量最多，因此快照间的时序信息是非常丰富的，而GCN、GAT和GIN都无法捕获快照间时序。加入快照层后，它们都可以生成具有时序信息的节点表示。此外，使用公式(15)的损失函数后，它们生成的嵌入具有连通接近性，从而进一步提高预测性能。

Table 3. Ablation experiment results

表3. 消融实验结果

GCN、GAT和GIN的性能弱于GTGNN，这说明GTGNN解除了只能聚合低阶邻居的限制并充分考虑全局信息是有效的。此外，GCN++、GAT++和GIN++性能也弱于Bi-GTGNN，因为即使GCN、GAT和GIN融合了快照层时序信息，但由于过平滑性限制了对远距离节点探测，所以生成的节点表示信息不足，因此预测性能难以提升。

3.5. 并行性分析

在GTGNN中有一个时序模块，本文在3.2.2节中阐述了每个时间戳的计算并行性，本节将分析并行原理以及实验结果。

首先常规的RNN模型每个时间通道需要使用上一个时间通道的隐层输出作为当前层的输入，因此只能保持串行进行计算。在GTGNN中的时序部分，如公式(10)，每个时间通道的输出由 $r_n$ 和 $o{p}_n$ 计算得出，其中 $r_n$ 是已知的。如公式(8)， $o{p}_n$ 则由当前时间通道 $k_n$ 、 $v_n$ 与之前所有时间通道的k、v计算得出，而所有的k、v是已知的。因此任意层的计算所需变量都可以直接获得，从而可以实现并行计算。

在数据集Facebook和Enron上对比了GCN、GAT、GIN、Bi-GTGNN和Bi-GTGNN-R训练每个epoch所花费的时间，其中Bi-GTGNN-R是使用RNN替换GTGNN中的时序模块，其它实验设置与对比实验相同。如图5所示，Bi-GTGNN-R的计算效率将近高于GTGNN的一倍，说明GTGNN中的并行计算是有效的。GAT的训练时间最高，远超于其它方法，训练时间最低的是GCN。这是因为GAT在每次卷积融合特征的过程中引入了注意力机制。这个机制允许模型为每条边分配一个可学习的权重系数α，使得特征融合过程更加灵活和自适应。具体来说，GAT的每个节点都会计算与其邻居节点之间的注意力系数，这个过程涉及到额外的参数和非线性变换，如LeakyReLU函数。而且，GAT通常采用多头注意力机制，即在同一层中并行计算多组注意力系数，然后将它们合并起来，以增强模型的表达能力，因此训练时间远大于Bi-GTGNN。相比之下，GCN的卷积过程相对简单，它使用度矩阵和邻接矩阵来计算邻居节点的加权平均，而这些权重是固定的，不涉及额外的学习过程。因此，GCN的计算效率更高，训练时间较短。

Figure 5. Training time results

图5. 训练时间结果

4. 总结

本文提出了Bi-GTGNN模型。Bi-GTGNN模型是一个双层时序模型，子图层时序通过提取抽象时序子图集并聚合信息，从而可以充分获取图的全局信息。快照层时序使用LSTM捕获每个时间戳的快照间时序，并设计了损失函数训练具有连通接近性的节点嵌入。最终的嵌入用于链路预测任务。在五个不同的社交网络数据集上实验比较了Bi-GTGNN与其它的基线方法，实验结果证明Bi-GTGNN具有先进的性能。其次将双层时序对基线方法进行了扩展以证明每个模块的有效性。最后分析了GTGNN中时序模块的并行性。在未来，可以探索使用更高效的算法来优化快照层时序，例如通过简化神经网络结构或采用轻量级的变体。同时，对于模型的训练过程，可以采用分布式计算资源，以进一步缩短训练时间并提升模型的响应速度。在保证模型准确性的前提下，这些改进将有助于模型在实际应用中的部署和运行。