Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications
in high-stakes domains are often hampered by unreliable predictions. Although
numerous uncertainty quantification methods have been proposed to address this
limitation, they often lack \textit{rigorous} uncertainty estimates. This work
makes the first attempt to introduce a distribution-free and model-agnostic
uncertainty quantification approach to construct a predictive interval with a
statistical guarantee for GNN-based link prediction. We term it as
\textit{conformalized link prediction.} Our approach builds upon conformal
prediction (CP), a framework that promises to construct statistically robust
prediction sets or intervals. We first theoretically and empirically establish
a permutation invariance condition for the application of CP in link prediction
tasks, along with an exact test-time coverage. Leveraging the important
structural information in graphs, we then identify a novel and crucial
connection between a graph's adherence to the power law distribution and the
efficiency of CP. This insight leads to the development of a simple yet
effective sampling-based method to align the graph structure with a power law
distribution prior to the standard CP procedure. Extensive experiments
demonstrate that for conformalized link prediction, our approach achieves the
desired marginal coverage while significantly improving the efficiency of CP
compared to baseline methods.

这篇论文介绍了一种无分布和无模型偏见的不确定性量化方法，用于构建基于 GNN 的链接预测的具有统计保证的预测区间，该方法在遵循幂律分布的图结构上显著提高了基线方法的有效性。

图神经网络上的等度连通预测

Conformalized Link Prediction on Graph Neural Networks

Ensemble learning is widely used in applications to make predictions in
complex decision problems---for example, averaging models fitted to a sequence
of samples bootstrapped from the available training data. While such methods
offer more accurate, stable, and robust predictions and model estimates, much
less is known about how to perform valid, assumption-lean inference on the
output of these types of procedures. In this paper, we propose the
jackknife+-after-bootstrap (J+aB), a procedure for constructing a predictive
interval, which uses only the available bootstrapped samples and their
corresponding fitted models, and is therefore "free" in terms of the cost of
model fitting. The J+aB offers a predictive coverage guarantee that holds with
no assumptions on the distribution of the data, the nature of the fitted model,
or the way in which the ensemble of models are aggregated---at worst, the
failure rate of the predictive interval is inflated by a factor of 2. Our
numerical experiments verify the coverage and accuracy of the resulting
predictive intervals on real data.

提出了一种基于 Jackknife + 和 Bootstrap 的预测区间构建方法 (J+aB)，该方法只使用可用的 Bootstrap 样本及其对应的拟合模型，可以在不假设数据分布，拟合模型的性质或集成模型聚合方式的情况下提供保证，并可以免费进行模型拟合，实验结果验证了预测区间的覆盖率和准确性。