链路预测中的局部相似性指标

李艳丽，周 涛

(电子科技大学复杂性科学实验室 成都611731)

链路预测的核心任务是预测两个没有连接关系的节点产生链接的可能性[1-4]。该研究方向最初的兴起是为了辅助万维网用户从海量的网页中寻找感兴趣的网页[5-6]。后来逐渐在朋友关系预测[7]、恐怖分子的发现[8]、潜在的学术合作关系预测[9]、生物学相互作用关系的揭示[10-11]、商品推荐[12]、网络生成机制探索[13-14]和网络可预测性[15-17]等问题上发挥了巨大价值。其预测类型囊括了根据观测到的网络结构预测可能存在的缺失连边(missing link)，未来可能产生的连边(future links)以及甄别虚假连边(spurious link)等[1,18]。其研究对象涵盖了简单网络、有向网络、二分网络、异构网络和时序网络等[19]。其方法论涉及了基于相似性的链路预测算法(similarity-based algorithms)[9,20]、概率模型(probabilistic models)[21-23]、最大似然模型(maximum likelihood methods)[8,18,24]、网络嵌入模型(network embedding)[25-28]和其他方法[29-31]。

基于相似性的链路预测算法尤其是局部相似性指标可应用领域最为广泛。因为它设计简洁、可解释性强、运算时间低、灵活可扩展，同时其预测准确度有时甚至优于相对复杂的概率模型、最大似然模型和网络嵌入模型[31-33]。该类算法的基本思路是利用节点的局部拓扑结构信息为每一条候选连边分配一个相似性得分，得分越高的连边被认为有更大可能是缺失边，因此在预测列表中排序更靠前。这些算法中最具代表性的几个工作分别是文献[9]总结的纯粹基于网络拓扑结构的一系列局部相似性指标的工作、文献[34]提出AA指标的工作和文献[20]提出RA指标(resource allocation)的工作。文献[9]首次明确提出了基于网络拓扑结构的相似性定义框架，同时一个非常简单且符合直觉的相似性指标——共同邻居指标(common neighbors,CN)也是在该文中被明确强调，即两个节点如果拥有越多的共同邻居，则越相似。定义 Γx为 节点x的邻居集合，则网络中节点x和 节点y的共同邻居指标可定义为：

不同于CN指标，AA指标不仅考虑两个节点拥有的共同邻居数目，而且考虑共同邻居的角色差异。具体定义如下：

式中，kz表示节点z的度。该指标大大削弱了共同邻居中大度节点的贡献。RA是众多局部相似性指标中少有的包含物理过程的指标[35]。由资源分配的物理过程出发，两个节点的相似性由从其中一个节点传递到另一个节点的资源量决定。节点x的每一个邻居都拥有一个单位的资源，并将各自拥有的资源平均分配给它们的邻居，节点y从中接收到的资源量即为两者的相似性值，即：

从数学形式上看，CN、AA和RA指标的区别在于是否考虑共同邻居的角色差异。在CN指标中，所有共同邻居的贡献相同，AA和RA则都是削弱了大度共同邻居的贡献，只是一个从物理过程出发设计，一个从信息论角度出发设计。从预测效果上看，三者在节点度相差不大的网络，即有较小的度异质性的网络中，预测效果不会有显著差异。但在度异质性大，且平均度较大的网络，CN、AA和RA指标在预测效果上差异显著。在大多数网络中，RA预测效果最好，AA次之，CN最差。原因有三：一是大多数真实网络的度分布呈长尾特性，度异质性较强[36-37]；二是大度节点成为共同邻居比较常见，难以体现节点间的相似性，因此惩罚大度节点可以更好刻画大度共同邻居与小度共同邻居不同的角色；最后，CN简并度高，很多候选边的CN值相同，而AA和RA的区分度远胜于CN。

这些工作可用相同且坚实的理论和实证依据进行解释，包括社会学中的同质性原理[38]，即两个相似的节点更大概率产生连边。三角闭包理论[39]，即“朋友的朋友就是朋友”和物理学中的聚集性原理[40]，即两个拥有更多共同邻居的节点更大概率产生连边。这一系列暗含同一内涵的理论早在2001年的合作演化网络[40]和2006年的邮件通信演化网络[41]中得到了验证。同时也被证实在一些非社交网络中同样成立[42]。

至此，大多数局部相似性指标的研究工作都在上述理论框架中开展。通过更精细的刻画共同邻居节点以及候选节点对的自身拓扑结构差异，引入并更好地利用节点的属性信息。研究人员发展出了一系列局部相似性指标，并一次又一次地刷新了预测效果[1,19,43-45]。一般而言，在如此简单的理论框架下很难产生突破，但最近的若干工作跳出了该框架的约束，提出了新的连边理论并对原始基于共同邻居的局部相似性指标设计框架发起了挑战。这些工作的出现将使我们对节点间局部连接模式的理解进入一个新的阶段。

1 LCP和Cannistraci-Hebb理论

在社团结构明显的网络中，同一社团内部产生连边的概率要大于社团之间产生连边的概率。基于该思想，只要增加同一社团内部连边产生的概率，预测性能便可以提高。最直接的做法是使用一些现成的社团识别算法先识别社团，再区分对待社团内部和社团之间的节点连边概率[46-47]，但这样做并不能为我们理解和利用上述思想提供更深刻的洞见和启发。针对没有显式社团标签的网络，有没有可能设计出一套考虑节点间社团连接模式的高效且性能良好的链路预测指标呢？

2013年，文献[48]做出了非常有价值的尝试和推动，如果把最近十年局部相似性指标发展史上有推动意义的工作收录成榜，这一贡献绝对名列前茅。受到以边为研究对象对社团进行划分的启发[48]，文献[49]提出了两个节点之间由边构成的局部社团内部连接越紧密，两个节点越容易产生连边的局部社团范式(local-community-paradigm,LCP)。LCP指由共同邻居及其之间的连边形成的局部结构，展示的是一种不依赖于节点标签和边标签的局部社团描述方法。尽管也有少量工作有类似的出发点[47,50]，但并没有形成一种坚实清晰且干净利落的方法论。LCP作为一种简单独立的结构，很容易作为一种性能增强插件融入到过去已有的局部相似性指标中。如针对CN指标，LCP融入后形成的CAR指标表示如下：

式中， γz表 示在节点x和 节点y形成的LCP结构中，节点z的节点度，亦即节点z与x和y的其他共同邻居的连边数。类似地，针对RA指标，LCP融入后形成的CRA指标可表示为：

从数学表达形式上来看，相对于CN和RA等指标，基于LCP的局部相似性指标对连边相似度有更强的区分度。但这些LCP增强指标存在一个明显的缺陷，在共同邻居之间连边稀疏甚至没有连边的网络中，它们的预测性能将差于原始的RA指标，甚至CN指标。

LCP的核心思想与著名的“赫布律”(Hebb Theory)一致[51]。赫布律的核心思想是知识、学习过程或记忆痕迹存储于由神经元(可视作网络中的节点)和突触(可视作网络中的边)构成的突触集合中，而非神经元个体。文献[52]在2018年指出网络的拓扑结构所起的关键作用便是将不同功能的“突触集合”隔离开，每个“突触集合”中的神经元通过在集合内部加强或者产生新的突触来完成信息的局部处理过程。这也就意味着连边更大概率产生于由边构成的隔离度良好的局部社团内部，这恰与前文提到的LCP范式一致。基于CRA进行微调后的Cannistraci-Hebb指标可表示为：

LCP和Cannistraci-Hebb理论是局部相似性指标研究历程重要且令人印象深刻的系列研究成果，该工作仅仅是对局部社团连接范式的初步尝试，就已获得卓越的预测效果，它必将为我们理解节点对之间的局部连接模式、刻画无标签依赖的局部社团结构以及设计出更优美有效的相似性指标带来灵感。

2 路径越短价值越高？

长久以来研究人员一个不证自明的认识是节点间较短连边的数目要比较长连边的数目更能刻画节点之间产生连边的似然。因为节点之间的互动关系和相互影响会随着连边距离的增大而衰减[53-54]。该现象在众多的基于2阶路径设计的相似性指标上可见一斑。即便考虑了较长路径连边数目的相似性指标(如Katz[55]和LP[56])，短路径也永远扮演主要角色，路径长度越长，贡献越小。这些长路径的加入主要起到增加连边似然分辨率的作用。然而2018年之后连续出现了一系列工作表明3阶路径比2阶路径能更有效地预测未知链路[52,57-58]。这非常反直觉甚至令人生疑，如果这一发现存在于大多数网络中，将会是对过去认知的巨大挑战。

文献[57]假定节点x和 节点y的连边似然可以由x的所有邻居贡献值的线性求和表示，即：

式中，Z为一个待求解的矩阵。通过最小化Z与观测到的邻接矩阵A的差异得到以下优化函数：

该优化问题有一个闭合解，即

式中，I为单位矩阵。从而，节点x和 节点y的LO连边似然可表示为：

LO算法的预测效果显著优于当前一些利用全局信息的代表性算法，包括SPM[15]和Katz[55]等。令人惊奇的是LO的退化指标——直接计算节点3阶路径数目的A3指标也优于CN指标。

同时期，在专门针对蛋白质相互作用网络(protein-protein interaction,PPI)进行关系预测的研究中，文献[58]从蛋白质相互作用网络的结构和演化证据出发，指出相互作用的两个蛋白质大多数情况下需要互补的界面表征(interface)。共享大量相同蛋白质的两个蛋白质界面表征大概率相似或者相同，而非互补。他们进一步通过实证分析表明传统的基于共同邻居的相似性指标与连边概率呈负相关性。为了迎合PPI网络的结构特性，他们启发式地设计了一个名为L3的3阶路径指标，其数学形式如下：

该指标显著提升了PPI网络中潜在相互作用关系的预测准确度。

文献[57]是针对一般性网络，通过抽象理论分析自动得到衍生指标A3；文献[58]则从一个具体的网络出发，基于对网络本身的连边结构特征的深刻理解启发式地提出L3指标。两种完全不同的方法论，在几乎相同的时间获得几乎一致的结果！文献[52]迅速关注了该项研究，并敏锐地认为有必要提出一个一般性的理论框架将该重要发现推广到已有的局部相似性指标和n阶路径上。基于几何平均数思想，即n个变量的几何平均为这n个变量连乘的n次方根，RA指标在n阶路径上的推广可自然而然的表示为：

式中，L(n)为 连接节点x和 节点y的n阶路径上的n–1个中间节点集合。不难发现，前文提到的L3指标即为RA指标在3阶路径上的推广。同时他们也进一步通过实证表明基于3阶路径的局部相似性指标不仅在蛋白质相互作用网络，而且在国际贸易网络和食物链网络上都优于基于2阶路径的局部相似性指标。

如果说上述发现所考虑的网络太少并不足以挑战我们对局部连边模式的传统认知，接下来两个大规模实验的结果促使我们不得不回看最开始的局部相似性指标的设计原理，并斟酌它是否绝对适合所有网络。首先文献[59]基于137个来自16个领域的真实网络进行的一次大规模实证[59]。该实证研究对比了CN、AA、RA、Cannistraci-Hebb指标和它们在3阶路径上的推广指标的预测性能。结果发现，3阶路径指标在相当大一部分网络中表现占优，但并不存在一类指标可以在所有领域绝对占优，即有些领域是基于2阶路径的相似性指标表现更好，而有些领域是基于3阶路径的相似性指标表现更好。如果把不同领域的网络放到一起综合评价，基于3阶路径的相似性指标在AUC指标(即ROC曲线下面积)上优于基于2阶路径的相似性指标，即在超过50%的网络中，基于3阶路径的相似性指标预测效果更好。而在Precision指标上，两者表现相当。该实证研究一个意外的发现就是验证了LCP理论和赫布律的价值：在涉及的4个系列的算法中，Cannistraci-Hebb系列指标成为表现最好的指标。文献[32]进一步基于1 371个来自14个领域的真实网络进行了又一次大规模实证分析，结果再一次表明，在以AUPR为评价指标的实验中，网络所属领域不同，表现占优的算法类别也不同。

针对基于2阶路径的相似性指标和基于3阶路径相似性指标预测性能的争议的意义并不在于选出一个表现更好的相似性指标，而是重塑我们对于节点间局部连接模式的认识，鼓励并启发我们设计出更有效的局部相似性指标。

3 结束语

在链路预测兴起的最初几年，得益于网络科学关于节点连边模式和网络拓扑结构特点的丰硕成果，产生了一系列在同一框架下的经典的局部相似性指标。然而想要在该框架下进一步大幅度提升预测性能更多地需要借助拓扑以外的节点或边的属性信息。本文总结了近十年有别于传统框架的新理论和新发现，其中必将孕育新的预测算法。在以应用为导向追求无限刷新预测效果的同时，链路预测研究的另一个重要使命是探索网络的形成和演化机制[13-14,60]，理解网络的组织结构以及节点连边范式。如果能够对网络背后的组织逻辑精确理解，对应的链路预测效果自然水到渠成。从这个角度而言，局部相似性指标便是以此目标为驱动发展形成的一个重要分支。该分支对应的算法简洁、易用、时间复杂度和空间消耗低、预测性能也具有竞争力，且每一个算法的提出都对应着对一般网络或特定网络节点连边模式的一个新的理解，在丰富了具体网络先验知识的同时，也可以进一步推广到利用全局信息的概率模型和网络嵌入等模型中，从而激发更多的后续研究。因此，即便在机器学习技术蓬勃发展的今天，局部相似性指标在链路预测研究的方法论中仍然有很大的不可替代性，且作为众多研究领域的技术基础，其科研价值和应用价值都不容小觑。