Distribution Free Prediction Sets for Node Classification

Graph Neural Networks (GNNs) are able to achieve high classification accuracy on many important real world datasets, but provide no rigorous notion of predictive uncertainty. Quantifying the confidence of GNN models is difficult due to the dependence between datapoints induced by the graph structure. We leverage recent advances in <PRE_TAG>conformal prediction</POST_TAG> to construct prediction sets for <PRE_TAG>node classification</POST_TAG> in <PRE_TAG>inductive learning</POST_TAG> scenarios. We do this by taking an existing approach for conformal classification that relies on exchangeable data and modifying it by appropriately weighting the conformal scores to reflect the network structure. We show through experiments on standard <PRE_TAG>benchmark datasets</POST_TAG> using popular GNN models that our approach provides tighter and better calibrated <PRE_TAG>prediction sets</POST_TAG> than a naive application of <PRE_TAG>conformal prediction</POST_TAG>.