  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 \textbf{PNSIS} model outperforms the state-of-the-art
techniques on graph OOD on several benchmarks, highlighting the effectiveness
in real-world scenarios.
