# Neural Link Prediction with Walk Pooling

arXiv: https://arxiv.org/abs/2110.04375 · HTML: https://mlsanity.com/paper/2110.04375/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 8 Oct 2021.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Graph InfoClust: Leveraging cluster-level node information for unsupervised graph representation learning](https://mlsanity.com/paper/2009.06946/) (2020)

## Built on by (most cited first, 30 of 37)

- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Neighborhood-aware Scalable Temporal Network Representation Learning](https://mlsanity.com/paper/2209.01084/) (2022)
- [Virtual Node Tuning for Few-shot Node Classification](https://mlsanity.com/paper/2306.06063/) (2023)
- [Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection](https://mlsanity.com/paper/2212.12488/) (2022)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [Collaboration-Aware Graph Convolutional Network for Recommender Systems](https://mlsanity.com/paper/2207.06221/) (2022)
- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [Sampling Enclosing Subgraphs for Link Prediction](https://mlsanity.com/paper/2206.12004/) (2022)
- [Conformalized Link Prediction on Graph Neural Networks](https://mlsanity.com/paper/2406.18763/) (2024)
- [Simplifying Subgraph Representation Learning for Scalable Link Prediction](https://mlsanity.com/paper/2301.12562/) (2023)
- [Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.09567/) (2022)
- [Enhancing Graph Representation Learning with Localized Topological Features](https://mlsanity.com/paper/2501.09178/) (2025)
- [Graph Unitary Message Passing](https://mlsanity.com/paper/2403.11199/) (2024)
- [Stochastic Subgraph Neighborhood Pooling for Subgraph Classification](https://mlsanity.com/paper/2304.08556/) (2023)
- [Link Prediction without Graph Neural Networks](https://mlsanity.com/paper/2305.13656/) (2023)
- [Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction](https://mlsanity.com/paper/2402.08174/) (2024)
- [Link Prediction with Untrained Message Passing Layers](https://mlsanity.com/paper/2406.16687/) (2024)
- [Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methods](https://mlsanity.com/paper/2411.14711/) (2024)
- [PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction](https://mlsanity.com/paper/2404.15225/) (2024)
- [Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity](https://mlsanity.com/paper/2511.06568/) (2025)
- [AutoHEnsGNN: Winning Solution to AutoGraph Challenge for KDD Cup 2020](https://mlsanity.com/paper/2111.12952/) (2021)
- [Generative Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2301.00169/) (2022)
- [NESS: Node Embeddings from Static SubGraphs](https://mlsanity.com/paper/2303.08958/) (2023)
- [Self-Explainable Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2305.12578/) (2023)
- [Introducing New Node Prediction in Graph Mining: Predicting All Links from Isolated Nodes with Graph Neural Networks](https://mlsanity.com/paper/2401.05468/) (2024)
- [PROXI: Challenging the GNNs for Link Prediction](https://mlsanity.com/paper/2410.01802/) (2024)
- [Attribute-Enhanced Similarity Ranking for Sparse Link Prediction](https://mlsanity.com/paper/2412.00261/) (2024)
- [Research topic trend prediction of scientific papers based on spatial enhancement and dynamic graph convolution network](https://mlsanity.com/paper/2203.16256/) (2022)

## Abstract (arXiv)

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.