Graph Neural Networks (GNNs) are powerful machine learning prediction models
on graph-structured data. However, GNNs lack rigorous uncertainty estimates,
limiting their reliable deployment in settings where the cost of errors is
significant. We propose conformalized GNN (CF-GNN), extending conformal
prediction (CP) to graph-based models for guaranteed uncertainty estimates.
Given an entity in the graph, CF-GNN produces a prediction set/interval that
provably contains the true label with pre-defined coverage probability (e.g.
90%). We establish a permutation invariance condition that enables the validity
of CP on graph data and provide an exact characterization of the test-time
coverage. Moreover, besides valid coverage, it is crucial to reduce the
prediction set size/interval length for practical use. We observe a key
connection between non-conformity scores and network structures, which
motivates us to develop a topology-aware output correction model that learns to
update the prediction and produces more efficient prediction sets/intervals.
Extensive experiments show that CF-GNN achieves any pre-defined target marginal
coverage while significantly reducing the prediction set/interval size by up to
74% over the baselines. It also empirically achieves satisfactory conditional
coverage over various raw and network features.

本研究提出了一种基于置信度的图神经网络模型 CF-GNN，以保证模型的可靠性，所采用的置信度预测方法即为 conformal prediction，该方法可产生预测区间，该区间内包含了真值标签，该模型通过拓扑感知输出修正模型减少了预测集大小，从而实现了较高的预测精度。