cs.LGNov 2, 2026

Graph-Localized Coverage for Conformal Prediction on Inductive Graphs

Authors: Jinwen Xu, Qin Lu, Georgios B. Giannakis

Organizations: School of ECE, University of Georgia, Athens, GA 30602, USA · Dept. of ECE, University of Minnesota, Minneapolis, MN 55455, USA

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)O(N^{-1/2}) marginal calibration error without exchangeability or stationarity and, for the exact-kernel formulation, an explicit O(N−1/2)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.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

    May 8, 2026Peyman Baghershahi, Fangxin Wang, Debmalya Mandal +1Graph Neural NetworksConformal Prediction

  2. Beyond Marginal Validity: Finite-Sample Guarantees for Localized Conformal Prediction

    Aug 6, 2026Anton Conrad, Rustam Isaev, Denis Belomestny +2Conformal PredictionStatistical Learning Theory

  3. Cluster Frequency Conformal Prediction for Local Coverage

    May 24, 2026Tomer Lavi, Bracha Shapira, Nadav RappoportConformal PredictionMulticlass Classification