Quantile-Free Uncertainty Quantification in Graph Neural Networks

Uncertainty quantification (UQ) in graph neural networks (GNNs) is crucial in high-stakes domains but remains a significant challenge. In graph settings, message passing often relies on strong assumptions such as exchangeability, which are rarely satisfied in practice. Moreover, achieving reliable UQ typically requires costly resampling or post-hoc calibration. To address these issues, we introduce Quantile-free Prediction Interval GNN (QpiGNN), a framework that builds on quantile regression (QR) to enable GNN-based UQ by directly optimizing coverage and interval width without requiring quantile inputs or post-processing. QpiGNN employs a dual-head architecture that decouples prediction and uncertainty, and is trained with label-only supervision through a quantile-free joint loss. This design allows efficient training and yields robust prediction intervals, with theoretical guarantees of asymptotic coverage and near-optimal width under mild assumptions. Experiments on 19 synthetic and real-world benchmarks show QpiGNN achieves average 22% higher coverage and 50% narrower intervals than baselines, while ensuring efficiency and robustness to noise and structural shifts.

When AI systems make predictions—say, estimating someone's income or traffic congestion in a city—it is not enough to just give a single number. In high-stakes settings like healthcare or criminal justice, we also need to know how confident the AI is. One way to express this is through a prediction interval: a range that says "the true answer is likely somewhere between X and Y." Graph Neural Networks (GNNs) are a popular class of AI models designed for data that comes naturally in networks—think social connections, road maps, or molecular structures. Getting reliable confidence intervals out of GNNs is surprisingly hard: standard approaches either make assumptions about the data that graphs routinely violate, or they require expensive extra computation steps after training. We developed QpiGNN, a new training framework that teaches a GNN to output calibrated confidence intervals directly, without any of those extra steps. The key ideas are a two-part output head—one part predicts the answer, the other predicts how wide the confidence band should be—and a novel training objective that simultaneously rewards hitting the right coverage rate and keeping intervals as tight as possible. Across 19 datasets ranging from synthetic graphs to real-world transportation and social networks, QpiGNN produced intervals that were on average 22% more likely to contain the true answer, and 50% narrower, compared to existing methods—all while training as fast as the simplest baselines.