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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 2 November 2026

  On Stochastic Continuous-Time Linear System Identification for Adaptive Stabilization

  Reza Sadeghi Hafshejani and Mohamad Kazem Shirani Faradonbeh
• arXiv preprint · 3 November 2026

  Nonparametric GARCH: An Iterated Neural Estimator

  Ruizhi Deng, Guohao Shen and Ngai Hang Chan
• arXiv preprint · 2 November 2026

  Efficient Proper Agnostic Learning of Halfspaces

  Anindya De, Elchanan Mossel, Shivam Nadimpalli and 1 other
• arXiv preprint · 3 November 2026

  Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions

  Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov and 1 other
• arXiv preprint · 2 November 2026

  Where Is a Prediction Model Miscalibrated, and for Whom? Local Audits in Outcome-Learned Pockets

  Bernardo Modenesi, Taoyi Chen, Sima Najafzadehkhoei and 3 others

All new papers in Machine Learning