ArXiv

GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

2026-05-08 · 17:56 UTC ·Peyman Baghershahi, Fangxin Wang, Debmalya Mandal... ·1 min read
Authors
Peyman Baghershahi, Fangxin Wang, Debmalya Mandal...
Categories
cs.LG
arXiv
https://arxiv.org/abs/2605.08074v1
PDF
https://arxiv.org/pdf/2605.08074v1

Brief

GRAPHLCP tackles conformal prediction for graph neural networks by addressing failures of embedding-space localization on graphs. It combines feature-aware densification to reduce locality bias in sparse graphs with a Personalized PageRank kernel to capture structural proximity for anchor sampling and calibration weighting. The approach yields finite-sample marginal coverage and empirically better test conditional coverage and smaller prediction sets on several regression and classification benchmarks compared to prior embedding-only localization methods.

Why it matters

GRAPHLCP is a structure-aware, proximity-based localized conformal prediction framework for GNNs introduced by Peyman Baghershahi, Fangxin Wang, Debmalya Mandal, and Sourav Medya (arXiv 2026-05-08).

Key details

  • The method adds a feature-aware densification step and a Personalized PageRank (PPR)-based kernel for topology-dependent anchor sampling and calibration weighting, explicitly modeling local and long-range graph dependencies.
  • GRAPHLCP provably guarantees marginal coverage with finite samples and, according to experiments on multiple regression and classification datasets, attains improved test conditional coverage and more efficient prediction sets versus embedding-only localization (paper: 20 pages, 9 figures, 8 tables).
Source evidence

Abstract

Conformal prediction (CP) provides a distribution-free approach to uncertainty quantification with finite-sample guarantees. However, applying CP to graph neural networks (GNNs) remains challenging as the combinatorial nature of graphs often leads to insufficiently certain predictions and indiscriminative embeddings. Existing methods primarily rely on embedding-space proximity for localization, which can be unreliable for graphs and yield inefficient prediction sets. We propose GRAPHLCP, a proximity-based localized CP framework that explicitly incorporates graph topology and inter-node dependencies into localization and weighting. Our approach introduces a feature-aware densification step to mitigate locality bias in sparse graphs, followed by a Personalized PageRank-based kernel computation to model structural proximity. This enables topology-dependent anchor sampling and calibration weighting that captures both local and long-range dependencies. Extensive experiments on several regression and classification datasets demonstrate that GRAPHLCP guarantees marginal coverage with finite samples while efficiently attaining favorable test conditional coverage across various conditioning scenarios.

Comment: 20 pages, 9 Figures, 8 Tables