On the Generalizability of Non-Causal Subgraphs: Addressing Cue Discordance for Graph OOD Generalization

Graph neural networks often exploit spurious correlations in training environments, leading to poor out-of-distribution generalization. Existing graph OOD methods typically seek causal or invariant subgraphs, implicitly treating non-causal structures as poorly generalizable by-products of overfitting. However, in our analysis and experiments, we find that non-causal subgraphs can also exhibit nontrivial cross-sample generalization and provide predictive cues that conflict with those encoded by causal subgraphs. We characterize this phenomenon as cue discordance, where the causal subgraph supports the ground-truth class while the spurious favors a different one. Empirically, we show that cue discordance is widespread and markedly more common among misclassified samples; moreover, increasing the proportion of discordant samples consistently reduces accuracy while increasing classification loss. We further theoretically establish the Discordance-Conditioned Causal Contrast (D3C) criterion, proving that under cue discordance, causal and non-causal subgraphs exhibit a non-trivial relative risk separation. Building on these findings, we propose Discordance-Oriented Causal Subgraph Discrimination (DCS), which uses full-graph classification risk as an observable proxy for latent discordance strength and adaptively enforces a stronger predictive advantage of candidate causal subgraphs over their non-causal complements, enabling efficient and robust causal subgraph identification. Extensive experiments on 8 datasets demonstrate consistent improvements over existing graph OOD methods.