唐晨，赵杰煜，叶绪伦，郑阳，俞书世

宁波大学 信息科学与工程学院，浙江 宁波315211

互联网的普及产生了大量的图结构数据，其中蕴含着丰富的信息。虽然这些信息很难直接获取，但是蕴含很高的商业价值和社会价值。链接预测作为图领域的典型问题，体现在现实生活的方方面面。例如在社交领域中，链接预测可以预测新朋友关系的产生，或是给用户推荐新的朋友。在电子商务领域，链接预测可以为用户提供个性化的商品推荐。在生物学领域，链接预测可以预测蛋白质在交互作用的过程中可能发生的反应，亦可发现基因序列中导致疾病的异常基因。

目前，静态图的链接预测模型已经取得了非常好的效果，但是在现实世界中，图的节点和链接通常是随着时间变化的，静态模型难以保留时域上的特征。比如在社交网络中，任何时刻用户都有可能因为部分属性发生改变导致新链接的产生或者旧链接的消失。如图1 所示，在-1 时刻，节点2 与节点1仅有一个共同邻居节点3。在时刻，节点1 和节点5 之间新增了一条链接，则节点2 和节点1 的共同邻居增长到两个，即节点3 和节点5。虽然时刻节点1、2、4 都有相同的邻居节点，但是从时域的角度看，节点1 和节点2、4 共同邻居的数量呈现增加的趋势，因此在+1 时刻，节点1 和节点2、4 之间建立链接的可能性较大，而节点2 和节点4 虽然共同邻居也是节点3 和节点5，但是在时域上，两者的邻居节点的数量比较稳定，在+1 时刻建立链接的可能性较小。由此可见静态图的链接预测模型在动态图上的表现非常有限，无法捕捉图在时间维度上变化的规律性，这更加凸显了研究动态图链接预测模型的必要性。

图1 动态图演变示意图Fig.1 Schematic diagram of dynamic diagram evolution

针对动态图的链接预测问题，传统的基于随机游走和矩阵分解的模型具有计算效率高的优点，但其无法利用深层次的特征，而且大部分模型最终会采用线性的方法进行预测。目前比较主流的基于深度学习的做法是将图神经网络（graph neural network，GNN）与循环神经网络（recurrent neural network，RNN）相结合。先利用GNN 学习静态图的节点嵌入，然后将节点嵌入作为时间序列信息输入到RNN 模型。

然而，上述方法没有考虑节点分类任务和链接预测任务的区别。分类任务更关注的是图局部特征，链接预测问题更加关注的是图全局特征。全局特征代表了图的整体表现特性，一般属于统计的范畴，而局部特征更加关注个体的细节，一般属于组合的范畴。图在时间维度的演化，是全局特征和局部特征共同作用的结果，全局特征包含了局部特征的成分，局部特征又在其某一方面反映了全局的信息。在动态图的链接预测问题上，则更应该关注不同时刻的图的共性。不可否认，全局特征是多个局部特征归一化的结果。因此，在链接预测任务中，提取特征这一部分需要一个合适的损失函数去均衡全局特征和局部特征。受到Hjelm 等人和Velickovic 等人工作的启发，本文将利用图卷积（graph convolutional network，GCN）和互信息（mutual information，MI）的优点去构造特征提取模块。同时，为此模块设计新的损失函数，该损失能在保证潜在特征更多地保留原始数据的概率特性的情况下，获取有效的全局特征表示，这是其他动态图链接预测模型没有考虑的。

全局特征是所有节点特征聚合的结果，如果其中某些节点特征发生异常，将会严重影响全局特征的提取。因此本文将全局特征表示为向量的形式，并将其本身视为随机变量，其演化过程视为宽平稳随机过程，那么它将存在两个概率性质，即在一个时间窗口内，全局特征的期望为常数，自相关函数只和时间差有关。依照上述规则，本文设计了一个感知模块，约束全局特征在时域维度上以一个宽平稳随机过程的方式演化。

为了探索图在时域上的演化规律，之前的研究是将所有节点特征作为长短期记忆网络（long shortterm memory networks，LSTM）的输入，但是模型的学习能力有限，它无法用一组参数捕捉到所有节点在时域上的演化规律。虽然本文采用LSTM 来捕捉时域上的特征，但是不同的是本文用全局特征代替所有节点特征作为LSTM 的输入。最后利用预测得到的全局特征构造链接，与真实的链接进行对抗训练，使预测值更加接近真实值。

本文的创新有以下两点：

（1）设计了一个新颖的全局特征提取模块，用于挖掘全局特征在动态图上的演变规律。该模块以GCN 模型为基础，利用全局特征和局部特征的互信息构造对比损失函数，采用对抗的方式训练，保证了全局特征在时域上的传递。

（2）设计了感知模块，对全局特征的平滑性做了约束。该模块从宽平稳随机过程获得灵感，通过对均值和自相关函数进行限制，达到规范全局特征的演化过程，是个全局的概念。

1 相关工作

1.1 传统的动态图链接预测模型

传统的动态图链接预测模型大部分是先学习节点嵌入，然后利用传统机器学习方法进行分类。节点嵌入学习主要分为基于随机游走和基于矩阵分解两种。自从Perozzi 等人和Grover 等人分别提出DeepWalk 模型和node2vec 模型以来，基于随机游走的方法广泛应用于图的特征提取。比如在动态图上，Nguyen 等人关注时间的重要性，给每条链接的存在时间定义一个区间，剔除随机游走产生的不合理的序列。Yu等人认为如果图不发生实质性的变化，那么只需要在一个连续的时间段中重新采样一些随机游走序列即可。Ahmed 等人利用随机游走为每个节点构造子图，在该节点周围的子图内计算节点与其邻居之间的相似度分数，整合局部和全局拓扑信息。基于矩阵分解的方法通常是根据特征值将一个大矩阵拆分成几个小矩阵相乘的形式。比如Li 等人和Zhu 等人提出的动态属性网络嵌入（dynamic attributed networks embedding，DANE）模型和动态高阶邻近保留嵌入（dynamic high-order proximity preserved embedding，DHPE）模型，都是基于广义奇异值分解（generalized singular value decomposition，GSVD）和矩阵摄动理论（matrix perturbation theory，MPT），在保留高阶相似性的同时，动态更新动态网络的节点表示。Ma 等人设计了一种新的矩阵分解规则，并从理论和实验上证明了算法的收敛性和准确性。

1.2 基于图神经网络的动态图链接预测模型

由于图卷积神经网络在静态图上的强大性能，一些研究者将GCN 应用于动态图的链接预测任务上，并取得了阶段性的研究成果。比如Seo 等人提出了图卷积循环网络模型（graph convolutional recurrent network，GCRN），该模型有两种形式：第一种是利用Defferrard 等人提出的GCN 模型提取静态图的特征，然后将特征作为LSTM 的输入；第二种是在第一种的基础上将LSTM 中的矩阵乘法替换成GCN 的操作。Manessi 等人引入残差网络的思想，将GCN 和LSTM 结合提出了瀑布动态图卷积神经网络（waterfall dynamic graph convolutional neural network，WD-GCN）和级联动态图卷积神经网络（concatenate dynamic graph convolutional neural network，CD-GCN）模型，并成功地将模型从节点任务拓展到了图任务上，在真实数据集上取得了很好的分类效果。Narayan 等人先利用PATCHY-SAN（PATCHY select-assemble-normalize）提取图的空间特征，然后结合LSTM 提取时域特征，提出循环图卷积神经网络（recurrent neural network on graph convolutional neural network，RgCNN）模型并在真实数据集上取得了优于Manessi 等人的效果。Pareja 等人将关注点聚焦在模型本身的适应性上而不是节点的嵌入上，提出了演化图卷积神经网络（evolving graph convolutional network，EvolveGCN）模型，该模型不训练GCN 的参数，而是去训练RNN 模型的参数，使模型参数不会随时间增长而增长。Lei 等人考虑到动态图在演化过程中的非线性特征，引入生成对抗网络（generative adversarial networks，GAN），结合GCN和LSTM提出了GCN-GAN模型。

2 动态图链接预测模型

2.1 问题定义

2.2 整体架构

本文提出了一种新的非线性时序预测模型LPMDG（link prediction model for dynamic graphs），解决动态图的链接预测问题。模型整体架构如图2所示，主要由四部分组成：（1）结构特征提取模块；（2）全局特征约束模块；（3）时域特征提取模块；（4）对抗网络训练模块。

图2 LPMDG 整体框架图Fig.2 LPMDG overall framework diagram

首先，选取一个合适的时间窗口大小，利用GCN 模型分别提取这个静态图的节点特征，通过优化本文设计的损失函数，获取图的全局特征。再将个全局特征输入到全局特征约束模块，保证全局特征在时域上表现为宽平稳随机过程。接着，将全局特征输入到时域特征提取模块，抓取时域上的非线性特征。最后，将（1）（2）（3）视为一个生成器，另外设计一个全连接网络作为判别器，利用GAN 的训练策略生成高质量的邻接矩阵。下面将详细介绍LPMDG 模型的四部分。

由于静态图原始的节点特征通常是按照一定的主观模式提取的，过于冗余，文中提出了结构特征提取模块，该模块是利用GCN 和对抗训练方式，对原始特征进行编码，以获取节点的潜在表示以及图的全局特征。其中，GCN 是卷积神经网络（convolutional neural network，CNN）在非欧数据上的扩展，自Kpif利用GCN 在半监督节点分类任务上取得卓越成果后，GCN 被广泛应用于提取图的结构特征，本文亦通过GCN 提取节点特征中最关键的成分。对抗训练方式能协助GCN 模型挖掘特征不同维度之间的非线性关系。假设存在一个节点数为的图，GCN 模型需要先得到图的邻接矩阵∈R和节点的特征矩阵∈R，然后利用式（2）进行相邻层之间的更新迭代。

为了得到全局特征，本文假设存在单射函数:R→R，该函数能将节点特征映射成全局特征。众所周知，最优的全局特征应该满足两点要求：（1）能最大程度地保留图的信息；（2）节点特征通过神经网络学习后依然能保留全局特征的成分。为了保证GCN 模型提取的全局特征能满足要求（1），本文引入互信息理论加以分析，互信息是度量两个随机变量之间的关联程度，它表示一个随机变量中包含另一个随机变量的信息量（本文将节点特征和全局特征视为两个随机变量），值越大则两个随机变量相关性越强，互相包含的信息量也越多。形式上可以表示成：

其中，(*,*)表示互信息量，表示KL 散度。下面本文将从概率的角度分析为什么互信息能增强全局特征和节点特征的联系。

互信息本身难以优化，但是注意到，如果将两个变量分开考虑（样本来自()()）和综合考虑（样本来自(,)）导致结果差别很大，那么就可以说明这两个变量、的关系很紧密。因此，为了优化问题，本文通过固定样本来源（(,)），以计算模型错误分类的概率值之和，并将其命名为关联距离（correlation distance，CD）。

（关联距离）假设存在两个集合、，并且满足||≤||，{(,)}表示从联合分布(,)采样得到的样本，则分类器将采样的样本判定为边缘分布()()的概率之和被定义为关联距离，形式上可写成：

其中，Ω={Gs|Fs=(Gs)}。据此可以进一步得到关联距离的上界：

由此，可以得到定理1。

假设两个集合、存在单射的关系，则最小化两者关联距离的误差上界等同于最大化两者的互信息。

上式可作如下理解，当、之间的互信息逼近上界时，(|)向1 逼近，这与、一一对应等价。因此得出最小化关联距离等同于最大化互信息的结论。

因为=()，并且具有反函数，所以可逆推=()，进而可得：

从形式上看，全局特征和高阶特征的关系满足定理1 的条件，同理可得：最小化全局特征和高阶特征的关联距离等价于最大化两者的互信息，即：

综合上述结论，可以总结出这样一条规律：一定条件下，全局特征的学习，在满足Infomax 准则时达到最优，即输入和输出的互信息最大时。为此，本文采用如下损失函数进行对抗训练：

其中，表示判别器，X表示潜在特征，表示负样本的特征。

虽然动态图的演化主要表现在时间维度上，但是内在驱动却是静态图的规律性。平稳过程是统计特性不随时间变化而改变的随机过程，是时序分析中寻找共性特征的重要工具，最常见的可分为严平稳过程（strictly stationary process，SSP）和宽平稳过程（weakly stationary process，WSP）。SSP 要求一切概率性质都固定，这在统计上无法验证，而WSP 要求相对宽松，只需要期望和自相关函数不随时间变化而改变即可。因此，本文假设全局特征在时域上是一个宽平稳随机过程，并设计与之对应的感知模块，该模块收集一个时间窗口的全局特征，并且将这些特征作为采样点去拟合整个时域演化曲线的概率特性，以此逼近真正的宽平稳随机过程。

若用{ε|∈}表示随机过程，则WSP 的两个性质在形式上可以表示成：

为了让上述两个公式具有现实意义，给出定理2：

若存在集合={ε|∈}，且关系：(ε,ε)=(-)成立，则的子集也满足关系。

显然，在一个时间窗口中的全局特征{(-+1),(-+2),…,()}，其自相关函数满足定理2：

同理，可得期望的表现形式：

其中，表示期望，(*,*)表示自相关函数，表示期望函数，表示随机变量，表示函数，()表示时刻GCN 提取的全局特征。若自相关函数可逆，则由上述式（12）、式（13）和定理2，可以进一步构造损失函数：

其中，⊙表示哈达玛积，表示时间窗口的大小，-表示时间差，将-进行one-hot 编码后作为标签，与全连接网络MLP 的输出构造优化目标。

RNN 系列的模型是解决时域问题的有效方法，LSTM 是一种特殊的RNN，它通过利用门机制解决了RNN 在训练过程中梯度消失和梯度爆炸的问题。为了捕获图序列在时间维度上的长短依赖关系，本文将GCN 提取的全局特征{(-+1),(-+2),…,()}作为LSTM 的输入数据。通常标准的LSTM 包含三个门（遗忘门、输入门、输出门）和一个记忆细胞。例如在时刻，LSTM将-1 时刻的细胞状态向量c和隐状态向量h和时刻的输入向量()同时作为输入，然后输出当前时刻的状态向量h：

LSTM 具体的更新步骤如下所示：

其中，i、o、f、c和h分别表示输入门、输出门、遗忘门、细胞状态、隐状态；{θ,θ,θ,θ,b,b,b,b}分别表示对应的网络参数；⊙表示哈达玛积。激活函数如下：

当()经过LSTM 模型之后，得到预测的+1 时刻隐状态h。本文在LSTM 之后另设计一个全连接神经网络，该网络以h作为输入，输出维度为×，即预测的邻接矩阵ˉ。为了训练LSTM，本文构造均方差损失函数：

为了探索动态图在时域上演化规律的一致性，本文利用GAN 来提高LSTM 的性能。经典的GAN由一个生成器和一个判别器组成，其优化过程采用极小极大的策略。一方面，生成器生成伪数据欺骗判别器，让判别器无法区分数据的真伪；另一方面，判别器一直优化性能，尽可能地区分真数据和伪数据。形式上表示为：

其中，和表示生成器和判别器的网络参数。但是难以直接训练，通常是采用控制变量法将生成器和判别器分开训练，先训练判别器，然后训练生成器，如此反复迭代直至模型收敛，两者的优化目标如下所示：

总结上述各部分，可得模型LPMDG 的训练过程，如算法1 所示。

LPMDG 算法

3 实验

3.1 数据集

为了验证LPMDG 模型的有效性，本文在三个常用数据集上进行了实验，这三个数据集的具体情况如表1 所示。

表1 数据集的具体情况Table 1 Details of dataset

USCB是衡量无线网状网络中链接质量的数据集，图中的节点表示电脑主机，图中的链接权重表示某个时间片内两个主机之间的流量或者链接存在的质量。为了构造无权无向图，本文设置一个质量的阈值，权重大于阈值设为1，否则设为0。SBM是随机图模型生成的图，它按一定的规则构成社区并模拟社区的演化。AS是一个由路由器组成的通信网络，图中节点表示路由器，图中链接表示路由器之间的流量交换，与处理USCB 数据集的方法相同，本文将AS 数据集设计成无权无向图的演化序列。

本文采用MSE（mean square error）和AUC（area under the curve）两个标准来评价模型的性能。MSE是最常见的评价指标之一，它通过逐点比较预测值和真实值的距离得到模型性能的量化结果。AUC 是ROC（receiver operating characteristic curve）曲线下的面积，而ROC 曲线的横纵坐标是由真阳性率（true positive rate，TPR）和伪阳性率（false positive rate，FPR）构成。AUC 值越大表示当前的分类器越有可能将正样本排在负样本的前面，从而说明模型的分类效果更好。

为了验证模型的泛化能力，本文将提出的模型和下面四个模型进行比较：

（1）GCN：第一个对比的模型是静态的GCN 模型，该模型没有任何针对时域信息的处理，仅对每一个时间片的静态图进行建模。

（2）GCN-GRU：是在GCN 模型的基础上，对每个节点的嵌入利用GRU（gated recurrent unit）递归模型进行联合训练。

（3）EnvolveGCN：利用RNN去更新GCN的参数，达到捕捉图序列动态性的目的，其中EnvolveGCN-h和EnvolveGCN-o 的区别在于RNN 的选取上，前者采用GRU，后者采用LSTM。

（4）GCN-GAN：将GAN、GCN、LSTM 进行组合设计，利用GCN 提取静态图的特征，LSTM 捕捉时域信息，GAN 优化模型的性能，充分发挥各个模块的优势，直接生成图的邻接矩阵。

3.2 实验设置

为了验证LPMDG 模型的有效性，本文的实验都是在统一的实验环境下进行的，具体如表2 所示。另外，用于对比的模型均采用原论文的实验配置，而LPMDG 则采用如表3 所示的参数设置，并且在训练过程，本文使用Adam 优化器进行优化，学习率设置为0.001。

表2 实验设置Table 2 Experimental setup

表3 模型参数设置Table 3 Setting of model parameters

3.3 结果与分析

实验结果如表4～表6 所示，通过观察对比可以发现，LPMDG 的效果在大多数情况下优于上述四种模型，这是因为LPMDG 不仅考虑了时间的全局性，还考虑了空间的全局性。反观另外几个模型，GCN 并未考虑时间的因素，只是将参数更新过程视为图在时域上的演化过程；GCN-GRU 虽然考虑了时间的影响，但是将每个节点看作一个单独演化的过程，忽视了全局信息的作用；EnvolveGCN-h 和EnvolveGCN-o认为图的演化过程蕴含在模型参数中，因此更加关注模型参数而不是单个节点，但是这种想法假设性太强，并且没有关注图本身的演化趋势；GCN-GAN结合了GCN、LSTM 和GAN，但是依旧将节点单独考虑，没有考虑图的整体性。

表4 USCB 的预测结果Table 4 Prediction results of USCB

表5 SBM 的预测结果Table 5 Prediction results of SBM

表6 AS 的预测结果Table 6 Prediction results of AS

本文的基准模型是GCN-GAN，为了验证所提创新点的作用，本文构造了LPMDG*模型。LPMDG*对应于创新点1，比基准模型更加注重全局特征，但是缺少WSD 的约束。LPMDG 则是本文的完整模型，由于创新点2 是基于创新点1 的，在实验部分不需要单独验证创新点2 对于基准模型的作用。从GCNGAN、LPMDG*和LPMDG 的实验结果来看，AUC 指标都有不同程度的提升，MSE 在大多数情况下也是有所减小的，这足以说明全局特征对重构任务的重要作用。另外LPMDG 在三个数据集上的表现都是优于LPMDG*的，这也反映了宽平稳随机过程确实能约束图在时域上的演化进程。

本小节给出SBM 在训练过程中损失函数值的变化曲线，如图3 所示。其中横坐标是迭代次数，纵坐标是函数值。可以看出，损失值虽然在局部有些许的波动，但是其整体趋势是下降的，并且随着迭代次数的增多，它的值逐渐收敛。由此，可间接证明本文模型在一定程度上是收敛的。

图3 SBM 训练损失Fig.3 SBM training loss

超参数是影响神经网络性能的重要部分，比如LPMDG 模型中的时间窗口和隐空间的特征维度。据此，在USCB 和SBM 上做了进一步的实验，观察这些参数对本文模型的影响。首先，为了验证不同时间窗口的影响，将USCB 隐空间的特征维度定义成64，SBM 的设为32，时间窗口取值分别为{2，3，4，5，6，7，8，9，10}，得出图4 和图5 的实验结果。然后，为了验证潜在特征维度的影响，本文将USCB 的时间窗口定义为6，SBM 的时间窗口定义为10，潜在特征维度的取值为{16，32，64，128，256}，得出图6 和图7的实验结果。

图4 AUC 实验结果（固定d）Fig.4 AUC experimental results(fixed d)

图5 MSE 实验结果（固定d）Fig.5 MSE experimental results(fixed d)

图6 AUC 实验结果（固定w）Fig.6 AUC experimental results(fixed w)

图7 MSE 实验结果（固定w）Fig.7 MSE experimental results(fixed w)

从实验结果来看，当=6，=64和=10，=32时，模型分别在USCB 和SBM 上的表现是最佳的。这是因为USCB 的节点个数相对较小，需要在隐空间增加维度，提高特征的表现力，而SBM 节点个数相对较多，原始的特征维度很容易造成信息冗余，在隐空间进行适当的特征降维，能提高潜在特征的质量。另外，同样的改变，对于小的图来说可能发生了大的变化，但是对于大的图来说可能变化很小，因此节点少的数据集会更加注意短期的演变趋势，节点多的数据集会更加关注长期的变化方向。

4 结束语

针对动态图的链接预测问题，本文提出了LPDMG模型，该模型利用GCN、LSTM 和GAN 的优势，耦合局部特征和全局特征的关系，学习高质量的全局特征表示。此外LPDMG 模型还考虑了全局特征在时域上的规律性，通过设计宽平稳感知模块，从而约束全局特征演化的平滑性。本文在三个动态图的数据集上对模型的性能进行了验证，实验结果表明，全局特征的高质量和平滑性对链接预测模型有着重要作用。在未来，会尝试将本文算法思想应用于解决多关系图和异构图的相关问题。