基于网络表示学习的链路预测算法*

2019-07-18杨晓翠宋甲秀张曦煌

计算机与生活 2019年5期

杨晓翠，宋甲秀，张曦煌

江南大学物联网工程学院，江苏无锡 214122

1 引言

如今，人类处于以互联网为代表的网络信息技术迅速发展的时代，多种形式的信息网络出现在现实生活中，包括社会网络、引文网络、通信网络、生物网络和万维网等。这些网络的规模从数百个顶点到数百万个甚至数十亿个顶点不等。分析此类网络对不同学科的各种新兴应用起着至关重要的作用。然而，对这些复杂网络的有效分析在很大程度上取决于网络表现的方式。通常，用一个离散邻接矩阵来表示网络，此方式只捕获顶点之间的相邻关系，但不能体现如路径、频繁的子结构等更复杂的高阶结构关系。

最近，网络表示学习（network representation learning，NRL）引起了学术界和工业界的广泛关注，复杂网络的研究迈入了全新纪元，其目的是学习网络顶点的潜在低维表示，同时保留网络拓扑结构、顶点内容和其他方面的信息。在学习新的顶点表示后，通过在获得的低维向量空间中应用传统的基于向量的机器学习算法，可以容易且高效地执行网络分析任务，从而避免了派生应用于原始网络的复杂算法的必要性。链路预测，作为网络研究的分析利器之一，在未来的科学和工程发展中角色的重要性毋庸置疑。其相关研究对于分析网络演化以研究网络缺失数据补齐具有重要的理论意义，在信息检索和推荐系统等领域具有巨大的应用价值[1]。然而，当前的链路预测算法大都基于原始网络而设计，不可否认，网络表示学习对链路预测的研究提供了一种新的视角和方法，将极大推动领域内相关工作的进展。

2 相关工作

近年来，链路预测吸引了广大研究者的兴趣，取得了很多显著成果。其中，基于相似性的一类算法，主要利用了包括实体或节点的属性和网络的拓扑两种类型的信息。这种链接预测方法的基本假设是，如果两个节点彼此相似，则更有可能具有链路。根据研究网络范围的差异，基于节点相似性的链路预测方法大致分为3类[2]：基于网络局部结构的预测方法、基于网络全局结构的预测方法、基于准局部结构的预测方法。

基于网络局部结构的预测方法只利用节点的邻居信息，PA（preferential attachment）[3]、CN（common neighbors）[3]、Salton[3]、JC（Jaccard）[3]、AA（Adamic-Adar）[3]和RA（resource allocation）[3]等最为常见。此类方法计算复杂度低，但预测精度受信息量的限制。相对于局部结构的预测方法，全局结构相似性方法则考虑了整个网络的结构，包括Katz[3]、LHN2（Leicht Holme-Newman）[3]、ACT（average commute time）[3]、RWR（random walk with restart）[3]、SimRank[3]、MFI（matrix-forest theory）[3]等。基于准局部结构的预测算法，无需全局网络拓扑信息，而是利用比局部指标更多的信息，如LP（local path）[3]、LRW（local random walk）[3]、SRW（superposed random walk）[3]。近期该方法领域的研究成果有：Cannistraci等人[4]通过强化经典相似性指标与共同邻居节点之间的联系，设计了相似性指标，称为CAR（Cannistraci-resource-allocation）。贾等人提出用H指标[5]代替度，以加权方式来衡量引文网络中文章的重要性，达到了增强Salton[3]、Sorenson[3]和AA[3]这3种经典链路预测方法的效果。Gao等人[6]基于网络中最小的局部结构三元闭包，提出了3个相似性指标TWCN（common neighbors with triadic closure weight）、TWAA（Adamic-Adar with triadic closure weight）、TWRA（resource allocation with triadic closure weight）和具有调节参数的3个相似性指标TWCN*、TWAA*、TWRA*，以O(N3)的时间复杂度为代价提高了预测精度。Liu等人[7]从局部路径上资源交换的角度，提出了扩展资源分配指标ERA（extended resource allocation index），通过在两个端点之间的公共邻居和非共同邻居交互的资源量来测量相似性。Wu等人[8]提出适用于大规模网络的NLC（similarity index based on node and link clustering information）算法，以节点聚类信息和边聚类信息融入相似性计算指标的方式更加充分地挖掘了共同邻居在链路预测中的作用。

概率模型或生成模型是链路预测的另一类有效方法。如Gao等人[9]提出了一种利用网络中多个信息源获取链路发生概率的模型。Barbieri等人[10]提出了一种用于定向和节点归属图的链路预测的随机主题模型。该模型不仅预测链接，而且还为每个预测的链接生成不同类型的解释。Hu等人[11]提出了一种在社会网络中检测人体运动的概率模型，并提出了一种使用基于约束的遗传算法对人体运动进行标记的方法来优化模型。Zhang等人[12]通过结合机器学习和神经网络技术，提出Weisfeiler-Lehman神经机器（Wlnm）模型，以图形形式学习拓扑特征，预测链接的形成，取得了比大多数基于节点邻居的方法更好的结果。模型类算法在网络分析和实际应用中具有许多优点。然而，这样的模型一般需要链接外观的预定义分布，参数学习和推理通常不易。

相关还有一些基于最大似然估计和矩阵分解技术的算法研究。最大似然估计类算法将假定的规则和参数与已知结构的最大概率结合来预测网络中缺失的链路。如Clauset等人[13-14]提出了一种基于分层网络结构的算法，对具有层次结构的网络给出了很好的预测。Lv等人[15]提出了结构一致性的概念，用于反映网络的固有链路可预测性，并提出了一种比现有技术方法更为准确和鲁棒的链路预测的结构扰动方法。而基于矩阵分解的预测算法是一种从网络数据中学习潜在特征以进行链接预测的方法，通过将网络中的节点投影到潜在空间，以节点在该空间中的位置来衡量链路的存在概率[16-17]。潜在空间的每个特征都被认为是一个潜在属性，若两节点具有相似的潜在特征，它们则更有可能是相似的[18]。从另一个角度来看，复杂网络的相似性矩阵可以近似为两个低维特征矩阵的乘积，分别对应基矩阵和系数矩阵，限制其元素非负，则可以通过非负矩阵分解算法来求解。此类方法的缺陷是潜在特征的数量很难确定。

到目前为止，多数链路预测算法都是基于高维稀疏表示的网络结构而设计，利用网络表示学习技术实现链路预测任务的算法尚未得到广泛研究。本文基于随机游走的NRL算法思维，并结合几何布朗运动（geometric Brownian motion，GBM）与传统网络图理论原理，提出了基于几何布朗运动的随机游走算法（GBM-based random walk algorithm，GbmRw），用于建模网络中的信息流动，即收集顶点序列，将信息传播的随机性质进行量化，从而实现网络结构关系的捕获；继而将此算法和通过最大化每个输入顶点与其周围上下文的条件概率的Skip-Gram模型[19]相结合，设计出信息网络表示学习算法（information network representation learning algorithm based on geometric Brown motion，GBMLA）。最后，以顶点表示向量之间的欧式距离表征链路相似性，提出链路预测算法（link prediction algorithm based on geometric Brown motion，GBMLP）。该算法首先是容易理解和实现；其次，预测效果好且性能稳定，实验结果表明其在多个数据集中的AUC值较于对比算法提高了1%～10%不等，且Precision保持领先；再次，鲁棒性高，与网络表示学习技术的融合，使其能有效应对规模不断增长的网络。

3 算法描述

3.1 定义描述

信息网络[20]：一个信息网络定义为G=(V,E,X,Y)。其中，V表示节点集，E⊆(V×V)为边集，X∈R|V|×m表示节点属性矩阵，m为属性个数，元素Xij代表节点i在第j个属性上的值，Y∈R|V|×y为节点标签矩阵，y为标签集，当节点i具有第k个标签时，Yik=1；否则，Yik=-1。对于每个(i,j)∈E，若G为无向信息网络，则有(j,i)∈E；若G有向，(j,i)∈E不一定成立。当G是二进制/无权网络时，则每个(i,j)∈E伴有权重wij=1。

网络表示学习[20]也称为网络嵌入（network embedding，NE），给定一个信息网络G=(V,E,X,Y)，网络表示学习的目标是学习一个映射函数f:v→rv∈Rd，这里rv为节点v的学习表示，d为学习表示的维度。映射函数f需要保留原始网络信息，使得在原始网络相似的顶点在学习向量空间里依然相似。同时，学习的顶点表示需要满足低维、信息完整、连续性等条件。换而言之，即其维数应该远小于原始邻接矩阵表示的维度；应该保持由网络结构和顶点属性和/或顶点标签反映的顶点邻近度；应该具有连续的实际值以支持后续的网络分析任务。

几何布朗运动（GBM）[21]也叫作指数布朗运动，是连续时间情况下的随机过程，其中随机变量的对数遵循布朗运动。即随机过程St在满足随机微分方程dSt=μStdt+σStdWt的情况下被认为遵循几何布朗运动。这里Wt是一个维纳过程,或者说是布朗运动，而μ（漂移百分比）和σ（波动百分比）则是常量，分别代表确定性趋势和这种模型中不可预测事件的影响。

链路预测[3]：针对任意无向网络G，N为网络节点总数，总边数为M。令U为N(N−1)/2个节点对组成的全集。U−E则是网络中所有不存在/缺少的链接的集合。链接预测的目的就是从集合U−E中找出缺失的链接。给定一种链路预测方法，该方法为每对没有连边的节点对(x,y)赋予一个分数值Sxy。这个分数值可以理解为一种接近性，它与两节点的链接概率正相关。即所有不存在的链接根据其分数按降序排序，分数越高的节点对表明该链接存在的可能性越大。

3.2 基本算法介绍

针对基于相似性的预测算法，本文选择四个经典算法 CN[3]、JC[3]、AA[3]和 LP[3]，以及两个近年来具有代表性的高质量算法CAR[3]和NLC[8]为基准，各算法相似性指标定义描述如下。

（1）CN指标。对于网络中的节点x，定义其邻居集合为Γ(x)，则两个节点x和y的相似性就定义为它们共同的邻居数，即：

（2）JC指标。用两节点共同邻居占两节点邻居总和的比例来表示节点x和y的相似性，即：

（3）AA指标。优化的CN指标，将不同的权重分配给该公共邻居集合中的不同节点，每个节点的权重等于该节点的度的对数分之一，即：

（4）LP指标。该指标通过利用节点x和y之间具有长度为2和3的不同路径的数量的信息，来表征节点之间的相似性，即：

其中，A为邻接矩阵，ε为自由参数。

（5）CAR指标。该指标是在基于网络局部结构的经典相似性指标RA[3]的基础上精确引入链接/社区策略而设计的变体，定义为：

其中，r(z)为共同邻居的局部社区度[4]，即节点z的邻居与x和y共同邻居的交集。

（6）NLC指标。将节点聚类系数和边聚类系数融合实现节点相似性的计算，可以理解为公共节点z到节点x和节点y的局部聚类系数的总和，定义如下：

其中，CN(x,z)/(kz-1)表示边聚类系数，Cz为节点聚类系数，tz表示通过节点z的三角形数量。

3.3 基于网络表示学习的链路预测算法

3.3.1 同化函数模型

首先，引入同化函数St如图1所示，来模拟顶点本身被游走（同化）的情况。将同化过程分为同化前期和同化期。在同化前期，该顶点的同化函数St将呈指数式增长，直到St在时间为T时达到同化阈值并进入同化期，并定义该过程不可逆，即顶点一旦被同化（游走），则不可撤销。针对给定网络，本文建模同化函数如下，其中μ表示随机过程平均值的变化：

Fig.1 Assimilation function图1 同化函数

然后，添加一个维纳过程Wt来解释随机性。根据维纳过程的特性可知，dWt实质为高斯白噪声，并且参与同化函数如式（9）。以此方式，St被建模为几何布朗运动过程，表示为B(μ,σ)，μ和σ为常数，分别对应漂移和波动。

给定初始值S0，根据伊藤积分，可得随机微分方程（9）的解如式（10）。不失一般性，本文取初始同化值S0=1。

3.3.2 基于GBM的随机游走算法

假设从节点i开始游走，则其邻居节点j是否加入游走序列取决于j对i的同化函数，只有当该函数的值超过某个阈值后，j才会被游走。为了更好地定量分析，以链路端节点及其公共邻居节点形成的局部环境的内部影响力为同化阈值，用dij表示，定义为：

其中，第一个因子表示节点i在节点j集体影响力中的占比，理解为节点j被节点i影响的直接可能性，而后两个因子主要表征间接因素（包括j占i影响力的比重，经公共节点z传递的影响力占比）对j最终被影响的贡献。kdi为节点i的度减1，Γ(i)为节点i的邻居节点集，这里节点i的集体影响力（collective influence）[22]CIi定义如式（12），Ball(i,j)为围绕节点i，且属于半径（最短路径）为l的球内的节点集合，∂Ball(i,j)为该球的边界，l是预定义的不超过有限网络的网络直径的非负整数，本文取l=1。

由于GBM是一个时间连续的随机过程，因此使用每个持续时间δt的时间步长来离散时间。因此本文设计基于GBM的随机游走算法GbmRw如算法1。其思路为：开始，设置所有节点均未被游走。一旦某一节点i被游走，将其设置为新游走节点，并加入游走序列，然后计算其各个邻居节点的同化函数，并与同化阈值比较以确定该邻居节点是否加入游走序列。对于每个j∈Γ(i)，使用tij=0来初始化i开始游走j的时刻。当节点i所有邻居节点都被条件判断过之后，将顶点i的状态更新为已游走节点。从游走序列选择最后加入的游走节点，重复此步骤，直至满足预设游走序列长度。其中表示在时刻t，节点j被节点i同化的函数，根据GBM特性，为一高斯变量，记为。在时刻t，若，则节点j被加入游走序列且成为新的游走起始点；否则，在下一时刻t+δt，同化函数是期望和方差更高的高斯变量，记为

算法1GbmRw算法

输入：网络G(V,E)，游走长度wl,开始节点i，时间步长参数δ。

输出：随机游走序列walk。

3.3.3 基于GbmRw的网络表示学习算法

基于GbmRw的网络表示学习算法GBMLA主要包含两部分：一个随机游走生成器和一个表示学习过程。随机游走生成器生成固定长度的随机游走序列，每个节点生成长度为wl的γ个随机游走序列，这里γ为迭代次数。表示学习过程则通过类比实现单词的向量表示的word2vec模型实现，主要用到了其中的Skip-Gram模型[19]，该模型的思想是建立一个神经网络，神经网络的训练集是由单词组成的句子。神经网络的输入是单词，输出是各个单词出现在输入单词的上下文中的概率。通过训练集对神经网络进行训练，得到神经网络中的一些参数，根据参数可以得到输入的单词的向量表示。本文以节点为单词，随机游走得到的节点序列walks为句子进行训练，从而实现节点的表示学习。具体过程见算法2：首先，将网络数据集的节点随机排列形成序列O；其次，利用算法1依次对O中的每个节点进行游走得到其对应的游走序列walk，将其加入walks；然后以重复以上操作γ次的最终walks以及设置的窗口大小w和表示维度d为Skip-Gram模型的输入进行学习，得到节点表示矩阵。

算法2GBMLA算法

输入：网络G(V,E)，窗口大小w，游走长度wl，表示维度d，迭代次数γ，时间步长参数δ。

输出：节点表示矩阵Φ∈ R(|V|×d)。

最后，定义基于GBMLA的链路预测算法，记为GBMLP，对应于算法3。其相似性指标表示为GBMLA算法所得到的节点向量表示之间的欧式距离。计算公式如下，其中rxi和ryi分别表示节点x和节点y的表示向量的第i维数据，d为表示向量的维度。

算法3GBMLP算法

输入：网络G(V,E)，窗口大小w，游走长度wl，表示维度d，迭代次数γ，时间步长参数δ。

输出：相似性矩阵S∈R(|V|×|V|)。

4 实验结果分析

4.1 实验数据

本文选择四个真实网络数据集进行测试，包括在线社交网络数据集Facebook[23]、引文网络Cora[24]、网页网络 Political Blog（PB）[25]和 Wikipedia[23]。各网络数据集的详细信息如表1所示（其中|V|表示节点数，|E|表示边数，|y|为网络标签数，Multi-label表示网络是否为多标签，N/A表示该列属性不存在）。

Table 1 Details of networks datasets表1 网络数据集详细信息

4.2 评价指标

链路预测度量指标采用AUC和精确度（Precision）。AUC[3]是链路预测任务中常用的评价指标，可以从整体上衡量算法的精确度。其具体含义指在测试集中随机选择一条边的分数值高于随机选择的一条不存在的链路分数值的概率，如果在n次独立重复实验中，有n1次测试集中的边分数大于不存在的边分数，有n2次两分数值相等，AUC定义为：

Precision[3]定义为在前L个预测边中被预测准确的比例。如果有m个预测准确，即根据出现连接的可能性从大到小排列，排在前L的边中有m个在测试集中，则精确度定义为m/L。

4.3 实验设置

为了不破坏原始网络的结构，对于每个网络数据，在保证网络连通的情况下，随机抽取90%的连边作为训练集ET，剩余10%的连边作为测试集EP。算法2中网络表示学习参数设置为w=10,γ=10,d=128,wl=80,δ=0.01。AUC中的采样次数n=100 000，Precision排列表的长度L=50、100、150、200、250，最终实验结果为各网络独立运行10次的平均值。实验的硬件环境为2.80 GHz Intel®CoreTMi7-7700HQ CPU,8 GB RAM，操作系统为Windows,开发环境为Python3.6.2。

4.4 结果分析

表2展示了在四个数据集上六种不同的算法与本文算法的AUC值。从结果数据中可以看出GBMLP算法普遍高于其他基于原始网络的相似性预测算法，算法性能平均提升了1%～10%不等，在一定程度上肯定了该算法的可行性和有效性。其在PB网络的预测性能尤为突出，提高率明显；在Cora网络的AUC值也保持较高水平,仅次于LP算法。

Table 2 AUCresults for GBMLP and other link prediction algorithms表2 GBMLP与其他链路预测算法的AUC指标结果

图2展示了六种算法与GBMLP算法在表1各数据集上针对不同L取值对应的Precision实验结果。由图可知，本文算法在四个数据集上的总体表现优于其他算法，随着L的变化，Precision值均处于领先位置，一方面说明了该算法预测的稳定性，另一方面也证实了网络表示学习技术在预测缺失链路方面的研究价值，突出了本文算法的创新意义。

综合以上实验结果发现：首先，各算法在不同数据集上的预测性能受网络拓扑结构的影响。如LP算法在Cora数据集上取得了最高的AUC值，在Facebook和Wikipedia数据集上却均为最低。GBMLP、NLC等算法在Facebook数据集上的精度明显高于其在Cora上的表现。其次，评估各预测算法性能的AUC和Precision指标并不总是同步。如经典的JC算法，虽然在四个数据集上都能取得较高水平的AUC值，Precision值却普遍很低。此现象的原因可能是精确度取值只注重前面的L条边是否预测准确，而AUC是从整体上衡量算法的精确度。

4.5 时间复杂度分析

运算效率是评价算法性能的一个重要因素，对于CN算法来说，计算节点对的共同邻居的时间复杂度为O(＜k＞)，计算所有节点的相似性的复杂度为O(N2＜k＞)，其中＜k＞为网络的平均度。AA、JC两算法与CN算法计算过程相同，时间复杂度同为O(N2＜k＞)。LP算法的时间复杂度较低，为O(N＜k＞3)。CAR算法与CN算法的差异在于计算局部社区度，该过程的时间复杂度为O(＜k＞2)，故CAR算法时间复杂度为O(N2＜k＞2)。NLC算法，计算所有节点聚类系数的时间复杂度为O(N2)，计算所有边聚类系数的时间复杂度为O(N2＜k＞)，分配相似性分数的时间复杂度为O(N2＜k＞)，因此其最终复杂度为O(N2＜k＞)。本文，GbmRw算法的时间复杂度为O(wl＜k＞2)，GBMLA算法的时间复杂度为O(γ×wl＜k＞2×dNlbN)，而相似性矩阵的计算复杂度为O(dN2)，则GBMLP算法的最终时间复杂度为O(dN2)。