当共形预测遇上图神经网络：用 Personalized PageRank 给不确定性画一张"地图"

一个尴尬的处境

想象你是一个银行风控员，手里有一张庞大的转账网络图。图神经网络（GNN）告诉你：节点 A 的欺诈概率是 0.87。你问：这个 0.87 有多靠谱？是 0.87±0.03，还是 0.87±0.5？GNN 沉默了。它只给点估计，不给区间。

共形预测（Conformal Prediction, CP）本来是解决这个问题的金钥匙——它能在几乎不做任何分布假设的前提下，给你一个有限样本保证的预测区间。但把 CP 搬到图上，却遇到了一个尴尬：图上的节点天生不独立。你的转账网络里，A 的标签和它邻居 B 的标签高度相关，这违反了 CP 赖以成立的可交换性假设。

更尴尬的是，现有的图上 CP 方法大多依赖 GNN 学到的嵌入向量来做"局部化"——也就是给离测试样本近的校准样本更高的权重。但 GNN 的嵌入常常是"失真"的：过平滑让所有节点长得越来越像，过挤压让远处的信息传不过来。用一个失真的地图去导航，结果只能是迷路。

GraphLCP 的核心洞察：换一张地图

GraphLCP 的作者们来自 UIC 和 Warwick，他们提出了一个看似简单却直击要害的问题：既然嵌入空间的距离不可靠，为什么不直接用图本身的结构？

论文的关键洞察是：嵌入空间是 GNN 编码后的"有损压缩"，而图拓扑是原始的"无损信号"。与其在失真的嵌入空间里量距离，不如在原始的图结构上量影响力。

具体来说，GraphLCP 用 Personalized PageRank（PPR）替代高斯核作为局部化函数。PPR 是 PageRank 的个性化版本：从某个种子节点出发做随机游走，每一步以概率 β 重启回种子节点。这个简单的随机过程捕捉了多跳的结构影响力，同时保留了局部性。

为什么 PPR 比嵌入距离更好？论文给出了一个精妙的论证：

• 嵌入距离的问题：GNN 的过平滑会让所有节点的嵌入趋于一致，距离的方差消失，权重退化成均匀分布——这等价于什么都没做，退回了标准 CP。
• PPR 的优势：它直接在图上传播，不经过 GNN 的有损编码。即使 GNN 训练得一塌糊涂，图结构本身的信息还在。

三板斧：PPR + 致密化 + 自适应带宽

但故事没这么简单。PPR 在稀疏图上会"短路"——随机游走没几步就概率耗尽，远处的节点权重几乎为零。这导致 PPR 在稀疏图上过度局部化，反而不如嵌入距离。

GraphLCP 的解决方案是三步走：

第一步：图致密化（Densification）。在算 PPR 之前，先用嵌入相似度给图加边。但这里有个微妙之处：嵌入距离太 noisy 不能用来做连续加权，但用来做离散的"加边/不加边"决策却足够可靠。论文的论证非常漂亮——PPR 作为多跳扩散过程，对噪声的鲁棒性远高于连续核函数。所以策略是：用嵌入做粗粒度的"桥梁连接"，用 PPR 做细粒度的"影响力传播"。

第二步：PCA 降维。GNN 嵌入的维度间高度相关，直接用高斯核会放大噪声。PCA 把嵌入投影到主成分空间，保留最大方差的方向，滤掉高频噪声。这步还附带一个好处：每个主成分的方差就是对应的特征值，可以直接用作各向异性高斯核的自适应带宽。

第三步：各向异性高斯核。不同维度的尺度不同，用各向异性核（Mahalanobis 距离）替代各向同性核，让加边决策更精准。

锚点采样：从"最近邻"到"随机游走落点"

GraphLCP 的另一个创新在于锚点采样。RLCP（Randomly Localized Conformal Prediction）框架要求在测试样本附近随机采一个锚点，然后以锚点为中心做加权分位数计算。在欧式空间里，这很简单——从高斯分布里采一个扰动点。

但在图上，"测试样本附近"是什么意思？GraphLCP 的回答是：从测试节点出发做一次 PPR 随机游走，落点就是锚点。这把欧式空间的高斯扰动自然推广到了图空间——随机游走的长度服从几何分布，落点分布就是 PPR 向量。

这个设计有一个数学上的优雅之处：PPR 本身就是一个合法的概率分布（对节点求和为 1），可以直接作为 RLCP 框架里的局部化核。不需要任何额外的归一化或近似。

实验结果：覆盖率和效率的双赢

论文在 7 个回归数据集和 8 个分类数据集上做了实验，miscoverage rate α=0.1。核心发现：

1. 最坏情况覆盖率（WSC）：GraphLCP 在大多数数据集上达到最优或次优，特别是在大图上表现突出。致密化机制让它能捕捉长程语义依赖。 2. 预测区间长度：即使 WSC 不是第一，GraphLCP 的预测区间也显著更短。这意味着在同样的覆盖率保证下，它给出的预测更"有信息量"。 3. 分组覆盖率：按同质性（homophily）和特征聚类分组时，GraphLCP 的优势尤其明显——这正是结构感知加权的用武之地。

消融实验验证了三个组件的贡献：PPR 核比高斯核好，致密化在稀疏图上关键，PCA 降维在小图上也有提升。

一个更深的洞察：离散 vs 连续

这篇论文最值得记住的洞察，不是 PPR 本身，而是关于"何时用离散、何时用连续"的方法论：

> 嵌入距离太 noisy 不能做连续加权，但足够做离散的加边决策；PPR 作为多跳扩散过程，对噪声的鲁棒性远高于连续核函数。

这其实是一个很普遍的工程智慧：当信号质量不够时，先做粗粒度的离散决策（保留高置信度的信息），再做细粒度的连续计算。就像图像处理里，先做边缘检测（离散）再做模糊（连续），顺序不能反。

GraphLCP 把这个智慧用在了图不确定性量化上：用嵌入相似度加边（离散、粗粒度），用 PPR 传播权重（连续、细粒度）。这个"离散桥梁 + 连续传播"的范式，可能适用于更多"有损编码器 + 结构数据"的场景。

局限与展望

论文坦诚地讨论了局限：PPR 的不对称性在无向图上可以用度归一化对称化，但有向图上还没解决；致密化阈值的选择依赖经验启发式；方法目前只适用于直推式（transductive）设置。

但瑕不掩瑜。GraphLCP 提出了一个清晰、可操作的方法论：当编码器不可信时，回到原始结构。这个思路不仅适用于 GNN 的不确定性量化，也适用于任何"有损表示 + 结构数据"的场景——比如分子图的性质预测、知识图谱的链接预测、社交网络的社区检测。

下次当你的 GNN 给出一个让你不安的预测时，记住：图本身就在那里，它比 GNN 的嵌入更诚实。GraphLCP 教我们的，是如何听懂图在说什么。

---

论文: GraphLCP: Structure-Aware Localized Conformal Prediction on Graphs 作者: Peyman Baghershahi, Fangxin Wang, Debmalya Mandal, Sourav Medya 机构: University of Illinois Chicago, University of Warwick 代码: 未开源