基于对偶图正则化非负矩阵分解的链路预测
时间：2023-05-28 15:10:28 来源：雅意学习网 本文已影响 人 
陈广福，阎兵早
(1.武夷学院 数学与计算机学院,福建 武夷山 354300；
2.认知计算与智能信息处理福建省高校重点实验室,福建 武夷山 354300)
大量真实世界复杂系统均可抽象为复杂网络，例如航空网、电力网和在线社交网等，其节点表示实体，链接表示为实体间关联程度.大部分情况下，由于受噪声和冗余链接等因素影响，所收集的网络数据是缺失和不完整的.因此，预测缺失链接是网络分析关键任务之一，而链路预测目标是通过已知网络结构去预测缺失链接形成可能性[1].因此，链路预测不仅有巨大理论价值且有广泛应用价值.例如社交网为不同用户推荐新朋友，获得更好的用户体验[2]；
在生物网，预测蛋白质之间未知的相互作用，显著降低实验成本[3].
当前，大量基于不同理论的链路预测算法涌现出来，其中基于结构相似度和基于减维方法最受关注.基于相似度算法根据已知网络结构、节点属性和节点聚类等信息计算尚未链接节点分数.基于相似度算法又可划分为局部相似度、半局部和全局相似度，其中局部相似度利用局部结构及聚类等信息去统计节点共同邻居数量，计算未链接节点间预测分数，共同邻居(common neighbors，CN)[4]、资源分配(resource allocation，RA)[5]和adamic-adar(AA)[6]指标是其中代表.另外，Zhou等[7]将节点三阶路径信息与CN、AA和RA相融合捕获更多网络节点信息，上述方法缺点是敏感于稀疏网络.全局相似度考虑节点高阶路径信息获得节点预测分数.例如顾秋阳等[8]提出高阶相似度预测算法，该算法以高阶路径信息为判别特征，并惩罚节点有效长路径；
Pech等[9]提出线性最优化(linear optimization，LO)算法用于多类型网络.半局部相似度克服了全局相似度不足，能够调节算法性能与时间复杂度的平衡关系.Rafiee等[10]提出共同邻居度惩罚预测方法，通过泛化CN、AA和RA局部相似度获得统一的预测框架，并与节点聚类系数相融合提高预测准确度；
还有刘树新等[11]融合节点间二阶和三阶路径拓扑信息提高资源分配能力.基于减维方法可划分为网络表示和非负矩阵分解的方法，下面重点介绍非负矩阵分解的方法，该类方法将任意网络邻接矩阵映射到低维潜在空间去探索网络潜在结构信息.例如Wang等[12]提出基于非负矩阵分解的扰动框架去探索网络结构信息；
Chen等[13]将图正则化和稀疏学习与鲁棒非负矩阵分解相融合去保持网络结构信息；
陈广福等[14]将聚类信息与非负矩阵分解融合去保持网络局部结构信息，上述方法缺点是仅考虑部分网络结构信息.
针对以上不足，将解决以下2个问题:① 如何捕获网络的一阶、局部和全局结构信息；
② 启用对偶图正则化如何同时保持局部和全局结构.针对以上2个问题，首先，使用随机游走方法捕获网络全局结构，再利用杰卡尔德系数捕获网络局部结构；
其次，将无向无权网络邻接矩阵映射到低维潜在空间保持原始网络可观察链接，并启用对偶图正则化方法同时保持局部和全局结构；
最后，融合一阶、局部和全局结构提出基于对偶正则化非负矩阵分解(dual graph-regularized nonnegative matrix factorization，DRNMF)预测模型.此外，利用拉格朗日更新法则学习参数模型，并用最小误差重构原始网络获得最优预测分数矩阵.在6个真实世界网络上，运用AUC和AUPR度量评估所提模型性能.
1.1 问题描述
1.2 随机游走和杰卡尔德相似度
(1)
令k=3,式(1)转换为三阶相似度，有
(2)
杰卡尔德相似度即Jaccard相似度节点间共同邻居数与所有节点间邻居数的比，可以更好反映网络局部结构信息.因此，利用Jaccard相似度去捕获网络局部结构，定义如下：
(3)
其中Γ(x)表示节点x的邻居数.
1.3 DRNMF模型构建
(4)
Tr(WTD3W)-Tr(WTT3W)=Tr(WTLwW),
(5)
其中，Tr(·)表示矩阵的迹，D3是对角矩阵且Lw=D3-S3是S3的拉普拉斯矩阵.
其次，对偶图正则化方法将特征矩阵H与式(3)相结合去保持局部结构信息，定义如下：
Tr(HTDJaccardH)-Tr(HTSJaccardH)=Tr(HTLhH),
(6)
其中，DJaccard是对角矩阵且Lh=DJaccard-SJaccard是SJaccard的拉普拉斯矩阵.
通过融合式(4)(5)(6)共同构建统一链路预测模型DRNMF，其执行框图如图1所示.
图1 DRNMF框架Fig.1 DRNMF framework
由图1所示，DRNMF的损失函数为
(7)
使用拉格朗日乘法规则学习所提模型参数.首先，重写式(7)，有
J(W,H)=Tr(AAT-2AHTWT+WHHTWT)+αTr(WTLwW)+βTr(HTLhH),
(8)
引入拉格朗日乘子矩阵Φ=[φ]nk和Ψ=[ψnk]，然后再重写式(8)，有
J(W,H)=Tr(AAT-2AHTWT+WHHTWT)+αTr(WTLwW)+βTr(HTLhH)+Tr(ΦHT)+Tr(ΨWT)，
(9)
固定W,更新H.删除式(9)中与H无关项，有
J(W,H)=Tr(-2AHTWT+WHHTWT)+βTr(HTLhH)+Tr(ΦHT),
求J(H)关于H的偏导,有以下等式成立
由KKT(Karush-Kuhn-Tucker)条件且φnkhnk=0，有
-AWT+WTWH-αLhH=0,
因此，更新规则如下：
(10)
固定W,更新H.删除式(9)中与W无关项,有
J(W,H)=Tr(-2AHTWT+WHHTWT)+αTr(WTLwW)+Tr(ΨWT),
求J(W)关于W的偏导，有
由KKT条件及ψnkwnk=0，有
-AWT+WHHT+βLwW=0,
因此，得到以下更新规则：
(11)
通过以上公式迭代更新所提模型参数，因此，所提算法DRNMF描述如表1所示.
表1 DRNMF算法Tab.1 DRNMF algorithm
2.1 评价度量
利用AUC[16]和AUPR[17]2个度量去评估所用方法的性能，其中AUPR是综合性指标.2个度量的值越高表示该方法预测准确度越高，定义如下.
1) AUC是ROC曲线与坐标轴围成的面积，AUC定义如下：
其中，n表示比较总数，n1表示测试集中节点间分数大于不存在集中节点分数的次数，n2表示测试集中节点间分数等于不存在集中节点分数的次数.
2) AUPR是召回率(recall)和准确率(precision)围成的面积.设TP(true positive)表示真正例，FN(false negative)表示假反例，FP(false positive)表示假正例和TN(true negative)表示真反例，那么Recall和Precision定义如下：
再利用复合梯形面积法近似求AUPR，定义：
AUPR=trapz(Recall，Precision),
其中，trapz是直接调用Matlab的梯形数值积分函数.
2.2 数据集
下面介绍6种无向无权网络，其拓扑特征统计在表2中，6个数据集具体说明如下：
1) 论文引用网络(SmaGr，SG)[18]是关于网络理论与实验的引用网络.它由1 024个节点和4 916条链接组成.链接方向表示引用关系.
表2 6个真实网络的结构特征Tab.2 Stuctural features of six real networks
2) EPA[18]是信息网络，它由4 471个节点和8 890条链接组成.
3) 美国航空运输网络(USAir，USA)[18]由332个节点和2 126个节点组成链接.节点是机场，链接表示2个机场间距离.
4) 欧洲电子邮件核心子集网(Email，EMA)[18]由1 005个节点和32 770条链接组成.节点表示成员，链接表示成员间所有传入和传出的电子邮件.
5) 脑网络(Nb-Fly，NF)[18]由1 781个节点和8 911条链接组成.节点表示纤维束，链接表示纤维束之间的关系.
6) Router是路由层次网[18]，它由5 022个节点和6 258条链接构成.节点表示路由器，链接表示路由器间数据交换关系.
2.3 基准方法
为评估所提模型性能，启用8个代表性方法与本文所提模型进行比较，具体介绍如下.
1) 基于3长度路径(3-length-based，L3)指标融合CN、AA和RA，包含3个指标包括CN-L3、AA-L3和RA-L3[7]，定义如下：
2) 线性最优化(linear optimization，LO)[9]指标用相邻节点贡献的线性求和分解表示节点形成的概率分数，其定义如下：
SLO=αA3-α2A5+α3A7-α4A9+…,
其中,0<α<1.
3) 共同邻居度惩罚(common neighbors degree penalization，CNDP)指标[10]表示共同邻居数与节点聚类系数关联程度，定义如下：
其中，|Cz|是共同邻居数.
4) 非负矩阵分解扰动模型(non-negative matrix factorization via deletion perturbation 1，NMFD1)[11]是基于非负矩阵分解的扰动框架预测缺失链接.
5) 融合共同邻居的概率矩阵分解模型(fusing probability matrix factorization via common neighbors，FPMF-CN)[19]，该模型融合邻接矩阵和局部结构，与概率矩阵分解模型共同构建统一链路预测模型.
6) 节点和链接聚类指标(node and link clustering，NLC)[20]，该指标利用局部节点和链接聚类揭示节点与链接关联程度，NLC定义如下：
2.4 结果分析
实验硬件平台为Intel Core i5-6500 CPU台式电脑，主频 3.20 GHz，内存8 GB，操作系统为Windows 10，所有算法均由Matlab R2016b实现.另外，所提模型包括参数α、β及潜在空间维数K和最大迭代次数.为公平比较所有的方法，所有数据集设α=0.5、β=0.5、K=70和最大迭代次数为70次.对于LO方法的参数设0.1和CNDP的参数设1.5.
首先，采用AUC和AUPR度量评估所用方法性能，其实验结果报告在表3.可观察到以下一些现象.
1) DRNMF在6个网络上均获得高质量预测准确度.具体地，AUC度量，在USA、SG、BF、EMA、EPA和Router中，所提模型与第2优秀预测者相比较，AUC值分别提升了2.5%、2.9%、2.2%、0.5%、1.3%和3.1%；
AUPR度量，在USA、SG、BF、EMA、EPA和Router中，所提模型与第2优秀预测者相比较，AUPR值分别提升了2.1%、2.1%、1.7%、2.6%、4.7%和8.9%.
2) CN-L3、AA-L3和RA-L3依赖于三阶路径信息.当网络稀疏时无法获取更多网络节点信息导致预测精度下降，NLC在EPA和Router上均获得较差预测准确度.主要原因是EPA和Router是高度稀疏网络，而CNDP和LO是全局指标，性能显著优于上述3个指标.FPMF-CN和NMFD1模型是基于非负矩阵分解理论的，性能均优于三阶及全局方法.DRNMF获得高质量性能的主要原因是同时保持一阶、局部和全局结构，从而在稀疏网络上保持较高鲁棒性.
表3 基准方法与DRNMF在6个网络上的预测准确性Tab.3 Prediction accuracies of baseline methods and DRNMF on six networks
其次，测试DRNMF鲁棒性，由于空间有限仅选取CDNP、LO、NLC、CN-L3和DRNMF 5个方法在USA和EMA上进行对比，其结果报告在图2.可观察到DRNMF在不同比率训练集下均获得最优AUC和AUPR值，当训练集为40%时意味着测试集占60%，网络处于高度稀疏状态，DRNMF性能优于其他指标且AUC和AUPR值未显著波动，表明DRNMF在稀疏网络上保持较高鲁棒性.
下面讨论DRNMF主要参数对性能影响.DRNMF包含4个重要参数分别为：α、β、潜在空间维数K和最大迭代次数.设α、β变化范围分别为{0.05，0.5，5，50，500}、{0.05，0.5，5，50，500}，K变化范围{10，20，30，…，100}，迭代次数变化范围{10，20，30，…，100}.研究1个参数变化，则需要固定其余3个参数.
3.1 参数α变化
参数α是约束全局结构对DRNMF性能影响，实验结果报告在图3中.可观察到当α>0.5时，AUC和AUPR
图2 5个不同预测方法在不同比率下对应的AUC和AUPR值Fig.2 Corresponding AUC and AUPR values of five different prediction methods under different ratios
图3 不同参数α在6个网络上对应不同AUC和AUPR值Fig.3 Different parameters α correspond to different AUC and AUPR values on six networks
值逐渐下降直到α=500时预测准确度最低.主要原因是α值过大则DRNMF损失函数误差增大导致预测分数矩阵不准确.而当α≥0.05时，AUC和AUPR值开始逐渐上升直到获得最优性能.因此，当α=0.5时，6个网络上AUC和AUPR值最优.
3.2 参数β变化
参数β是约束网络局部结构贡献，实验结果报告在图4中.可观察当β>0.5时，AUC和AUPR值逐渐下降，直到β=500时性能最差，表明β取值过大影响DRNMF捕获局部结构.当β≥0.05时AUC和AUPR值开始显著提高.因此，当β=0.5时，6个网络上AUC和AUPR值最优.
图4 不同参数β在6个网络上对应不同AUC和AUPR值Fig.4 Different parameters β correspond to different AUC and AUPR values on six networks
3.3 参数K变化
参数K大小直接影响到所提模型性能，其结果报告在图5中.可观察到当K=10时，AUC和AUPR值最小，表明潜在空间无法保持更多网络结构信息.随着K逐渐增大，AUC和AUPR值增大，直到K=70时开始保持稳定.因此，当K=70时，AUC和AUPR值最优.
图5 不同参数K在6个网络上对应不同AUC和AUPR值Fig.5 Different parameters K correspond to different AUC and AUPR values on six networks
3.4 迭代次数变化
迭代次数直接反映收敛速度，其结果报告在图6中.当迭代次数达到40次时，AUC和AUPR值开始保持稳定，表明所提算法在较短时间内获得收敛.因此，迭代次数为40次时，DRNMF性能最优且快速收敛.
图6 不同迭代次数在6个网络上对应不同AUC和AUPR值Fig.6 Different numbers of iterations correspond to different AUC and AUPR values on six networks
如何融合网络结构信息去提高链路预测的准确度是当前研究的热点之一.因此，提出对偶图正则化非负矩阵分解链路预测模型，该模型通过杰卡尔德相似度捕获网络局部结构信息，利用随机游走方法捕获网络全局结构信息，再使用对偶图正则化技术融合局部和全局结构，与非负矩阵分解共同组成统一链路预测目标函数.在6个真实世界网络上利用AUC和AUPR度量与现存具有代表性算法进行比较，实验结果表明所提模型性能获得显著改善.
猜你喜欢 全局局部矩阵 基于改进空间通道信息的全局烟雾注意网络北京航空航天大学学报(2022年8期)2022-08-31领导者的全局观中国医院院长(2022年13期)2022-08-15爨体兰亭集序（局部）中华书画家(2021年12期)2022-01-06凡·高《夜晚露天咖啡座》局部[荷兰]散文诗(2020年1期)2020-07-20二分搜索算法在全局频繁项目集求解中的应用现代计算机(2019年19期)2019-08-12落子山东，意在全局金桥(2018年4期)2018-09-26多项式理论在矩阵求逆中的应用读与写·教育教学版(2017年10期)2017-11-10丁学军作品东方艺术·国画(2016年3期)2017-02-08局部遮光器发明与创新(2016年38期)2016-08-22矩阵南都周刊(2015年4期)2015-09-10
