# GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

arXiv: https://arxiv.org/abs/2605.08074 · HTML: https://mlsanity.com/paper/2605.08074/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 47 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 30 of 32)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [A Tutorial on Principal Component Analysis](https://mlsanity.com/paper/1404.1100/) (2014)
- [GOOD: A Graph Out-of-Distribution Benchmark](https://mlsanity.com/paper/2206.08452/) (2022)
- [Localized Conformal Prediction: A Generalized Inference Framework for Conformal Prediction](https://mlsanity.com/paper/2106.08460/) (2021)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration](https://mlsanity.com/paper/2109.14285/) (2021)
- [Uncertainty Quantification over Graph with Conformalized Graph Neural Networks](https://mlsanity.com/paper/2305.14535/) (2023)
- [On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks](https://mlsanity.com/paper/2212.02374/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Conformal prediction with local weights: randomization enables local guarantees](https://mlsanity.com/paper/2310.07850/) (2023)
- [PotentialNet for Molecular Property Prediction](https://mlsanity.com/paper/1803.04465/) (2018)
- [Exchangeability, Conformal Prediction, and Rank Tests](https://mlsanity.com/paper/2005.06095/) (2020)
- [What Makes Graph Neural Networks Miscalibrated?](https://mlsanity.com/paper/2210.06391/) (2022)
- [Distribution Free Prediction Sets for Node Classification](https://mlsanity.com/paper/2211.14555/) (2022)
- [Graph Neural Networks for Financial Fraud Detection: A Review](https://mlsanity.com/paper/2411.05815/) (2024)
- [Conformal Prediction for Network-Assisted Regression](https://mlsanity.com/paper/2302.10095/) (2023)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [Conformal Inductive Graph Neural Networks](https://mlsanity.com/paper/2407.09173/) (2024)
- [Conformal link prediction for false discovery rate control](https://mlsanity.com/paper/2306.14693/) (2023)
- [Conformalized Link Prediction on Graph Neural Networks](https://mlsanity.com/paper/2406.18763/) (2024)
- [Trust your neighbors: A comprehensive survey of neighborhood-based methods for recommender systems](https://mlsanity.com/paper/2109.04584/) (2021)
- [Similarity-Navigated Conformal Prediction for Graph Neural Networks](https://mlsanity.com/paper/2405.14303/) (2024)

## Abstract (arXiv)

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.