PaperlayerView exact revision on arXiv

Source-linked AI summary

Handling Distribution Shifts on Graphs: An Invariance Perspective

Qitian Wu, Hengrui Zhang, Junchi Yan, David Wipf

arXiv:2202.02466v5cs.LGcs.AI

TL;DR

Graph OOD generalization is under-explored because node interdependence and graph structure complicate node-level prediction. The paper formulates this problem and proposes EERM, which uses adversarial graph editors to create virtual environments from a single graph. It provides theoretical guarantees and consistently improves OOD performance across diverse datasets and GNN backbones.

  • Problem

    Graph OOD generalization lacks clear formulation and evidence despite distribution shifts and the non-IID, structurally informative nature of node-level graph data.

  • Method

    EERM uses adversarially trained graph structure editors to generate virtual environments and optimize GNN risk invariance from a single observed graph.

  • Results

    EERM consistently outperforms standard ERM across diverse graph distribution shifts and distinct GNN backbones.

  • Takeaways & Limitations

    The approach supports OOD extrapolation for node-level graph prediction from a single environment while incorporating graph structure.

  • Takeaways & Limitations

    The theoretical guarantee assumes environment heterogeneity in which p(y|r, e) can change arbitrarily across environments.

Abstract

from arXiv · show

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.

1 INTRODUCTION

OOD generalization is important because neural networks can fail under distribution shifts, while graph settings remain under-explored due to node interdependence and predictive graph structure. The paper formulates graph OOD prediction, proposes EERM, proves guarantees, and evaluates it across diverse shifts.

  • Neural networks can perform unsatisfactorily in new environments, sometimes exploiting undesired shortcuts such as data-source artifacts.
  • Graph OOD generalization is under-explored despite distribution shifts in citation, social, and financial networks.
  • Graph node-level prediction differs because interconnected nodes induce non-IID data generation, while graph structure also informs prediction.
  • The paper formulates graph OOD prediction and develops an invariance-based learning approach for node-level tasks.
  • EERM uses graph structure editors to simulate multiple virtual environments and trains GNNs to minimize a weighted combination of mean and variance risks.
  • The paper theoretically shows that its objective can guarantee a valid OOD solution and control an upper bound on OOD error under mild conditions.
  • Across diverse real-world shifts and five GNN backbones, EERM consistently outperforms standard ERM on OOD data.

2 PROBLEM FORMULATION

The paper reformulates node-level graph OOD prediction around ego-graphs and extends invariance principles to hierarchical, permutation-invariant structural representations. It defines the environment-dependent graph-label process and the assumptions supporting invariant prediction.

  • 2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA: The graph-level formulation represents an input graph with adjacency matrix A, node features X, and node labels Y.
  • 2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA: Graph-label generation is modeled as p(G, Y|e) = p(G|e)p(Y|G, e), where latent environment e impacts the data distribution.
  • 2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA: For node-level tasks, each centered node is represented by an L-hop ego-graph Gv containing local features and adjacency structure.
  • 2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA: The whole graph is fragmented into instances {(Gv, yv)}v∈V, with each node label conditioned on its ego-graph.
  • 2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA: The node-level OOD problem trains on ego-graph-label pairs from one environment and tests on pairs from a new distribution.
  • 2.1 OUT-OF-DISTRIBUTION PROBLEM FOR GRAPH-STRUCTURED DATA: The formulation typically ignores first-step whole-graph sampling because node-level prediction often has only one input graph.
  • 2.2 INVARIANT FEATURES FOR NODE-LEVEL PREDICTION ON GRAPHS: Invariant graph representations must handle hierarchical ego-graph structure and variable-length, permutation-invariant nodes within each layer.
  • 2.2 INVARIANT FEATURES FOR NODE-LEVEL PREDICTION ON GRAPHS: Assumption 1 requires a recursively computed node readout whose label distribution is environment-invariant and sufficient for prediction.

3 METHODOLOGY

The methodology motivates invariant risk learning with a toy example, then constructs EERM to explore virtual environments from a single graph. Graph editors maximize risk variance while the predictor minimizes mean and variance risk.

  • 3.1 MOTIVATING EXAMPLE: The motivating example uses one-layer graph convolution, identity mappings, mean pooling, and two-dimensional node features.
  • 3.1 MOTIVATING EXAMPLE: In the citation-network example, publication avenue is invariant for predicting paper sub-area, whereas citation index is a spurious feature affected by label and environment.
  • 3.1 MOTIVATING EXAMPLE: The ideal predictor selects the invariant feature with parameters [θ1, θ2] = [1, 0], making predictions insensitive to environment changes.
  • 3.1 MOTIVATING EXAMPLE: Standard ERM instead has a unique optimum that relies on spurious correlation under environment-dependent noise.
  • 3.1 MOTIVATING EXAMPLE: Minimizing risk variance across environments reaches the desirable invariant solution in the motivating example.
  • 3.2 STABLE LEARNING WITH EXPLORE-TO-EXTRAPOLATE RISK MINIMIZATION: Because node-level training often provides one graph and lacks environment correspondences, ordinary multi-environment risk objectives cannot be directly estimated.
  • 3.2 STABLE LEARNING WITH EXPLORE-TO-EXTRAPOLATE RISK MINIMIZATION: EERM introduces K context generators that create graph views mimicking different environments and maximize variance loss to facilitate stable GNN learning.
  • 3.2 STABLE LEARNING WITH EXPLORE-TO-EXTRAPOLATE RISK MINIMIZATION: The graph generators edit edges through Boolean masks and are optimized with REINFORCE because graph editing is non-differentiable and constrained.

4 THEORETICAL DISCUSSIONS

The theoretical analysis connects the proposed objective to graph OOD generalization through environment heterogeneity, invariant representations, and predictive sufficiency. Under these conditions, the objective is shown to guarantee a valid OOD solution and control OOD error through training-error minimization.

  • Theoretical setup: The analysis decomposes each GNN into an encoder h and classifier c, with z=h(Gv) serving as the learned representation.Predictions are formed as ŷv=c(zv).
  • Theoretical setup: Environment heterogeneity separates input features into domain-invariant information and prediction-sensitive information that can change across environments.This assumption supports analyzing which information the representation should preserve or discard.
  • Invariance and sufficiency: The objective forces z toward invariance, I(y; e|z)=0, while also encouraging sufficiency by maximizing I(y; z).These are the two representation conditions used in the theoretical guarantee.
  • OOD guarantee: Under the stated assumptions, the predictor based on Ey[y|z] is a solution to the formulated graph OOD problem.The result directly links invariant and sufficient representations to valid prediction on new environments.
  • OOD guarantee: The objective guarantees a valid OOD solution, while minimizing training error can effectively control an upper bound on OOD error.Training and OOD errors are measured with KL divergences under the training and testing environment distributions.
  • OOD guarantee: The resulting condition is attainable when z is a sufficient cross-environment representation, reducing OOD generalization error and enhancing GNN extrapolation.This conclusion concerns in-the-wild extrapolation to out-of-distribution data.

5 EXPERIMENTS

Experiments evaluate EERM against ERM across artificial feature shifts, unseen domains, and temporal graph evolution using diverse datasets and GNN backbones. EERM consistently improves OOD performance, while extreme emerging events still limit both methods.

  • Experimental setup: Experiments cover artificial spurious-feature shifts, cross-domain transfers, and temporal graph evolution across diverse node-level datasets.The evaluation compares EERM with standard ERM under domain-level and time-aware settings.
  • Artificial distribution shifts: EERM consistently outperforms ERM on Cora and Amazon-Photo under artificial distribution shifts.Experiments use 10-fold graph data, with one fold each for training and validation and eight for testing.
  • Artificial distribution shifts: Removing spurious features causes a larger accuracy drop for ERM than EERM, indicating stronger reliance on spurious features under standard training.The comparison uses the epoch with highest validation accuracy and evaluates inference with all versus non-spurious features.
  • Temporal graph evolution: On Elliptic, EERM improves average F1 by 9.6% with GraphSAGE and 10.0% with GPRGNN across chronological test folds.Both methods degrade after the dark-market shutdown, but ERM suffers more.
  • Temporal graph evolution: On temporally split OGB-Arxiv, EERM outperforms ERM in five of six cases, with up to 8.1% relative improvement using GPRGNN.The evaluation uses an inductive setting in which test nodes are strictly unseen during training.

6 DISCUSSIONS WITH EXISTING WORKS

The paper distinguishes its graph-focused OOD setting from prior work on generalization, invariant learning, and graph structure modification. Its key difference is enabling node-level OOD extrapolation from a single observed environment.

  • Prior graph generalization bounds mainly address in-distribution performance, whereas this work focuses on distribution shifts and OOD data.
  • Node-level tasks involve non-IID node generation through graph interconnections, unlike graph-level tasks that treat graphs as IID prediction instances.

7 CONCLUSION

The paper concludes that its graph-specific formulation and EERM approach address node-level OOD generalization from a single environment. It combines theoretical guarantees with experiments spanning multiple graph shifts and GNN backbones.

  • 7 CONCLUSION: The work formulates node-level OOD generalization on graphs and develops an invariance-based approach for extrapolation from a single environment.
  • 7 CONCLUSION: The training algorithm alternates graph-editer updates based on risk variance and GNN updates using a variance-plus-mean objective, producing trained parameters θ∗.
  • 7 CONCLUSION: EERM differs from existing risk-extrapolation methods by generating virtual environments adversarially instead of requiring multiple observed environments.
  • 7 CONCLUSION: Graph structure modification is related work, but this paper uses graph editers as adversarial context generators within an invariant-learning objective.
  • 7 CONCLUSION: The approach is evaluated across artificial spurious features, cross-domain transfers, and dynamic graph evolution using GCN, GAT, GraphSAGE, GCNII, and GPRGNN.

C.1 PROOF FOR PROPOSITION 1

The proposition proof analyzes first-order conditions for the objective under environment variation. It concludes that only the invariant parameter solution satisfies the required condition for arbitrary environment distributions.

  • C.1 PROOF FOR PROPOSITION 1: The proof derives the risk under a specific environment and differentiates the empirical objective with respect to model parameters.
  • C.1 PROOF FOR PROPOSITION 1: The stationary condition yields θ1 + θ2 = 1 before substitution into the second-order objective derivative.
  • C.1 PROOF FOR PROPOSITION 1: The resulting derivative depends on the environment unless the parameters equal [θ1, θ2] = [1, 0].

D.1 PROOF FOR THEOREM 1

The theoretical analysis links the objective’s expectation and variance terms to sufficiency, invariance, and an upper bound on OOD error. The experiments examine these claims across synthetic and real-world graph settings.

  • D.1 PROOF FOR THEOREM 1: The proof characterizes invariance as I(y; e|r) = 0 and sufficiency as maximizing I(y; r).
  • D.1 PROOF FOR THEOREM 1: The expectation term is shown to reduce an upper bound on I(y, Gv|z) while encouraging predictive information between labels and representations.
  • D.1 PROOF FOR THEOREM 1: The variance term is shown to help minimize I(y; e|z), linking risk consistency across environments to representation invariance.
  • D.1 PROOF FOR THEOREM 1: Reducing OOD error requires controlling representation error, latent predictive error, and the environment-dependent information I(y; e|z).
  • D.1 PROOF FOR THEOREM 1: Theorem 3 states that optimizing the objective can reduce an upper bound on OOD error when the conditional information term is equal across training and test environments.
  • D.1 PROOF FOR THEOREM 1: Synthetic experiments use X1 as invariant features and X2 as environment-conditioned features to test whether the model reduces reliance on domain-variant information.

E.2 CROSS-DOMAIN TRANSFERS ON MULTI-GRAPH DATA

The section evaluates cross-domain transfer across multiple graphs, where domain shifts arise from differing collection settings and graph structures. Experiments use Twitch-Explicit and Facebook-100 under graph-level transfer protocols.

  • Cross-domain graph shifts can reflect when or where networks are collected, or distinct biological species in protein-interaction data.
  • Twitch-Explicit contains seven regional friendship networks with similar sizes but different densities and maximum node degrees.
  • On Twitch-Explicit, OOD transfer trains on DE and tests on ENGB, whereas IID evaluation holds out nodes within DE.
  • Twitch-Explicit shows a clear performance drop from IID to OOD evaluation, indicating distribution shifts between input graphs.
  • Facebook-100 uses fourteen university friendship networks with substantially diverse sizes, densities, and degree distributions for training, validation, and testing.

E.3 TEMPORAL EVOLUTION ON DYNAMIC GRAPH DATA

The temporal experiments study evolving graph snapshots and future-node prediction under changing data distributions. Elliptic and OGB-Arxiv provide complementary transaction and citation-network settings with chronological shifts.

  • Temporal graph evolution can involve sequences of snapshots with changing node sets and data distributions, such as financial transaction networks.
  • Elliptic contains 49 Bitcoin-transaction snapshots, using snapshots 7th-11th, 12th-17th, and 17th-49th for training, validation, and testing.
  • Elliptic groups 33 testing snapshots chronologically because positive-label rates are low and differ across training, validation, and testing sets.
  • OGB-Arxiv contains 169,343 papers across 40 subject areas, with the task of predicting each paper’s subject area.
  • As the time gap from training and validation increases, more OGB-Arxiv test nodes become non-overlapping in the T-SNE visualization, indicating larger shifts and harder extrapolation.

F IMPLEMENTATION DETAILS

The implementation uses several GNN backbones, graph-editing explorers, validation-based model selection, and dataset-specific hyperparameters. Architectures and optimization settings are specified for reproducibility.

  • Experiments use GraphSAGE, GCN, GAT, GCNII, and GPRGNN as GNN backbones.
  • GAT uses L-layer attention convolutions with H heads, self-loops, batch normalization, and ELU activation.
  • GCN and GraphSAGE use L-layer convolutions with self-loops, batch normalization, and ReLU activation.
  • The hyperparameter search varies the backbone and graph-editer learning rates, combination weight β, edits per node s, and inner-update iterations.
  • Dataset-specific settings include 2-layer GCN with hidden size 32, while GCNII uses 10 layers and GraphSAGE and GPRGNN use 5 layers.
  • For each method, the reported test result comes from the epoch with the best validation performance.

G MORE EXPERIMENT RESULTS

Additional experiments examine test-accuracy distributions and spurious-feature removal on Cora and Photo under SGC- and GAT-generated shifts. The reported patterns are consistent with the main experiments.

  • Figures 10 and 11 show Cora test-accuracy distributions under artificial shifts generated by SGC and GAT.
  • Figures 12 and 13 compare Cora training accuracy using all features versus removing spurious features for inference.
  • Figures 14 and 15 show Photo test-accuracy distributions under artificial shifts generated by SGC and GAT.
  • Figures 16 and 17 compare Photo training accuracy using all features versus removing spurious features for inference.
  • The additional Cora and Photo results are consistent with Section 5.1 and further verify the effectiveness of the approach.
Loading 2202.02466v5…