Handling Distribution Shifts on Graphs: An Invariance Perspective

Qitian Wu, Hengrui Zhang, Junchi Yan, David Wipf

Deep learning models are notoriously brittle when faced with data that looks different from their training set. While this "out-of-distribution" (OOD) generalization problem has been studied extensively for images and text, graph-structured data presents a unique set of headaches.

In their ICLR 2022 paper, researchers from Shanghai Jiao Tong University, UIC, and Amazon Propose EERM (Explore-to-Extrapolate Risk Minimization), a framework designed to make Graph Neural Networks (GNNs) robust to distribution shifts by leaning into the principle of invariance.

TL;DR

EERM enables GNNs to generalize to unseen distributions by using adversarial "context explorers" to simulate multiple virtual environments from a single training graph. By minimizing the variance of risks across these simulated environments, the model learns to prioritize stable, causal features over spurious correlations.

What Problem Does This Paper Address?

Most machine learning assumes that training and testing data are "IID"—independent and identically distributed. In the real world, this is rarely true. A GNN trained on a citation network from the 1990s might fail on a 2020s network because the "environment" (research trends, citation styles) has shifted.

Graphs are particularly challenging for OOD generalization for two reasons:

  1. Non-IID Nature: Nodes in a graph are interconnected. You can't just shuffle them like images in a dataset; the dependencies matter.
  2. Structural Information: The topology of the graph is itself a feature that can shift, making it hard to define what exactly should remain "invariant."

Existing OOD methods often require multiple training datasets from different known environments to identify stable patterns. However, in graph tasks (like node classification), we often only have one large graph. EERM aims to solve OOD generalization even when you only have a single observed environment.

Methods

The core idea of EERM is to move from Empirical Risk Minimization (ERM)—which just tries to get the lowest average error on the training data—to a strategy that values stability.

Figure 1: (a) The proposed approach Explore-to-Extrapolate Risk Minimization which entails K context generators that generate graph data of different (virtual) environments based on input data from a single (real) environment. The GNN model is updated via gradient descent to minimize a weighted combination of mean and variance of risks from different environments, while the context generators are updated via REINFORCE to maximize the variance loss. (b) Illustration for our Assumption 1. (c) The dependence among variables in the motivating example in Section 3.1.

The framework consists of two main components:

  • Explore (The Adversaries): The system uses $K$ "context generators" (graph structure editors). These generators are trained via reinforcement learning (REINFORCE) to perturb the input graph—adding or deleting edges—to maximize the variance of the GNN's prediction risk. Essentially, they are trying to find "virtual environments" where the current GNN model fails.
  • Extrapolate (The GNN): The GNN model is updated via gradient descent to minimize a weighted combination of the mean risk and the variance of risks across all these virtual environments.

By forcing the GNN to perform well and consistently across many adversarial versions of the graph, the model is discouraged from using "shortcuts" (spurious features) that only work in the original training setup.

Datasets

The authors evaluated EERM across three types of distribution shifts:

  1. Artificial Transformation: Cora and Amazon-Photo, modified with synthetic spurious features to test if the model can ignore them.
  2. Cross-Domain Transfers: Twitch-explicit (social networks from different countries) and Facebook-100 (friendship networks from different universities).
  3. Temporal Evolution: Elliptic (Bitcoin transaction graphs over time) and OGB-Arxiv (citation networks split by year).

Key Insights and Ideas

  • Virtual Environments from a Single Source: The most clever part of EERM is that it doesn't need multiple real-world datasets. It creates its own "stress tests" by adversarially editing the graph structure.
  • Risk Variance as a Proxy for Causal Stability: If a feature is truly causal (e.g., a paper's topic determines its citations), it should be a reliable predictor even if you mess with the graph's local structure. If a feature is spurious, the prediction risk will fluctuate wildly when the structure changes. EERM uses this fluctuation (variance) to guide the model toward stable features.
  • Structural Invariance: The paper formalizes how the "invariance principle" applies to the recursive nature of GNNs, treating ego-graphs as the fundamental unit of data generation.

Key Results

EERM consistently outperformed standard training (ERM) across all backbones (GCN, GAT, GraphSAGE, etc.):

  • Robustness to Spurious Features: On Cora and Amazon-Photo, when spurious features were removed at test time, standard ERM performance plummeted, while EERM remained stable, proving it hadn't relied on those "shortcuts."
  • Real-World Shifts: On the Twitch dataset, EERM improved ROC-AUC by up to 7.0%. On Facebook-100, it saw gains of up to 7.2%.
  • Handling "Black Swan" Events: In the Elliptic Bitcoin dataset, both models suffered during a major market shutdown event (a massive distribution shift), but EERM maintained a significantly higher F1 score (averaging 9.6% to 10.0% improvement) than the baseline.

Limitations and Future Work

  • Generator Complexity: The current context generators only edit edges. Future work could involve more complex generators that also perturb node features or use more sophisticated graph generative models.
  • Hyperparameter Sensitivity: The balance between mean risk and variance ($\beta$) and the number of explorers ($K$) are crucial and may require careful tuning for different datasets.
  • Computational Overhead: Training multiple adversarial generators alongside the GNN is more computationally expensive than standard training, though the authors argue this is a necessary trade-off for robustness in high-stakes applications.

Summary updated

Abstract

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.
BibTeX
@inproceedings{wu2022handling,
  author = {Qitian Wu and Hengrui Zhang and Junchi Yan and David Wipf},
  title = {{Handling Distribution Shifts on Graphs: An Invariance Perspective}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=nTUfzOkYbZS},
}
Figure