# Uncertainty Quantification over Graph with Conformalized Graph Neural Networks

arXiv: https://arxiv.org/abs/2305.14535 · HTML: https://mlsanity.com/paper/2305.14535/

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 55 references that are in the map.
- First posted on arXiv 23 May 2023.

## Builds on (most cited first, 30 of 39)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?](https://mlsanity.com/paper/1703.04977/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift](https://mlsanity.com/paper/1906.02530/) (2019)
- [A Review of Uncertainty Quantification in Deep Learning: Techniques, Applications and Challenges](https://mlsanity.com/paper/2011.06225/) (2020)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Accurate Uncertainties for Deep Learning Using Calibrated Regression](https://mlsanity.com/paper/1807.00263/) (2018)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with Dirichlet calibration](https://mlsanity.com/paper/1910.12656/) (2019)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [What Are Bayesian Neural Network Posteriors Really Like?](https://mlsanity.com/paper/2104.14421/) (2021)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [GraphCast: Learning skillful medium-range global weather forecasting](https://mlsanity.com/paper/2212.12794/) (2022)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning](https://mlsanity.com/paper/2003.07329/) (2020)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Calibration of Neural Networks using Splines](https://mlsanity.com/paper/2006.12800/) (2020)
- [Uncertainty Aware Semi-Supervised Learning on Graph Data](https://mlsanity.com/paper/2010.12783/) (2020)
- [Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration](https://mlsanity.com/paper/2109.14285/) (2021)

## Built on by (most cited first, 30 of 79)

- [Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees](https://mlsanity.com/paper/2405.10301/) (2024)
- [Conformal prediction for multi-dimensional time series by ellipsoidal sets](https://mlsanity.com/paper/2403.03850/) (2024)
- [Conformalized-DeepONet: A Distribution-Free Framework for Uncertainty Quantification in Deep Operator Networks](https://mlsanity.com/paper/2402.15406/) (2024)
- [Boosted Conformal Prediction Intervals](https://mlsanity.com/paper/2406.07449/) (2024)
- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)
- [E-Values Expand the Scope of Conformal Prediction](https://mlsanity.com/paper/2503.13050/) (2025)
- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Uncertainty in Graph Neural Networks: A Survey](https://mlsanity.com/paper/2403.07185/) (2024)
- [Transductive conformal inference with adaptive scores](https://mlsanity.com/paper/2310.18108/) (2023)
- [Trustworthy Classification through Rank-Based Conformal Prediction Sets](https://mlsanity.com/paper/2407.04407/) (2024)
- [Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration](https://mlsanity.com/paper/2406.06818/) (2024)
- [Robust Yet Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2407.09165/) (2024)
- [Optimized Conformal Selection: Powerful Selective Inference After Conformity Score Optimization](https://mlsanity.com/paper/2411.17983/) (2024)
- [U-Cast: A Surprisingly Simple and Efficient Frontier Probabilistic AI Weather Forecaster](https://mlsanity.com/paper/2604.09041/) (2026)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Conformal Load Prediction with Transductive Graph Autoencoders](https://mlsanity.com/paper/2406.08281/) (2024)
- [Relational Conformal Prediction for Correlated Time Series](https://mlsanity.com/paper/2502.09443/) (2025)
- [Conformal Inductive Graph Neural Networks](https://mlsanity.com/paper/2407.09173/) (2024)
- [Conformal Prediction Sets for Deep Generative Models via Reduction to Conformal Regression](https://mlsanity.com/paper/2503.10512/) (2025)
- [Conformal link prediction for false discovery rate control](https://mlsanity.com/paper/2306.14693/) (2023)
- [TorchCP: A Python Library for Conformal Prediction](https://mlsanity.com/paper/2402.12683/) (2024)
- [Scalable Training of Trustworthy and Energy-Efficient Predictive Graph Foundation Models for Atomistic Materials Modeling: A Case Study with HydraGNN](https://mlsanity.com/paper/2406.12909/) (2024)
- [Conformalized Interval Arithmetic with Symmetric Calibration](https://mlsanity.com/paper/2408.10939/) (2024)
- [GraphAgent: Agentic Graph Language Assistant](https://mlsanity.com/paper/2412.17029/) (2024)
- [HealthMamba: An Uncertainty-aware Spatiotemporal Graph State Space Model for Effective and Reliable Healthcare Facility Visit Prediction](https://mlsanity.com/paper/2602.05286/) (2026)
- [Similarity-Navigated Conformal Prediction for Graph Neural Networks](https://mlsanity.com/paper/2405.14303/) (2024)
- [C-Adapter: Adapting Deep Classifiers for Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2410.09408/) (2024)
- [DA-MoE: Addressing Depth-Sensitivity in Graph-Level Analysis through Mixture of Experts](https://mlsanity.com/paper/2411.03025/) (2024)
- [Parametric Scaling Law of Tuning Bias in Conformal Prediction](https://mlsanity.com/paper/2502.03023/) (2025)
- [A Generic Framework for Conformal Fairness](https://mlsanity.com/paper/2505.16115/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are powerful machine learning prediction models on graph-structured data. However, GNNs lack rigorous uncertainty estimates, limiting their reliable deployment in settings where the cost of errors is significant. We propose conformalized GNN (CF-GNN), extending conformal prediction (CP) to graph-based models for guaranteed uncertainty estimates. Given an entity in the graph, CF-GNN produces a prediction set/interval that provably contains the true label with pre-defined coverage probability (e.g. 90%). We establish a permutation invariance condition that enables the validity of CP on graph data and provide an exact characterization of the test-time coverage. Moreover, besides valid coverage, it is crucial to reduce the prediction set size/interval length for practical use. We observe a key connection between non-conformity scores and network structures, which motivates us to develop a topology-aware output correction model that learns to update the prediction and produces more efficient prediction sets/intervals. Extensive experiments show that CF-GNN achieves any pre-defined target marginal coverage while significantly reducing the prediction set/interval size by up to 74% over the baselines. It also empirically achieves satisfactory conditional coverage over various raw and network features.