Graph-Localized Coverage for Conformal Prediction on Inductive Graphs
Abstract
Conformal prediction (CP) provides marginal coverage guarantees, but marginal coverage does not determine where prediction errors occur on a graph. Queries from different graph neighborhoods can exhibit substantially different levels of uncertainty even when aggregate coverage remains near its target. We introduce GLocalCP, an online CP framework for inductive node classification and edge prediction that combines marginal and graph-local calibration with uncertainty-adaptive prediction sets. Specifically, GLocalCP puts forth a novel uncertainty-adaptive nonconformality score that relies on the mutual information obtained from Monte-Carlo (MC) dropout based prediction. Then, it augments a global online threshold with a kernel-based local correction that propagates coverage feedback among similar graph queries. On the theoretical horizon, we establish pathwise O(N−1/2) marginal calibration error without exchangeability or stationarity and, for the exact-kernel formulation, an explicit O(N−1/2) graph-localized calibration guarantee. Experiments on seven node-classification and seven edge-prediction benchmarks show that similar marginal coverage can conceal substantially different local reliability. Our proposed GLocalCP maintains coverage near the target while consistently reducing graph-local calibration error. Uncertainty scaling in GLocalCP further reduces prediction-set size across all evaluated node and edge datasets while leaving marginal coverage essentially unchanged.
Related
- Conformal Prediction and Conditional Coverage for Tabular Foundation Models
- How Synthetic Labels Improve Conformal Prediction: A Perspective on Conditional Coverage
- Sharp training-conditional coverage for conformal prediction under covariate shift
- Self-Organized Conformal Prediction: Reducing Regional Coverage Gaps with Unsupervised Group Discovery
- Online Bayesian Node Classification on Inductive Graphs under Distribution Shift
BibTeX
@misc{xu2026graphlocalized,
title = {{Graph-Localized Coverage for Conformal Prediction on Inductive Graphs}},
author = {Jinwen Xu and Qin Lu and Georgios B. Giannakis},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04066},
eprint = {2611.04066},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04066},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Graph-Localized Coverage for Conformal Prediction on Inductive Graphs
AU - Jinwen Xu
AU - Qin Lu
AU - Georgios B. Giannakis
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.04066
UR - https://arxiv.org/abs/2611.04066
AB - Conformal prediction (CP) provides marginal coverage guarantees, but marginal coverage does not determine where prediction errors occur on a graph. Queries from different graph neighborhoods can exhibit substantially different levels of uncertainty even when aggregate coverage remains near its target. We introduce GLocalCP, an online CP framework for inductive node classification and edge prediction that combines marginal and graph-local calibration with uncertainty-adaptive prediction sets. Specifically, GLocalCP puts forth a novel uncertainty-adaptive nonconformality score that relies on the mutual information obtained from Monte-Carlo (MC) dropout based prediction. Then, it augments a global online threshold with a kernel-based local correction that propagates coverage feedback among similar graph queries. On the theoretical horizon, we establish pathwise O(N^−1/2) marginal calibration error without exchangeability or stationarity and, for the exact-kernel formulation, an explicit O(N^−1/2) graph-localized calibration guarantee. Experiments on seven node-classification and seven edge-prediction benchmarks show that similar marginal coverage can conceal substantially different local reliability. Our proposed GLocalCP maintains coverage near the target while consistently reducing graph-local calibration error. Uncertainty scaling in GLocalCP further reduces prediction-set size across all evaluated node and edge datasets while leaving marginal coverage essentially unchanged.
ER -