Quantile-Free Uncertainty Quantification in Graph Neural Networks

Soyoung Park, Hwanjun Song, Sungsu Lim

TL;DR

Quantile-free Prediction Interval GNN (QpiGNN) is a novel framework for uncertainty quantification (UQ) in Graph Neural Networks (GNNs). It generates reliable prediction intervals without the need for costly resampling, post-hoc calibration, or explicit quantile inputs. By leveraging a dual-head architecture and a "quantile-free" joint loss, QpiGNN achieves 22% higher coverage and 50% narrower intervals than existing baselines, all while remaining robust to the structural dependencies inherent in graph data.

The Challenge of Uncertainty in Graphs

In high-stakes applications such as healthcare, finance, or criminal justice, knowing how certain a model is about a prediction is just as important as the prediction itself. While Graph Neural Networks are powerful tools for node regression, they typically produce only point estimates.

Quantifying uncertainty in graphs is notoriously difficult for two primary reasons:

  1. Structural Dependencies: Most statistical methods assume data points are independent and identically distributed (i.i.d., or exchangeable). In a graph, the "message passing" mechanism explicitly breaks this assumption by mixing information between neighbors.
  2. Computational Cost: Traditional frequentist methods often rely on resampling (running the model many times) or post-hoc calibration (requiring extra hold-out datasets). Both approaches are computationally expensive and often unstable on large, complex graphs.

Standard Quantile Regression (QR) is a potential alternative, but it suffers from "quantile crossing" (where a lower bound ends up higher than an upper bound) and "oversmoothing," where the graph structure washes out local uncertainty signals.

Methodology: Introducing QpiGNN

The authors introduce Quantile-free Prediction Interval GNN (QpiGNN), which stands out by directly optimizing for interval coverage and width during training. Its innovation lies in two core components:

  • Dual-Head Architecture: Instead of a single output, the model features two distinct "heads" branching off a shared GNN encoder. One head predicts the target value ($\hat{y}$), while the other predicts the interval width ($\hat{d}$). This decoupling prevents "representational conflict"—where the model struggles to learn accuracy and uncertainty simultaneously—and helps mitigate the oversmoothing common in GNNs.
  • Quantile-Free Joint Loss: Unlike standard QR, which requires a specific quantile (like the 5th or 95th percentile) as input, QpiGNN uses a joint loss function. This loss penalizes the model if the empirical coverage deviates from a target (e.g., 90%) and includes a violation penalty for how far true values fall outside the predicted range. Crucially, it also includes an L1-based width penalty to keep the intervals as tight as possible.

This approach allows for end-to-end training with only standard labels, bypassing the complex post-processing steps required by methods like Conformal Prediction.

Datasets and Evaluation

The authors evaluated QpiGNN across 19 benchmarks to ensure robustness:

  • 9 Synthetic Datasets: These include various graph topologies (Tree, Grid, Barabási–Albert, Erdős–Rényi) and noise types (Gaussian, Uniform, Outliers) to test how the model handles specific structural challenges.
  • 10 Real-World Datasets: These cover diverse domains, including U.S. county-level socioeconomic outcomes (Education, Election, Income, Unemployment), social and knowledge graphs (Chameleon, Squirrel, Crocodile, PTBR), and transportation networks (traffic flow estimates in Anaheim and Chicago).

Key Insights

  • Decoupling is the Secret Sauce: By separating the prediction of the mean from the prediction of the interval width, the model avoids the "entanglement" that usually causes GNNs to produce overly smooth, non-adaptive uncertainty bounds.
  • Quantile-Free Efficiency: By removing the need for quantile-level inputs ($\tau$), the model avoids the "quantile crossing" problem entirely and simplifies the training pipeline.
  • Robustness to Non-Exchangeability: The paper provides theoretical guarantees that QpiGNN maintains valid coverage even when the standard i.i.d. assumptions are violated, which is the norm in graph data.
  • L1 vs. L2 Width Penalties: The authors found that an L1 penalty for interval width is much more stable than L2 in graph settings, as L2 tends to over-amplify the impact of heavy-tailed residuals caused by graph heterophily.

Key Results

QpiGNN consistently outperformed six major baselines, including Bayesian NNs, MC Dropout, and Conformalized GNNs:

  • Better Coverage & Tighter Intervals: On average, it achieved 22% higher coverage and 50% narrower intervals than the next best competitors.
  • Efficiency: Its training time and memory usage are comparable to simple deterministic GNNs, making it significantly faster than sampling-based Bayesian methods or multi-step conformal approaches.
  • Robustness: In stress tests involving feature noise, target noise, and edge dropout, QpiGNN maintained stable, calibrated intervals while other methods' performance collapsed.

Limitations and Future Work

While QpiGNN is highly robust, the authors note a few areas for future improvement:

  • Symmetry Assumption: The current theoretical framework assumes symmetric conditional distributions. While empirical results show it handles skewed data well, formalizing this for asymmetric noise is a future goal.
  • Hyperparameter Sensitivity: The width penalty ($\lambda_{width}$) currently requires tuning (often via Bayesian optimization) to find the perfect balance between coverage and tightness for a specific dataset.
  • Task Extensions: The current work focuses on node regression. Extending this framework to graph-level regression, link prediction, and dynamic or evolving graphs is the next logical step.

Summary updated

Abstract

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.
BibTeX
@inproceedings{park2026quantile,
  author = {Soyoung Park and Hwanjun Song and Sungsu Lim},
  title = {{Quantile-Free Uncertainty Quantification in Graph Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=zlU90YE4EJ},
}
Figure