[Paper] GRAPHLCP：结构感知的图上局部化 Conformal Prediction

Source: arXiv - 2605.08074v1

概述

图神经网络（GNN）已成为处理关系数据的首选工具，但对其预测不确定性的量化仍是一个未解决的问题。论文 GRAPHLCP: Structure‑Aware Localized Conformal Prediction on Graphs 提出了一种新的符合图结构的局部化保守预测（CP）框架，该框架尊重底层图拓扑，提供有限样本覆盖保证，同时生成的预测集合比以往方法更紧凑。

关键贡献

• 拓扑感知定位: 将节点特征与图结构（通过 Personalized PageRank）相结合，以定义对 CP 更有意义的“邻域”概念。
• 特征感知稠密化: 一种预处理步骤，丰富图的稀疏区域，降低当局部数据稀缺时产生的偏差。
• 自适应校准加权: 使用结构接近度分数为校准样本加权，使方法能够捕获短程和长程依赖。
• 理论保证: 在有限样本下证明边际覆盖，并提供在多种条件下改进条件覆盖的实证证据。
• 广泛的实证验证: 在多个回归和分类图数据集上的基准测试表明，GRAPHLCP 能够在保持所需覆盖水平的同时，持续产生更小、更具信息量的预测集合。

方法论

1. 嵌入与密集化

   • 每个节点首先使用标准 GNN（例如 GCN、GraphSAGE）进行嵌入。
   • 在图的稀疏部分，方法注入从邻近特征分布中衍生的合成“锚点”，以降低节点校准邻居过少的风险。

2. 通过 Personalized PageRank (PPR) 的结构邻近性

   • 对于任意测试节点，计算其 PPR 向量，得到到每个其他节点的加权可达性分数。
   • 这些分数作为核函数，量化每个校准节点相对于测试节点的“接近程度”，不仅在嵌入空间，还在图拓扑上。

3. 局部校准

   • 从训练集中收集校准残差（例如回归的绝对误差）。
   • 每个残差被赋予一个权重，该权重与其基于 PPR 的与测试节点的邻近程度成比例。

4. 预测集合构建

   • 将校准残差的加权经验分位数作为共形阈值。
   • 对于分类，同样的加权方案应用于类别得分，以生成一组可能的标签。

由于加权同时考虑了特征相似性和图连通性，得到的预测集合在“局部化”上能够反映数据的真实依赖结构。

结果与发现

• 覆盖率: 所有实验均满足或超过规定的边际覆盖率，验证了理论保证。
• 条件覆盖率: 在以节点度、社区成员或特征密度为条件时，GRAPHLCP 的覆盖率仍接近目标，而朴素的 CP（仅基于嵌入）常常对高阶节点覆盖不足。
• 效率: 预测集平均缩小 30‑45 %，从而在后续任务中更具决定性（例如，需要检查的候选标签更少）。

实际意义

• 更安全的 GNN‑基于服务部署： 无论是推荐好友、标记欺诈交易，还是预测分子属性，GRAPHLCP 都为您提供校准的置信区间或标签集合，尊重数据的关系结构。
• 主动学习与数据获取： 更小且可靠的预测集合可用于优先决定下一个标记哪些节点，将精力集中在图中最不确定或影响最大的区域。
• 模型无关插件： 该框架可与任何现成的 GNN 编码器配合使用；您只需运行一次 PPR 计算（通过幂迭代高效近似）以及密集化步骤。
• 合规监管： 在金融或医疗等需强制解释性和风险界限的领域，GRAPHLCP 在不假设任何分布形式的前提下提供有限样本保证。

限制与未来工作

• 精确 PPR 的可扩展性: 计算全图 PPR 向量在大规模图上可能代价高昂；作者依赖近似方法，这可能影响权重的紧致性。
• 密集化启发式: 合成锚点生成是启发式的；其效果可能在特征空间高度异构的领域中有所不同。
• 对动态图的扩展: 当前的公式假设图是静态的；处理不断演化的边结构需要对邻近核进行增量更新。
• 更广泛的不确定性度量: 未来研究可以探索将其他不确定性量化方法（例如贝叶斯 GNN）与拓扑感知 CP 框架结合，以进一步提升条件覆盖率。

GRAPHLCP 弥合了严格不确定性量化与图数据关系特性之间的关键鸿沟，为开发者提供了一个实用工具，使 GNN 预测既可信又可操作。

作者

• Peyman Baghershahi
• Fangxin Wang
• Debmalya Mandal
• Sourav Medya

论文信息

• arXiv ID: 2605.08074v1
• 分类: cs.LG
• 发表时间: 2026年5月8日
• PDF: 下载 PDF