# OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 97 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [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)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [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)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [A simple neural network module for relational reasoning](https://mlsanity.com/paper/1706.01427/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)

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

- [GOOD: A Graph Out-of-Distribution Benchmark](https://mlsanity.com/paper/2206.08452/) (2022)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Deciphering Spatio-Temporal Graph Forecasting: A Causal Lens and Treatment](https://mlsanity.com/paper/2309.13378/) (2023)
- [Does Invariant Graph Learning via Environment Augmentation Learn Invariance?](https://mlsanity.com/paper/2310.19035/) (2023)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Inductive Logical Query Answering in Knowledge Graphs](https://mlsanity.com/paper/2210.08008/) (2022)
- [GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts](https://mlsanity.com/paper/2312.04693/) (2023)
- [A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptation](https://mlsanity.com/paper/2410.19265/) (2024)
- [GOLD: Graph Out-of-Distribution Detection via Implicit Adversarial Latent Generation](https://mlsanity.com/paper/2502.05780/) (2025)
- [Investigating Out-of-Distribution Generalization of GNNs: An Architecture Perspective](https://mlsanity.com/paper/2402.08228/) (2024)
- [How Interpretable Are Interpretable Graph Neural Networks?](https://mlsanity.com/paper/2406.07955/) (2024)
- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)
- [Graph Data Selection for Domain Adaptation: A Model-Free Approach](https://mlsanity.com/paper/2505.17293/) (2025)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Causal Lifting and Link Prediction](https://mlsanity.com/paper/2302.01198/) (2023)
- [Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks](https://mlsanity.com/paper/2209.06589/) (2022)
- [Tackling Size Generalization of Graph Neural Networks on Biological Data from a Spectral Perspective](https://mlsanity.com/paper/2305.15611/) (2023)
- [Topology-Aware Dynamic Reweighting for Distribution Shifts on Graph](https://mlsanity.com/paper/2406.01066/) (2024)
- [Link Prediction with Untrained Message Passing Layers](https://mlsanity.com/paper/2406.16687/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [A Survey of Out-of-distribution Generalization for Graph Machine Learning from a Causal View](https://mlsanity.com/paper/2409.09858/) (2024)
- [Causal invariant geographic network representations with feature and structural distribution shifts](https://mlsanity.com/paper/2503.19382/) (2025)
- [Addressing the Impact of Localized Training Data in Graph Neural Networks](https://mlsanity.com/paper/2307.12689/) (2023)
- [Beyond Transduction: A Survey on Inductive, Few Shot, and Zero Shot Link Prediction in Knowledge Graphs](https://mlsanity.com/paper/2312.04997/) (2023)
- [PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning](https://mlsanity.com/paper/2405.06418/) (2024)
- [LinkThief: Combining Generalized Structure Knowledge with Node Similarity for Link Stealing Attack against GNN](https://mlsanity.com/paper/2410.02826/) (2024)

## Abstract (arXiv)

This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) -- such as Graph Neural Networks (GNNs) -- to perform inductive out-of-distribution (OOD) link prediction tasks, where deployment (test) graph sizes are larger than training graphs. We first prove non-asymptotic bounds showing that link predictors based on permutation-equivariant (structural) node embeddings obtained by gMPNNs can converge to a random guess as test graphs get larger. We then propose a theoretically-sound gMPNN that outputs structural pairwise (2-node) embeddings and prove non-asymptotic bounds showing that, as test graphs grow, these embeddings converge to embeddings of a continuous function that retains its ability to predict links OOD. Empirical results on random graphs show agreement with our theoretical results.