Source-linked AI summary
Out-Of-Distribution Generalization on Graphs: A Survey
Haoyang Li, Xin Wang, Ziwei Zhang, Wenwu Zhu
TL;DR
Graph OOD generalization addresses the mismatch between training and testing graph distributions that undermines the in-distribution assumption. This survey formalizes the problem, organizes methods by data, model, and learning strategy, and synthesizes theories, datasets, and future directions. It concludes that these method families show promising empirical performance, while theoretical guarantees and broader deployment remain open challenges.
Problem
Graph learning usually assumes identical training and testing distributions, although real-world graph data can exhibit distribution shifts that degrade model performance.
Method
The survey formalizes graph OOD generalization, categorizes methods into data, model, and learning-strategy branches, and reviews theories, datasets, and future directions.
Results
Data augmentation, disentanglement and causality models, and learning strategies show promising OOD generalization performance, with learning-strategy methods offering backbone compatibility.
Takeaways & Limitations
Graph OOD generalization provides a framework for studying graph models intended for unseen data under distribution shifts across multiple methodological perspectives.
Takeaways & Limitations
A substantial gap remains between empirical graph OOD methods and existing theories, including the need for learnable problems with theoretical guarantees and assumptions tailored to shift types.
Abstract
from arXiv · showhide
Graph machine learning has been extensively studied in both academia and industry. Although booming with a vast number of emerging methods and techniques, most of the literature is built on the in-distribution hypothesis, i.e., testing and training graph data are identically distributed. However, this in-distribution hypothesis can hardly be satisfied in many real-world graph scenarios where the model performance substantially degrades when there exist distribution shifts between testing and training graph data. To solve this critical problem, out-of-distribution (OOD) generalization on graphs, which goes beyond the in-distribution hypothesis, has made great progress and attracted ever-increasing attention from the research community. In this paper, we comprehensively survey OOD generalization on graphs and present a detailed review of recent advances in this area. First, we provide a formal problem definition of OOD generalization on graphs. Second, we categorize existing methods into three classes from conceptually different perspectives, i.e., data, model, and learning strategy, based on their positions in the graph machine learning pipeline, followed by detailed discussions for each category. We also review the theories related to OOD generalization on graphs and introduce the commonly used graph datasets for thorough evaluations. Finally, we share our insights on future research directions. This paper is the first systematic and comprehensive review of OOD generalization on graphs, to the best of our knowledge.
1 INTRODUCTION
Graph OOD generalization addresses the failure of in-distribution graph learning when training and testing distributions differ. This survey organizes the problem, reviews existing approaches, and identifies future research directions.
- Motivation: Graph learning commonly assumes identical training and testing distributions, but real-world graph data inevitably exhibit distribution shifts.Such shifts matter in applications including molecule prediction, finance, criminal justice, autonomous driving, and healthcare.
- Challenges: Graph distribution shifts can affect node features, graph size, and other structural properties, creating challenges beyond standard Euclidean OOD methods.Graph-specific methods must address non-Euclidean data and diverse node-, link-, and graph-level tasks.
- Survey scope: The survey provides a formal problem definition and categorizes graph OOD methods by data, model, and learning-strategy positions in the pipeline.It also reviews theories, evaluation datasets, and future research opportunities.
- Prior surveys: Existing surveys address graph augmentation, self-supervised learning, or adversarial learning, but none comprehensively review graph OOD generalization methods.The survey frames these areas as pieces of the broader graph OOD generalization problem.
2 PROBLEM DEFINITION AND CATEGORIZATION
Graph OOD generalization seeks a predictor that performs optimally on an unknown test distribution differing from the training distribution. The survey categorizes solutions into data, model, and learning-strategy methods.
- Problem definition: Graph OOD generalization learns a predictor for test data drawn from Ptest(X, Y) ≠ Ptrain(X, Y), using node-, link-, or graph-level inputs.The objective is defined through a loss measuring prediction distance from ground-truth labels.
- Problem definition: Minimizing average training loss under the in-distribution hypothesis may fail to produce a predictor that generalizes under distribution shifts, with the test distribution unknown during training.This motivates methods that target OOD performance rather than training-distribution fit alone.
- Categorization: Data methods manipulate input graphs through augmentation to increase the quantity and diversity of training samples.They include structure-wise, feature-wise, and mixed-type augmentation strategies.
- Categorization: Model methods design graph models for OOD-generalized representations, especially through disentanglement-based and causality-based approaches.These methods introduce graph-specific representational properties intended to support generalization.
- Categorization: Learning-strategy methods tailor optimization objectives and constraints through invariant learning, adversarial training, and self-supervised learning.The taxonomy distinguishes these methods from changes to input data or model architecture.
3 DATA
Graph data augmentation improves OOD generalization by expanding training diversity through structure-wise, feature-wise, mixed-type, and environment-oriented transformations.
- Overview: Graph augmentation generates additional training instances, with literature commonly divided into structure-wise, feature-wise, and mixed-type strategies.The goal is to improve generalization by increasing training-data diversity.
- Structure-wise and feature-wise augmentation: Structure-wise methods modify graph topology, while feature-wise methods perturb node attributes to expose models to diverse graph inputs.Examples include edge prediction or sampling for topology and feature dropping or adversarial perturbations for attributes.
- Mixed-type augmentation: Mixed-type methods combine graph transformations such as node dropping, edge perturbation, attribute masking, and subgraph sampling.These operations jointly vary topology and node attributes.
- Environment-based augmentation: GREA replaces environment subgraphs while preserving graph labels to improve rationale identification for OOD generalization.Its latent-space procedure separates predictive rationales from environment information.
- Environment and Mixup methods: Other methods generate augmented domains, address covariate shift, or mix graph data and graphons to create diverse training examples.DPS learns consistent semantics across augmented domains, AdvCA targets covariate shift, and G-Mixup interpolates graphons before sampling graphs.
4 MODEL
Model-based graph OOD methods design representations that separate stable information from nuisance variation. The survey reviews disentanglement and causality approaches, including supervised and unsupervised models.
- Overview: Model-based methods introduce graph-specific architectural priors to produce representations with properties that support OOD generalization.The survey focuses on disentanglement-based and causality-based graph models.
- Disentanglement-based graph models: Disentanglement methods separate latent graph factors into distinct representation components, often using multichannel message passing or factorized graph encoders.DisenGCN routes neighboring information into factor-specific channels, while FactorGCN decomposes graphs into interpretable factor graphs.
- Causality-based graph models: DisC disentangles causal and bias subgraphs, trains separate representations, and uses causal information to support stable predictions under severe bias.It also permutes latent representations across graphs to generate additional training samples.
- Disentanglement-based graph models: Several methods explicitly promote independence among disentangled representations using dependence penalties such as HSIC.IPGDN and IDGCL extend disentanglement by reducing dependence between representations associated with different latent factors.
- Causality-based graph models: Causal graph models target spurious correlations that may change across testing environments and degrade OOD performance.OOD-GNN removes dependence between causal and noncausal representations, while StableGNN learns decorrelated subgraph representations through pooling and reweighting.
5 LEARNING STRATEGY
Learning-strategy methods address graph OOD generalization through invariance optimization, representation alignment, adversarial training, self-supervision, and distribution-aware regularization across graph tasks and shift types.
- Learning-strategy methods include graph invariant learning, graph adversarial training, and graph self-supervised learning, alongside graph data augmentation and graph models.
- Invariance Optimization: Invariant learning seeks feature–label relationships that remain stable across environments while disregarding variant spurious correlations.The invariance assumption requires a portion of input information to yield the same conditional label distribution across environments.
- Invariance Optimization: These methods commonly require multiple environments, which may be supplied explicitly or generated during training.Their objectives optimize risks or regularizers across environment splits, with |E| > 1.
- Invariance Optimization: GIL, DIR, and GSAT learn invariant graph substructures, while GIL additionally infers latent environments when environment labels are unavailable.GIL jointly optimizes invariant subgraph identification, environment inference, and invariant learning modules.
- Invariance Optimization: EERM adapts invariance optimization to node-level tasks by representing nodes as ego-graphs and optimizing mean and variance of risks across generated environments.Its environment generators maximize variance loss through policy-gradient training.
- Representation Alignment: Representation-alignment methods reduce cross-environment differences through regularization, while SR-GNN and SizeShiftReg target distributional or graph-size shifts.SizeShiftReg simulates size shifts through graph coarsening and seeks generalization from smaller to larger graphs.
6 THEORY
Theory work analyzes GNN generalization through VC-dimension, stability, Rademacher complexity, PAC-Bayes, kernels, and data-generating mechanisms, with bounds tailored to graph structure and tasks.
- Theoretical analyses mainly derive GNN generalization bounds using statistical learning theories.
- VC-dimension and stability analyses relate GNN generalization to connected-node counts and provide theoretical analyses for graph convolutional networks.
- Rademacher-complexity analyses account for local permutation invariance and specialize bounds to graph classification or node-level GCN tasks.
- PAC-Bayesian analyses tighten dependencies on maximum node degree and hidden dimension and extend to non-IID node-level subgroups.
- GNTK characterizes graph-classification generalization through pairwise graph kernels induced by infinitely wide GNNs.The kernel has an analytic formula and combines GNN expressive power with graph-kernel theoretical guarantees.
- More recent analyses make bounds depend on graph data-generation mechanisms, including contextual stochastic block models and graphons.These works study linear separability, one-layer GCN guarantees, and tighter bounds under graphon models.
7 DATASETS FOR EVALUATION
Evaluation datasets span graph-level and node-level tasks across social, citation, molecular, linguistic, synthetic, and transaction graphs, with shifts induced by features, topology, time, domains, species, scaffolds, and graph size.
- The survey groups datasets into graph-level and node-level tasks covering diverse graph sources and distribution-shift causes.Examples include social, citation, and molecular graphs, with shifts based on time, species, and scaffold.
- Graph-level datasets: Spurious-Motif creates structural shifts by combining motifs with base subgraphs whose spurious correlations differ from the motif-dependent ground-truth label.
- Graph-level datasets: MNIST-75sp and CMNIST-75sp use superpixel graphs to evaluate feature, covariate, or concept shifts through image colorization and noise.
- Graph-level datasets: D&D200 evaluates size shifts by training on smaller protein graphs and testing on larger graphs, while Graph-SST2 splits text graphs by average node degree.
- Graph-level datasets: OGBG and DrugOOD provide molecular graph benchmarks with realistic distribution shifts and diverse splitting indicators for graph property prediction and drug discovery.
- Node-level datasets: Node-level benchmarks induce shifts across structural roles, universities, regions, time, and emerging market events in datasets such as CBA-Shapes, Facebook-100, WebKB, Twitch-Explicit, Elliptic, and OGBN.Elliptic uses older transaction snapshots for training and newer snapshots for testing; OGBN-Arxiv splits papers by time ranges.
- Open-source benchmark packages collect multiple datasets and report results for general OOD algorithms and graph OOD methods under standardized protocols.
8 DISCUSSIONS
The survey highlights data, model, and learning-strategy advances in graph OOD generalization, while identifying persistent gaps in theory, architecture design, environment handling, and test-time adaptation.
- 8.1 Summary: Graph data augmentation methods improve OOD generalization through structure-wise, feature-wise, and mixed-type transformations.The survey emphasizes the importance of training-graph diversity and quality.
- 8.1 Summary: Graph models provide graph-specific designs and stronger theoretical grounding, with disentanglement- and causality-based approaches showing promising practical performance.These models target OOD generalization through tailored representations and causal reasoning.
- 8.1 Summary: Graph invariant learning, adversarial training, and self-supervised learning focus on the learning process and flexibly support different GNN backbones.Their backbone compatibility distinguishes these strategies from graph-model approaches.
- 8.1 Summary: Generalization bounds and diverse datasets covering node- and graph-level tasks support deeper understanding and broader evaluation of graph OOD methods.The datasets incorporate complex, realistic distribution shifts for more comprehensive assessment.
- 8.2 Discussions: A major open problem is closing the gap between empirical methods and theories that could provide guarantees for OOD optimality.The survey also calls for theories tied to specific shift types, including covariate, concept, and label shifts.
- 8.2 Discussions: Future work includes theoretically guaranteed architectures, single-environment and dynamic generalization, test-time training, and deployment in real-world applications.These directions address architecture adaptation, costly environment labels, evolving data, and unknown test-time shifts.