融合权重和结构的加权非负矩阵分解的链路预测

陈广福，刘奇，李晓飞

（1.武夷学院数学与计算机学院,福建武夷山 354300；2.福建省茶产业大数据应用与智能化重点实验室,福建武夷山 354300）

当前，复杂网络已是在日常生产生活中无处不在，如交通运输网络、在线社交网络、生物网络和电力网络等。复杂网络的分析和挖掘变得非常重要和有价值。作为复杂网络分析的研究热点之一，链路预测越来越受到研究者的关注。链路预测的目标是根据网络可观测结构信息来推断网络中缺失的或新的链接[1]。链路预测在现实世界中有着广泛的应用，例如：识别生物网络中潜在的蛋白质—蛋白质相互作用[2]、在在线商业系统中推荐商品[3]、预测书目网络中的引用关系[4]等。

真实世界网络存在大量加权网络，例如科学家合作网、生物网和交通运输网等。不同加权网络链接权重蕴含着不同含义，例如：科学家合作网中链接权重表示引用次数；食物网中链接权重代表物种之间的碳流量。链接权重是加权网络最原始结构信息。目前，加权网络的链路预测可归纳为2类：基于结构相似度和非负矩阵分解。其中基于结构相似度的主要思想是利用链接权重信息去计算节点相似度。例如：文献[5]将共同邻居(common neighbors，CN)、资源分配(resource allocation，RA)和Adamic-Adar(AA)指标扩展到加权网络中构成加权局部相似度方法，分别是加权共同邻居（weightedcommon neighbors，WCN）、加权Adamic-Adar（weighted Adamic-Adar，WAA）和加权资源分配（weighted resource allocation，WRA），其结果表明考虑自然权重可显著改善预测准确度；文献[6]提出基于信息论的加权局部相似度方法，同理也证实弱链接理论作用；袁榕等[7]同时考虑网络中链接的聚类和扩散性信息与WCN、WAA和WRA相融合，以改善加权网络预测精度；王曦等[8]将网络结构相似度与节点行为同步指数相融合，提出用户行为同步的加权网络链路预测算法。以上方法尽管改善了算法性能，然而仅考虑自然权重或拓扑权重，却无法同时保持自然权重和拓扑权重信息。

基于非负矩阵分解[9]方法是将邻接矩阵映射到低维潜在空间，保持结构信息，再重构原始网络获得最小误差预测分数矩阵。当前，现有大部分基于非负矩阵分解的链路预测算法仅适用于无向无权网络，例如：Chen等[10]提出在非负矩阵分解框架中融合图则化和稀疏学习，保持网络局部和全局结构；Ma等[11]提出在非负矩阵分解框架中融合多标签信息提取网络特征。上述算法忽略了网络链接权重无法处理加权网络链路问题。随着非负矩阵分解在链路预测研究深入，一些研究者将非负矩阵分解方法扩展到加权网络，例如：文献[12]首次利用非负矩阵分解技术处理加权网络链路预测问题，该方法假设所有链接权重服从泊松分布，其结果表明该方法考虑链接权重后性能有所提高；Chen等[13]提出在非负矩阵分解框架中融合聚类与自然权重，保持加权网络结构。上述方法缺点是仅考虑自然权重链接及局部结构。

针对以上方法的不足，本文提出了一种融合自然权重链接和多类型局部结构的加权非负矩阵分解(weight nonnegative matrix factorization，WNMF)模型。它保持多类型局部结构。首先将加权网络邻接矩阵映射到低维潜在空间，去保持网络链接权重信息；然后，将加权网络3个经典基于局部结构相似度作为指示矩阵指派到低维潜在空间，保持多类型局部结构；接着，融合上述信息提出3个链路预测模型，分别是WNMF-WCN、WNMF-WAA和WNMF-WRA，再利用更新法则去学习所提模型的参数并从理论上证明所提算法收敛性；最后，在6个加权网络上将现有加权网络方法与本文模型相比较，验证本文所提模型的性能。

1 融合自然权重和结构的加权非负矩阵分解的链路预测模型

1.1 相关概念

考虑一个无向加权网络G(V,E,W)，其中V=是节点集，E表示链接集，W表示自然权重。每条边e∈E是一个有序对e=(υi,υj)，并与权重Wυiυj>0相关联。本文不考虑多个链接和自循环存在，利用X=[xij]N×N来表示G的邻接矩阵。若G是无向加权网络，如果节点υi和υj之间存在链接，则否则xij=0。

U表示所有可能的链接，并且U−E是不存在的链接集。链路预测的目标是从集合U−E中寻找缺失链接。为评估所提模型性能，将可观察链接集E随机划分为2部分：训练集ET和测试集EP。显然,ET∩EP=φ和ET∪EP=E。本文中：运算符〈·〉表示内积；AT表示矩阵A的转置；Tr(A)表示矩阵A的迹；‖A‖F表示F范数；I表示单位矩阵。

1.2 融合自然权重和结构的加权非负矩阵分解的预测模型

加权非负矩阵分解（weighted non-negative matrix factorization，WNMF）[14]是非负矩阵分解变形。它的优点是引入指示矩阵改善预测缺失链接能力。具体地，设任意网络的邻接矩阵A，将A映射到低维潜在空间，其损失函数为

式（1）仅适用无向无权网络无法处理加权网络。本文扩展式（1）到加权网络，需要修改S。权重拓扑是加权网络重要组成部分。现有的加权网络3个经典局部结构相似度是加权共同邻居（weighted common neighbors，WCN）、加权Adamic-Adar（weighted Adamic-Adar，WAA）和加权资源分配（weighted resource allocation，WRA），它们的定义如表1所示。

表13 个加权网络局部相似度

将式（2）—（4）替换式（1）中S，则其表达式分别为：

将加权网络局部结构相似度替换原有的指示矩阵S有2方面的优点：1）适用于加权网络并预测缺失权重链接；2）同时保持局部结构和自然权重链接适用于不同类型加权网络。为防止目标函数过度拟合化，将式（5）—（7）中因子矩阵W和H正则化约束，目标函数为：

式中：⊙为哈达玛积（Hadamard Product）；α是防止过度拟合化。将上述3个损失函数归纳为一个统一的目标损失函数，为

采用拉格朗日乘法规则学习所提模型参数。根据矩阵迹性质有：Tr(A+B)=Tr(B+A)和Tr(AB)=Tr(BA)。再重写式（11），为

引入拉格朗日乘子矩阵Φ=[φ]nk和Ψ=[ψnk]，有

1）固定W，更新H。

删除式（13）中与H无关项，有

对J(H)求H的偏导，有

由 KKT（Karush-Kuhn-Tucker）条件且φnkhnk=0，有

因此，得到更新规则为

2）固定H，更新W。

删除式（13）中与W无关项，有

对J(W)求W的偏导，有

由 KKT（Karush-Kuhn-Tucker）条件且ψnkwnk=0，有

因此，得到更新规则，为

目标函数中所有的变量因子矩阵都获得更新，然后以最小误差重构原始加权网络获得链路预测概率矩阵，再将预测概率矩阵按降序排列构成有序列表，并将有序列表的分数插入训练集中，计算评价度量PCC和Precision值。

1.3 本文算法流程

本文算法的具体执行过程如下。

输入：A为加权网络的邻接矩阵；α为超级参数；K为潜在空间；最大迭代次数为maxiter。

输出：平均PCC和Precision。

步骤1，加权网络邻接矩阵划分为：训练集ET和测试集EP。

步骤2，初始化W和H。

步骤3，式（5）—（7）保持自然权重和局部结构。

步骤4，Fort=1:maxiterdo

步骤5，根据式(14)，更新H//更新因子矩阵H。

步骤6，根据式(15)，更新W//更新因子矩阵W。

步骤7，|Jt+1−Jt|<10−6直到收敛为止//收敛终止条件。

步骤8，Endfor。

步骤9，计算链路预测概率矩阵：S=WHT//预测分数矩阵。

步骤10，将S按降序排序构成有序表。

步骤11，将有序表分数插入训练集ET。

步骤12，计算PCC和Precision。

步骤13，获得最终平均预测准确度，即平均PCC和Precision值。

2 算法的收敛性

本章通过理论方法证明所提算法收敛性。具体证明过程如下。

定理目标函数J在更新规则式(14)下是非单调递增的。

证明定理成立，需要以下辅助定理。

定义对任意的x和x′，若M(x,x′)是F(x)的辅助函数，那么必须满足条件：M(x,x′)≥F(x),M(x,x)=F(x)。

引理1若M(x,x′)是F(x)的辅助函数，F(x)在更新规则下单调递减。

首先，删除式（12）中与H无关项，有

求F(H)对H的一次和二次偏导数，为：

证明Fnk(Hnk)泰勒展开式为

定理得证。同理可证目标函数J在更新规则式(15)下是非单调递增的，本文省略。

3 实验结果

3.1 评价度量

采用PCC和Precision 2个指标[15]评价所提模型性能。

1）PCC(pearson correlation coefficient)是衡量预测向量与实际向量的线性关系。其定义为

2）Precision是预测排名靠前链接的能力。若按分数排序的前L个链接中，有m个链接属于测试集，则Precision计算公式为

3.2 数据集

6个真实世界加权网络作为测试所提性能数据集。其拓扑结构如表1所示。表中：|V|是节点数；|E|是链接数；Cw表示节点平均聚类系数；Density代表网络稀疏程度。

表16 个真实世界加权网拓扑结构

1)神经元网络（CELegans，CEL）[16]是由306个节点和4296个链接构成秀丽隐杆线虫的神经网络。节点表示神经元，链接权重表示2个神经元之间的突触数量。

2)期刊和杂志网（JOUrnals，JOU）[16]是由124个节点和11944条链接构成期刊和杂志网络。节点表示期刊和杂志，链接权重表示读者数量。

3)USA1[16]是美国的航空运输网络。该网络由332个节点和2126条链路组成。节点表示机场，链接表示路线。链接的权重是2个机场之间的航班数量的频率。

4）USA2[17]是美国500个最繁忙的商业机场网络。该网络由500个节点和5960条链路组成。

5）信息交换论坛网（MESsage，MES）[17]是由899个节点和11万2168链接构成的在线信息交换网。节点表示用户，链接权重表示用户发布到主题的消息或字符数关系。

6）CEGT[18]是由923个节点和6470链接构成的生物网。节点表示基因，链接权重表示基因相互作用。

3.3 基准算法

为评估所提3个模型的预测准确度，选择10个现有的加权网络链路预测方法与本文模型进行对比。10个现有的加权网络链路预测方法说明如下。

1)加权共同邻居(WCN)[5]、加权AA((WAA)[5]、加权资源分配指标RA(WRA)[5]。3个指标是在基于局部相似度基础上考虑链接权重信息，其定义为：

式中z∈Oxy表示节点x和y的共同邻居。

2)WMI-WCN[6]、WMI-WAA[6]和WMI-WRA[6]。基于信息论框架下融合网络局部结构信息。

3)rWCN、rWAA和rWRA[15]是局部权重拓扑结构与可靠路径相融合的加权网络预测指标。

式中z∈Oxy表示节点x和y的共同邻居。

4）线性最优化(linear optimization，LO)[19]。该指标假设2个节点之间存在链接的可能性，可以通过相邻节点贡献的线性求和来展开，其定义为

式中 α为超级参数。

3.4 实验结果分析

本文采用PCC和Precision度量指标去评估所提模型性能。由于所提模型中包含有3个重要的参数α、潜在空间维数K和迭代次数需要进行预设，因此对所有数据集设置参数α=3，潜在空间维数K=60，最大迭代次数为60。在6个加权网络上实验结果如表2所示。

1）所提模型WNMF-WCN、WNMF-WAA和WNMF-WRA在6个加权网络上，PCC和Precision值均获得最优，表明所提模型获得高质量性能。所提模型获得高预测准确度的主要原因是可同时保持自然权重和多类型局部结构，获得了更多结构信息。具体地，所提模型与第二优秀方法相比，在CEL、JOU、MES和CEGT加权网络上PCC分别提高了4.9%、0.4%、22.8%和3.1%，在CEL、JOU、USA1、USA2、MES和CEGT网络上Precision分别提高了4.3%、6%、0.7%、7%、23.5%和5%。在PCC度量方面，第二优秀方法分别指：在CEL数据集中是LO；在JOU数据集中是WMI-WAA；在MES数据集中是WRA；在CEGT数据集中是WRA。在Preecision度量方面，第二优秀方法分别指：在CEL数据集中是LO；在JOU数据集中是WRA；在USA1数据集中是WAA；在USA2数据集中是rWRA；在MES数据集中是LO；在CEGT数据集中是WAA。

2)3个基于局部结构相似度指标WCN、WAA和WRA，以及基于可靠路径rWCN、rWAA和rWRA在6个加权网络上均获得较差预测准确度。主要原因是该类指标仅考虑自然权重链接，无法捕获更多结构信息。基于信息论的3个预测指标WMI-WCN、WMI-WAA和WMI-WRA启用互信息捕获网络结构在6个加权网络上预测，其准确度与上述方法有提高。

3）LO在本质上与非负矩阵分解类似，采用节点邻居贡献线性和分解获得最优解，在6个加权网络上获得较优性能。然而，与所提模型相比较，LO获得较低预测准确度的原因是该指标仅捕获节点三阶路径信息。所提模型最优预测者与LO相比较，在CEL、JOU、USA1、USA2、MES和CEGT网络上Precision分别提高了4.3%、7.8%、15.2%、18.5%、23.5%和5%。

4）所提模型WNMF-WCN、WNMF-WAA和WNMF-WRA本质上都是在WNMF框架融合加权网络局部结构。然而它们最大区别是从不同角度捕获加权网络局部结构。例如：WNMF-WCN是统计节点间共同邻居数量方式获得加权网络结构，与WCN相比较预测准确度显著提高；WNMF-WAA是以惩罚节点共同邻居权重较大节点形式捕获加权网络结构；WNMF-WRA是通过共同邻居间资源分配去捕获网络结构。由表2可知：WNMF-WCN性能最优的主要原因是6个加权网络的聚类系数都较高，表明WNMF-WCN捕获更多节点间共同邻居数量；WNMF-WAA在JOU网络上获得最优预测准确度，其原因是JOU聚类系数最大，表明存在权重较大节点，通过惩罚机制获得最优性能；WNMF-WRA在CEGT网络（稀疏率0.0076）获得最优性能，其主要原因是通过资源分配改善了稀疏性。因此，3个模型适用不同类型加权网络。

本文还通过设置不同比率改变网络稀疏性，以测试所提模型鲁棒性。设训练集比率范围为40%、50%、···、90%。由于空间有限，本实验仅选取WCN、rWCN、WMI-WCN、NMF和WNMFWCN 5个模型，其实验结果如图1所示。由图可知，在不同比率下本文所提模型获得最优性能，当训练集40%时，意味着网络稀疏率达到60%，在6个加权网络上所提模型均获得最优性能，表明所提模型鲁棒于稀疏网络。

图1 不同训练集下对应Precision值

4 参数敏感性分析

本章讨论所提模型主要参数对性能的影响。所提模型包含3个重要参数：α、潜在空间K和最大迭代次数。设 α变化范围为{0，0.03，0.3，3，30}，潜在空间K变化范围为{10，20，30，···，100}以及最大迭代次数变化范围为{10，20，30，···，100}。研究一个参数对性能影响，固定其他2个参数。由于空间有限，本文仅讨论WNMF-WCN模型与3个参数的变化关系，WNMF-WAA和WNMF-WRA类似WNMF-WCN。

4.1 参数α变化

参数 α约束因子矩阵预防模型过度拟合，其结果如图2所示。当α=0时，所提模型退化为融合多类局部结构的加权非负矩阵分解模型，PCC和Precision值较高，表明该模型以最小误差重构原始网络。随着 α增加，直到α=3时，PCC和Precision值最优，而当α>3时，PCC和Precision值显著下降，表明 α取较大值时影响算法收敛速度。因此，α=3时，所提模型获得最优预测准确度。

图2 参数α变化对应PCC和Precision值

4.2 参数K变化

所提模型性能直接受参数K影响：K过小导致预测准确度下降；K太大导致时间复杂度增加。其实验结果如图3所示。当K=10时，PCC和Precision值最小，表明潜在空间无法捕获更多加权网络结构和自然权重链接。当K值逐渐增加，PCC和Precision值随之改善，直到K=60，PCC和Precision获得最优预测准确度，表明所提模型的潜在空间获得足够网络结构。当K>60时，PCC和Precision值开始稳定。因此K=60时，所提模型性能最优。

图3 参数K变化对应PCC和Precision值

4.3 最大迭代次数变化

最大迭代次数直接影响所提模型的收敛速度，其实验结果如图4所示。仅MES网络在开始时处于波动而其他5个加权网络波动不明显，当迭代次数为60时，在6个加权网络上的PCC和Precision值基本保持稳定。

图4 最大迭代次数变化对应PCC和Precision值

5 结束语

现有大量的链路预测算法仅考虑无向无权网络而忽略权重贡献。如何将非负矩阵分解模型扩展到加权网络的链路预测方法中是一种挑战。针对现有大部分非负矩阵分解算法仅适用于无向无权网络，本文提出一个融合自然权重和多类结构的加权非负矩阵分解的链路预测模型。该模型将3个经典加权局部相似度作为指示矩阵分配给非负矩阵分解模型，构建加权非负矩阵分解的链路预测模型。此外，提供拉格朗日乘法法则优化模型和学习模型的参数，并重构原始网络获得链路预测分数矩阵。在6个真实加权网络上，将该模型与现有代表性加权网络方法比较，其实验结果表明该模型的预测性能获得明显改善。