# Conformal link prediction for false discovery rate control

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

## Key facts

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

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [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)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Controlling the false discovery rate via knockoffs](https://mlsanity.com/paper/1404.5609/) (2014)
- [Uncertainty Quantification over Graph with Conformalized Graph Neural Networks](https://mlsanity.com/paper/2305.14535/) (2023)
- [Selection by Prediction with Conformal p-values](https://mlsanity.com/paper/2210.01408/) (2022)
- [A statistical framework for efficient out of distribution detection in deep neural networks](https://mlsanity.com/paper/2102.12967/) (2021)
- [Conformal Prediction with Missing Values](https://mlsanity.com/paper/2306.02732/) (2023)
- [Imputation and low-rank estimation with Missing Not At Random data](https://mlsanity.com/paper/1812.11409/) (2018)
- [A Two-Sample Conditional Distribution Test Using Conformal Prediction and Weighted Rank Sum](https://mlsanity.com/paper/2010.07147/) (2020)
- [Integrative conformal p-values for powerful out-of-distribution testing with labeled outliers](https://mlsanity.com/paper/2208.11111/) (2022)
- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [Adaptive novelty detection with false discovery rate guarantee](https://mlsanity.com/paper/2208.06685/) (2022)
- [Conformal Prediction for Network-Assisted Regression](https://mlsanity.com/paper/2302.10095/) (2023)
- [Conformalized matrix completion](https://mlsanity.com/paper/2305.10637/) (2023)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [Link prediction for partially observed networks](https://mlsanity.com/paper/1301.7047/) (2013)
- [Modeling heterogeneity in random graphs through latent space models: a selective review](https://mlsanity.com/paper/1402.4296/) (2014)
- [Variational Inference for Stochastic Block Models from Sampled Data](https://mlsanity.com/paper/1707.04141/) (2017)
- [Semi-supervised multiple testing](https://mlsanity.com/paper/2106.13501/) (2021)
- [A Burden Shared is a Burden Halved: A Fairness-Adjusted Approach to Classification](https://mlsanity.com/paper/2110.05720/) (2021)
- [A Power and Prediction Analysis for Knockoffs with Lasso Statistics](https://mlsanity.com/paper/1712.06465/) (2017)

## 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)
- [Conformal confidence sets for biomedical image segmentation](https://mlsanity.com/paper/2410.03406/) (2024)
- [Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training](https://mlsanity.com/paper/2501.02767/) (2025)
- [Volume-Sorted Prediction Set: Efficient Conformal Prediction for Multi-Target Regression](https://mlsanity.com/paper/2503.02205/) (2025)
- [Uncertainty Quantification on Graph Learning: A Survey](https://mlsanity.com/paper/2404.14642/) (2024)
- [Extending Prediction-Powered Inference through Conformal Prediction](https://mlsanity.com/paper/2510.16166/) (2025)
- [Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs](https://mlsanity.com/paper/2409.18332/) (2024)
- [GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs](https://mlsanity.com/paper/2605.08074/) (2026)

## Abstract (arXiv)

Most link prediction methods return estimates of the connection probability of missing edges in a graph. Such output can be used to rank the missing edges from most to least likely to be a true edge, but does not directly provide a classification into true and non-existent. In this work, we consider the problem of identifying a set of true edges with a control of the false discovery rate (FDR). We propose a novel method based on high-level ideas from the literature on conformal inference. The graph structure induces intricate dependence in the data, which we carefully take into account, as this makes the setup different from the usual setup in conformal inference, where data exchangeability is assumed. The FDR control is empirically demonstrated for both simulated and real data.