Benchmarking Graph Conformal Prediction: Empirical Analysis, Scalability, and Theoretical Insights

Modern machine learning models trained on losses based on point predictions are prone to be overconfident in their predictions [Guo et al., 2017]. The Conformal Prediction (CP) framework [Vovk et al., 2005] provides a mechanism for generating statistically sound post hoc prediction sets (or intervals, in case of continuous outcomes) with coverage guarantees under mild assumptions. The usual assumption made in CP is that data are exchangeable, i.e., the joint distribution of the data is invariant to permutations of the data points. CP's guarantees are distribution-free and can be added post hoc to arbitrary black-box predictor scores, making them ideal candidates for quantifying uncertainty in complex models, such as neural networks. Network-structured data such as social networks, transportation networks, and biological networks are ubiquitous in modern data science applications.