# Graph Neural Networks for Link Prediction with Subgraph Sketching

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 57 references that are in the map.
- First posted on arXiv 30 Sep 2022.

## Builds on (most cited first, 30 of 35)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [PyTorch-BigGraph: A Large-scale Graph Embedding System](https://mlsanity.com/paper/1903.12287/) (2019)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Learning from Counterfactual Links for Link Prediction](https://mlsanity.com/paper/2106.02172/) (2021)
- [Neural Link Prediction with Walk Pooling](https://mlsanity.com/paper/2110.04375/) (2021)

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

- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights](https://mlsanity.com/paper/2406.10727/) (2024)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Mosaic of Modalities: A Comprehensive Benchmark for Multimodal Graph Learning](https://mlsanity.com/paper/2406.16321/) (2024)
- [Foundation Models for the Electric Power Grid](https://mlsanity.com/paper/2407.09434/) (2024)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [TRIX: A More Expressive Model for Zero-shot Domain Transfer in Knowledge Graphs](https://mlsanity.com/paper/2502.19512/) (2025)
- [Pure Message Passing Can Estimate Common Neighbor for Link Prediction](https://mlsanity.com/paper/2309.00976/) (2023)
- [Efficient Neural Common Neighbor for Temporal Graph Link Prediction](https://mlsanity.com/paper/2406.07926/) (2024)
- [LPFormer: An Adaptive Graph Transformer for Link Prediction](https://mlsanity.com/paper/2310.11009/) (2023)
- [Expressive Sign Equivariant Networks for Spectral Geometric Learning](https://mlsanity.com/paper/2312.02339/) (2023)
- [PageRank Bandits for Link Prediction](https://mlsanity.com/paper/2411.01410/) (2024)
- [Universal Link Predictor By In-Context Learning on Graphs](https://mlsanity.com/paper/2402.07738/) (2024)
- [Link Prediction with Non-Contrastive Learning](https://mlsanity.com/paper/2211.14394/) (2022)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [Graph Neural Networks in Vision-Language Image Understanding: A Survey](https://mlsanity.com/paper/2303.03761/) (2023)
- [Mixture of Link Predictors on Graphs](https://mlsanity.com/paper/2402.08583/) (2024)
- [Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning](https://mlsanity.com/paper/2405.16435/) (2024)
- [On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks](https://mlsanity.com/paper/2409.17475/) (2024)
- [Diffusion-based Negative Sampling on Graphs for Link Prediction](https://mlsanity.com/paper/2403.17259/) (2024)
- [TAGLAS: An atlas of text-attributed graph datasets in the era of large graph and language models](https://mlsanity.com/paper/2406.14683/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Flock: A Knowledge Graph Foundation Model via Learning on Random Walks](https://mlsanity.com/paper/2510.01510/) (2025)
- [SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2303.03379/) (2023)
- [Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction](https://mlsanity.com/paper/2309.17417/) (2023)
- [Simplifying Subgraph Representation Learning for Scalable Link Prediction](https://mlsanity.com/paper/2301.12562/) (2023)

## Abstract (arXiv)

Many Graph Neural Networks (GNNs) perform poorly compared to simple heuristics on Link Prediction (LP) tasks. This is due to limitations in expressive power such as the inability to count triangles (the backbone of most LP heuristics) and because they can not distinguish automorphic nodes (those having identical structural roles). Both expressiveness issues can be alleviated by learning link (rather than node) representations and incorporating structural features such as triangle counts. Since explicit link representations are often prohibitively expensive, recent works resorted to subgraph-based methods, which have achieved state-of-the-art performance for LP, but suffer from poor efficiency due to high levels of redundancy between subgraphs. We analyze the components of subgraph GNN (SGNN) methods for link prediction. Based on our analysis, we propose a novel full-graph GNN called ELPH (Efficient Link Prediction with Hashing) that passes subgraph sketches as messages to approximate the key components of SGNNs without explicit subgraph construction. ELPH is provably more expressive than Message Passing GNNs (MPNNs). It outperforms existing SGNN models on many standard LP benchmarks while being orders of magnitude faster. However, it shares the common GNN limitation that it is only efficient when the dataset fits in GPU memory. Accordingly, we develop a highly scalable model, called BUDDY, which uses feature precomputation to circumvent this limitation without sacrificing predictive performance. Our experiments show that BUDDY also outperforms SGNNs on standard LP benchmarks while being highly scalable and faster than ELPH.