Abstract
Enhancing node-level Out-Of-Distribution (OOD) generalization on graphsremains a crucial area of research. In this paper, we develop a StructuralCausal Model (SCM) to theoretically dissect the performance of two prominentinvariant learning methods -- Invariant Risk Minimization (IRM) andVariance-Risk Extrapolation (VREx) -- in node-level OOD settings. Our analysisreveals a critical limitation: due to the lack of class-conditional invarianceconstraints, these methods may struggle to accurately identify the structure ofthe predictive invariant ego-graph and consequently rely on spurious features.To address this, we propose Cross-environment Intra-class Alignment (CIA),which explicitly eliminates spurious features by aligning cross-environmentrepresentations conditioned on the same class, bypassing the need for explicitknowledge of the causal pattern structure. To adapt CIA to node-level OODscenarios where environment labels are hard to obtain, we further proposeCIA-LRA (Localized Reweighting Alignment) that leverages the distribution ofneighboring labels to selectively align node representations, effectivelydistinguishing and preserving invariant features while removing spurious ones,all without relying on environment labels. We theoretically prove CIA-LRA'seffectiveness by deriving an OOD generalization error bound based onPAC-Bayesian analysis. Experiments on graph OOD benchmarks validate thesuperiority of CIA and CIA-LRA, marking a significant advancement in node-levelOOD generalization. The codes are available athttps://github.com/NOVAglow646/NeurIPS24-Invariant-Learning-on-Graphs.