🤖 machine learning

Quantile-Free Uncertainty Quantification in Graph Neural Networks

The paper presents QpiGNN, a novel framework that employs a dual-head architecture and a quantile-free joint loss to enable efficient, robust, and theoretically guaranteed uncertainty quantification for Graph Neural Networks without relying on costly resampling procedures or strict exchangeability assumptions.

Original authors: Soyoung park, Hwanjun Song, Sungsu Lim

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Soyoung park, Hwanjun Song, Sungsu Lim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Confident but Wrong" Robot

Imagine a super-smart robot (a Graph Neural Network, or GNN) looking at a complex web of connections—like a social network, a street map, or a chemical structure—to predict something about a specific node (a person, a city, or a molecule).

The robot is excellent at giving a single numerical answer, such as "This person will earn $50,000." However, in high-risk situations (like healthcare or criminal justice), a single number is not enough. You need to know: "How sure are you?"

If the robot says "$50,000" but is actually guessing wildly, that is dangerous. Ideally, it should say: "I am fairly sure it is between $45,000 and $55,000." This range is called a prediction interval.

The problem is that existing robots are bad at creating these ranges.

The "too wide" robot: Some methods say: "It could be anywhere between $0 and $1,000,000!" Technically, they are right (the answer is included), but the range is so broad it is useless.
The "too narrow" robot: Other methods say: "It is definitely between $49,900 and $50,100." They look precise but are often wrong because they fail to account for the chaotic, interconnected nature of the data.
The "expensive" robot: To get a good range, current methods often require running the robot thousands of times (resampling) or performing a complex calibration step afterward. This is slow and computationally intensive.

The Solution: Meet QpiGNN

The authors introduce QpiGNN (Quantile-free Prediction Interval GNN). Think of this as a new training method that teaches the robot to draw the perfect box around its answers without needing to run it thousands of times or apply complicated mathematical tricks.

Here is how it works, broken down into three simple concepts:

1. The "Two-Headed" Robot (Dual-Head Architecture)

Most robots have one brain trying to do two things at once: guess the number and guess how wide the box should be. This often confuses the robot, leading to blurry or "over-smoothed" answers where every node looks the same.

QpiGNN's Trick: It gives the robot two separate heads.

Head A focuses only on guessing the number (e.g., "$50,000").
Head B focuses only on guessing the size of the uncertainty box (e.g., "The box should be ±$5,000").

The Analogy: Imagine a chef. A normal chef tries to cook the food and season it simultaneously, which can lead to a bland dish. QpiGNN is like a kitchen with two chefs: one is the Chef (Head A), focusing purely on flavor, and the other is the Sous-Chef (Head B), focusing purely on portion size. They work together but don't get in each other's way. This allows the robot to be precise about the number and flexible regarding uncertainty.

2. The "No-Quantiles" Rule (Quantile-Free)

Old methods for creating these boxes often rely on a concept called "quantiles." Imagine trying to draw a box by asking: "What is the 5% lowest value?" and "What is the 95% highest value?" You have to ask these specific questions for every single data point. In a complex web of connections (a graph), this becomes chaotic, causing the boxes to overlap or become unstable.

QpiGNN's Trick: It discards the specific "5%" and "95%" questions. Instead, it uses a Joint Loss (a scoring system) that simply asks two questions during training:

Coverage: "Is the true answer inside your box?" (If not, you get a penalty).
Compactness: "Is your box as small as possible while still capturing the answer?" (If it is too big, you get a penalty).

The Analogy: Imagine a game of "Hot and Cold."

Old Way: You must calculate the exact temperature of the "cold" zone and the "hot" zone separately before you can play.
QpiGNN Way: You just play the game. If the treasure is outside your circle, you lose points. If your circle is huge and you still lose points, you lose more points. The robot learns to shrink its circle just enough so the treasure remains inside, without needing to calculate complex temperature zones beforehand.

3. The "Goldilocks" Result

Since QpiGNN separates the tasks and uses this simple scoring system, it achieves a "Goldilocks" result:

It is not too wide (it is useful).
It is not too narrow (it is reliable).
It is fast (it does not need to be run thousands of times).

What the Experiments Showed

The authors tested this new robot on 19 different datasets, ranging from artificially generated, made-up graphs to real-world data, such as:

Social Networks: (Twitch, Wikipedia pages).
Geographic Data: (US counties, Chicago traffic).
Synthetic Graphs: (Grids, trees, random networks).

The Results:

Better Coverage: On average, QpiGNN catches the true answer 22% more often than other methods.
Narrower Boxes: When it catches the answer, the range is 50% narrower than the competition.
Robustness: Even when the data was noisy (like static on a radio) or the graph structure changed (like a closed road), QpiGNN continued to work well. Other methods either got confused or gave up.

Summary

In short, QpiGNN is a new way to teach Graph Neural Networks to admit when they are uncertain. Instead of using slow, complex mathematics or guessing specific statistical thresholds, it uses a "two-headed" design and a simple "catch the ball" training game. This leads to predictions that are both trustworthy (they hit the right answer) and precise (they don't give you a useless, huge range).

It is like upgrading from a robot that guesses wildly or gives you a map of the whole world to find a coffee shop, to a robot that draws a perfect, tight circle around the exact coffee shop you are looking for.

Technical Summary: Quantile-Free Uncertainty Quantification in Graph Neural Networks

1. Problem Statement

Uncertainty quantification (UQ) in Graph Neural Networks (GNNs) is critical for high-risk applications such as healthcare and criminal justice, yet it remains a significant challenge. Existing GNNs typically generate deterministic point estimates without capturing the reliability of predictions. Furthermore, standard message-passing mechanisms can propagate and amplify data biases, increasing risks in decision-making processes.

Current UQ approaches for GNNs face three main limitations:

Bayesian Methods: Although theoretically grounded, they often suffer from scalability issues and sensitivity to the specification of prior distributions.
Resampling and Post-hoc Calibration: Frequentist approaches such as Conformal Prediction (CP) or ensemble methods rely on repeated inference or separate calibration sets. These are computationally intensive and often depend on strong assumptions, such as exchangeability (often simplified as i.i.d.), which are frequently violated in graph data due to structural dependencies (e.g., hubs, heterophily).
Limitations of Quantile Regression (QR): Standard QR requires explicit quantile-level inputs (e.g., $\tau = 0.05$ ) or separate models for each quantile. When applied to GNNs, this design leads to entangled node representations, resulting in issues such as quantile crossing, over-smoothing, and poorly calibrated intervals.

The work argues that a frequentist framework is required that avoids strong assumptions, eliminates the need for quantile inputs or post-processing, and remains computationally feasible for graph-structured data.

2. Methodology: QpiGNN

The authors propose Quantile-free Prediction Interval GNN (QpiGNN), a framework that generates calibrated and compact prediction intervals for node-based regressions without requiring quantile inputs, resampling, or post-hoc calibration.

2.1. Dual-Head Architecture

QpiGNN employs a dual-head architecture to decouple the prediction of the target value from the estimation of uncertainty.

Encoder: A standard GNN (e.g., GraphSAGE) aggregates neighborhood information to produce node embeddings $H$ .
Prediction Head: A linear layer predicts the target mean: $\hat{y} = W_{pred}H + b_{pred}$ .
Uncertainty Head: A separate linear layer predicts the half-interval width: $\hat{d} = \text{Softplus}(W_{diff}H + b_{diff})$ . The Softplus activation ensures that $\hat{d} > 0$ .
Output: The prediction interval for node $v$ is defined as $[\hat{y}_v - \hat{d}_v, \hat{y}_v + \hat{d}_v]$ .

This separation prevents representation conflicts and gradient interference between accuracy and uncertainty estimation, mitigating over-smoothing problems common in single-head GNNs.

2.2. Quantile-Free Joint Loss Function

Instead of optimizing for specific quantiles, QpiGNN is trained end-to-end with a joint loss function $\mathcal{L}_{total}$ that directly optimizes for coverage and interval width:

$\mathcal{L}_{total} = \mathcal{L}_{coverage} + \lambda_{width} \cdot \mathcal{L}_{width}$

Coverage Term ( $\mathcal{L}_{coverage}$ ): This term penalizes deviations from the target coverage rate $(1-\alpha)$ $(1 - α)$ . It includes a squared error term $(\hat{c} - (1-\alpha))^2$ $(\overset{c}{^} - (1 - α))^{2}$ and a violation loss $\hat{\ell}_{viol}$ $\hat{ℓ}_{v i o l}$ that provides fine-grained feedback when true targets lie outside the predicted bounds.
- $\hat{c}$ is the empirical coverage proportion.
- $\hat{\ell}_{viol}$ penalizes the magnitude of the violation when $y_v < \hat{y}^{low}_v$ or $y_v > \hat{y}^{up}_v$ .
Width Term ( $\mathcal{L}_{width}$ ): This term minimizes the average interval width $\mathbb{E}[\hat{y}^{up}_v - \hat{y}^{low}_v]$ using an $L_1$ penalty to ensure stability against outliers.
Trade-off: The hyperparameter $\lambda_{width}$ balances the trade-off between maintaining target coverage and minimizing interval width (compactness).

This design enables the model to learn adaptive, node-specific intervals directly from label monitoring without requiring explicit quantile inputs or calibration sets.

3. Theoretical Guarantees

The work provides theoretical justifications for QpiGNN under mild assumptions (bounded noise, weak dependence across nodes, and convergence of predicted means/widths):

Asymptotic Coverage: Under the Weak Law of Large Numbers (WLLN), the empirical coverage $\hat{c}$ converges in probability to the target level $1-\alpha$ as the number of nodes $N \to \infty$ .
Finite-Sample Bounds: Using concentration inequalities (McDiarmid and Hoeffding), the work shows that for moderate $N$ , the deviation of empirical coverage from the target is bounded by $O(1/\sqrt{N})$ , even in the presence of graph-dependent dependencies.
Optimal Width: The joint loss function is interpreted as a Lagrange relaxation of a constrained optimization problem. When coverage is satisfied, the model prioritizes width reduction, yielding nearly optimal interval widths.
Convergence: It is shown that the non-convex joint loss function converges to a stationary point under standard conditions for stochastic optimization.

4. Experimental Results

The authors evaluated QpiGNN on 19 datasets, comprising 9 synthetic graphs (e.g., BA, ER, Grid, Tree) and 10 real-world benchmarks (e.g., US County data, Twitch, Wikipedia graphs).

4.1. Performance Metrics

The primary metrics were Prediction Interval Coverage Probability (PICP) and Mean Prediction Interval Width (MPIW).

Coverage: QpiGNN achieved an average 22% higher coverage than competing baselines (SQR-GNN, RQRadj.-GNN, CF-GNN, BayesianNN, MC Dropout).
Compactness: QpiGNN generated intervals that were on average 50% narrower while maintaining valid coverage.
Comparison:
- BayesianNN ensured coverage but produced excessively wide intervals.
- MC Dropout generated narrow intervals but suffered from severe under-coverage.
- SQR-GNN and RQRadj.-GNN often exhibited instability, quantile crossing, or poor calibration on heterophilic graphs.
- CF-GNN (Conformalized) required calibration sets and produced wider intervals than QpiGNN.

4.2. Robustness and Generalization

Perturbations: QpiGNN remained robust against feature noise, target noise, and edge dropout, maintaining valid coverage where baselines failed or required significantly wider intervals.
Structural Shifts: In Out-of-Distribution (OOD) tests where models trained on one graph type were tested on others, QpiGNN trained on expressive graphs (BA, ER) generalized well, whereas models trained on simple structures (Tree, Basic) failed to cover targets on complex graphs.
Exchangeability: QpiGNN maintained performance under non-exchangeable splits (e.g., splits by node degree or community) and demonstrated robustness against violations of the i.i.d. assumption.

4.3. Efficiency

QpiGNN shares the same computational complexity $O(Ed + Nd^2)$ as lightweight baselines like SQR-GNN. Unlike MC Dropout (which requires multiple forward passes) or CF-GNN (which requires a separate calibration module), QpiGNN performs uncertainty estimation during inference in a single pass.

5. Main Contributions

Quantile-Free UQ Framework: QpiGNN is the first framework enabling calibrated, compact node-based uncertainty quantification in GNNs without requiring quantile inputs, resampling, or post-processing.
Architecture and Loss Design: The introduction of a dual-head architecture combined with a quantile-free joint loss function that decouples prediction and uncertainty, mitigates over-smoothing, and enables stable training.
Theoretical and Empirical Validation: The work provides theoretical guarantees for asymptotic and finite-sample-based coverage under mild assumptions and demonstrates superior performance across 19 diverse benchmarks, with significant improvements in both coverage and interval width compared to state-of-the-art baselines.

6. Significance

The work claims that QpiGNN bridges the critical gap in trustworthy GNN applications by providing a computationally efficient, robust, and assumption-light method for uncertainty quantification. By avoiding the strong exchangeability assumptions required for Conformal Prediction as well as the computational burden of Bayesian methods, QpiGNN offers a practical solution for high-risk domains where reliable prediction intervals are essential. The authors note that the method remains robust even when theoretical assumptions (such as symmetry or independence) are only approximately met in real-world graph data.

Proposed future work by the authors includes extending QpiGNN to graph-based and link prediction tasks, disentangling aleatoric and epistemic uncertainty, and applying the framework to dynamic or evolving graphs.