🤖 machine learning

GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

本文提出了 GRAPHLCP，这是一种面向图神经网络的感知结构的局部共形预测框架，它通过特征感知的稠密化与基于个性化 PageRank 的核函数，将图拓扑结构与节点间依赖关系相融合，从而实现具备改进的条件覆盖率的、高效的、有限样本保证的不确定性量化。

原作者： Peyman Baghershahi, Fangxin Wang, Debmalya Mandal, Sourav Medya

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Peyman Baghershahi, Fangxin Wang, Debmalya Mandal, Sourav Medya

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一个非常聪明的机器人（图神经网络），它观察一个复杂的连接网络——比如社交网络、道路地图或化学分子——并做出预测。也许它会猜测某人下一条动态会发什么，或者预测某个特定社区的房价。

问题在于，这个机器人往往过于自信。它只给你一个单一的答案，却不告诉你它有多大的把握。在高风险情境下（如侦测欺诈或预测天气），出错是危险的。

共形预测（Conformal Prediction）是一个安全网。它不是给出一个答案，而是给你一个可能答案的列表（即“预测集”）。它承诺：“我有 90% 的把握，真实答案在这个列表中。”

然而，将这种安全网应用于图数据却充满挑战。以下是原因，以及作者的新方法GRAPHLCP如何解决这一问题。

问题所在：“模糊照片”与“孤立岛屿”

现有方法试图通过查看节点的“嵌入”（embeddings）来判断两个节点（图上的点）有多相似。你可以把嵌入想象成节点特征的模糊照片。

模糊性：由于机器人一次性处理整个图，照片变得模糊（这种现象称为“过平滑”）。两个截然不同的节点在这张模糊照片中可能看起来几乎一模一样。
孤立性：如果图很稀疏（比如一个道路很少的小镇），机器人无法看得足够远，从而无法真正了解它的邻居是谁。它会将远处的节点视为不存在。

当你试图利用这些模糊照片构建安全网时，会导致两种糟糕的结果：

“包罗万象”的列表：机器人认为一切看起来都差不多，因此生成的预测集大得毫无用处（例如：“答案在 0 到 100 之间的任何地方”）。
“空无一物”的列表：机器人认为测试节点完全独特，没有任何相似的邻居，因此给你一个极小且高风险的列表，可能会遗漏真实答案。

解决方案：GRAPHLCP（“智能邻里向导”）

作者提出了GRAPHLCP，它不再依赖模糊照片，而是开始利用实际地图（图结构）来决定谁与谁相似。

以下是其工作原理，分步说明，并辅以生动的类比：

1. “地图修复”（特征感知稠密化）

想象你身处一个安静的小村庄（稀疏图），道路破损，你无法清晰地看到你的邻居。

GRAPHLCP 的做法：在尝试寻找相似的人之前，它会在那些特征相似（比如穿着相同的衬衫）的人之间临时搭建新的、临时的桥梁，即使他们在地图上并没有直接相连。
原因：这解决了“孤立岛屿”问题。它确保机器人能看到更广阔的邻里范围，弥合稀疏区域的断层，使其不会因孤立无援而困惑。

2. “个性化导游”（个性化 PageRank）

一旦地图修复完毕，机器人就需要挑选一位“邻居”来协助预测。旧方法只是在模糊照片中挑选离得最近的人。

GRAPHLCP 的做法：它使用一种称为个性化 PageRank（PPR）的方法。想象你就是测试节点。你派出一位“导游”，从你家开始随机行走。
- 导游在任何一步都有机会停下来，说：“这个人是我的邻居！”
- 如果导游继续行走，他可能会访问更远的人，但他更有可能在那些通过多条路径真正与你相连的人那里停下来。
原因：这捕捉到了长程连接。它意识到，即使两个人不是直接邻居，他们也可能通过一串朋友相连。这比仅仅查看模糊照片要可靠得多。

3. “加权投票”

现在，机器人向这些“邻居”寻求帮助。

旧方法：“照片中所有看起来相似的人拥有平等的投票权。”（这很糟糕，因为照片是模糊的）。
GRAPHLCP 的方法：“那些在结构上离你更近（通过导游路径）的邻居拥有更多的投票权。”
结果：机器人基于最相关、结构上相连的邻居构建预测集。这创造了一个既紧凑到有用，又宽广到安全的列表。

结果：他们发现了什么？

作者在15 个不同的数据集（包括社交网络、引文图和地理数据）上测试了该方法。

安全第一：GRAPHLCP 成功兑现了承诺。如果它说“我有 90% 的把握”，那么真实答案就有 90% 的概率在列表中，即使数据量很小也是如此。
效率：与其他方法不同（那些方法要么让列表过大而浪费时间，要么让列表过小而产生风险），GRAPHLCP 找到了“恰到好处”的区间。列表的大小刚刚好。
处理怪异情况：它在连接混乱的图上表现尤为出色，或者在“模糊照片”方法完全失效的情况下表现优异。

总结

可以将GRAPHLCP视为对机器人安全系统的升级。它不再问“在这张模糊照片中谁长得像我？”，而是问“在现实世界中谁真正与我相连，以及我可以通过一串朋友联系到谁？”。通过使用实际的连接地图并先修复破损的道路，它为预测构建了一个更聪明、更可靠的安全网。

技术摘要：GRAPHLCP

问题陈述

图神经网络（GNN）正日益部署于药物发现、天气预测和欺诈检测等高风险领域，这要求具备可靠的量化不确定性（UQ）能力。共形预测（CP）提供了一个分布无关的框架，用于构建具有有限样本保证的集合预测。然而，将 CP 应用于 GNN 面临着独特的挑战：

结构依赖性：图中的节点天然存在依赖性，这违反了经典 CP 所需的独立同分布（i.i.d.）假设。
嵌入局限性：现有的图局部化 CP 方法通常依赖嵌入空间邻近性（例如，在 GNN 嵌入上进行核密度估计）来定义局部邻域。由于以下原因，这种方法往往不可靠：
- 过度平滑：深度的消息传递降低了相似性度量的方差，使得嵌入缺乏区分度。
- 过度压缩：拓扑瓶颈限制了全局信息流，特别是在异配性（heterophily）条件下。
- 置信度不足：GNN 在所学表示中往往表现出分离性不足。
现有解决方案的低效性：当前的特定图 CP 方法要么依赖训练辅助模型（增加了计算开销），要么使用僵化的结构划分（例如硬聚类），无法捕捉细粒度的局部异配性。因此，现有方法在复杂拓扑中往往产生过于保守或局部化不足的预测集。

方法论：GRAPHLCP

作者提出了GRAPHLCP，这是一种基于邻近性的局部化共形预测框架，旨在将图拓扑和节点间依赖性显式地纳入局部化和加权步骤。该方法在 GNN 已预训练并冻结的直推式（transductive）设置下运行。该框架包含四个关键阶段：

1. 特征感知致密化

为了缓解稀疏图中的局部偏差并捕捉长程语义依赖，作者在核计算之前引入了致密化步骤。

PCA 投影：首先通过主成分分析（PCA）对节点嵌入进行投影，以解耦相关的特征维度并压缩空间，解决由过度平滑引起的噪声和冗余问题。
自适应各向异性核：利用 PCA 变换后的嵌入构建各向异性高斯核。带宽根据协方差矩阵的特征值进行调整，以考虑各维度间变化的尺度。
边增强：如果非连接节点之间的相似性（通过高斯核计算）超过动态阈值 $\tau_d$ ，则向图邻接矩阵添加新边。该阈值根据图的同配率自动调整，以平衡信息边的添加与噪声的引入。

2. 个性化 PageRank (PPR) 核

GRAPHLCP 利用 PPR 来建模结构邻近性，而不仅仅依赖嵌入距离。

局部化：PPR 通过重启概率（ $\beta$ ）在保持局部性的同时捕捉多跳影响。它提供了一种软性的、概率性的邻近概念，自然地与加权 CP 相一致。
采样：对于测试节点，从以该测试节点为中心的 PPR 诱导分布中采样一个锚点节点。这确保了邻近节点对分位数估计产生更大的影响。
加权：校准节点和测试节点根据其相对于采样锚点的结构邻近性进行加权。作者利用 PPR 的度归一化对称性（ $d_i H(u_i, u_j) = d_j H(u_j, u_i)$ ）来高效计算权重，即使在校准样本数量超过测试样本数量时也是如此。

3. 随机化局部化共形预测 (RLCP) 集成

GRAPHLCP 适配了 RLCP 框架。通过从测试节点 $u_{n+1}$ 的 PPR 分布中采样一个锚点节点 $\tilde{u}_{n+1}$ ，该方法基于非一致性分数的加权分位数构建预测集。权重源自相对于采样锚点的 PPR 分数，使该方法能够适应局部图上下文。

4. 预测构建

最终预测集 $\hat{C}_n(u_{n+1})$ 被构建为满足非一致性分数 $s(u_{n+1}, y)$ 小于或等于加权分位数 $\hat{q}_{1-\alpha}$ 的标签 $y$ 的集合。该分位数是使用源自 PPR 核的权重以及校准集的非一致性分数计算得出的。

主要贡献

结构感知局部化：本文通过将仅基于嵌入的邻近性替换为基于 PPR 的核，弥合了结构局部化与特征局部化之间的差距。这显式地将图拓扑纳入共形加权过程。
特征感知致密化：一种新颖的预处理步骤，利用嵌入相似性（通过 PCA 和自适应各向异性核）增强图拓扑，以缓解稀疏性并捕捉长程依赖，而无需依赖可能充满噪声的嵌入连续加权。
高效加权方案：该方法提供了一种高效计算无向图 PPR 权重的方式，通过利用度归一化对称性，避免了为大型校准集计算完整 PPR 向量的计算低效问题。
理论有效性：该方法保持了直推式设置中边际覆盖所需的交换性保证，同时旨在改善松弛的测试条件覆盖。

实验结果

作者在七个节点回归和八个节点分类数据集（包括引文网络、亚马逊共同购买数据集和地理数据集）上评估了 GRAPHLCP。

边际覆盖：所有方法（包括 GRAPHLCP）均满足目标未覆盖率（ $\alpha = 0.1$ ），证实了该方法的有效性。
条件覆盖 (WSC)：在最坏情况平板（WSC）诊断中（该诊断对抗性地寻找投影方向上的最小覆盖），GRAPHLCP 在大多数数据集上取得了最佳或次佳结果，优于 CalLCP、RLCP 和 SCP 等基线。
基于分组的覆盖：GRAPHLCP 在基于同配性、特征聚类、聚类系数和节点度数的划分中表现出更优越的覆盖性。该方法在同配性较低的区域特别有效，而标准方法在这些区域往往表现不佳。
预测效率：虽然 CalLCP 通常产生过大的预测集（过度覆盖），但 GRAPHLCP 实现了有利的归一化预测长度，在覆盖率和集合大小之间提供了更好的权衡。
消融研究：
- 将 PPR 核替换为高斯核（GSS）导致覆盖率降低和预测集变大，证实了结构感知局部化的重要性。
- 致密化步骤被确定为最重要的组件，特别是在回归任务中。
- PCA 投影被证明对于缓解相关嵌入特征的负面影响至关重要。

意义与主张

本文声称，GRAPHLCP 通过显式建模结构依赖性，成功解决了现有图 CP 方法的局限性。通过将权重与可能有损的 GNN 编码器解耦，并利用基于 PPR 的核，该方法为不确定性量化创建了一条“低噪声残差路径”。

作者断言，GRAPHLCP 保证了有限样本下的边际覆盖，同时高效地在各种条件场景下实现了有利的测试条件覆盖。他们强调，该方法在复杂拓扑中特别稳健，在这些拓扑中，基于嵌入的相似性会因过度平滑或过度压缩而失效。这项工作强调了结构感知局部化对于图有效 UQ 的必要性，超越了仅依赖特征空间邻近性的局限。作者谦逊地指出，未来的方向包括将此框架扩展到具有演化拓扑的动态图。