mlsanityData to 14 Oct 2026

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

arXiv 2205.15117 ↗First posted 30 May 2022cs.LG cs.AI cs.NAcited by 38

Not on the map. Why?

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.

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

50 of 97 references.

References · 50

  1. 2017Attention Is All You Needcited by 60,361
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  4. 2017Graph Attention Networkscited by 8,923
  5. 2017Inductive Representation Learning on Large Graphscited by 6,320
  6. 2018How Powerful are Graph Neural Networks?cited by 4,393
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  9. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  10. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  11. 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
  12. 2014DeepWalk: Online Learning of Social Representationscited by 1,547
38 more
  1. 2016Variational Graph Auto-Encoderscited by 1,382
  2. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  3. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  4. 2016Complex Embeddings for Simple Link Predictioncited by 902
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  6. 2018Link Prediction Based on Graph Neural Networkscited by 832
  7. 2017Convolutional 2D Knowledge Graph Embeddingscited by 730
  8. 2020A Generalization of Transformer Networks to Graphscited by 661
  9. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  10. 2019Provably Powerful Graph Networkscited by 389
  11. 2017A simple neural network module for relational reasoningcited by 346
  12. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  13. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 275
  14. 2015A Review of Relational Machine Learning for Knowledge Graphscited by 265
  15. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  16. 2019Position-aware Graph Neural Networkscited by 203
  17. 2021Identity-aware Graph Neural Networkscited by 198
  18. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 193
  19. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 188
  20. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  21. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 164
  22. 2019Relational Pooling for Graph Representationscited by 150
  23. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 149
  24. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 124
  25. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  26. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 118
  27. 2018Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputscited by 98
  28. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  29. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 92
  30. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 84
  31. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 80
  32. 2021Counterfactual Invariance to Spurious Correlations: Why and How to Pass Stress Testscited by 77
  33. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
  34. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  35. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 53
  36. 2013Stochastic blockmodel approximation of a graphon: Theory and consistent estimationcited by 39
  37. 2018Dual-Primal Graph Convolutional Networkscited by 18
  38. 2021Neural Networks for Learning Counterfactual G-Invariances from Single Environmentscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 12; 2024: 13; 2025: 6; 2026: 3.

38 papers.

Sort:

By area:

  1. 2022GOOD: A Graph Out-of-Distribution Benchmarkcited by 141
  2. 2023Towards Foundation Models for Knowledge Graph Reasoningcited by 86
  3. 2023Attending to Graph Transformerscited by 83
  4. 2024A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challengescited by 54
  5. 2023Deciphering Spatio-Temporal Graph Forecasting: A Causal Lens and Treatmentcited by 47
  6. 2023Does Invariant Graph Learning via Environment Augmentation Learn Invariance?cited by 42
  7. 2023Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databasescited by 35
  8. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 31
  9. 2023Revisiting Link Prediction: A Data Perspectivecited by 29
  10. 2022Inductive Logical Query Answering in Knowledge Graphscited by 26
  11. 2023GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Expertscited by 19
  12. 2024A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptationcited by 17
26 more
  1. 2025GOLD: Graph Out-of-Distribution Detection via Implicit Adversarial Latent Generationcited by 15
  2. 2024Investigating Out-of-Distribution Generalization of GNNs: An Architecture Perspectivecited by 13
  3. 2024How Interpretable Are Interpretable Graph Neural Networks?cited by 13
  4. 2022FakeEdge: Alleviate Dataset Shift in Link Predictioncited by 12
  5. 2025Graph Data Selection for Domain Adaptation: A Model-Free Approachcited by 7
  6. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
  7. 2023Causal Lifting and Link Predictioncited by 5
  8. 2022Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networkscited by 4
  9. 2023Tackling Size Generalization of Graph Neural Networks on Biological Data from a Spectral Perspectivecited by 3
  10. 2024Topology-Aware Dynamic Reweighting for Distribution Shifts on Graphcited by 3
  11. 2024Link Prediction with Untrained Message Passing Layerscited by 3
  12. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  13. 2024A Survey of Out-of-distribution Generalization for Graph Machine Learning from a Causal Viewcited by 3
  14. 2025Causal invariant geographic network representations with feature and structural distribution shiftscited by 3
  15. 2023Addressing the Impact of Localized Training Data in Graph Neural Networkscited by 2
  16. 2023Beyond Transduction: A Survey on Inductive, Few Shot, and Zero Shot Link Prediction in Knowledge Graphscited by 2
  17. 2024PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learningcited by 2
  18. 2024LinkThief: Combining Generalized Structure Knowledge with Node Similarity for Link Stealing Attack against GNNcited by 2
  19. 2025Evolving Graph Learning for Out-of-Distribution Generalization in Non-stationary Environmentscited by 2
  20. 2024SSHPool: The Separated Subgraph-based Hierarchical Poolingcited by 1
  21. 2025Transfer Learning on Edge Connecting Probability Estimation under Graphon Modelcited by 1
  22. 2026What Information Matters? Graph Out-of-Distribution Detection via Tri-Component Information Decompositioncited by 1
  23. 2024Towards Understanding Link Predictor Generalizability Under Distribution Shiftscited by 0
  24. 2025Subgraph Generation for Generalizing on Out-of-Distribution Linkscited by 0
  25. 2026Graph Hierarchical Recurrence for Long-Range Generalizationcited by 0
  26. 2026Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networkscited by 0