# Similarity-Navigated Conformal Prediction for Graph Neural Networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 54 references that are in the map.
- First posted on arXiv 23 May 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?](https://mlsanity.com/paper/1703.04977/) (2017)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (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)
- [Graph Neural Network for Traffic Forecasting: A Survey](https://mlsanity.com/paper/2101.11174/) (2021)
- [Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning](https://mlsanity.com/paper/2003.07329/) (2020)
- [Node Similarity Preserving Graph Convolutional Networks](https://mlsanity.com/paper/2011.09643/) (2020)
- [Calibration of Neural Networks using Splines](https://mlsanity.com/paper/2006.12800/) (2020)
- [Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration](https://mlsanity.com/paper/2109.14285/) (2021)
- [Graph Representation Learning in Biomedicine](https://mlsanity.com/paper/2104.04883/) (2021)
- [Uncertainty Quantification over Graph with Conformalized Graph Neural Networks](https://mlsanity.com/paper/2305.14535/) (2023)
- [Simplifying approach to Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2111.06748/) (2021)
- [Conformal Prediction for Deep Classifier via Label Ranking](https://mlsanity.com/paper/2310.06430/) (2023)
- [What Makes Graph Neural Networks Miscalibrated?](https://mlsanity.com/paper/2210.06391/) (2022)

## Built on by (most cited first, 7 of 7)

- [HeAD-CP: Heterophily-Aware Diffused Conformal Prediction Sets for Graph Neural Networks](https://mlsanity.com/paper/2607.25273/) (2026)
- [Semi-Supervised Conformal Prediction With Unlabeled Nonconformity Score](https://mlsanity.com/paper/2505.21147/) (2025)
- [Conformalized Gaussian processes for online uncertainty quantification over graphs](https://mlsanity.com/paper/2510.06181/) (2025)
- [CONTINA: Confidence Interval for Traffic Demand Prediction with Coverage Guarantee](https://mlsanity.com/paper/2504.13961/) (2025)
- [Softmax is not Enough (for Adaptive Conformal Classification)](https://mlsanity.com/paper/2602.19498/) (2026)
- [GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs](https://mlsanity.com/paper/2605.08074/) (2026)
- [Temporal Graph Prototype-conditioned Conformal Prediction for Fraud Detection](https://mlsanity.com/paper/2608.15768/) (2026)

## Abstract (arXiv)

Graph Neural Networks have achieved remarkable accuracy in semi-supervised node classification tasks. However, these results lack reliable uncertainty estimates. Conformal prediction methods provide a theoretical guarantee for node classification tasks, ensuring that the conformal prediction set contains the ground-truth label with a desired probability (e.g., 95%). In this paper, we empirically show that for each node, aggregating the non-conformity scores of nodes with the same label can improve the efficiency of conformal prediction sets while maintaining valid marginal coverage. This observation motivates us to propose a novel algorithm named Similarity-Navigated Adaptive Prediction Sets (SNAPS), which aggregates the non-conformity scores based on feature similarity and structural neighborhood. The key idea behind SNAPS is that nodes with high feature similarity or direct connections tend to have the same label. By incorporating adaptive similar nodes information, SNAPS can generate compact prediction sets and increase the singleton hit ratio (correct prediction sets of size one). Moreover, we theoretically provide a finite-sample coverage guarantee of SNAPS. Extensive experiments demonstrate the superiority of SNAPS, improving the efficiency of prediction sets and singleton hit ratio while maintaining valid coverage.