# Unifying Invariance and Spuriousity for Graph Out-of-Distribution via Probability of Necessity and Sufficiency

arXiv: https://arxiv.org/abs/2402.09165 · HTML: https://mlsanity.com/paper/2402.09165/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 64 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Builds on (most cited first, 30 of 32)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Deep CORAL: Correlation Alignment for Deep Domain Adaptation](https://mlsanity.com/paper/1607.01719/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs](https://mlsanity.com/paper/2202.05441/) (2022)
- [GOOD: A Graph Out-of-Distribution Benchmark](https://mlsanity.com/paper/2206.08452/) (2022)
- [Uncertainty Aware Semi-Supervised Learning on Graph Data](https://mlsanity.com/paper/2010.12783/) (2020)
- [Probabilities of Causation: Bounds and Identification](https://mlsanity.com/paper/1301.3898/) (2013)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [OOD-GNN: Out-of-Distribution Generalized Graph Neural Network](https://mlsanity.com/paper/2112.03806/) (2021)
- [Does GNN Pretraining Help Molecular Representation?](https://mlsanity.com/paper/2207.06010/) (2022)
- [Explaining Black-Box Algorithms Using Probabilistic Contrastive Counterfactuals](https://mlsanity.com/paper/2103.11972/) (2021)
- [Local Explanations via Necessity and Sufficiency: Unifying Theory and Practice](https://mlsanity.com/paper/2103.14651/) (2021)
- [Does Invariant Graph Learning via Environment Augmentation Learn Invariance?](https://mlsanity.com/paper/2310.19035/) (2023)
- [HiddenCut: Simple Data Augmentation for Natural Language Understanding with Better Generalization](https://mlsanity.com/paper/2106.00149/) (2021)
- [Causal Sufficiency and Actual Causation](https://mlsanity.com/paper/2102.02311/) (2021)
- [Invariant Learning via Probability of Sufficient and Necessary Causes](https://mlsanity.com/paper/2309.12559/) (2023)
- [Spuriosity Didn't Kill the Classifier: Using Invariant Predictions to Harness Spurious Features](https://mlsanity.com/paper/2307.09933/) (2023)
- [Unit Selection with Causal Diagram](https://mlsanity.com/paper/2109.07556/) (2021)
- [Multi-Instance Causal Representation Learning for Instance Label Prediction and Out-of-Distribution Generalization](https://mlsanity.com/paper/2202.12570/) (2022)

## Built on by (most cited first, 3 of 3)

- [Dissecting the Failure of Invariant Learning on Graphs](https://mlsanity.com/paper/2411.02847/) (2024)
- [Seeking the Sufficiency and Necessity Causal Features in Multimodal Representation Learning](https://mlsanity.com/paper/2408.16577/) (2024)
- [Seeking Necessary and Sufficient Information from Multimodal Medical Data](https://mlsanity.com/paper/2603.00289/) (2026)

## Abstract (arXiv)

Graph Out-of-Distribution (OOD), requiring that models trained on biased data generalize to the unseen test data, has a massive of 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 subgraph and further result in suboptimal generalization. To address this challenge, we propose a unified framework to exploit the Probability of Necessity and Sufficiency to extract the Invariant Substructure (PNSIS). Beyond that, this framework further leverages the spurious subgraph to boost the generalization performance in an ensemble manner to enhance the robustness on the noise data. Specificially, we first consider the data generation process for graph data. Under mild conditions, we show that the invariant subgraph can be extracted by minimizing an upper bound, which is built on the theoretical advance of probability of necessity and sufficiency. To further bridge the theory and algorithm, we devise the PNSIS model, which involves an invariant subgraph extractor for invariant graph learning as well invariant and spurious subgraph classifiers for generalization enhancement. Experimental results demonstrate that our PNSIS model outperforms the state-of-the-art techniques on graph OOD on several benchmarks, highlighting the effectiveness in real-world scenarios.