摘要

本文探讨了图神经网络（GNNs）在链接预测任务中的不确定性量化问题。尽管GNNs在多种任务中表现出色，但在高风险领域的应用常受限于其预测的不确定性。本文首次尝试引入一种无分布假设、模型不可知的不确定性量化方法，为基于GNN的链接预测构建具有统计保证的预测区间，称为“conformalized link prediction”。该方法基于conformal prediction（CP）框架，该框架承诺构建统计稳健的预测集或区间。主要挑战包括：在处理依赖数据（如图）时，CP的关键假设——可交换性是否仍然适用于链接预测；即使可交换性假设有效，如何确保结果预测集或区间足够小以提供有用信息。为解决这些挑战，本文首先理论和实证地建立了链接预测任务中CP应用的排列不变性条件，并进行了精确的测试时间覆盖验证。利用图中的重要结构信息，本文发现图的幂律分布遵循性与CP效率之间的新颖且关键的联系，并开发了一种简单而有效的基于采样的方法，以在标准CP程序之前将图结构与幂律分布对齐。大量实验表明，对于conformalized link prediction，本文的方法在实现所需边际覆盖的同时，显著提高了CP的效率。

原理

本文提出的“conformalized link prediction”方法的核心在于利用conformal prediction（CP）框架来量化基于图神经网络（GNNs）的链接预测任务中的不确定性。CP框架允许构建预测集或区间，同时确保统计稳健的覆盖保证。具体来说，CP使用一组可交换的保留（或校准）数据来构建预测区间，这些区间覆盖真实标签或值的概率至少为1−𝛹?，其中𝛹?是用户指定的未覆盖率。本文的关键创新在于理论和实证地建立了链接预测任务中CP应用的排列不变性条件，并利用图的结构信息，特别是节点度分布的幂律特性，来提高CP的效率。通过选择性地移除特定边并利用剩余边进行链接预测，本文的方法能够生成更符合幂律分布的图结构，从而提高预测区间的效率。

流程

1. 数据准备：将图数据分为训练集、验证集、校准集和测试集。
2. 模型训练：在子图上训练GNN模型，生成节点和边的嵌入。
3. 校准过程：使用校准集数据计算非一致性得分，并构建预测区间。
4. 采样优化：通过采样方法调整图的节点度分布，使其更符合幂律分布。
5. 预测区间构建：利用调整后的图结构重新计算非一致性得分，并构建最终的预测区间。

具体步骤如下：

• 数据分割：将链接集分为训练集、验证集、校准集和测试集。
• 子图构建：构建子图G′，其中G′包含所有节点和部分边。
• 模型训练：在G′上训练GNN模型，生成节点嵌入和边嵌入。
• 采样过程：通过采样方法调整图的节点度分布，使其更符合幂律分布。
• 校准和预测：使用校准集数据计算非一致性得分，并构建预测区间。

应用

本文提出的conformalized link prediction方法在多个领域具有广泛的应用前景，特别是在需要高可靠性预测的高风险领域，如药物发现、金融分析和社交网络分析。通过提供具有统计保证的预测区间，该方法能够帮助决策者更好地评估预测的可靠性，从而做出更明智的决策。此外，该方法的模型不可知性和无分布假设特性使其具有很高的灵活性和适应性，可以与各种GNN模型结合使用，进一步扩展其应用范围。