Graph neural networks measure uncertainty for safer predictions
A Unified Uncertainty Representation for Graph Neural Networks via Doubly-Spectral Stochastic Expansion
Machine LearningArtificial Intelligence
Summary
Graph neural networks are powerful but can make unreliable predictions when they see new or unusual data. The authors propose a new mathematical method that captures uncertainty in these networks by treating node outputs as random signals in two ways, combining structural and stochastic variations. This unified approach helps the networks know how confident they should be, detect data that looks very different, and maintain accuracy when conditions change. Their method works well on many standard tests and can be used alone or alongside existing models.
What this means in practice
- •For machine learning engineers: Improve the reliability of node classification by detecting uncertain predictions and data shifts within graph-based models.
- •For network security teams: Detect anomalous or unexpected patterns in network graphs to flag potential security threats or intrusions.
Authors
Fred Xu, Thomas Markovich, Florence Regol, Yizhou Sun
Abstract
Reliable deployment of graph neural networks requires calibration, out-of-distribution (OOD) detection, and robustness to distribution shift, yet existing methods address these needs with separate models and objectives. We model uncertain node embeddings as random graph signals: graph Fourier filters capture structural variation, and a scalar orthogonal-polynomial chaos coordinate captures latent stochastic variation. The resulting doubly-spectral stochastic (DSS) expansion supplies task-matched readouts from one representation: the mean coefficient encodes class evidence for the energy-based OOD score, the higher-order coefficients encode structured logit variation, and quadrature averaging over the chaos coordinate defines the single predictive distribution used for prediction and calibration. A capacity theorem shows that, under a full-rank feature assumption, a restricted subfamily matches the chaos coefficients of any Gaussian-latent random graph signal, with exponentially decaying truncation error under a growth condition; the task-level claims are established empirically. DSS-GNN has two deployment modes: standalone, or as a residual branch beside a deterministic encoder (DSS-Hybrid). Standalone DSS-GNN achieves the lowest Brier score among the compared uncertainty-aware baselines on all 14 node classification benchmarks without post-hoc correction; DSS-Hybrid achieves the best AUROC on most node-OOD settings, competitive cross-graph OOD detection, and the strongest shifted accuracy on all 7 GOOD concept-shift benchmarks under standard empirical risk minimization (ERM). Cross-evaluating both modes on all three tasks shows that each remains effective on the other's tasks, with documented exceptions, and yields explicit deployment guidance.