Generative Risk Minimization for Out-of-Distribution Generalization on Graphs

Song Wang, Zhen Tan, Yaochen Zhu, Chuxu Zhang, Jundong Li

TL;DR

Graph Neural Networks (GNNs) frequently degrade in performance when deployed on test data that differs from their training distribution. Instead of trying to hard-prune or extract discrete invariant subgraphs to solve this, this paper introduces Generative Risk Minimization (GRM)—a framework that generates continuous invariant subgraphs via a variational approach, achieving state-of-the-art out-of-distribution (OOD) generalization on both node- and graph-level tasks.

What Problem Does This Paper Address?

Standard machine learning paradigms rely on the assumption that training and testing data are independent and identically distributed (i.i.d.). However, real-world graph data—such as evolving citation networks, social networks, or molecular structures—frequently violate this assumption due to temporal changes or cross-domain shifts.

To achieve out-of-distribution (OOD) generalization, recent methods try to identify an "invariant subgraph" that contains the true causal features needed for classification, discarding the domain-specific "spurious" features. The problem is that existing methods do this by extracting a hard, discrete subset of nodes and edges. Because graph components are highly interconnected, a single node or edge often contains a messy mixture of both invariant and spurious information. Hard extraction forces a binary choice, which either discards crucial causal information or inadvertently lets spurious domain noise slip through.

Figure 1: The SCMs with distribution shift (left) and without distribution shifts (right).

Methods

To overcome the limitations of discrete extraction, the authors propose Generative Risk Minimization (GRM). Instead of cutting out pieces of the graph, GRM preserves the original node set but generates continuous edge weights and node representations. This allows the model to flexibly downweight spurious correlations without destroying the underlying graph topology.

Because the true "ground truth" invariant subgraph is unobservable, directly optimizing for it is intractable. The authors solve this by introducing a latent causal variable $Z$ within a Structural Causal Model (SCM) and deriving a tractable Evidence Lower Bound (ELBO).

The architecture is implemented as a Variational Graph Auto-Encoder (VGAE) consisting of an encoder-decoder structure optimized via three distinct losses:

  1. Supervision Loss ($L_s$): Uses the graph's class label as a proxy to ensure the generated continuous subgraph retains maximum predictive power.
  2. Regularization Loss ($L_r$): Applies Kullback-Leibler (KL) divergence to regularize the latent variable $Z$ and models the generated edge weights as independent Bernoulli distributions to prevent overfitting.
  3. Invariance Loss ($L_d$): Minimizes the discrepancy between the latent causal representations and domain-specific representations. Crucially, domain representations are learned from influential one-hop neighbor nodes, ensuring the model strips away domain-dependent noise.
Figure 2: The overall framework of GRM. Each input graph G is processed by the encoder of our generator to learn the latent variable Z. Then we extract the most influential nodes from the domain and learn a domain-specific representation for each node in G. These domain-specific representations will be used in the invariance loss. We further classify the output invariant subgraph with a classifier to obtain the predictions. The regularization loss is calculated for Z and the invariant subgraph.

Datasets

The authors evaluated GRM across ten diverse real-world graph datasets spanning different distribution shift types:

  • Node-Level OOD:
  • Artificial Transformations: Cora and Photo (augmented with synthetic spurious features).
  • Cross-Domain Transfers: Twitch (networks from different geographic regions) and FB-100 (friendship networks from different universities).
  • Temporal Evolution: Elliptic (Bitcoin transaction networks over time) and Arxiv (citation networks split by publication years).
  • Graph-Level OOD: SP-Motif (synthetic), MNIST-75sp (image-to-graph superpixels), G-SST2 (sentiment text graphs), and Molhiv (molecular property prediction).

Key Insights and Ideas

  • Generation Beats Extraction: Moving from discrete structure extraction to continuous generation allows GNNs to smoothly disentangle causal signals from spurious noise within the exact same node or edge representation.
  • Tractable OOD via ELBO: By framing graph OOD generalization as a latent variable problem, the authors successfully map an intractable mutual information objective into an optimizable variational framework.
  • Localized Domain Influence: To capture domain information effectively without overwhelming the model, GRM selectively aggregates domain data from immediate (one-hop) neighborhoods, leveraging the principle that a node's spurious influence decays exponentially with distance.

Key Results

GRM consistently outperformed both general OOD baselines (like ERM, DRNN, MMD, ARM) and state-of-the-art graph-specific OOD methods (EERM, LiSA, IS-GIB, MARIO, DIR, GIL, CIGA, GALA).

  • Node Classification: On the Cora dataset, GRM achieved an average accuracy of 81.2% (compared to ERM's 68.2% and the next-best baseline IS-GIB at 78.6%).
  • Handling Temporal Shifts: On the highly challenging Elliptic dataset, which suffers from severe temporal distribution shifts, GRM achieved a staggering 88.0% F1-score, vastly outperforming the top baseline, MARIO, which only reached 71.2%.
  • Graph Classification: GRM achieved top-tier performance across all graph-level benchmarks, notably hitting an 81.02% ROC-AUC on the large-scale Molhiv molecular dataset.

Limitations and Future Work

While highly effective, the authors note a couple of limitations:

  • Domain Data Dependency: GRM relies on learning domain-specific information from other nodes or graphs within the same domain. If the available data or number of graphs per domain is highly sparse, the model's performance could be impacted.
  • Task Scope: The framework was validated extensively on node-level and graph-level tasks, but its performance on edge-level OOD generalization (e.g., link prediction under distribution shift) has not yet been explored.

Summary updated

Abstract

Out-of-distribution (OOD) generalization on graphs aims at dealing with scenarios where the test graph distribution differs from the training graph distributions. Compared to i.i.d. data like images, the OOD generalization problem on graph-structured data remains challenging due to the non-i.i.d. property and complex structural information on graphs. Recently, several works on graph OOD generalization have explored extracting invariant subgraphs that share crucial classification information across different distributions. Nevertheless, such a strategy could be suboptimal for entirely capturing the invariant information, as the extraction of discrete structures could potentially lead to the loss of invariant information or the involvement of spurious information. In this paper, we propose an innovative framework, named Generative Risk Minimization (GRM), designed to generate an invariant subgraph for each input graph to be classified, instead of extraction. To address the challenge of optimization in the absence of optimal invariant subgraphs (i.e., ground truths), we derive a tractable form of the proposed GRM objective by introducing a latent causal variable, and its effectiveness is validated by our theoretical analysis. We further conduct extensive experiments across a variety of real-world graph datasets for both node-level and graph-level OOD generalization, and the results demonstrate the superiority of our framework GRM.
BibTeX
@article{wang2025generative,
  author = {Song Wang and Zhen Tan and Yaochen Zhu and Chuxu Zhang and Jundong Li},
  title = {{Generative Risk Minimization for Out-of-Distribution Generalization on Graphs}},
  journal = {Trans. Mach. Learn. Res.},
  year = {2025},
}
Figure