基于深度神经网络和门控循环单元的动态图表示学习方法

李慧博，赵云霄，白 亮*

（1.计算机智能与中文信息处理教育部重点实验室（山西大学），太原 030006；2.山西大学计算机与信息技术学院，太原 030006）

（∗通信作者电子邮箱bailiang@sxu.edu.cn）

0 引言

基于图结构数据的表示学习已经成为一项重要的机器学习任务，在诸如社交网络［1］、合作网络［2］、蛋白质网络［3］等各种结构中普遍适用。图表示学习的基本思想是学习节点的低维向量表示，要求该向量尽可能地保留节点在图中的结构信息、属性信息等。目前多数静态图表示学习［4-6］已经能有效学习到节点的向量表示，但生活中大量的真实数据表现出复杂的时间特性。例如学术合作网络中，研究人员周期性地更换合作对象；蛋白质之间的相互作用导致结构体时刻在发生变化；电子邮件通信网络的结构也会随着时间的推移不断发生变化，这些信息说明了图结构及其属性随时间的动态演变过程。在这种情况下，动态网络建模对于准确预测节点属性和未来链接非常重要。

本文的工作是对一系列动态图的学习，捕获到节点的各种信息，进而预测下一时刻的网络。之前一些工作［7-9］试图学习图的结构信息和节点的时态信息，但是他们的方法存在对邻居节点信息提取不完善、不能有效保留历史节点信息、预测精度较低等问题。

本文受Sankar 等［10］的提出的DySAT 模型的启发，提出了DynAEGRU 方法。DySAT模型是通过两个注意力模块分别学习图的结构信息和节点的时态信息。本文方法DynAEGRU以自编码器为框架，首先编码器使用深度神经网络来学习网络的结构特征，然后输入递归层来学习网络中的时间动态性，最后在解码器重构网络与真实网络对比构建损失。本文将实验用在链路预测任务上进行评估，与经典的图表示学习算法进行比较，结果表明DynAEGRU 在链路预测任务上优于对比算法。本文的主要工作如下：

1）提出了一种新的动态网络学习方法——DynAEGRU，该方法可以有效捕获节点的结构和时态特征信息；

2）展示了DynAEGRU 方法的各种变体，以显示主要的优势和差异；

3）通过对比实验验证了DynAEGRU 方法在链路预测任务上的有效性和优势。

1 相关工作

图表示学习算法以图的结构是否会发生变化可以分为两类：1）静态图表示学习，通过训练一个固定网络来获取图中节点的向量表示；2）动态图表示学习，它通常考虑图的多个快照，并获得每个节点向量表示的时间序列。考虑到真实世界网络的动态性，近几年的工作多致力于动态图的学习。

1.1 图表示学习

静态图表示学习方法的目标是在嵌入空间中尽可能地保持原始图中的某些属性信息。一部分工作旨在保持图中的结构信息［5-6］；另一部分旨在保持嵌入空间中节点的距离［11-13］；还有一些基于深度学习的方法［14-15］，它们使用深度自编码器保留图中节点的属性和结构信息。

目前动态图表示学习的多数工作是学习多个快照图，目的是减小模型复杂度并保证嵌入的稳定性。DynamicTriad［7］是通过在动态网络中预测三角闭合的概率来学习每个节点的向量表示，但此算法仅收集前两个时间步的信息，不能有效捕捉动态网络的结构变化模式；DynGEM［8］通过最小化一阶和二阶相似度学习节点信息，但仅保留了前一个时间步的网络信息，忽略了动态网络长时间的演化模式；DynAERNN［9］是以编码器-解码器为架构，将网络中历史节点组成序列用长短期记忆（Long Short-Term Memory，LSTM）网络［16］进行学习，模型缺点是不能有效提取邻域结构。

通过对近几年动态图表示学习的观察，发现大多数模型存在对邻域节点特征信息提取不完善、因保留时间步数较少而无法有效获取动态图的时间演化模式等问题。

1.2 自编码器

自编码器（Auto-Encoder，AE）［17］分为编码器-解码器两部分结构，是前馈非循环神经网络，具有非常好的提取数据特征表示的能力，在图像重构［18］、聚类［19］、机器翻译［20］等方面有着广泛的应用。编码器负责接收输入x，并通过函数h变换为信号y，表达为：

解码器将信号y作为输入，通过函数f重构信号r表达为：

解码器定义误差损失为原始输入x与重构信号r之差，网络训练的目标是减小两者之间的误差，并通过反向传播更新隐藏层。自编码器可以进行权值共享，即解码器和编码器的权值彼此互为转置，目的是减少训练参数，提高网络学习的速度。

1.3 门控循环单元

2014 年Cho 等［21］提出门控循环单元（Gated Recurrent Unit，GRU）。GRU是循环神经网络（Recurrent Neural Network，RNN）［22］的一种变体，RNN 结构如图1所示。对于一个长度为T的序列，使用RNN 建模后是一个长度为T的前馈神经网络，第t层的隐藏状态聚集了前t次的信息，是用当前输入xt和上一层隐藏状态的输出ht-1进行建模。

图1 GRU的结构示意图Fig.1 Schematic diagram of GRU structure

由于RNN 存在梯度弥散和梯度爆炸问题，往往和预期的效果相差甚远，因此提出GRU 网络。RNN 和GRU 网络同样是使用前一隐藏状态和当前输入进行建模，不同的是后者在其内部结构使用了重置门和更新门，GRU 结构如图2 所示。直观来看，重置门决定了如何将新的输入信息与历史信息相结合，更新门定义了前面记忆保存到当前时间步的信息量。单个GRU网络的隐藏状态表示定义为：

其中：rt和zt分别为控制信息传递的重置门和更新门；Wr、Wz、Wh'、Wo为学习的参数矩阵；(1-zt)∗ht-1表示对隐藏状态中选择性地丢弃上个时间步输出ht-1维度中不重要的信息；则表示对当前隐藏状态选择性地保留，保留当前时间步h't中一些重要的信息；因此ht就是保留上一时间步中相关的信息，并把当前时间步中相关信息加入其中；yt是当前时间步的输出，其信息不会再改变。GRU 的优势就在于使用一个门控zt就可以同时丢弃和保留维度中的信息，并且效率高，更易于计算。

2 DynAEGRU结构

本文旨在解决上述动态图网络中的复杂性和动态性问题，本文提出的方法DynAEGRU 采用经典的无监督自编码器框架学习，它使用编码器对输入图A进行编码生成特征X，并将特征X使用解码器生成，通过最小化A与重构邻接矩阵的距离，在编码器将输入图映射到向量空间的同时让解码器学习到预测图的能力。

1）编码器部分，本文分别使用聚合函数和分段GRU 来学习图的结构和时态特征信息。其中聚类函数采用两层神经网络，每层使用聚集邻居特征，这样在保留所有邻居信息的同时，更加准确地学习到局部邻域结构，并使图的计算更加简便，效率更高；分段GRU 则通过保留每个节点出现的所有时刻的历史信息来提高节点之间边的预测能力。

2）解码器可以重构原始图并与原始图对比来构建损失，这样可以更加准确地学习到节点之间的链接关系。

本文方法DynAEGRU 的结构如图2 所示：图中左侧编码器（Encoder）部分采用聚合函数和分段GRU 对每个时间步网络图进行编码；右边解码器（Decoder）部分完成图的预测，并使用交叉熵损失函数来描述预测与真实网络之间的差距，最后使用反向传播实现网络的训练。实验表明，本文在学习随时间推移节点和边不断增加的网络图时，可以有效地学习节点信息并提高链路预测能力。

图2 DynAEGRU的结构Fig.2 Structure of DynAEGRU

2.1 编码器

本文将深度神经网络和GRU 拼接到一个层中构成编码器。在结构层，使用两层神经网络来捕捉节点的邻域结构信息；在时态层，通过GRU 网络分段学习节点的时态特征，并将结果拼接得到编码器的嵌入输出。

2.1.1 结构层

本文在结构层引入了一个简单灵活的聚合函数f(X，A)用于图的信息传播。通过输入一个t时刻的特征矩阵X和对称的邻接矩阵A，f(X，A)能够输出当前时刻的向量表示。t时刻的聚合函数定义为：

其中：i和j分别表示节点所在的行、列，代表图中的两个节点；X∈ℜn×k为节点输入特征，n和k分别为t时刻图中节点数和输入特征维度；A∈ℜn×n是图的邻接矩阵，若i，j两节点之间有边，Ai，j=1，否则Ai，j=0。ReLU(x)=max(0，x)为激活函数，W0∈ℜk×m，W1∈ℜm×f分别为可学习参数矩阵，m和f分别为隐藏层、输出层的特征维度；b1∈ℜm，b2∈ℜf分别为两层神经网络的偏置。

2.1.2 时态层

在动态图中，一些交互存在长期依赖关系，这种依赖关系无法被全连接的神经网络层捕捉到。因此在结构层输出节点嵌入后，将其和过去节点的嵌入共同输入到序列模型GRU 网络中进行学习。

考虑到每一个时间步的节点数都在增加，因此在进行训练网络时根据每个时间步节点的数量分段执行GRU 网络。通过定义一个函数：GRU(·)函数表示GRU 神经网络，旨在学习每个时刻节点的时态信息，t时刻的时态层函数表达为：

其中：t表示当前时间步，Gt为t时刻的拓扑图，Gti表示第ti个子图，yVi表示第i个时间步所增加节点的向量表示。

此结构在每个时间步对每个新增节点进行GRU 训练，目的是保留每个时间步的信息，并且通过更新门和重置门可以保留更有效的信息。

2.2 解码器

解码器通过编码器学习到的前t个时间步的信息重建邻接矩阵，即为预测t+1 时刻的拓扑图。解码器使用点积来重构原始图，解码过程表达为：

邻接矩阵直接决定了图的拓扑结构，所以此模型的目标就是使重构邻接矩阵与原始邻接矩阵尽可能地相似，将两者对比构建损失函数，反向传播更新参数，从而学习隐藏层节点的表示。将t时刻的损失定义为交叉熵损失函数：

其中：y表示t时刻原邻接矩阵的标签值，表示重构邻接矩阵预测值，k表示元素个数，w0表示正例的权重。

在DynAEGRU 中，编码器第一部分设计一个聚合函数f(X，A)通过使用At⋅Xt来聚集目标节点的邻域信息；第二部分对网络中节点分段使用GRU 网络学习每个时间步新增节点的时态特征，并将结果拼接得到嵌入；最后在解码器重构邻接矩阵，与原邻接矩阵对比构建损失最终学习节点向量表示。

算法1 动态网络节点嵌入计算算法。

输入 随机值矩阵X1，时间步数T，每个时间步的邻接矩阵{A1，A2，…，AT}，每个时间步增加节点数{V1，V2，…，VT}；输出T时刻图中的节点嵌入ZT。

3 实验与分析

本文将在动态链路预测的基本任务上评估DynAEGRU学习节点表示好坏的能力，动态链路预测已被广泛使用在评估动态网络表示学习的算法［8，23］上。在此实验中，将DynAEGRU 测试的性能与各种静态和动态图表示学习基线进行比较。

本文所进行的实验与对比算法针对的数据集皆是无属性图，本文方法通过式（8）可以很容易地推广到属性图上，简单来说，本文方法采用的是随机值作为嵌入初始化，属性图初始化嵌入同样是通过随机矩阵作为映射函数进行降维，最后得到的矩阵将作为节点嵌入，因此两者达到的效果是一样的。本文实验更想突出的是图的结构和时态信息，采用嵌入向量作为顶点的特征，在三个公开可用数据集上的实验结果表明，DynAEGRU相比其他模型获得了较高的性能提升。

3.1 实验数据集

实验使用的三个动态图数据集详细情况如表1 所示。由于动态图通常包含连续的时间戳，本文实验使用合适的时间窗口将数据分割成多个快照，这样每个快照都有公平且合理的交互次数。

表1 实验中的数据集Tab.1 Datasets in experiments

Email-uci［24］：该数据集包含的内容是在加州大学欧文分校的在线社交网络平台上，用户之间在六个月时间内发送的私人信息。快照是使用其通信历史创建的，时间窗口为10天。

Yelp［25］：该数据集使用第11 轮的Yelp 数据集挑战赛，选择评级数量最多的亚利桑那州的所有企业和一组选定的餐馆类别。此外，只保留至少有15 个评级的用户和企业。最后，此数据集使用6 个月的时间窗口提取2009 年至2015 年期间的12个快照。

ML_10M［26］：该数据集描述了电影用户的标签行为，以及用户对其分级电影应用的标签，用户标签链接将用户与他们在某些电影上应用的标签联系起来。本文实验中数据集使用3个月的时间窗口来提取3年中的13个快照。

3.2 实验设置

实验在动态图中的链接预测任务上进行评估，学习多个快照图上的动态节点表示{G1，G2，…，GT}，并在评估期间使用Gt预测Gt+1时的链接。将三个数据集中每个节点对正确分类为链接和非链接来比较它们。该模型使用前一个时间步的嵌入作为初始化当前时刻快照图的向量表示，执行梯度训练。

通过训练动态链接预测的逻辑回归分类器来评估不同模型的性能［7］。本文设置初始学习率为0.000 1，根据Gt+1中的链路和相等数量随机抽样的未连接节点对创建评估示例。本文使用20%的链接作为验证集来调整模型的超参数，20%的链接进行训练，剩下的60%作为本实验的测试集。

3.3 评价指标

本文使用受试者工作特征（Receiver Operating Characteristic，ROC）曲线和ROC 曲线下方面积（Area Under ROC Curve，AUC）评分来评估链路预测的性能［6］。ROC 曲线是反映敏感性与特异性之间关系的曲线，可以直观地判断学习效果的好坏。AUC评分是衡量二分类模型优劣的一种评价指标，表示预测的准确性，AUC 值越高，即曲线越接近左上角说明预测准确率越高。该方法简单、直观，通过图示能够分析方法的准确性。

3.4 基线模型

将本文方法DynAEGRU 与几种静态图和动态图表示学习的算法进行比较，分析了使用时间信息进行动态链路预测的好处。为了与静态图表示学习算法进行公平的比较，通过构建一个直到时间t的聚合图来提供对整个历史快照图的访问。本文对所有基线使用原论文中作者提供的参数，并设置最终嵌入维数d=128。

第一，首先和几种无监督静态嵌入方法进行了比较：如node2vec、GraphSage［27］等。按照GraphSage原论文中的实验设置，对邻域信息使用平均、池化、LSTM 等聚合器，并报告每个数据集中评价最高的聚合器的性能。基于本文的动机，对比算法中使用同样可以聚集邻域结构信息的图注意力机制（Graph Attention neTwork，GAT）［28］作为聚合器进行实验，称为GraphSage-GAT；并把GAT 作为自编码器中的编码器来进行实验对比，表示为GAT-AE。

第二，与动态图表示学习的最新研究做了比较。DynamicTriad 利用三元闭合过程生成一个图的嵌入表示；DynGEM 利用深度编码器模型，仅使用t-1时刻的快照图，在t时刻生成动态图的嵌入；DynAERNN 使用编码器-解码器结构，用LSTM 来编码历史信息；DySAT 模型是在每个快照图上使用两个注意力模块分别学习结构嵌入和时态嵌入，最终通过二元交叉熵损失函数实现对图中节点的学习。

3.5 实验结果

本文用T个时间步中出现的节点对模型进行评估。从实验结果中观察到，与所有数据集的最佳基线相比，DynAEGRU实现了1～7 个百分点的AUC 评分增益。本文将DynAEGRU的性能调整为比其他算法相对更稳定，这种对比在所有数据集中都表现明显。本文实验在pytorch 中实现了DynAEGRU测试，并使用Adam优化器［29］进行训练，实验结果如表2所示。

表2 各算法在三个数据集上进行链路预测任务的实验结果比较 单位：%Tab.2 Comparison of experimental results of different algorithms performing link prediction task on three datasets unit：%

此外，为了验证本文提出的聚合函数和分段门控神经网络两部分的有效性，并了解它们分别学习了节点的哪方面信息，对DynAEGRU 进行了消融实验，做法是独立地去除编码器中的结构层和时态层，从而创建更简单的结构，称DynAE为变体一，DynGRU 为变体二。分别对两种变体使用和DynAEGRU 相同的损失函数、相同的数据集和相同的参数设置以准确比较两种变体的学习能力。实验对比了DynAEGRU、DynAE 和DynGRU 在三种数据集上做链路预测任务的AUC评分，结果如图3所示。

图3 DynAEGRU及两种变体的AUC性能Fig.3 AUC performance of DynAEGRU and two variants

DynAEGRU、DynAE 和DynGRU 在三个数据集上的ROC曲线如图4 所示。DynAEGRU 预测性能对变体一实现了3～9个百分点的AUC 增益效果。这表明本文提出的聚合函数可以很好地捕获节点的邻域结构信息，在变体一结构上加入GRU 网络可以有效提取动态图的时间演化信息，提高动态图的链路预测性能。DynAE 模型结果表明随着图中节点的增加，变体一相对DynAEGRU 的增益效果逐渐降低，可以判断节点数越多时，结构特征信息在目标节点信息中占据越来越大的比重。

图4 Email-uci数据集上的ROCFig.4 ROC on Email-uci dataset

在实验中选用上一个快照图的嵌入表示作为当前节点向量表示的初始化值进行学习，因此学习到的向量表示更加稳定。DynGRU 模型用随机值作为初始化向量表示，后期没有用聚合器来捕获邻域特征，这导致节点几乎不包含任何信息，因此在三个数据集上的AUC评分值均在0.7以下。这个结果表明图中节点自身和邻域属性特征包含了大量信息，若缺少这部分信息，可能会导致学习预测能力降低，直接使用价值很低。

在Email-uci 和Yelp 数据集上发现，DynAEGRU 在面对网络较稠密的情况时，有更好的表示学习能力，链路预测能力明显强于其他基准模型，能高效地提取节点的结构特征信息。在ML_10M 数据集节点数较多的情况，DynAEGRU 的链路预测能力比其他两个数据集提高很多；而DySAT 模型采用了双自我注意力机制，在节点数较多但是更稀疏的数据集上可以取得更好的性能。可以观察到DynAE 模型在节点数量较少但数据信息较为复杂的情况下，依然可以很好地学习节点的邻域特征。

4 结语

本文提出了一种新的动态网络表示学习方法DynAEGRU。针对对比算法在链路预测上的不足，DynAEGRU 方法在编码器结构层使用深度神经网络捕获节点周围的邻域特征信息，时态层通过GRU 学习节点的时态依赖特征，并使用增量式的方法进行学习。本文在三个数据集上通过链路预测任务结果证明，本文定义的聚合函数可以准确捕捉节点的结构信息，而GRU 可以很好地聚集到节点的时态信息。实验结果表明，DynAEGRU 在较稠密复杂的网络中能很好地学习节点的嵌入。

虽然实验是在没有节点特征的图上进行的，但是DynAEGRU 可以很容易地推广到特征丰富的属性图上。在未来的研究中，将使用更复杂的数据集来使本文框架的连续时间一般化，并将其运用到解决更细粒度的时间变化上。