Conformal Network Link Prediction with False Discovery Rate Control under Unstructured Missingness

2025/07/09 by Wenqin Du, Wanteng Ma, Du, Wenqin +7
Computer Science · Physics and Astronomy · Psychology · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Mental Health Research Topics #Methodology (stat.ME) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2507.07025

openalex publication_date 2025/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We propose a new method for predicting multiple missing links in partially observed networks while controlling the false discovery rate (FDR), a largely unresolved challenge in network analysis. The main difficulty lies in handling complex dependencies and unknown missing patterns. We introduce conformal link prediction, a distribution-free procedure grounded in the exchangeability structure of weighted graphon models. Our approach constructs conformal p-values via a novel multi-splitting strategy that restores exchangeability within local test sets, thereby ensuring valid row-wise FDR control, even under unknown missing mechanisms. To achieve FDR control across all missing links, we further develop a new aggregation scheme based on e-values, which accommodates arbitrary dependence across network predictions. Our method requires no assumptions on the missing rates, applies to weighted, unweighted, undirected, and bipartite networks, and enjoys finite-sample theoretical guarantees. Extensive simulations and real-world data study confirm the effectiveness and robustness of the proposed approach.

Citations

• Improved thresholds for e-values
• Conformalized Link Prediction on Graph Neural Networks
• Structured Conformal Inference for Matrix Completion with Applications to Group Recommender Systems
• FDR control and FDP bounds for conformal link prediction
• Conformal link prediction for false discovery rate control
• Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern
• Conformalized matrix completion
• Derandomized Novelty Detection with FDR Control via Conformal E-values
• Selection by Prediction with Conformal p-values
• E-values as unnormalized weights in multiple testing
• False discovery rate control with e-values
• Conformal Inference of Counterfactuals and Individual Treatment Effects
• Large Dimensional Latent Factor Modeling with Missing Observations and Applications to Causal Inference
• Conformal Prediction Under Covariate Shift
• Graphical Models for Processing Missing Data
• Rates of Convergence of Spectral Methods for Graphon Estimation
• Distribution-Free Predictive Inference For Regression
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Estimating network edge probabilities by neighborhood smoothing
• 1-Bit Matrix Completion
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion
• Robust Principal Component Analysis?
• Robust principal component analysis?

Related

• Conformal link prediction for false discovery rate control
• FDR control and FDP bounds for conformal link prediction
• Conformalized Link Prediction on Graph Neural Networks
• Conformal Prediction for Federated Graph Neural Networks with Missing Neighbor Information
• Synthetic graphs for link prediction benchmarking