Generalizing Graph Neural Networks on Out-Of-Distribution Graphs

Shaohua Fan, Xiao Wang, Chuan Shi, Peng Cui, Bai Wang

TL;DR

Graph Neural Networks (GNNs) often fail when encountering data distributions different from their training data due to relying on spurious correlations. This paper introduces StableGNN, a framework that uses causal inference to extract robust, high-level graph representations, enabling GNNs to generalize better to out-of-distribution graphs by focusing on true causal relationships rather than spurious ones.

What Problem Does This Paper Address?

Modern machine learning models, including Graph Neural Networks (GNNs), typically assume that training and testing data are drawn from the same distribution (the I.I.D. hypothesis). However, in real-world applications, this assumption often breaks, leading to a significant drop in performance when models encounter "out-of-distribution" (OOD) data. For GNNs, this problem is exacerbated because they tend to learn spurious correlations between graph substructures (like motifs) and their labels, which might not hold true in different environments. For instance, a GNN trained to identify "house" motifs might incorrectly associate a "star" motif with the "house" label if they frequently co-occur in the training data, leading to misclassifications when the "star" motif is absent or paired with different structures in the test set. The core challenge is to make GNNs robust to these distribution shifts by identifying and leveraging true causal relationships rather than superficial, spurious correlations.

Methods

The proposed solution, StableGNN, tackles this problem in two main stages:

  1. Graph High-level Variable Learning: This component aims to extract meaningful, high-level representations of subgraphs. It employs a differentiable graph pooling layer (specifically, inspired by DiffPool) to group nodes into clusters, where each cluster represents a densely connected subgraph. These cluster-level embeddings are then aggregated and aligned across graphs using an ordered concatenation operation. This process creates "high-level variables" that capture structural information at a coarser granularity. The paper theoretically proves that this pooling mechanism, when combined with ordered concatenation, aligns the semantic meaning of these high-level representations across different graphs.
  2. Causal Variable Distinguishing Regularizer (CVD): Once high-level representations are obtained, this stage focuses on disentangling causal relationships from spurious correlations. Inspired by causal inference techniques like confounder balancing, the CVD regularizer learns a set of sample weights. These weights are optimized to minimize the dependence (measured by Hilbert-Schmidt Independence Criterion - HSIC) between a chosen "treatment" high-level variable and other "confounding" high-level variables. By learning these weights, the training process is effectively guided to focus on the true causal effect of subgraph representations on the graph label, rather than being misled by spurious correlations. The framework can learn these weights globally to decorrelate all high-level representations simultaneously. Finally, a weighted GNN loss is used to train the model, allowing it to learn from a less biased pseudo-distribution.

Datasets

The paper evaluates StableGNN on two types of datasets:

  • Synthetic Datasets: These were generated with controllable degrees of spurious correlation to specifically test the model's ability to handle distribution shifts. The generation process involves creating graphs with a "house" motif as the causal feature for positive labels, and then introducing a "star" motif with varying degrees of co-occurrence to create spurious correlations.
  • Real-world Datasets: Eight datasets were used, primarily from the OGB (Open Graph Benchmark) Datasets, focusing on molecular property prediction. These datasets include binary classification, multi-label classification, and regression tasks. The paper notes that these datasets often employ "scaffold splitting" to create environments with different graph distributions, making them suitable for OOD generalization evaluation. The MUTAG dataset was also used for interpretability analysis.

Key Insights and Ideas

  • Spurious Correlations are Subgraph-Level: The paper posits that the root cause of GNN degeneration in OOD settings lies in spurious correlations at the subgraph level, not just individual node features.
  • Causal Inference for Robustness: Applying principles from causal inference, particularly confounder balancing and invariant risk minimization, is crucial for building GNNs that generalize.
  • Hierarchical Representations are Key: Extracting meaningful high-level representations of subgraphs is a necessary precursor to disentangling causal effects. The proposed differentiable pooling mechanism effectively achieves this.
  • Sample Reweighting for Bias Correction: Learning sample weights to down-weight or up-weight specific training examples is a powerful mechanism to correct for biased training distributions and mitigate spurious correlations.
  • Generalizability of the Framework: StableGNN is designed as a flexible framework that can be applied on top of various existing GNN architectures (like GCN and GraphSAGE), demonstrating its broad applicability.

Key Results

  • Significant Performance Gains: StableGNN consistently outperformed state-of-the-art GNN models on both synthetic and real-world OOD datasets. For instance, on synthetic data with high spurious correlation degrees, StableGNN achieved up to 19.64% performance improvement in F1 score compared to baseline GCN.
  • Robustness to Distribution Shifts: The model showed substantial improvements as the degree of distribution shift increased, highlighting its effectiveness in challenging OOD scenarios.
  • Effective Decorrelation: Ablation studies and comparisons with other decorrelation methods demonstrated that StableGNN's approach of decorrelating high-level subgraph representations is more effective than decorrelating individual dimensions or using simpler pooling strategies.
  • Interpretability: Explanation analyses (using GNNExplainer) showed that StableGNN correctly identifies and focuses on the true causal subgraphs (e.g., specific chemical groups responsible for mutagenicity) while baseline GNNs were misled by spurious correlations.

Limitations and Future Work

  • Assumed Causal Graph Structure: The framework assumes a general causal graph structure for data generation. For datasets with more complex causal relationships among high-level variables, discovering this structure might be beneficial for further improving generalization.
  • Future Directions: The authors suggest extending the framework to learn the causal substructures of proteins and applying the causal representation learning idea to other domains like object recognition, multi-modal data fusion, and autonomous driving. They also note that while the framework learns appropriate cluster numbers end-to-end, some clusters might not be used, implying potential for further optimization in cluster selection.

Summary updated

Abstract

Graph Neural Networks (GNNs) are proposed without considering the agnostic distribution shifts between training and testing graphs, inducing the degeneration of the generalization ability of GNNs on Out-Of-Distribution (OOD) settings. The fundamental reason for such degeneration is that most GNNs are developed based on the I.I.D hypothesis. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. However, such spurious correlations may change in testing environments, leading to the failure of GNNs. Therefore, eliminating the impact of spurious correlations is crucial for stable GNNs. To this end, we propose a general causal representation framework, called StableGNN. The main idea is to extract high-level representations from graph data first and resort to the distinguishing ability of causal inference to help the model get rid of spurious correlations. Particularly, we exploit a graph pooling layer to extract subgraph-based representations as high-level representations. Furthermore, we propose a causal variable distinguishing regularizer to correct the biased training distribution. Hence, GNNs would concentrate more on the stable correlations. Extensive experiments on both synthetic and real-world OOD graph datasets well verify the effectiveness, flexibility and interpretability of the proposed framework.
BibTeX
@article{fan2021generalizing,
  author = {Shaohua Fan and Xiao Wang and Chuan Shi and Peng Cui and Bai Wang},
  title = {{Generalizing Graph Neural Networks on Out-Of-Distribution Graphs}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2021},
  url = {https://openreview.net/forum?id=L31xWuK839},
}
Figure