Optimized Graph Structures for Calibrating Graph Neural Networks with Out-of-Distribution Nodes

Calibrating graph neural networks (GNNs) in the presence of out-of-distribution (OOD) nodes is challenging because messages propagated from OOD neighbors can distort both the predictions and confidence estimates of in-distribution (ID) nodes. Existing graph calibration methods primarily adjust model outputs through node-wise temperature scaling or reweight edges according to general predictive importance and homophily. However, they do not directly account for the adverse effects of ID-OOD connections and may therefore preserve or even amplify misleading information propagated from OOD nodes. Inspired by the ability of graph structure learning to filter noisy topological information, we empirically observe that downweighting edges between ID and OOD nodes can substantially improve calibration. Identifying these edges and assigning appropriate weights is challenging because the identities of OOD nodes are unknown. To address this challenge, we propose Graph Calibration via Structure Optimization (GCSO), a novel framework for calibrating GNNs in the presence of OOD nodes. GCSO introduces an iterative edge-sampling mechanism to capture graph topological information and formulates adaptive structure optimization as a Markov Decision Process (MDP). An actor-critic policy then dynamically adjusts edge weights based on their effects on target-node predictions. We further design a tailored calibration-aware reward to guide the policy toward an adaptive graph structure that suppresses harmful OOD information propagation. Moreover, the optimized graph structure can be seamlessly integrated with existing temperature-scaling methods for further calibration improvements. Experiments on benchmark datasets demonstrate that GCSO significantly reduces expected calibration error while maintaining competitive classification accuracy. The source code is available at https://github.com/DamoSWL/GCSO.