摘要

图是建模复杂关系数据（如社交网络、蛋白质相互作用等）的常用模型，而这类数据往往随时间演化（例如新友谊的产生）且可能包含噪声（例如未被观测到的相互作用）。链接预测的目标是预测图中未来可能出现的边，或推断缺失的边，在推荐系统、实验设计以及复杂系统研究等领域具有广泛应用。尽管现有的链接预测算法性能高度依赖于图中已有的边集，但现有方法通常不会通过修改图的拓扑结构来提升性能。本文展示了一种简单而有效的方法：在预处理阶段向图中添加一组特定的边，我们称之为提议边集（proposal set），即可显著提升多种链接预测算法的性能。其核心思想在于，若提议边集中的边整体上与图的结构保持一致，则能够为链接预测算法提供更强的结构引导，使其更准确地预测正确的边；换言之，添加提议边集相当于一种“信号增强”的预处理步骤。我们展示了如何利用现有的链接预测算法生成高效的提议边集，并在多种合成数据集和真实数据集上对该方法进行了评估。结果表明，无论基于邻域启发式方法还是图神经网络的算法，引入提议边集均能显著提升其预测准确性。相关代码已开源，地址为：\url{https://github.com/CUAI/Edge-Proposal-Sets}。