Let Invariant Learning Inspire Neighbor-Shift Generalization on Graphs

Graph Neural Networks (GNNs) have achieved strong performance on various graph learning tasks under the assumption of independently and identically distributed (IID) data. However, recent studies reveal that GNNs suffer from performance drops under distribution shifts, prompting growing interest in out-of-distribution (OOD) generalization. In this work, we identify a previously underexplored challenge <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Neighbor Shift</i>, which refers to structural inconsistencies in node neighborhoods across environments. We analyze its characteristics and demonstrate its negative impact on node-level classification. To tackle this issue, we propose the Neighbor-Shift Robust Graph Neural Network (NSRGNN), which disentangles invariant and variant subgraphs through conflict-based structure analysis, infers latent environments using the variant components, and regularizes semantic consistency of node representations across inferred environments. Extensive experiments on both real-world and synthetic benchmarks show that NSRGNN consistently outperforms strong OOD baselines and exhibits robust generalization under diverse structural shifts.