  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.
