Unifying invariant and variant features for graph out-of-distribution via probability of necessity and sufficiency

Xuexin Chen, Ruichu Cai, Kaitao Zheng, Zhifan Jiang, Zhengting Huang, Zhifeng Hao, Zijian Li

TL;DR

This paper introduces SNIGL (Sufficiency and Necessity Inspired Graph Learning), a framework that improves Graph Out-of-Distribution (OOD) generalization by identifying subgraphs that are both "necessary" and "sufficient" causes for a label. Unlike previous methods that discard domain-specific features, SNIGL leverages these "variant" features through a calibrated ensemble to boost performance on unseen test data.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) often fail when the testing data distribution differs from the training data (OOD). This usually happens because the model learns spurious correlations—features that appear to predict the label in the training set but are actually irrelevant "noise" from the environment (e.g., a specific molecular scaffold that happens to be overrepresented in a biased dataset).

Current "invariant learning" methods try to strip away this noise to find the "invariant subgraph." However, the authors identify a major gap: these methods often struggle with a trade-off. They either focus too much on prediction accuracy (finding sufficient but unnecessary features) or too much on alignment (finding necessary but insufficient features). Furthermore, most methods completely discard domain-specific features, even though those features might contain useful context for prediction if handled correctly.

Methods

The authors propose SNIGL, which stands for Sufficiency and Necessity Inspired Graph Learning. The approach has two main pillars:

  1. PNS-based Invariant Extraction: They use the causal concept of Probability of Necessity and Sufficiency (PNS).
  2. A feature is necessary if the label cannot exist without it.
  3. A feature is sufficient if the presence of the feature guarantees the label. Since calculating PNS directly is mathematically "intractable" (requires counterfactual data we don't have), the authors derive a theoretical lower bound for PNS that can be optimized using observational data.

  4. Variant Feature Ensembling: Instead of ignoring domain-variant subgraphs (features that change across environments), SNIGL treats them as a secondary source of information.

  5. Test-Domain Adaptation: Since test labels are unavailable, the model uses "pseudo-labels" generated by the invariant classifier to train a domain-specific variant classifier.
  6. Calibrated Ensemble: It then combines the predictions from the invariant and variant classifiers using a principled "COMBINE" function based on logit-space addition.

Datasets

The model was evaluated on six public benchmarks representing different types of distribution shifts:

  • Synthetic: SP-Motif-Mixed and GOOD-Motif (focusing on structural and attribute shifts).
  • Real-world (Molecular): GOOD-HIV, OGBG-Molsider, OGBG-Molclintox, and OGBG-Molbace. These datasets use "scaffold splitting," where the training and testing sets contain molecules with fundamentally different chemical backbones.

Key Insights and Ideas

  • The "Goldilocks" Subgraph: The optimal invariant subgraph isn't just one that is "stable" across domains; it must be the "necessary and sufficient" cause. If a subgraph is sufficient but not necessary, the model will miss instances of the class. If it's necessary but not sufficient, the model will produce false positives.
  • Variant Features are Not Trash: In many OOD scenarios, the "noise" or environment features actually correlate with the label within a specific domain. By calibrating a classifier for these variant features at test time, the model can "boost" its confidence.
  • Pseudo-label Calibration: The paper provides a rigorous mathematical proof (Theorem 2) showing that you can accurately recover the relationship between variant features and true labels using only pseudo-labels from an invariant model, provided certain causal assumptions hold.

Key Results

SNIGL consistently outperformed state-of-the-art (SOTA) methods like GALA, DIR, and CIGA across all benchmarks:

  • Significant Gains: On the SP-Motif-Mixed dataset, SNIGL improved accuracy by approximately 11.2% over the previous best method (GALA).
  • Robustness: The model showed much lower variance in its results compared to baselines, suggesting that the PNS constraint leads to more stable and reliable subgraph extraction.
  • Ablation Success: Removing either the PNS risk or the ensemble strategy led to a drop in performance, confirming that both the "necessity/sufficiency" logic and the "variant feature" logic are essential.

Limitations and Future Work

The authors acknowledge a primary limitation: their ensemble strategy assumes that variant and invariant features are conditionally independent given the label. In complex real-world graphs, these features might interact in ways the current model doesn't capture.

Future work is suggested to develop more flexible ensembling methods that can handle dependencies between these two types of features, potentially moving beyond the current logit-addition framework.

Summary updated

Abstract

Graph Out-of-Distribution (OOD), requiring that models trained on biased data generalize to the unseen test data, has considerable real-world applications. One of the most mainstream methods is to extract the invariant subgraph by aligning the original and augmented data with the help of environment augmentation. However, these solutions might lead to the loss or redundancy of semantic subgraphs and result in suboptimal generalization. To address this challenge, we propose exploiting Probability of Necessity and Sufficiency (PNS) to extract sufficient and necessary invariant substructures. Beyond that, we further leverage the domain variant subgraphs related to the labels to boost the generalization performance in an ensemble manner. Specifically, we first consider the data generation process for graph data. Under mild conditions, we show that the sufficient and necessary invariant subgraph can be extracted by minimizing an upper bound, built on the theoretical advance of the probability of necessity and sufficiency. To further bridge the theory and algorithm, we devise the model called Sufficiency and Necessity Inspired Graph Learning (SNIGL), which ensembles an invariant subgraph classifier on top of latent sufficient and necessary invariant subgraphs, and a domain variant subgraph classifier specific to the test domain for generalization enhancement. Experimental results demonstrate that our SNIGL model outperforms the state-of-the-art techniques on six public benchmarks, highlighting its effectiveness in real-world scenarios.
BibTeX
@inproceedings{chen2025unifying,
  author = {Xuexin Chen and Ruichu Cai and Kaitao Zheng and Zhifan Jiang and Zhengting Huang and Zhifeng Hao and Zijian Li},
  title = {{Unifying invariant and variant features for graph out-of-distribution via probability of necessity and sufficiency}},
  booktitle = {Neural Networks},
  year = {2025},
  url = {https://openreview.net/forum?id=MXVYiBtshz},
}

Loading related content...

Figure