基于动态网络表示的链接预测*
2020-08-29韩忠明李胜男郑晨烨段大高杨伟杰
韩忠明 李胜男 郑晨烨 段大高 杨伟杰
1) (北京工商大学计算机与信息工程学院，北京 100048)
2) (北京工商大学食品安全大数据技术北京市重点实验室，北京 100048)
1 引 言
在现实世界中, 很多复杂系统以复杂网络的形式出现, 如社会网络、引文网络、生物网络和web 网络等. 网络提供了一种组织现实世界中的多样化信息的方式, 成为人们工作生活中不可或缺的一部分, 对这些网络进行分析研究具有非常大的学术价值和潜在应用价值[1]. 在这些网络中, 节点之间的交互行为通常以“链接”的形式表示, 即使用边将两个节点连接. 以社交网络为例, 网络节点用于描述用户, 边用于描述用户之间的交互行为. 链接预测[2]通过分析网络中的信息来预测未来网络中任意两个节点之间是否可能出现链接. 有效的链接预测对人们生活中各个方面都具有重要意义, 例如帮助人们控制信息在网络上的传播, 帮助社交平台进行更准确的好友推荐等.
在真实世界中, 网络会随着时间的推移不断进行演变, 即网络中的节点和边会随时间发生变化.网络演变会导致网络信息发生变化, 进而对链接预测任务产生影响, 因此, 捕获这些网络演化信息是很有必要的. 以社交网络为例, 网络中随时会有新用户注册, 用户随时会创建新的好友关系, 这些新信息的增加不仅改变了当前用户的属性信息, 其邻域的拓扑结构和属性信息也会随之发生改变.
图1 展示了一个动态网络示意图, 假设在对网络进行链接预测任务时, 以节点共同邻居个数度量节点相似性, 相似度越大的节点对在下一时刻发生链接的可能性越大. 在T1 时刻, 网络中的节点2 和节点5 拥有一个共同邻居(节点4), 在T2 时刻, 该网络在节点3 和节点5 之间新增了一条边,即节点3 变成了节点5 的邻居. 此时节点2 和节点5 拥有两个共同邻居(节点4 和节点3), 它们在下一时刻产生链接的可能性变大. 由此可见, 虽然新增加的边只涉及到节点3 和节点5, 但其邻域中的节点2 的属性也受到了影响. 因此, 网络动态演化对节点及其邻域的特征信息有着非常重要的影响, 在链接预测过程中加入动态信息将会提高链接预测的性能.
图1 动态网络示意图Fig. 1. Schematic diagram of dynamic network.
现有的链接预测方法大多针对静态网络, 使用网络拓扑结构特征分析的方法进行链接预测, 当网络信息发生变化时, 其性能将会受到很大影响. 此外, 网络中的节点并不是每时每刻都在产生新的交互信息, 其发生变化的时间是不规律的, 即变化发生的时间分布不均匀. 而两次变化之间的时间间隔会影响节点的偏好信息. 例如, 如果某节点两次变化之间的时间间隔较长, 则应该更关注新的交互信息, 因为新的信息更能体现该节点当前的偏好. 为了有效地捕获网络中的动态演化信息, 本文使用表示学习方法, 用低维稠密向量表示网络节点的偏好信息, 通过度量网络节点表示的相似度进行链接预测, 并提出了基于动态网络表示的链接预测模型
DNRLP(dynamic network representation based link prediction). 针对网络演化产生的动态信息,DNRLP 设计了基于不均匀时间间隔的信息更新机制. 同时, 考虑到动态信息对相关节点邻域的影响, 设计了基于连接强度的随机游走算法对邻域信息进行更新. 该模型可以有效地捕获网络动态信息, 提高链接预测的质量和有效性.
2 相关研究
2.1 链接预测
现有的链接预测研究方法主要分为两类, 基于网络拓扑结构特征分析的方法和基于机器学习的方法. 传统的链接预测方法主要是通过对网络拓扑结构进行特征分析, 计算节点之间的相似度, 认为相似度高的节点在将来会发生链接. Newman 等[3]首先提出基于网络共同邻居的节点相似度计算方法, 即节点拥有的共同邻居越多, 越可能在未来发生链接. Adamic 等[4]提出了一种新的网络节点相似性度量方法, 该方法根据共同邻居节点的链接情况为每个邻居节点设置权重, 并使用其加权和作为节点对的相似度. Fouss 等[5]通过随机游走算法对网络中节点的邻域信息进行采样, 得到目标节点的随机游走序列, 然后计算节点随机游走序列的相似性进行链接预测.
随着人工智能和机器学习技术的快速发展, 越来越多的研究人员尝试使用机器学习方法去解决链接预测问题. 基于机器学习的链接预测方法首先需要从网络中得到各个节点的特征向量, 然后将节点的特征向量作为机器学习算法的输入. Hasan 等[6]将链接预测问题转化为机器学习中的二分类问题,尝试使用支持向量机[7], 多层感知机等机器学习方法进行链接预测, 若两节点间未来可能产生链接则预测值为1, 否则为0. Freno 等[8]使用自然语言处理领域的词袋模型对论文引用网络中论文的摘要进行建模, 得到论文节点的特征表示, 然后使用神经网络进行链接预测. Hosein 等[9]针对引文网络使用论文作者和论文的互聚类方法进行链接预测.Xu 等[10]将信息熵应用于加权网络中的链接预测,提出基于路径贡献的加权相似度指标, 实现了加权网络的链接预测. Lai 等[11]针对复杂网络, 用模块化的置信度传播算法来获得网络的底层块结构, 并通过块结构信息对节点间产生链接的可能性进行建模, 从而实现链接预测. Kovács 等[12]针对蛋白质相互作用网络, 根据蛋白质之间的交互特性,使用长度为3 的网络路径(L3)进行链接预测.Pech 等[13]提出了一种新的链接方法, 由节点邻居贡献率的线性和来估计链接的可能性, 从而将链接预测问题转化为似然矩阵的优化问题. Zhang 等[14]认为现有的相似性度量方法往往只适用于某几种网络, 为此提出了一种g-衰减理论来统一现有的相似性度量方法, 同时还提出了一种基于图神经网络(graph neural network, GNN)[15]的链接预测框架SEAL, 从网络中的局部子图来学习节点表示以进行链接预测. 以上方法大多是针对特定网络提出了新的相似性度量方法. 除此之外, Ostapuk 等[16]首次将深度主动学习[17]应用于链接预测, 基于贝叶斯深度学习[18]提出了一种深度主动学习框架ActiveLink, 将不确定性采样引入到聚类算法中,并且采用基于元学习[19]的无偏增量的方法进行训练, 提高了模型的训练速率. 相较于传统的基于网络结构相似度的链接预测方法而言, 有监督的机器学习模型使链接预测的结果有了明显提升.
由于真实世界中的网络是随时间不断演化的,因此虽然上述方法在大规模网络的链接预测中取得了较好的成果, 但其大多仅考虑了网络结构且大多只适用于静态网络, 而忽视了真实网络中的动态信息以及节点间产生链接的时间信息, 因而在网络发生变化时需要进行大量的重新计算.
2.2 动态网络表示学习
由于复杂网络通常包含数十亿的节点和边, 且数据具有稀疏性, 在网络上很难直接进行复杂的推理过程, 为了有效地进行复杂网络分析, 学者们提出了各种各样的网络表示学习[20]方法. 网络表示学习作为网络分析领域的一个重要基础问题, 其核心思想是寻找一个映射函数将网络中的节点转化成低维稠密的实数向量, 即网络节点表示. 这些网络节点表示保存了网络中所包含的信息, 为网络分析任务提供了良好的特征基础, 并可以直接用于各种网络分析任务中, 如链接预测, 社团检验, 推荐系统等. 网络表示学习的形式化定义如下:
对于给定网络 G=(V,E) , 使用映射函数fv→τk为网络中的每个节点 v∈V 学习到一个低维稠密的实数向量 Rv∈Rk作为节点的表示向量,该向量的维度 k 远远小于网络节点的总个数 |V| .
由于网络表示在常见的网络分析任务中展现出了良好的能力, 因此越来越多的学者关注于网络表示学习领域, 并提出了多种网络表示学习方法,如DeepWalk[21], LINE[22], node2vec[23], SDNE[24],GCN[25], GraphSAGE[26]等.
近年来, 针对动态网络的表示学习研究逐渐受到了研究人员的关注. 如Michael 等[27]基于复杂网络动力学以及多元微分方程定义节点在不同时刻的表示, 提出了一种复杂网络的多尺度动态嵌入技术. Kumar 等[28]基于递归神经网络提出了JODIE模型, 对网络中的用户和项目分别进行动态表示学习, 并提出了一种并行批处理算法t-Batch. 李志宇等[29]通过对不同阶层的网络节点关系进行正负阻尼采样, 构建针对新增节点的动态特征学习方法, 使得模型可以提取大规模社会网络在动态变化过程中的结构特征. Palash 等[30]基于深度自编码器提出DynGEM 模型, 该模型可以动态学习网络中高度非线性的表示. 同时很多学者针对动态网络表示学习中的链接预测任务进行了相关研究.Chen 等[31]将长短期记忆网络[32](LSTM)与编码器-解码器体系结构相结合, 提出了一种新颖的encoder-LSTM-decoder(E-LSTM-D)深度学习模型来预测动态链接. Li 等[33]基于SDNE 算法提出了DDNE 模型, 使用门控循环单元[34](GRU)作为编码器来捕获动态网络中的时间信息, 从而在动态网络中进行链接预测. Lei 等[35]结合了图卷积网络(graph convolutional network, GCN)、长短期记忆网络(long short-term memory, LSTM)以及生成对抗网络[36](generative adversarial networks,GAN)的优势, 用深度神经网络(即GCN 和LSTM)来探索网络中隐藏的拓扑结构和演化模式的非线性特征, 用GAN 来解决动态网络中链接的稀疏性问题, 同时通过对抗的方式在动态网络中进行链接预测. 这些研究方法大多只考虑了发生变化的节点本身的信息变化情况, 而没有关注节点邻域所受到的影响. 并且现有方法大多仅考虑了均匀间隔的时间间隔, 而忽视了不同时间间隔对节点偏好信息的影响. 由于网络表示学习是网络分析的基础任务, 如何设计具有动态适应性的网络表示学习模型, 学习网络节点及其邻域的信息变化并对它们的表示进行快速更新, 对现实世界中的网络分析任务有着至关重要的作用.
3 基于动态网络表示的链接预测模型
本文针对动态网络的链接预测问题提出了基于动态网络表示的链接预测模型DNRLP. 该模型对LSTM 进行了改进, 考虑了网络演化过程中产生新信息的非平均时间间隔问题以及新信息的扩散问题, 有效地捕获和学习了网络中的动态信息,并得到了含有节点偏好信息的节点表示. 然后通过计算习得节点表示之间的相似度, 最终得到链接预测的结果.
图2 基于动态网络表示的链接预测模型结构Fig. 2. The architecture of link prediction model based on dynamic network representation.
图2 给出DNRLP 模型的结构示意图, DNRLP模型主要分为两个模块: 动态网络表示学习模块和链接预测模块, 其中动态网络表示学习模块由节点信息动态更新单元和节点邻域更新单元组成.DNRLP 模型根据 Ti时刻网络中出现的新增信息,得到与其直接关联的节点集合, 使用节点信息动态更新单元对该集合内的节点进行节点表示更新. 然后对该集合内的节点进行邻域采样, 得到与新增信息间接关联的节点集合, 使用节点邻域更新单元对邻域节点进行更新, 最终得到当前时刻更新后的网络节点表示. 基于这些节点表示使用链接预测模块计算节点间的相似度并进行排序, 最终得到链接预测的结果.
3.1 节点信息动态更新
随时间动态演化的网络可以看作不同时刻下的静态网络, 使用 G(Vt,Et,t)表示 t 时刻的网络,其中 Vt为该时刻的节点集合, Et为该时刻的边集合, t 为对应的时间戳. 随着时间的推移, 网络中的节点会不断地与网络中的其他节点建立新链接, 这些新链接会改变当前节点的属性信息. 例如在社交网络中, 如果两个用户有联系, 他们会逐渐分享共同的兴趣爱好. 新链接的建立顺序以及它们建立的时间间隔对节点属性特征的变化也有着非常重要的影响. 按照时间戳对节点 v 新产生的链接进行排序得到链接序列 Sv={(v,vi,t0),(v,vi,t1),...,(v,vi,tn)}, 其中 (v,vi,t)表示 t时刻节点 v与节点 vi之间新建立的链接, vi∈Nv表示节点 v 的一阶邻域节点, Nv表示节点 v的一阶邻域节点集合; t 表示链接建立的时间戳, t0 综上所述, 针对网络中的任一节点, 当产生新链接时, 应该根据链接产生的时间间隔决定需要更新哪些新信息, 以及需要遗忘哪些历史信息.DNRLP 模型基于LSTM 模型对网络中的节点进行动态表示学习. LSTM 模型通过遗忘门、输入门和输出门解决了对历史信息的长期依赖问题. 但是现有的LSTM 中没有考虑不同的时间间隔对历史信息丢弃策略所产生的影响, 因此我们根据动态网络信息传播规律, 在LSTM 的计算过程中增加了一个基于时间间隔的信息过滤单元(time interval based filter unit, TIFU), 从而达到了根据时间间隔的大小决定下一时刻节点对历史信息的丢弃程度的目的, 使模型更关注节点的新增信息, 其计算单元如图3 所示. 图3 基于时间间隔的LSTM 单元Fig. 3. Time interval based LSTM unit. 图3 左半部分描述了TIFU 的示意图. TIFU的工作原理是根据时间间隔 ∆t的大小, 决定当前细胞状态信息Ct−1传递到下一时刻t的信息的具体计算过程如下所示:上述公式中, TIFU 将上一时刻t −1 标准LSTM计算单元输出的细胞状态Ct−1分成了两个部分:短期记忆和长期记忆. 我们认为细胞状态Ct−1是由长期记忆和短期记忆两个部分构成的,短期记忆对信息的存储时间较短, 容易被遗忘, 而长期记忆对信息的存储时间较长, 不容易被遗忘.同时短期记忆与长期记忆并不是完全割裂的, 通过重复、巩固短期记忆可以转化为长期记忆, 即随着时间的流逝, 部分短期记忆可以演变为长期记忆.(1)式使用神经网络和tanh 激活函数自动选择历史信息中较为短暂的历史信息, 即单元的短期记忆, 其中为根据t −1 时刻的细胞状态生成的短期记忆. (2)式中为相应的需要传递给下一时刻t的长期记忆. TIFU 根据时间间隔 ∆t对单元短期记忆的部分信息进行丢弃, 如(3)式所示, 其中为保留下来的短期记忆信息, ∆t越大丢弃的短期记忆信息越多. 经过上述计算, 完成对节点历史信息保留的决策, 并得到需要传递给下一时刻t的历史信息, 如(4)式所示,将和进行组合, 并作为下一时刻t标准LSTM 单元的输入, 即最终传递给下一时刻t的节点历史信息是由节点的部分短期记忆与全部长期记忆所组成的. 图3 中右半部分为标准LSTM 计算单元示意图, 其具体计算过程如下所示: 其中xt为当前时刻t的输入向量, 表示网络的新增信息. 由于新增信息由节点vi,vj之间的新增链接产生, 因此可以通过计算两节点当前表示的加权和来得到xt, 计算方式如(5)式所示. 接下来分别对标准LSTM 单元的输入门、遗忘门及输出门进行计算, 其中σ表示sigmoid 激活函数,⊙表示矩阵乘积运算,it,ft,ot分别代表t时刻LSTM 单元输入门、遗忘门以及输出门的系数.{Wi,Ui,bi},{Wf,Uf,bf}和{Wo,Uo,bo}分为上述三种门的网络参数.表示用于更新细胞状态ct的候选状态.{Wc,Uc,bc}是网络产生候选记忆的参数.ht是在时刻t时经过上述三种门的过滤后的隐藏状态, 该状态记录了t时刻之前习得的所有有用信息.ct经过输出门舍弃掉部分信息后形成当前时刻t的输出向量ht. 根据上述TIFU 和标准LSTM 计算单元的计算过程, 可将上述过程进行如下表示: 当网络中有新信息产生时, 使用f对关系两端的节点信息(节点表示)进行更新, 其中Ct−1,ht−1为上一时刻f计算得到的细胞状态和隐藏状态,xt=W1uvi+W2uvj+b是网络新增关系为涉及到的两个节点vi和vj带来的新信息,W1,W2,b是生成新信息的表示向量的模型参数.ht即为目标节点更新后的表示向量. 针对模型冷启动问题, 在初始时刻, DNRLP模型使用网络的邻接矩阵作为网络节点的表示向量, 并对网络中每个节点进行固定大小的邻域采样, 然后使用聚合函数对节点邻域内的节点表示进行聚合, 最终得到节点初始化表示向量, 并使用上述表示向量作为f的初始化的节点表示. 网络中两节点vi,vj之间的新增链接不仅会对链接两端的节点产生影响, 同时也会影响与vi,vj距离较近的节点. 因此当网络产生新链接时, 涉及到的两个节点vi,vj的邻域节点也应该进行信息更新. 为此, DNRLP 模型通过对产生新链接的节点进行邻域采样来模拟新信息在网络中的扩散过程,然后对采样到的邻域节点进行信息更新. 这么做的原因主要有三个方面: 第一, 文献[37]表明新链接对整个网络的影响往往是局部的. 第二, 由于网络的复杂性, 与新链接直接关联的节点不一定会将收集到的新信息传播给其所有的邻居, 同时新信息很有可能会被传播到与其较近但不直接相邻的节点.第三, 通过实验发现, 当对目标节点的局部邻域进行信息更新时, 模型的性能会更好. 在节点邻域采样的过程中, DNRLP 模型采用基于连接强度的随机游走算法. 把节点间的连接强度作为随机游走中的边权重, 对目标节点进行加权随机游走采样从而得到节点vi,vj的局部邻域. 其中边权重的计算过程如下: 其中,uv为节点v的表示向量,Nv表示节点v的一阶邻居节点集合,fs(uvi,uv)表示节点v和其邻域节点vi间的连接强度, 可以将该连接强度看作一个归一化后的概率值, 根据该概率值来选择目标节点信息在下一时刻要扩散到的节点. 图4 给出一个简单网络实例, 图中实线代表历史链接, 虚线代表当前时刻新产生的链接. 分别对网络中新链接两端的节点v4,v5进行随机游走. 以节点v5的随机游走邻域采样为例, 其具体的随机游走采样策略如下: 图4 节点邻域采样示意图Fig. 4. Schematic diagram of node neighborhood sampling. (1)建立随机游走结果集合Rv5={}. (2)根据边权重概率分布随机选择下一节点v1,并将该节点加入Rv5中. (3)判断所选节点v1是否有一阶邻居, 或者其一阶邻居是否全部在Rv5中, 是则退回到上一时刻的节点重复此步骤, 否则进入下一步. (4)重复步骤(2)和(3)直到随机游走的结果集合达到期望的长度. (5)若随机游走过程中选择的节点与结果集合中的节点重复, 则退回到上一时刻的节点重新进行选择. 如图中节点v2下一刻游走选择节点v5, 则退回到节点v2重新进行决策. 表1 给出了扩散算法的伪代码. 在表1 中,Enew代表新增链接的集合;v代表与新增链接相关联的一个节点;m代表随机游走了的长度;L是给定的随机游走序列的最大长度;P表示边权重概率分布;u代表节点v的一阶邻居;Rv代表节点v的随机游走结果集合;R代表所有节点的随机游走结果集合. 步骤6—8 实现节点间边权重的计算. 步骤9 实现相关节点的邻域采样. 步骤4—12 实现基于连接强度的随机游走算法, 找到了相关节点的局部邻域Rv, 其中Rv是一个有序的随机游走序列,越靠前的节点越容易从相关节点到达, 即相关节点的信息更容易扩散到序列中排位靠前的节点上去,刻画出了相关节点信息的扩散过程. 整个算法得到了与新增信息直接相关的节点的随机游走序列Rv的集合R, 描绘出了整个网络中新增信息的扩散过程. 表1 信息扩散算法Table 1. Information diffusion algorithm. 由于新增链接并没有对随机游走序列中的节点产生直接影响, 因此新增链接的信息并没有影响这些节点的历史信息, 只带来了新信息, 并且对于相关节点局部邻域中较老、较远的节点(较老的节点: 相关节点与其的交互发生在比较早先的时候或者其与随机游走序列中的上一个节点之间的交互发生在比较早先的时候; 较远的节点: 相关节点与其的距离比较远)而言, 新信息对其影响较小. 综上, DNRLP 模型根据相关节点与其随机游走序列中的节点之间的链接存在的时间长短, 或者根据随机游走序列中相邻两节点之间链接存在的时间长短, 对新信息进行处理. 建立链接的时间越长, 需要丢弃的新增信息越多. 同时还使用相关节点与其随机游走序列中节点之间的距离对新信息进行进一步的处理. DNRLP 模型设计了节点邻域更新单元对新信息涉及到的相关节点vi的随机游走序列进行信息更新, 更新过程如下: 式 中,v ∈Rv,indv为 节 点v在Rv中 的 索 引 号,为节点v上一时刻的细胞状态,xt=W1uvi+W2uvj+b为节点vi和vj之间新增关系产生的新信息. 更新后节点v的表示向量为. 上述相关节点邻域信息更新单元的结构如图5 所示. 图5 节点邻域更新单元Fig. 5. Node neighborhood update unit. 为了在无监督方式下进行参数学习, DNRLP模型将输出的节点表示向量hv,v ∈V应用于基于图的损失函数, 并使用梯度下降法对模型参数进行更新. 基于图的损失函数假设相互连接的节点有着相似的网络表示向量, 损失函数如下: 在网络中相似节点在未来发生链接的可能性更大, 因此, 本文通过度量网络节点之间的相似度来进行网络链接预测. 通过上述动态网络表示学习过程, 我们可以得到每次网络演化后的新节点偏好表示, 这些节点表示保存了节点的偏好信息, 可以直接进行节点间的相似度计算, 计算过程如下: 其中,hv和hu表示两个节点在当前时刻的表示向量,i和j表示节点偏好表示向量的分量. 相似度越大, 则节点间发生链接的可能性越大, 因此对网络目标节点进行链接预测时, DNRLP 模型首先会计算该节点与网络中的其余节点之间的相似度并对其进行排序, 选择top-k 的节点作为最终链接预测的结果. 为了验证DNRLP 模型在网络链接预测任务下的性能和有效性, 本文在具有代表性的四个公开动态网络数据集上进行了对比实验. 这四个数据集的数据统计信息如表2 所示. 表2 动态网络数据详细信息Table 2. Dynamic network data details. 其中, UCI[38]是由加利福尼亚大学欧文分校的在线学生社区的用户之间的消息通信而组成的网络. 网络中的节点表示社区用户, 如果用户之间有消息通信, 那么用户之间就会有边连接, 与每条边相关联的时间表示用户之间的通信时间. DNC 是2016 年民主党全国委员会电子邮件泄漏的电子邮件通信网络. 网络中的节点代表人员, 边代表人员之间的邮件交互. Wikipedia talk, Chinese(Wikipedia)[39]是中文维基百科的通讯网络, 节点表示中文维基百科的用户, 边表示在某一时刻某一用户在另一用户的对话页上发送了一条消息.Enron[40]是由Enron 员工之间发送的电子邮件所组成的电子邮件网络. 和DNC 一样, 网络中的节点代表员工, 边代表电子邮件. 这些数据集涵盖了多种情况, 例如: UCI 和DNC 的节点数和边数较少, 而聚类程度较高, 形成较为密集的小网络. 但是它们在持续时间上又有所不同, UCI 的持续时间短, 而DNC 的持续时间较长. Enron 是节点数和边数较多, 聚类程度也较高的数据集, 形成较为密集的大网络. 而Wikipedia 是节点数和边数很多,持续时间很长, 但聚类程度却极低的数据集, 形成稀疏的大网络. 使用这些数据集, 我们可以对模型的鲁棒性进行测试. 根据表1 中所述的时序网络数据得到t时刻的网络拓扑图以及时间信息, 使用平均交互排序(mean reciprocal rank, MRR)指标评估链接预测任务的质量. MRR 计算了测试集中真实节点的排名倒数的平均值, 其计算过程如下所示: 其中,H为测试集中的节点个数, 将目标节点与和其有真实连接的节点之间的余弦相似度进行降序排序,ranki则表示了它们的余弦相似度在降序序列中所处的位置. 当测试集中的节点与目标节点间有真实连接时, 其相似度排名应尽可能靠前, 因此MRR值越大, 说明链接预测的质量越高, 即网络表示越精准有效. 实验按照时间顺序选取前80%的数据作为模型的训练数据, 后10%的数据作为验证数据, 其余10%的数据作为测试数据. 实验不但与现有的链接预测模型进行了对比, 还与使用了不同信息扩散策略的DNRLP 模型的变体进行了比较. 并且, 为了验证DNRLP 模型的准确性,我们还选取了不同数量的训练数据来与对比模型进行对比. 对于测试集中的每个链接节点对, 我们固定链接一端的节点, 将其看作目标节点, 计算网络中其余节点与该目标节点的余弦相似度, 并进行降序排列. 本文还使用Recall@k指标来计算在测试数据集中真实链接占预测结果集中Top-k 的百分比,其计算过程如下所示: 其中σ{ranki≼k}=1 表示在预测结果集中真实链接节点的排名ranki小于设定阈值k.Recall@k的值越大, 说明链接预测任务的效果越好. 此外, 本文还使用Precision@k指标来计算在测试数据集中预测结果占真实链接集中Top-k 的百分比, 其计算过程如下所示: 其中,σ{ranki≼k}=1 表示在预测结果集中真实链接节点的排名ranki小于设定阈值k.Precision@k的值越大, 说明链接预测任务的效果越好. 鉴于机器学习模型在链接预测任务中的优异表现, 以及网络表示在常见的网络分析任务中展现出的优异能力, 本文分别使用基于机器学习的链接预测方法和基于网络表示的链接预测方法作为对比方法. 在基于机器学习的方法中, 我们选择两个经典的机器学习模型, 支持向量机(SVM)模型和逻辑回归(LR)模型. 在链接预测任务中, 将节点的特征向量作为SVM 和LR 模型的输入, 通过节点的特征向量得到节点对的特征向量, 将节点对的特征向量分为有链接和无链接两类, 从而将链接预测问题转变为机器学习中的二分类问题. 在基于网络表示的方法中, 主要通过计算节点表示之间的相似性来进行链接预测, 因此得到更为合适的节点表示是该类方法的主要目的. 为此我们分别选取了具有代表性的三个静态网络表示学习方法和三个动态网络表示学习方法来进行对比, 静态网络表示学习方法包括node2vec、GCN 和GraphSAGE, 动态网络表示学习方法包括DynGEM、GCN-GAN和DDNE. Node2vec 是一种优异的图表示学习方法, 它利用随机游走来捕获网络中的邻近性, 并将所有节点映射到一个保持邻近性的低维表示空间中. GCN 构建了一个半监督的节点嵌入模型, 通过对网络拓扑结构和网络节点特征进行编码, 从而得到了含有丰富信息的节点表示. GraphSAGE 通过训练聚合函数将GCN 扩展到归纳学习任务中,使其可以直接泛化到未知节点上去. DynGEM 是一种针对时间间隔固定的动态网络的表示学习模型, 它学习到了含有时间信息的节点表示. GCNGAN 将GCN、LSTM 和GAN 相结合, 用GCN和来捕获空间结构信息, 用LSTM 来挖掘时间信息, 最后通过对抗的方式在动态网络中进行链接预测. DDNE 用GRU 作为编码器来捕获动态网络中的时间信息, 从而在动态网络中进行链接预测. 在上 述 模 型 中, SVM、 LR、 node2vec、 GCN 和GraphSAGE 是适用于静态网络的模型, 因此需要将动态网络转化为静态网络进行实验, 即将所有时刻的网络信息拼接到一个网络中. 而DynGEM、GCN-GAN、DDNE 以及我们提出的DNRLP 都是适用于动态网络的模型, 但DynGEM、GCNGAN 和DDNE 中的新链接建立的时间间隔是固定的, 因此在实验中我们忽略动态网络中不同大小的时间间隔. 实验使用网络的邻接矩阵作为模型的输入特征, 将邻接矩阵的行向量作为节点的特征向量. 本文中所有模型的统一实验环境如表3 所示. 实验中各模型的参数设置如下: SVM, LR: 根据节点的特征向量得到节点对的特征向量, 将节点对的特征向量分为两类: 有链接的标为0, 无链接的标为1. SVM 模型的核函数选用sigmoid 函数, LR 模型则使用sag 优化算法来进行求解, 迭代次数设定为100. 表3 实验环境设置信息Table 3. Experimental environment setup information. node2vec: 将模型中随机游走的数量定为20,随机游走的步长定为40, 语言模型Skip-Gram 的窗口大小设定为10, 最终输出的网络表示维度为128. GCN: 将模型中的图卷积网络层数设定为2,训练过程迭代次数设定为500, 学习率设定为0.01,输出网络表示的维度设定为128. GraphSAGE: 将模型中的搜索深度设定为2,邻域采样数量设定为20, 学习率设定为0.01, 输出网络表示的维度设定为128. DynGEM: 将模型中深度编码器的隐藏层层数设定为2, 隐藏层单元数分别设定为[256, 128],输出的网络表示维度设定为128. GCN-GAN: 将模型中的图卷积网络层数设定为2, LSTM 隐藏层层数设定为2, 学习率设定为0.01, 输出的网络表示维度设定为128. DDNE: 将模型中深度编码器的隐藏层层数设定为2, 历史窗口的大小设定为2, 学习率设定为0.01, 输出的网络表示维度设定为128. DNRLP: 将模型中LSTM 中的隐藏单元数设定为128, 新信息扩散过程中的随机游走步长设定为40, 输出的网络表示的维度设定为128. 实验结果如表4 所示. 通过观察对比结果可以看出基于网络表示学习的链接预测方法比基于机器学习的链接预测方法更加有效. 这是因为网络表示学习方法可以对网络节点间的关系进行深入挖掘, 从而得到更加丰富的特征信息. 在基于网络表示学习的链接预测方法中, node2vec 在四个数据集上均表现一般, 主要因为node2vec 仅通过随机游走来捕获节点的邻域结构, 没有重视直接相连节点间的信息交互. 且其主要适用于静态网络, 忽略了网络中的动态信息. DynGEM、GCN-GAN 和DDNE 模型是针对动态网络的表示学习模型, 它们引入了网络中的动态信息, 因而预测效果优于node2vec, 这说明了动态信息在网络演化中的重要性. 但是DynGEM 和DDNE 模型的预测效果不如或者与GCN 和GraphSAGE 的效果相似, 这是因为它们仅对网络拓扑图的邻接矩阵进行学习, 只得到了网络的全局拓扑结构信息, 而忽略了网络中的局部信息, 因而学习到的网络特征并没有GCN 和GraphSAGE 丰富. 而GCN 和GraphSAGE通过聚合邻居节点的信息来模拟信息在节点间的扩散过程, 既学习到了网络中全局信息也学习到了局部信息, 这表明了局部特征在网络中的重要性,同时也体现出GCN 和GraphSAGE 模型适用于聚类系数较高的邻域信息丰富的网络. 但是GCN 和GraphSAGE 忽视了信息传播随时间的衰减, 没有对信息进行遗忘, 而GCN-GAN 既考虑到了网络中的全局特征和局部特征, 又考虑到了网络演化过程中的动态信息, 因而效果优于GCN 和GraphSAGE. 但是GCN-GAN 模型忽视了时间间隔对信息更新的影响, 而DNRLP 模型通过信息动态更新模块和信息扩散模块不仅学习到了网络的动态信息, 考虑到了节点邻域所受的影响, 同时还考虑了时间间隔对信息更新的影响, 因此, 该模型在链接预测任务中较其他模型有明显优势. 此外,我们可以看到, 在Wikipedia 数据集上所有方法的表现均不佳, 这是因为它的聚类系数太低, 持续时间又太长, 给链接预测任务带来了极大的挑战. 同时对比于其他数据集我们可以看出在聚类系数稍高的情况下, 我们的模型效果要远优于其他所有模型. 表4 链接预测MRR 结果对比Table 4. Link prediction MRR results comparison. 本文还在四个数据集上对基于表示学习的链接预测方法中效果较好的几个模型计算了其在不同k值下的Recall@k指标, 实验结果如图6 所示.本文所提出的DNRLP 模型在不同k值下的链接预测效果均优于对比模型. 同时随着k值的不断增大,Recall@k的值也在不断增大. 我们可以看出,DynGEM 的预测效果与GraphSAGE 的效果相似, 并且在DCN 数据集中它的表现较差, 表明了学习局部信息的重要性. 而GraphSAGE 在DCN数据集中的表现优异, 表明了GraphSAGE 强大的学习邻域信息的能力, 也表明了GraphSAGE 适用于聚类系数较高的网络. 在不同k值下, GCNGAN 模型的预测效果基本位列第二, 表明了同时考虑空间信息与时间信息的重要性, 而GCNGAN 的预测效果要次于DNRLP, 表明了时间间隔在网络演化过程中的重要性. 上述实验结果表明, DNRLP 模型可以更好的学习网络中的节点信息, 得到含有全局信息、局部信息以及节点偏好信息的节点表示. 此外, 本文还对上述几个模型计算了其在不同k值下的Precision@k指标, 实验结果如图7 所示.我 们 可 以 看 出,Precision@k指 标 与 Recall@k指标的实验结果相似. 在DCN 数据集中, 所有方法的表现都比较好, 且当k值较小时, DNRLP 与GraphSAGE、GCN-GAN 的差别不大, 这是因为DCN 数据的聚类系数较大, 网络中的局部信息相对重要, 而这三个模型均可以通过聚合邻居节点的信息来更新节点表示, 体现了学习网络中局部信息的重要性. 相反在Wikipedia 数据集上所有方法的表现均不佳, 这是因为它的聚类系数太低, 持续时间又太长, 对进行准确的链接预测有很大的挑战.在四个数据集上, 本文所提出的DNRLP 模型在不同k值下的Precision@k指标均优于对比模型, 并且随着k值的不断增大,Precision@k的值也在不断增大, 当k值较大时, 所提DNRLP 模型的优势更为明显. 实验结果表明, 在动态网络中DNRLP模型可以更为准确地进行链接预测. 图6 各数据集上的 Recall@k 对比图 (a) UCI 数据集; (b) DNC 数据集; (b) Wikipedia 数据集; (d) Enron 数据集Fig. 6. Recall@k comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset. 图7 各数据集上的 Precision@k 对比图 (a) UCI 数据集; (b) DNC 数据集; (b) Wikipedia 数据集; (d) Enron 数据集Fig. 7. Precision@k comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset. 为了验证DNRLP 模型中用基于连接强度的随机游走算法模拟信息扩散过程的有效性, 我们对模型的三个变体进行了对比实验. DNRLPprop 模型是加入了基于连接强度的随机游走算法的链接预测模型. DNRLP-1 st 模型是使用节点在网络中的一阶邻域模拟信息传播过程的链接预测模型. DNRLP-org 模型为不考虑新信息在网络中的传播的链接预测模型. 对比实验结果如图8 所示, 可以看出在四个数据集上, DNRLP-prop 模型的预测效果均优于其他两个变体模型, 且k值越大,Recall@k的值也越大, 而DNRLP-org 模型的预测效果最差. DNRLP-org 模型的低预测效果主要是因为它忽略了信息在网络中的扩散过程, 没有将新信息传播到节点邻域中去, 这表明了信息传播在网络中的重要性. DNRLP-prop 模型的预测效果优于DNRLP-1st 模型的预测效果, 这主要是因为新信息的扩散往往是局部性的, 不仅会对相关节点的一跳邻居产生影响, 也会对与其距离较近的多跳邻居产生影响. 实验结果表明, 动态信息对动态网络的表示学习有着至关重要的作用, 不仅对直接相关的节点有影响, 对其周围一定范围内的节点也有影响. 使用基于连接强度的随机游走算法可以有效地将网络中的动态信息更新到受影响的节点中去. 图8 DNRLP 模型变体的Recall@k 对比图 (a) UCI 数据集; (b) DNC 数据集; (c) Wikipedia 数据集; (d) Enron 数据集Fig. 8. Recall@k comparison diagram of the variants of DNRLP. (a) UCI dataset; (b) DNC dataset; (c) Wikipedia dataset;(d) Enron dataset. 图9 不同训练率的MRR 结果对比图 (a) DNC 数据集; (b) Enron 数据集Fig. 9. MRR results of different training rates. (a) DNC dataset; (b) Enron dataset. 此外, 为了验证DNRLP 模型的准确性, 本文还选取了三个表现较好的模型计算了其在不同比率的训练样本下的MRR 指标. 我们在两个典型的数据集上, 按照时间顺序分别选取前60%, 70%,80%, 90%的数据作为训练数据, 其余的选择10%作为测试数据. 实验结果如图9 所示, 可以看出在两个数据集上, 随着训练数据比率的增大,MRR 的值也在增大. 并且在任意比率下, DNRLP的训练效果均优于对比模型, 表现了我们所提模型在链接预测任务中优异的性能. 本文针对现实世界中动态演化的网络提出了一种基于动态网络表示的链接预测模型DNRLP.该模型根据动态网络的特性, 在标准LSTM 单元的基础上引入了基于时间间隔的信息过滤单元, 来决策节点新、旧信息的去留. 此外, DNRLP 模型还考虑了新信息在直接相关节点邻域内的信息传播问题. 本文在四个动态网络公开数据集上对模型的有效性进行了验证, 实验结果表明网络中的全局信息和局部信息对学习良好的网络表示有非常重要的作用, 同时动态网络中的时间信息以及动态信息在网络中的传播对网络节点表示的更新有着极其重要的影响. DNRLP 模型可以学习到动态网络中丰富的信息, 能够有效地对新信息进行快速准确地学习, 在链接预测任务中表现出了明显的优势. 由于现实世界中的网络通常含有多类异构信息, 如社交网络中, 除了含有用户交互产生的网络结构信息以外, 每个用户还具有不同的属性信息,包括用户的性别、年龄、爱好等. 如何将这些信息加入到链接预测中, 将是一个重要的研究方向.
3.2 节点信息扩散算法和更新
3.3 参数训练
3.4 基于动态网络表示的链接预测
4 实验分析
4.1 实验设计
4.2 结果分析
5 结 论
