为了让叙述变得简洁和紧凑，本文聚焦于简单无向图上的链路预测问题，其中连边的方向和权重都不用考虑，也不允许出现节点自环的情况。通常用$ G(V,E) $表示一个简单图，其中$ V $是节点的集合，$ E $是连边的集合。在链路预测的研究中，假设因为实验分析、调查问卷和观察记录等手段的局限性，已知的连边$ E $只是真实存在的连边的一部分——这在生物网络和社会网络中特别常见^[29-32]，而链路预测的主要任务就是基于已知的网络拓扑结构，去推断实际存在但未被观察到的连边——称其为缺失边。对于动态演化的网络，如Internet、WWW等技术网络和Facebook、Twitter等在线社交网络，一个自然推广的链路预测任务就是基于当前的网络拓扑结构和历史演化轨迹，预测未来将会出现但现在尚不存在的连边——称其为未来潜在边。

对于任何链路预测方面的研究，如果要说明算法的有效性，一个自然且必要的步骤是在真实网络中测试算法的表现。有少量关于算法的研究是针对特定类型的网络开展的，如社会网络^[33-34]和生物网络^[35]，而更多的研究是适用于各领域的网络——至少从研究者的描述来看是这样的。对于后者而言，一个自然的问题就是针对来自不同领域的网络，算法的表现是否存在差异。如会不会某算法A在社交网络上预测的精度显著好于算法B，但针对交通网络，算法A的精度却显著差于算法B。当然，为了能够针对一个领域的网络，比较若干算法的预测性能，需要选择足够多的网络——从数学上讲，应该多到无论去掉哪一个网络，都不会对算法性能的排名产生任何影响。如果不管多少网络都无法达到这个条件，就说明针对该领域的网络，有一些算法的性能是非常接近的，分不出胜负。因此，在还不完全清楚领域对于算法性能的影响时，如果研究者想要说明他们所提出的算法性能优异，一种让人信服的做法是选择多个领域的网络，并且保证在每个领域都选择足够多的网络。

再次回到上面提到的关键问题：针对不同领域的网络，算法的表现有显著差异吗？尽管没有专门针对这个问题的研究，但是从最近一些涉及大量网络的链路预测研究中可以发现端倪。我们对比分析了基于二阶路径和基于三阶路径的局部相似性指标在16个领域的128个真实网络上的链路预测精度^[36-37]，发现在软件网络和食物链网络中，三阶指标的表现优于二阶指标。与此同时，在合作网络，人类接触网络和动物接触网络中，二阶指标的表现远胜于三阶指标。同样是与蛋白质相关的网络，在蛋白质相互作用网络中，三阶指标的表现远胜于二阶指标，但在以二级结构单元为节点的蛋白质结构网络中，三阶指标却远不如二阶指标。文献[38]对比分析了CHA^[39]、SPM^[20]、SBM^[17]、Stacking^[25]等算法在6个领域550个网络中的表现。从文献[38]的实验结果可以看出，针对不同领域的网络，算法的相对表现有显著差异。根据预测精确度^[40]的胜率来看，CHA在生物、信息、技术、经济、社会这5类网络中胜率都排名第一，但在交通网络中胜率却是上述4种算法中最低的；SPM在交通网络中胜率第一，在其他5类网络中胜率均排第二；SBM在生物、信息、经济3类网络中胜率超过了Stacking，但在技术、社会和交通3类网络中胜率又低于Stacking。文献[41]针对上述6个领域550个网络，对比分析了基于低阶点轨道度和低阶边轨道度的链路预测器的预测精度，发现对于不同领域的网络，占优的预测器差异巨大。如在社会网络中，与共同邻居等价的边轨道度预测器胜率高达91%，但在生物、技术和经济网络中，同一个预测器的胜率还没有超过5%。我们测试了9种著名的链路预测算法在来自6个领域中的131个网络上的表现，如果按照平均AUC^[42]分值给9种算法排名，发现两个排名之间的平均关联，如果用肯德尔等级相关系数^[43]和斯皮尔曼等级相关系数^[44]的方法来计算，其关联值分别为0.5185和0.6067。可见，排名之间虽然存在正向关联，但也存在显著的不一致，说明算法在不同领域网络中的表现是不一致的。

基于目前的文献和计算，可以确认算法在不同领域网络上的表现是不一致的——算法A在某领域网络中表现好于算法B，并不意味着算法A在另外一个领域网络中的表现也会好于算法B。由于本文所讨论的链路预测算法都只依赖于网络的拓扑特征，所以原则上只要对网络拓扑特征有充分的理解，就能够很好估计给定算法的表现。算法在不同领域的网络上表现不一致可以被归因为：1）不同领域的网络拓扑性质不同；2）拓扑特性会影响链路预测算法的表现。

对于第一个原因，网络科学家早已达成共识。如大部分真实网络都表现出小世界效应，也就是网络平均距离的增长速度不超过网络节点数的对数^[45]，但是对于高度依赖于基础设施的陆上交通网络，如地铁网络、公路网络和街道网络等^[46]，因为直接修建“长程连接”是不经济的，所以网络的平均距离会显著高于同等规模和密度的典型的小世界网络^[47]。类似地，许多真实网络都展现出无标度特性，即节点的度分布近似符合幂律分布^[48]，与此同时，也有很多真实网络不具备无标度特性。根据文献[49]针对928个真实网络的实证研究，不同领域的网络中无标度网络的丰富程度大不相同，如即便按照最宽松的定义，也有63%的生物网络不是无标度网络，但有92%的技术网络可以归为不同严格程度的无标度网络。如果继续深入一个个大领域中，会进一步发现，不同子领域网络的度分布也大相径庭。如在社交网络大类中，Facebook、Youtube、Flickr等在线社交网络的度分布是幂律的^[50]，科学家和演员合作网络的度分布是介于幂律和指数之间的^[51-52]，而某些特定的熟人关系网络的度分布却是高斯的^[53]。又如在交通网络中，航空网络的节点度分布是幂律的^[54]，但铁路网络的节点度分布是指数的^[55]，而地铁网络^[56]和公交网络^[57]节点的度分布比指数还要狭窄^[58]。从目前已知的研究结果来看，来自不同领域的网络，在各个拓扑特征方面都存在显著的不同。如社交网络的度度相关性往往大于零，而生物与技术网络的度度相关性却几乎都小于零^[59]。又如三角结构在大部分真实网络中随处可见，然而在蛋白质相互作用网络^[24]和人类浪漫关系网络^[60-61]中却非常少见。事实上，来自不同领域的网络，在社团结构^[62]、模体结构^[63-64]、富人俱乐部效应^[65-66]、自相似性^[67]等方面，也呈现出显著的差别。

对于第二个原因，相关的研究非常少。基于18个真实网络，文献[68]分析了常见的网络结构特征和若干知名链路预测算法精确度之间的关系，研究发现网络度分布的异质性越强或者度序列的Gini系数越大，基于优先连接的指数表现越好，而网络的簇系数越大，基于共同邻居的指数表现越好。

综上，本文可以断定链路预测算法在不同领域网络中的表现是不一致的，因此，在对一个普适性的算法进行评价的时候，有必要选取来自不同领域的网络，并且在每个领域都要选择足够多数量的网络，否则评价的结果极可能是有偏差的。我们认为，要想真正理解算法在不同领域网络中表现不同的原因，就必须挖掘网络不同结构特征对于算法表现的影响，从而未来有望通过结构分析快速筛选合适的算法。文献[68]的工作开了一个好头，但是在这方面还需要开展深入的分析和全面的实证。

链路预测是一个特殊的二分类问题^[69]——已存在的边被视为正例，而未出现的边则被视为负例。为了评价算法的性能，通常要从已经观察到的边集$ E $中选取一部分边作为测试集$ {E}^{T} $——测试集是用来评价算法的，因此涉及测试集的所有信息在训练算法模型的时候都是严格不可知的。如果待训练的模型还有参数，通常要把剩余的边$ E-{E}^{T} $进一步划分成训练集和验证集，前者用于特征提取，后者用于确定模型的参数。为了保持数据分布的一致性，从$ E-{E}^{T} $中抽取验证集的方法应该与从$ E $中抽取测试集的方法保持一致，因此关键的问题是如何从$ E $中抽取测试集。这个过程叫作链路抽样，以便于和一个紧密相关的图抽样过程^[70-71]有所区分，后者往往关注如何抽取一部分节点，其首要目的是判断抽样后的较小网络和原始网络结构及功能的差异，而不是为了预测缺失链路。

应该怎么进行链路抽样呢？如果网络中每条边出现的时间是已知的^[72]，一种自然的方法就是把最后出现的一批连边作为测试集，因为用过去的信息预测未来的信息是一个基本的原则。如果没有时间信息，所面对的问题就是如何预测缺失边。即，假设在那些不存在的边中（$ E $的补集），有一些是实际存在但没有被观察到的边，而链路预测的任务就是要把这些边找出来。假设未被观察到的缺失边的集合是$ {E}^{M} $，那么，如同从$ E-{E}^{T} $中抽取验证集的方法应该与从$ E $中抽取测试集的方法保持一致，从$ E $中抽取测试集的方法也应该与从$ E\cup {E}^{M} $中抽取$ {E}^{M} $的方法保持一致，这样训练得到的算法模型才能够很好地基于$ E $预测$ {E}^{M} $。如果能够知道为什么有一些实际存在的连边在真实网络中无法被观察到（也就是$ {E}^{M} $出现的原因，称其为缺失模式），那么就可以通过模拟这种缺失模式而从$ E $中抽样出$ {E}^{T} $。遗憾的是，这种模式通常是未知的。

对于“找到真实网络的缺失模式以便更好设计链路抽样方法”这个问题，研究人员要么没有意识到这个问题的重要性，要么没有找到解决这个问题的切入口，因此目前已知的几乎所有不涉及时间信息的链路预测研究，都是采用完全随机的方式从$ E $中抽样出$ {E}^{T} $，但事实上边的缺失模式受到网络本身特性或数据收集过程的复杂影响，展现出明显的非均匀性和非随机性^[73]。一些零星的研究考虑了连边的缺失模式。文献[74]认为低度节点之间的连边可能更易遗漏，因此采用基于节点度的抽样策略，并让连接低度节点的连边有更高的概率被抽到测试集中。在此基础上对比研究不同算法的表现，得到了一个让人惊讶的结果：Leicht–Holme–Newman相似性指标^[75]表现最优，而这个指标在完全随机抽样的前提下表现很差^[74]。由此可见，不同的链路抽样方法对结果影响很大，因此深入开展这方面的研究很有必要。最近特别值得关注的是文献[76]对链路缺失模式的系统性研究，该研究再次指出，基于均匀随机分布假设的抽样可能会因忽视了网络数据的非随机缺失特性而引入系统性偏差，进而误导对模型效能的正确评估。文献[77]的研究系统性地分析了常见的20种不同的抽样方法，发现不同缺失模式下算法的表现不尽相同，再次验证了缺失模式的重要性。该研究所涉及的抽样方法主要来自图抽样的研究，并不一定与真实网络的链路缺失模式一致，但因为覆盖的方法很多，所以具有较大的参考价值。

要找到恰如其分的链路抽样方法，一个首要的任务是要搞清楚真实网络的缺失模式到底是什么样子的。对于时序网络，要进一步观察和分析最后一段时间出现的连边具有什么特性，这些连边的特征就代表了链路缺失模式。对于本身没有时序信息，但是是逐步被构造出来的网络，特别是通过大量实验逐渐累积构建的生物网络，可以认为理论上具有共识的或实验容易验证的连边先出现，因此相关论文发表顺序也可以作为类似的参考，从而可以把后发表论文所报道的连边的特征看作链路的缺失模式。当对目标网络的链路缺失模式了解清楚后，就可以设计对应的链路抽样方法，或者从常见的抽样方法^[77]中选择最接近的方法。另外，如何确定测试样本的数量也是一个需要关心的问题，因为过大的测试集可能会削弱模型训练（训练数据过少），而过小的测试集则可能导致对算法性能评估不准确。本文集中讨论的是无向简单图上的链路预测问题，如果要考虑更复杂的网络上的链路预测，如针对多层网络^[78]或者高阶网络^[79]，也需要考虑如何进行链路抽样，以符合真实目标网络的链路缺失模式。这个时候进行抽样还需要考虑层间交互或高阶交互，问题变得更具挑战性。

如上节所述，在训练模型参数时，绝不应当使用测试集中的信息。如果使用了部分或者全部测试集的信息，然后再用算法在测试集上的表现来评价算法的性能，就相当于提前知道了考试的答案，那么考试的价值就失去了。这样得到的算法可能在测试集上表现优异，但是在真实场景中表现不佳，用机器学习的术语来说，就是泛化能力差——泛化能力是指从已有的学习经验中提取和应用知识到新的、未经处理的情境中的能力。

遗憾的是，在链路预测实际发表的研究工作中，研究人员经常比较预测结果与测试集来获得所谓的最优参数，相当于利用了测试集的信息。这是一个严重的错误，在链路预测研究的早期就存在，并且一直延续至今。这在很大程度上对无参数算法是不公平的，因为这些算法无法从测试集的信息中得到任何附加的好处，与之相对，泛化能力差的算法则“不当得利”，因为它们既使用测试集的信息来拟合参数，又使用测试集来评价算法，所以它们泛化能力差的缺陷被错误地掩盖了。文献[80]的研究发现了“选择偏差”的现象，即选择的模型对于特定数据集过于拟合，无法泛化到其他数据集。为了避免这种现象，该研究提出一种修正方法，即在进行交叉验证时，每次模型选择后应在独立的验证集上进行评估，而不是在同一个数据集上评估，以更准确地评估模型的泛化能力。文献[81]也讨论了模型选择中的过拟合问题以及由此导致的选择偏差，建议在进行模型选择时应使用一个独立的验证集进行性能评估，并且在整个模型选择过程中不再使用该验证集。

因此，我们迫切需要分析曾经可能因为这种错误被高估或者低估的算法。可以想象，那些对参数非常敏感且本质上容易过拟合的算法性能会急剧下降，而无参算法或具有强大泛化能力的算法的相对性能倾向于提升。2024年，文献[82]对图神经网络的泛化性能进行了研究，展示了泛化误差如何被图噪声等因素的相互作用所塑造，其中也阐述了模型算法的泛化性能受到训练集相对于所有节点比例的影响。事实上，更早一点的时候，文献[83]的研究表明存在一种违反直觉的双下降机制，即更多的训练数据和更大的模型反而会损害泛化能力。如果是先按照一个固定的比例进行链路抽样并得到测试集，再按照一个固定的比例（这两个比例通常相同，但也可以不同）从剩下的链路中选出验证集，那么按照文献[82]和文献[83]的建议，选择什么样的比例才能提高算法的泛化能力是需要研究的。除了用一次抽样后便固定的测试集外，文献[84]使用$ k $折交叉验证的方法可以提高分类算法的泛化性，并提倡通过考虑数据集的大小和计算资源来选取最优的$ k $值。类似的结论是否也适用于链路预测，针对链路预测又怎么选择合适的$ k $值呢？这些问题目前还没有答案。总体而言，本文认为要厘清这些问题，除了重新使用正确的方法确定参数外，还需要进一步研究已知链路预测算法的泛化能力。

最近十几年有数以千计的链路预测算法被提出，因此，如何选择合适的评价指标来科学、公正地评估这些算法的性能，进而正确引导算法设计和优化的方向，成为了链路预测领域亟待解决的核心问题。不同的评价指标通常具备独特的属性，且各自适用于特定的场景。如精确度关注的是预测为正样本的准确性，特别适用于假阳性（预测为正样本但实际为负样本）成本较高时的场景，如医学诊断、金融风险评估等^[85]；马太关联参数（Matthews Correlation Coefficient, MCC）特别适用于数据类别不平衡或样本数量不均匀的情况，如药物筛选、信用评分等^[86]；归一化折损累计增益（Normalized Discounted Cumulative Gain, NDCG）考量了预测结果的排序及每个位置的重要性，主要用于推荐系统、搜索引擎等排序任务中^[87]；ROC（Receiver Operating Characteristic）曲线下的面积（Area Under Curve, AUC）反映的是模型区分正负样本的能力，在数据不平衡的情况下，能较好地评估模型的整体性能^[42]；Precision-Recall曲线下的面积（Area Under the Precision-Recall, AUPR）适用于类别不平衡且关注高精确度的任务^[88]，如异常检测等；Precision曲线下的面积（AUC-Precision）关注模型在不同阈值下召回率和精确度之间的关系，其更加重视模型在少数类上的表现^[89]。

到目前为止，尚没有选择评价指标的标准：一些研究人员习惯于遵循经典的指标，而另一些则有自己的偏好。如果不同的指标给出的算法性能排序是相同或者几乎相同的，那么如何选择评价指标就不是一个值得关注的问题。然而，近期的实证研究显示，不同评价指标呈现出显著的不一致性^[89-90]。即，在一个评价指标下A算法性能好于B算法，如果换了另一种评价指标，则很有可能B算法的性能会超过A算法。在这种情况下，如何选择合适的指标来评价算法性能，就成了一个亟待解决的问题。

由于在所有链路预测算法性能的评价指标中，AUC是最为流行的，因此在仅存不多的关于评价指标性能方面的研究中，往往都是讨论AUC的缺点和提出改进方案^[91]。文献[92]的研究认为在正负样本严重不均衡时，使用AUPR会更优于AUC。文献[93]提出AUC会给许多负样本排序在底部的算法过高得分，而这种能力对于找到需要的正样本而言，没有太大意义。文献[94]则强调了AUC在评估只有少量头部预测才有价值的场景（常见于搜索和推荐）时存在局限性。针对AUC可能存在的不足，一些科学家提出了AUC的若干改良版本。如文献[95]认为AUC存在一个重大的缺陷，就是在衡量不同分类器的性能时使用了不同的错误分类代价矩阵，基于此，提出了名为H-measure的指标，它采用了AUC指标的设计思路，又可以保证不同分类器下错误分类代价局部是一致的。文献[89]认为靠前的位置重要性要大于靠后的位置，因此提出了一种基于放缩ROC曲线横纵坐标的新指标AUC-mROC。

在没有明确选择标准情况下，有些研究人员同时选择多个指标，以期达到一种更全面的评价。如文献[96]使用了6个评价指标来评估算法性能，文献[38]从预测的精确度、排序性能、类别不平衡的角度选取了7个评价指标来量化预测性能。尽管这种做法可以有效避免依赖单一指标可能带来的偏见或限制，但占用了更多的计算资源，并且在评价指标出现不一致时，并没有办法判断哪一个评价指标更加可信。我们认为衡量评价指标好坏的关键是看一个评价指标能否正确分辨性能相近的算法孰优孰劣。基于此，我们针对一个链路预测算法性能可控的人工网络模型，提出了一套刻画评价指标分辨能力的方法^[97-98]，这是较少见的定量刻画任意指标特定能力并在不同指标之间对比分析的研究。总体而言，探索链路预测中评价指标的有效性，形成具备广泛共识的一套评价算法优劣的标准，是目前推动链路预测领域坚实发展的关键性问题。相关研究刚刚起步，值得特别关注。

链路预测是网络科学研究中最具活力的分支之一，在最近的十多年，有数以千计的算法被提出。与此同时，在快速发展的过程中，很多基础性的问题没有得到足够重视，特别地，在网络选取、链路抽样、模型训练和算法评价等方面要么没有广泛达成共识的规范和标准，要么虽然形成了一定的共识（如完全随机的链路抽样和利用AUC指标进行算法评估，都非常流行），但这些共识背后的理论是不充分的。

本文回归链路预测问题的研究本质与核心，挖掘并梳理出在此研究领域中仍需重点关注的4个基础性研究方向。总结起来，我们认为在链路预测领域中，未来应首先在以下8个方面重点开展研究：1）网络的领域性如何影响链路预测算法性能，针对不同领域网络应选择何种算法？2）同领域的网络具备什么样的有差异性的拓扑特性？3）不同类型网络连边的内在缺失机制是什么，针对这些机制应采用何种链路抽样方法？4）如何度量链路预测算法的泛化能力？5）经典链路预测算法的泛化能力如何，如何有效提高算法的泛化能力？6）网络特征与算法特性是如何影响泛化能力的？7）如何量化评价指标对算法优劣的分辨能力？8）选取哪一个或一组评价指标能更高效且全面地评估链路预测算法的性能？