# Handling Distribution Shifts on Graphs: An Invariance Perspective

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

## Key facts

- Cited by 164 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 71 references that are in the map.
- First posted on arXiv 5 Feb 2022.

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

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Do ImageNet Classifiers Generalize to ImageNet?](https://mlsanity.com/paper/1902.10811/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Out-of-Distribution Generalization via Risk Extrapolation (REx)](https://mlsanity.com/paper/2003.00688/) (2020)
- [Recognition in Terra Incognita](https://mlsanity.com/paper/1807.04975/) (2018)
- [Domain Generalization via Invariant Feature Representation](https://mlsanity.com/paper/1301.2115/) (2013)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Causal inference using invariant prediction: identification and confidence intervals](https://mlsanity.com/paper/1501.01332/) (2015)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Environment Inference for Invariant Learning](https://mlsanity.com/paper/2010.07249/) (2020)
- [The Risks of Invariant Risk Minimization](https://mlsanity.com/paper/2010.05761/) (2020)
- [Domain Generalization using Causal Matching](https://mlsanity.com/paper/2006.07500/) (2020)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Invariant Risk Minimization Games](https://mlsanity.com/paper/2002.04692/) (2020)
- [Understanding the Failure Modes of Out-of-Distribution Generalization](https://mlsanity.com/paper/2010.15775/) (2020)

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

- [Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs](https://mlsanity.com/paper/2202.05441/) (2022)
- [GOOD: A Graph Out-of-Distribution Benchmark](https://mlsanity.com/paper/2206.08452/) (2022)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [Debiasing Graph Neural Networks via Learning Disentangled Causal Substructure](https://mlsanity.com/paper/2209.14107/) (2022)
- [OpenGraph: Towards Open Graph Foundation Models](https://mlsanity.com/paper/2403.01121/) (2024)
- [Energy-based Out-of-Distribution Detection for Graph Neural Networks](https://mlsanity.com/paper/2302.02914/) (2023)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Structural Re-weighting Improves Graph Domain Adaptation](https://mlsanity.com/paper/2306.03221/) (2023)
- [Does Invariant Graph Learning via Environment Augmentation Learn Invariance?](https://mlsanity.com/paper/2310.19035/) (2023)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs](https://mlsanity.com/paper/2205.15117/) (2022)
- [Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift](https://mlsanity.com/paper/2211.02843/) (2022)
- [Mind the Label Shift of Augmentation-based Graph OOD Generalization](https://mlsanity.com/paper/2303.14859/) (2023)
- [GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation](https://mlsanity.com/paper/2310.00800/) (2023)
- [Graph Out-of-Distribution Generalization via Causal Intervention](https://mlsanity.com/paper/2402.11494/) (2024)
- [Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization](https://mlsanity.com/paper/2306.01103/) (2023)
- [Environment-Aware Dynamic Graph Learning for Out-of-Distribution Generalization](https://mlsanity.com/paper/2311.11114/) (2023)
- [Pairwise Alignment Improves Graph Domain Adaptation](https://mlsanity.com/paper/2403.01092/) (2024)
- [Geometric Knowledge Distillation: Topology Compression for Graph Neural Networks](https://mlsanity.com/paper/2210.13014/) (2022)
- [Graph Domain Adaptation with Dual-branch Encoder and Two-level Alignment for Whole Slide Image-based Survival Prediction](https://mlsanity.com/paper/2411.14001/) (2024)
- [GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts](https://mlsanity.com/paper/2312.04693/) (2023)
- [Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts](https://mlsanity.com/paper/2403.05026/) (2024)
- [Graph Learning under Distribution Shifts: A Comprehensive Survey on Domain Adaptation, Out-of-distribution, and Continual Learning](https://mlsanity.com/paper/2402.16374/) (2024)
- [GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels](https://mlsanity.com/paper/2310.14586/) (2023)
- [Subgraph Pooling: Tackling Negative Transfer on Graphs](https://mlsanity.com/paper/2402.08907/) (2024)

## Abstract (arXiv)

There is increasing evidence suggesting neural networks' sensitivity to distribution shifts, so that research on out-of-distribution (OOD) generalization comes into the spotlight. Nonetheless, current endeavors mostly focus on Euclidean data, and its formulation for graph-structured data is not clear and remains under-explored, given two-fold fundamental challenges: 1) the inter-connection among nodes in one graph, which induces non-IID generation of data points even under the same environment, and 2) the structural information in the input graph, which is also informative for prediction. In this paper, we formulate the OOD problem on graphs and develop a new invariant learning approach, Explore-to-Extrapolate Risk Minimization (EERM), that facilitates graph neural networks to leverage invariance principles for prediction. EERM resorts to multiple context explorers (specified as graph structure editers in our case) that are adversarially trained to maximize the variance of risks from multiple virtual environments. Such a design enables the model to extrapolate from a single observed environment which is the common case for node-level prediction. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution and further demonstrate its power on various real-world datasets for handling distribution shifts from artificial spurious features, cross-domain transfers and dynamic graph evolution.