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

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.

The Challenge of Graph Out-of-Distribution Generalization

Graph Neural Networks (GNNs) have shown remarkable success in various domains, but they often struggle when the testing data distribution differs from the training data—a phenomenon known as Out-of-Distribution (OOD) shift. This failure typically stems from the model learning spurious correlations: features that appear predictive in a biased training set but are actually irrelevant "noise" from the environment (e.g., a specific molecular scaffold overrepresented in a training batch).

Current "invariant learning" methods attempt to mitigate this by stripping away environmental noise to find an "invariant subgraph." However, these methods often face a critical trade-off: they either focus too much on prediction accuracy (finding sufficient but unnecessary features) or too much on alignment across environments (finding necessary but insufficient features). This leads to the loss or redundancy of semantic subgraphs, resulting in suboptimal generalization.

Overview of graph space and distribution shifts. (a) shows the feature space used by current methods vs. SNIGL. (b) illustrates distribution shifts in training and OOD test sets. (c) demonstrates correlations between invariant/variant features and labels.

The SNIGL Framework: Necessity and Sufficiency

To address these limitations, we introduce SNIGL (Sufficiency and Necessity Inspired Graph Learning). The framework is built on two primary pillars: PNS-based invariant extraction and variant feature ensembling.

1. PNS-based Invariant Extraction

We utilize the causal concept of Probability of Necessity and Sufficiency (PNS) to identify the "Goldilocks" subgraph. In this context:

  • A feature is necessary if the label cannot exist without it.
  • A feature is sufficient if the presence of the feature guarantees the label.

While calculating PNS directly is mathematically intractable due to the lack of counterfactual data, we derive a theoretical upper bound for the risk that can be optimized using observational data. This ensures the extracted invariant subgraph is both a necessary and sufficient cause for the label, reducing false positives and false negatives simultaneously.

2. Leveraging Variant Features

Unlike traditional methods that discard domain-variant subgraphs (features that change across environments), SNIGL recognizes that these features can contain useful context. We treat them as a secondary source of information through a calibrated ensemble. Since test labels are unavailable, the model uses pseudo-labels generated by the invariant classifier to train a domain-specific variant classifier. These predictions are then combined using a principled logit-space addition function.

Causal graph representing the data generation process, where Y is the label, S is the invariant subgraph, G is the observed graph, E is the environment, and C is the domain-variant subgraph.

Causal Foundations and Theoretical Insights

The effectiveness of SNIGL is grounded in a rigorous causal data generation process. As shown in the causal graph above, the observed graph $G$ is generated by both invariant features $S$ (directly related to label $Y$) and variant features $C$ (influenced by the environment $E$).

A key insight of this work is that variant features are not merely "trash." In many OOD scenarios, environmental features 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. We provide mathematical proof (Theorem 2) showing that the relationship between variant features and true labels can be recovered using pseudo-labels from an invariant model, provided certain causal independence assumptions hold.

Experimental Results

SNIGL was evaluated on six public benchmarks, including synthetic datasets (SP-Motif-Mixed, GOOD-Motif) and real-world molecular datasets (GOOD-HIV, OGBG-Molsider, OGBG-Molclintox, and OGBG-Molbace) using scaffold splitting.

Key findings include:

  • Superior Performance: SNIGL consistently outperformed state-of-the-art methods like GALA, DIR, and CIGA. Notably, on the SP-Motif-Mixed dataset, SNIGL improved accuracy by approximately 11.2% over the previous best method (GALA).
  • Stability: The model exhibited lower variance in results compared to baselines, suggesting that the PNS constraint leads to more stable and reliable subgraph extraction.
  • Ablation Studies: Removing either the PNS risk or the ensemble strategy led to a performance drop, confirming that both the "necessity/sufficiency" logic and the "variant feature" logic are essential for robust OOD generalization.

Conclusion

SNIGL represents a significant step forward in Graph OOD by unifying invariant and variant features. By ensuring that invariant subgraphs are both necessary and sufficient, and by intelligently ensembling domain-variant features rather than discarding them, SNIGL achieves state-of-the-art performance and robustness across diverse graph datasets.

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},
}
Figure