What Information Matters? Graph Out-of-Distribution Detection via Tri-Component Information Decomposition

Graph neural networks are widely used for node classification, but they remain vulnerable to out-of-distribution (OOD) shifts in node features and graph structure. Prior work established that methods trained with standard supervised learning (SL) objectives tend to capture spurious signals from either features and/or structure, leaving the model fragile under distributional changes. To address this, we propose TIDE, a novel and effective Tri-Component Information Decomposition framework that explicitly decomposes information into feature-specific, structure-specific and joint components. TIDE aims to preserve only the label-relevant part of the joint information while filtering out spurious feature- and structure-specific information, thereby enhancing the separation between in-distribution (ID) and OOD nodes. Beyond the framework, we provide theoretical and empirical analyses showing that an information bottleneck objective is preferable to standard SL for graph OOD detection, with higher ID confidence and a greater entropy gap between ID and OOD data. Extensive experiments across seven datasets confirm the efficacy of Tide, achieving up to a 34% improvement in FPR95 over strong baselines while maintaining competitive ID accuracy. Code is available at https://github.com/DannyW618/TIDE.

Graph neural networks help AI systems reason about connected data, such as social networks, recommendation systems, and biological networks. However, these models can become unreliable when the data changes in unexpected ways. They often learn shortcuts from training data, relying too heavily on either node features or connection patterns that do not generalize well to new situations. To address this problem, we developed TIDE, a new framework that teaches graph neural networks to separate reliable information from misleading patterns. TIDE breaks information into three parts: what comes mainly from node features, what comes mainly from graph connections, and what is consistently supported by both. The model then focuses on the shared and trustworthy information while reducing dependence on unstable signals. Across seven benchmark datasets, TIDE was much better at identifying unfamiliar or out-of-distribution data while still maintaining strong prediction accuracy. Our work helps make graph-based AI systems more robust and trustworthy for real-world applications where data distributions can change over time.