它有什么作用?
链接预测是一项网络分析任务,用于估计观察到的图中缺失的边或未来可能形成的边。该任务由 Liben-Nowell 和 Kleinberg (2003, 2007) 正式提出,涵盖了一系列方法——从简单的结构相似性指标,如共同邻居数、Jaccard 系数和 Adamic-Adar 指数,到矩阵分解和图神经网络 (GNN) 方法——并使用 AUC 和平均精度 (Average Precision) 进行评估,以处理真实边与不存在边之间严重不平衡的比例。
方法背后的直觉
在任何真实世界的网络中,记录的边只占真实连接的一小部分:社交平台会遗漏未公开的联系,引文数据库会省略未索引的论文,蛋白质相互作用的实验也会遗漏许多配对的测试。链接预测旨在:根据我们能看到的连接,推断哪些未观察到的配对最有可能连接?核心思想是,两个节点共享许多共同邻居,或者在学习到的嵌入空间中彼此靠近,比两个结构上距离较远的节点更有可能被连接。相似性指标通过一个单一的公式明确这一点;基于 GNN 的方法则从标记的样本中学习哪些结构模式最能预测连接性。
历史学
该任务由 Liben-Nowell 和 Kleinberg 在 2003 年的 SODA 会议论文和 2007 年的 JASIST 期刊扩展版中正式定义,他们在其中对合作者网络上的简单结构相似性指标进行了基准测试,并表明仅拓扑结构就具有强大的预测信号。随后的工作将其扩展到矩阵分解和概率生成模型。Zhang 和 Chen (2018) 的工作极大地推动了该领域的发展,他们提出了 Seal 框架——提取局部封闭子图并使用 GNN 对其进行分类——证明了学习到的结构特征在各种基准网络上始终优于手工设计的相似性指标。
何时使用
链接预测适用于网络不完整或不断演变且目标是恢复或预测边的任何问题。适用的场景包括推荐社交网络中的新连接、预测未来的引文或合作关系、推断蛋白质-蛋白质相互作用以及完成知识图谱。该方法至少需要 50 个节点和足够密度的观察边,以便能够学习结构模式。当节点少于 20 个时,中心性分析是更安全的选择。图的观察部分必须具有代表性;如果采样机制存在严重偏差,则推断出的边可能反映的是采样伪影而非真实结构。
局限与注意事项
- 性能在很大程度上取决于负采样策略;不同的策略可能导致对同一模型的不同结论。
- 基于 GNN 的方法需要足够大的标记边集和显著的计算资源。
- 结构指标假设观察到的拓扑相似性意味着未来的连接性,这在具有异质性结构的网络中可能不成立。
- 时间训练-测试分割至关重要,但需要可靠的时间戳;如果没有时间戳,信息泄露会夸大表面性能。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 涵盖了广泛的复杂性——简单的 Jaccard 或 Adamic-Adar 指数无需训练,直接在图拓扑上工作,而基于 GNN 的方法则学习复杂的结构模式。
- 无模型相似性指标速度快、可解释性强,并且在具有有限训练信号的稀疏图上表现稳健。
- GNN 方法在不同领域(社交、生物、知识图谱)具有良好的泛化能力,并能捕获高阶拓扑结构。
- AUC/AP 评估框架对真实边和不存在边之间严重的类别不平衡具有鲁棒性。
应用
- 社交网络中的好友或连接推荐(Facebook 的“你可能认识的人”、LinkedIn)。
- 预测学术网络中未来的研究合作或引文关系。
- 从部分实验数据中推断生物网络中缺失的蛋白质-蛋白质相互作用。
- 通过预测实体之间的关系来完成知识图谱。
- 药理学网络中的药物-靶点相互作用预测。
使用方式
使用方式
网络由观察到的边构成,并使用时间分割或随机分割将其划分为训练集和测试集。只要有时间戳,就倾向于使用时间分割,因为它可以防止信息泄露:未来的边不应告知模型过去的信息。训练图是评分方法唯一可以观察到的图。
由于绝大多数节点对都没有连接,因此评估每一对不存在的边是不切实际的。负采样策略选择一组不存在的边作为负例。样本量和采样策略(随机、困难负例、度平衡)会显著影响测量到的性能,并且必须与结果一起报告。
每个候选对都会收到一个似然分数。结构指标根据观察到的图拓扑计算分数——共同邻居数计算共享邻居的数量,Jaccard 通过并集对该计数进行归一化,Adamic-Adar 则通过共享邻居的度数的倒数对数进行加权。矩阵分解方法将邻接矩阵分解为潜在因子,其点积近似边概率。基于 GNN 的方法,最突出的是 Zhang 和 Chen (2018) 的 Seal 框架,它提取每个候选对周围的局部子图,并训练一个图分类器来区分真实边和虚假边,从而捕获简单指标所遗漏的高阶结构模式。
预测按分数排序,并与保留的正面和负面边进行比较。AUC-ROC 衡量随机正面对排在随机负面对之上的概率。平均精度 (AP) 总结了整个排序的精度,在正面样本稀少时信息量更大。必须报告这两个指标;在类别严重不平衡的情况下,仅报告准确率具有误导性。
常见陷阱
- 将未来边泄露到训练图中——始终使用时间分割或严格的随机分割,并验证测试边是否出现在训练邻接矩阵中。
- 仅报告准确率;因为不存在的边数量远超真实边的数量,准确率几乎没有意义——始终报告 AUC 和 AP。
- 在比较方法时忽略负采样策略;改变采样策略可能会颠倒模型之间的排名。
- 将链接预测应用于节点少于 20 个的图——节点太少时,结构模式过于稀疏,无法产生可靠的预测;此时应优先选择中心性分析。
- 将有偏的观察图视为代表性样本——如果观察到的边系统性地遗漏了某些节点类型,预测结果将继承这种偏差。
常见问题
我应该选择哪种方法——相似性指标还是 GNN?
相似性指标(共同邻居数、Jaccard、Adamic-Adar)是一个很好的起点:它们无需训练,具有可解释性,并且在稀疏图上表现出人意料地好。像 Seal 这样的基于 GNN 的方法在具有复杂高阶结构的网络上优于指标,但需要足够数量的标记边和更多的计算资源。当数据有限或可解释性很重要时,从指标开始。
如何在不泄露信息的情况下分割图进行评估?
如果您的边带有时间戳,请使用时间分割:在某个截止时间之前的边上进行训练,并在之后形成的边上进行测试。如果没有时间戳,请将一部分边作为正面样本保留,并采样相同数量或固定数量的非边作为负面样本,确保保留的边不出现在训练邻接矩阵中。
为什么 AUC 比准确率更受青睐?
在任何真实网络中,不存在的边数量远远超过存在的边数量——通常相差几个数量级。一个预测每对节点之间“无边”的平凡模型可以获得近乎完美的准确率,但却预测不出任何有用的信息。AUC-ROC 和平均精度是基于排名的指标,对这种不平衡不敏感,并直接衡量排名的质量。
链接预测是否可以应用于有向图或加权图?
可以。对于有向图,分数可以在每个方向上分别计算,并且一些 GNN 框架原生支持有向邻接。对于加权图,相似性指标可以在邻域计算中纳入边权重,GNN 方法可以使用边特征。然而,大多数基准研究都在无权无向图上进行,因此在调整方法时需要格外小心。
相关方法
参考文献
Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.
打开 DOI 文献已复制。Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.
打开出版物文献已复制。