# Conformalized Link Prediction on Graph Neural Networks

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 26 Jun 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?](https://mlsanity.com/paper/1703.04977/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Confident Adaptive Language Modeling](https://mlsanity.com/paper/2207.07061/) (2022)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning](https://mlsanity.com/paper/2003.07329/) (2020)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration](https://mlsanity.com/paper/2109.14285/) (2021)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Selection by Prediction with Conformal p-values](https://mlsanity.com/paper/2210.01408/) (2022)
- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [What Makes Graph Neural Networks Miscalibrated?](https://mlsanity.com/paper/2210.06391/) (2022)
- [Confidence May Cheat: Self-Training on Graph Neural Networks under Distribution Shift](https://mlsanity.com/paper/2201.11349/) (2022)
- [Neural Link Prediction with Walk Pooling](https://mlsanity.com/paper/2110.04375/) (2021)
- [Distribution Free Prediction Sets for Node Classification](https://mlsanity.com/paper/2211.14555/) (2022)
- [Principal Uncertainty Quantification with Spatial Correlation for Image Restoration Problems](https://mlsanity.com/paper/2305.10124/) (2023)
- [Uncertainty-aware Attention Graph Neural Network for Defending Adversarial Attacks](https://mlsanity.com/paper/2009.10235/) (2020)
- [Calibration of Natural Language Understanding Models with Venn--ABERS Predictors](https://mlsanity.com/paper/2205.10586/) (2022)
- [Examining the Effects of Degree Distribution and Homophily in Graph Learning Models](https://mlsanity.com/paper/2307.08881/) (2023)
- [Unveiling the Role of Message Passing in Dual-Privacy Preservation on GNNs](https://mlsanity.com/paper/2308.13513/) (2023)

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

- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Trustworthy Classification through Rank-Based Conformal Prediction Sets](https://mlsanity.com/paper/2407.04407/) (2024)
- [Relational Conformal Prediction for Correlated Time Series](https://mlsanity.com/paper/2502.09443/) (2025)
- [Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs](https://mlsanity.com/paper/2409.18332/) (2024)
- [Devil's Hand: Data Poisoning Attacks to Locally Private Graph Learning Protocols](https://mlsanity.com/paper/2506.09803/) (2025)
- [Graph Sparsification for Enhanced Conformal Prediction in Graph Neural Networks](https://mlsanity.com/paper/2410.21618/) (2024)
- [Quantile-Free Uncertainty Quantification in Graph Neural Networks](https://mlsanity.com/paper/2605.04847/) (2026)
- [GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs](https://mlsanity.com/paper/2605.08074/) (2026)
- [A Survey on GNN-based Link Prediction: Techniques, Applications, and Challenges](https://mlsanity.com/paper/2607.16198/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications in high-stakes domains are often hampered by unreliable predictions. Although numerous uncertainty quantification methods have been proposed to address this limitation, they often lack textitrigorous uncertainty estimates. This work makes the first attempt to introduce a distribution-free and model-agnostic uncertainty quantification approach to construct a predictive interval with a statistical guarantee for GNN-based link prediction. We term it as textitconformalized link prediction. Our approach builds upon conformal prediction (CP), a framework that promises to construct statistically robust prediction sets or intervals. We first theoretically and empirically establish a permutation invariance condition for the application of CP in link prediction tasks, along with an exact test-time coverage. Leveraging the important structural information in graphs, we then identify a novel and crucial connection between a graph's adherence to the power law distribution and the efficiency of CP. This insight leads to the development of a simple yet effective sampling-based method to align the graph structure with a power law distribution prior to the standard CP procedure. Extensive experiments demonstrate that for conformalized link prediction, our approach achieves the desired marginal coverage while significantly improving the efficiency of CP compared to baseline methods.