Link Prediction Based on Graph Neural Networks
Link Prediction Based on Graph Neural Networks
复制标题
作者：
Muhan Zhang;Yixin Chen
链路预测是网络结构化数据的一个关键问题。链接预测启发式使用一些评分函数，如共同邻居和Katz指数，来衡量链接的可能性。由于它们的简单性、可解释性和可扩展性，它们已经获得了广泛的实际应用。然而，每个启发式算法都对两个节点何时可能连接有很强的假设，这限制了它们在这些假设失效的网络上的有效性。在这方面，更合理的方法应该是从给定的网络中学习合适的启发式，而不是使用预定义的启发式。通过在每个目标链接周围提取一个局部子图，我们的目标是学习一个将子图模式映射到链接存在的函数，从而自动学习适合当前网络的“启发式”。在本文中，我们研究了这种启发式学习范式用于链接预测。首先，我们开发了一个新的$\gamma$衰变启发式理论。该理论将广泛的启发式方法统一在一个框架中，并证明了所有这些启发式方法都可以很好地从局部子图中逼近。结果表明，局部子图保留了丰富的链路存在性相关信息。其次，基于$\gamma$-衰减理论，提出了一种基于图神经网络（GNN）的局部子图启发式学习算法。它的实验结果显示了前所未有的性能，在广泛的问题上一直工作得很好。
Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a `heuristic' that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel $\gamma$-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the $\gamma$-decaying theory, we propose a new algorithm to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.