摘要
链接预测是网络结构数据中的一个关键问题。链接预测启发式方法使用一些评分函数，如共同邻居和Katz指数，来衡量链接的可能性。由于其简单性、可解释性和某些方法的可扩展性，这些启发式方法在实际应用中得到了广泛使用。然而，每种启发式方法都对两个节点何时可能连接做出了强烈的假设，这限制了它们在网络中这些假设不成立时的有效性。因此，一种更为合理的方法是从给定的网络中学习一个合适的启发式方法，而不是使用预定义的启发式方法。通过提取每个目标链接周围的局部子图，我们旨在学习一个将子图模式映射到链接存在的函数，从而自动学习适用于当前网络的“启发式”（heuristic）。本文研究了这种用于链接预测的启发式学习范式。首先，我们提出了一种新颖的$\gamma$衰减启发式理论。该理论在一个统一框架内整合了广泛的启发式方法，并证明所有这些启发式方法都可以从局部子图中得到良好的近似。我们的结果表明，局部子图保留了与链接存在相关的丰富信息。其次，基于$\gamma$衰减理论，我们提出了一种新的算法，利用图神经网络（GNN）从局部子图中学习启发式方法。实验结果显示该算法具有前所未有的性能，在各种问题上表现出色且一致性良好。