  Graph neural networks achieve high accuracy in link prediction by jointly
leveraging graph topology and node attributes. Topology, however, is
represented indirectly; state-of-the-art methods based on subgraph
classification label nodes with distance to the target link, so that, although
topological information is present, it is tempered by pooling. This makes it
challenging to leverage features like loops and motifs associated with network
formation mechanisms. We propose a link prediction algorithm based on a new
pooling scheme called WalkPool. WalkPool combines the expressivity of
topological heuristics with the feature-learning ability of neural networks. It
summarizes a putative link by random walk probabilities of adjacent paths.
Instead of extracting transition probabilities from the original graph, it
computes the transition matrix of a "predictive" latent graph by applying
attention to learned features; this may be interpreted as feature-sensitive
topology fingerprinting. WalkPool can leverage unsupervised node features or be
combined with GNNs and trained end-to-end. It outperforms state-of-the-art
methods on all common link prediction benchmarks, both homophilic and
heterophilic, with and without node attributes. Applying WalkPool to a set of
unsupervised GNNs significantly improves prediction accuracy, suggesting that
it may be used as a general-purpose graph pooling scheme.
