Uncertainty Quantification over Graph with Conformalized Graph Neural Networks

2023/05/23 by Kexin Huang, Ying Jin, Huang, Kexin +5 · 13 citations
Computer Science · Materials Science · #Advanced Graph Neural Networks #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning in Materials Science

paper · pdf · doi:10.48550/arxiv.2305.14535

openalex publication_date 2023/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Cited by

• HeAD-CP: Heterophily-Aware Diffused Conformal Prediction Sets for Graph Neural Networks
• Conformal Correction for Efficiency May be at Odds with Entropy
• Cost-Sensitive Conformal Training with Provably Controllable Learning Bounds
• Conformal Prediction for Multi-Source Detection on a Network
• Conformalized Polynomial Chaos Expansion for Uncertainty-aware Surrogate Modeling
• Conformal Inference for Time Series over Graphs
• Conformalized Gaussian processes for online uncertainty quantification over graphs
• HybridFlow: Quantification of Aleatoric and Epistemic Uncertainty with a Single Hybrid Model
• Conformal Unlearning: A New Paradigm for Unlearning in Conformal Predictors
• GNN's Uncertainty Quantification using Self-Distillation
• Residual Reweighted Conformal Prediction for Graph Neural Networks
• A Generic Framework for Conformal Fairness
• LOBSTUR: A Local Bootstrap Framework for Tuning Unsupervised Representations in Graph Neural Networks
• U-Cast: A Surprisingly Simple and Efficient Frontier Probabilistic AI Weather Forecaster

Related

• Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training
• Conditional Shift-Robust Conformal Prediction for Graph Neural Network
• Conformalized Link Prediction on Graph Neural Networks
• RoCP-GNN: Robust Conformal Prediction for Graph Neural Networks in Node-Classification
• On the Temperature of Bayesian Graph Neural Networks for Conformal Prediction