GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

Conformal prediction (CP) provides a distribution-free approach to uncertainty quantification (UQ) with finite samples. However, applying CP to graph neural networks (GNNs) remains challenging. The combinatorial nature of graphs makes their encoding non-trivial, leading to insufficiently uncertain prediction logits and indiscriminative embeddings. Existing methods mostly rely on the embedding space for conformal prediction, which can be unreliable for graphs and often yields inefficient prediction sets. We propose GRAPHLCP, a structure-aware weighted conformal prediction framework that explicitly incorporates the graph topology and inter-node dependencies into localization and weighting. Based on experimental results that show a strong correlation between node homophily and sample coverage, we propose GRAPHLCP that utilizes a feature-aware densification followed by Personalized PageRank–based kernel computation to model structural proximity between nodes. Accounting for both structural and feature similarity allows GRAPHLCP to efficiently guarantee marginal coverage while attaining favorable test conditional coverage across extensive experiments on multiple datasets for both regression and classification.