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.

本文研究了一种基于图神经网络的启发式学习方法，通过提取目标链接周围的局部子图，学习一个将子图模式映射到链接存在性的函数，从而自动学习适合当前网络的启发式算法，实验结果表明其性能优越。