Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Each language version is independently generated for its own context, not a direct translation.

这篇论文讲述了一个关于**“如何给复杂的图形预测结果加上‘安全网’"**的故事。

想象一下，你正在玩一个超级复杂的拼图游戏，或者让 AI 去猜一个化学分子的结构。AI 给出了一个答案（比如一个分子图），但 AI 也会犯错。传统的 AI 只会告诉你：“我猜这是分子 A"，但它不会告诉你：“我有多大的把握？”或者“如果我不确定，还有哪些可能的分子？”

这篇论文提出了一套新方法，让 AI 不仅能给出一个答案，还能给出一个**“候选名单”，并保证这个名单里一定**包含正确答案（比如 90% 的情况下）。

为了让你更容易理解，我们用几个生活中的比喻来拆解这篇论文的核心内容：

1. 核心难题：图形世界的“旋转木马”

在普通的世界里，如果你说“苹果”，大家知道是指那个红色的水果。但在图形世界（比如分子结构、社交网络）里，情况很复杂。

比喻：想象一个由几个乐高积木搭成的城堡。如果你把城堡转个身，或者把积木的编号换一下，它看起来还是同一个城堡，但在计算机眼里，它可能变成了完全不同的数据。
问题：传统的比较方法（比如直接数积木位置）会因为这种“旋转”或“编号变化”而误判，以为两个一样的城堡是不同的。
论文方案（Z-Gromov-Wasserstein 距离）：
这就好比我们不再死板地看积木的编号，而是看积木之间的相对关系。不管城堡怎么转，只要积木之间的连接方式（谁挨着谁）和颜色没变，我们就认为它们是一样的。
论文引入了一种叫 Z-Gromov-Wasserstein (Z-GW) 的数学工具，它就像一把**“万能尺子”**，能无视图形的旋转和编号，直接比较两个图形的“灵魂”（结构和特征）是否相似。

2. 核心创新：给预测结果穿上“防弹衣”（共形预测）

有了这把尺子，我们怎么知道 AI 猜得准不准呢？

传统做法：AI 猜一个，错了就错了。
论文做法（共形预测 Conformal Prediction）：
想象你在打靶。传统 AI 只射出一支箭。而这篇论文的方法是：AI 射出一支箭，然后画出一个圈。
- 这个圈里包含了所有“看起来不太离谱”的候选答案。
- 论文保证：只要数据是公平的（交换性假设），这个圈90% 的概率会把真正的靶心（正确答案）包在里面。
- 关键点：这个圈不是随便画的，它是用上面提到的“万能尺子”量出来的。如果某个候选分子和 AI 预测的分子在“万能尺子”下距离太远，它就会被踢出圈外。

3. 进阶技巧：聪明的“动态调整” (SCQR)

一开始，这个“圈”的大小是固定的。比如不管题目多难，圈都画得一样大。

问题：这很不划算。如果题目很简单，圈画得那么大，里面全是废话；如果题目很难，圈画得那么小，可能就把正确答案漏掉了。
论文方案（SCQR - 分数共形化分位数回归）：
这就像是一个**“聪明的裁判”**。
- 当题目很简单（比如候选分子很少，或者特征很清晰）时，裁判会把圈缩小，只保留最像的几个，让你快速锁定目标。
- 当题目很难（候选分子很多，特征模糊）时，裁判会把圈扩大，把更多可能性包进来，确保不丢分。
- 比喻：就像你出门看天气。如果是晴天（简单情况），你只带一把伞（小圈）；如果是暴风雨（复杂情况），你就带上雨衣、雨靴甚至躲进屋里（大圈）。SCQR 就是那个能根据天气自动调整装备的机器人。

4. 实际效果：真的有用吗？

论文在两个场景下测试了这套方法：

合成游戏（图像转图形）：给 AI 看一张画着颜色的图，让它猜背后的图形结构。
- 结果：这套方法成功地把候选名单缩小了 95% 以上，同时保证了 90% 的准确率。
真实世界（化学分子识别）：给 AI 看一张质谱图（像指纹一样的化学信号），让它猜这是什么分子。
- 结果：在成千上万个可能的分子中，这套方法能迅速筛选出最可能的几个（平均从 24 个缩小到 15 个），而且从来没有把正确答案漏掉（在统计意义上）。

总结

这篇论文就像给 AI 的“图形预测”能力装上了一个智能的安全气囊：

它懂行：用 Z-GW 距离，无视图形怎么转、怎么编号，只看本质。
它负责：用共形预测，保证给出的答案列表里一定包含正确答案，绝不瞎猜。
它灵活：用 SCQR，根据题目难易程度，自动调整答案列表的大小，既不让用户看一堆废话，也不让用户错过正确答案。

这对于化学家、药物研发人员来说非常重要，因为他们不需要再盲目地验证所有可能性，而是可以信任 AI 给出的这个**“高置信度候选名单”**，从而节省大量时间和金钱。

Each language version is independently generated for its own context, not a direct translation.

1. 研究背景与问题定义 (Problem)

核心问题：
监督图预测（Supervised Graph Prediction, SGP）旨在将任意模态的输入（如文本、图像、分布）映射为结构化的图输出（如分子结构、场景图）。尽管现有的图预测模型（如端到端学习、图回归）取得了进展，但缺乏对预测结果的不确定性量化。在化学分子识别或场景理解等高风险领域，仅提供单一预测结果而缺乏置信度评估（Confidence Sets）是危险的，因为实验验证成本高昂。

现有挑战：

非欧几里得空间： 图数据存在于高度结构化、非欧几里得且组合空间巨大的流形上，传统的共形预测（Conformal Prediction, CP）方法难以直接应用。
置换不变性（Permutation Invariance）： 图是同构的，节点标签的排列不应改变图的结构。现有的度量方法往往无法在商空间（Quotient Space，即忽略节点排列的图空间）中定义有效的非一致性分数（Nonconformity Score）。
异方差性（Heteroscedasticity）： 不同输入实例的预测难度不同（例如，某些分子结构更复杂），使用单一的全局阈值会导致简单样本的预测集过大（保守），而复杂样本的覆盖不足。

2. 方法论 (Methodology)

本文提出了一种**分布无关（Distribution-free）**的共形预测框架，专门用于图值输出，主要包含以下核心组件：

2.1 基于 Z-Gromov-Wasserstein (Z-GW) 距离的非一致性分数

为了在图空间定义有效的距离度量，作者引入了 Z-Gromov-Wasserstein (Z-GW) 距离。

Z-网络 (Z-networks)： 将图视为带有节点和边属性的 Z-网络，其中 $Z$ 是一个度量空间，用于编码节点和边的关系。
置换不变性： Z-GW 距离天然具有置换不变性。它通过最优传输（Optimal Transport）在两个图之间寻找最佳耦合，最小化结构（边）和属性（节点特征）之间的差异。
具体实现： 在实践中，使用 Fused Gromov-Wasserstein (FGW) 距离作为 Z-GW 的特例。FGW 同时考虑了图的结构（邻接矩阵或拉普拉斯矩阵）和节点/边的特征，能够处理带标签的图。
非一致性分数定义： 对于输入 $x$ 和候选图 $y$ ，分数定义为 $s(x, y) = \text{FGW}(f_\theta(x), y)$ ，其中 $f_\theta$ 是预训练的图预测模型。

2.2 商空间上的共形有效性

由于图在同构意义下是等价的，预测集必须在商空间 $\mathcal{M} = \mathcal{M} / \sim$ 上定义。

作者证明了基于 Z-GW 的分数在商空间上是良定义的（Well-defined），并且如果原始数据是可交换的（Exchangeable），那么在商空间上的投影数据也是可交换的。
这保证了在商空间上构建的共形集具有严格的边际覆盖保证（Marginal Coverage Guarantee）： $P(Y_{n+1} \in \mathcal{C}_\alpha(X_{n+1})) \geq 1 - \alpha$ 。

2.3 局部自适应预测：Score Conformalized Quantile Regression (SCQR)

为了解决输入依赖的异方差性问题，作者提出了 SCQR，这是 Conformalized Quantile Regression (CQR) 在图空间上的扩展。

机制： 不直接使用全局阈值，而是训练一个分位数回归模型 $\psi(\omega(x))$ 来预测非一致性分数的条件分位数。其中 $\omega(x)$ 是输入相关的特征（如候选集大小或谱嵌入）。
自适应阈值： 最终的预测集定义为 $C(x) = \{y \in \mathcal{M} : s(x, y) \leq \psi(\omega(x)) + \hat{q}_{1-\alpha}\}$ 。
优势： SCQR 能够根据输入的难度动态调整预测集的大小，在保持边际覆盖的同时，显著减少预测集的平均大小（提高效率）。

2.4 实际限制与候选集

由于图空间是组合爆炸的，无法枚举所有可能的图。因此，方法假设存在一个输入相关的候选集库 $L(x)$ （例如，质谱分析中质量匹配的分子库）。最终的预测集是理论共形集与候选库的交集： $\mathcal{C}_L(x) = \mathcal{C}(x) \cap L(x)$ 。

3. 主要贡献 (Key Contributions)

理论框架： 提出了基于 Z-Gromov-Wasserstein 距离的共形图预测框架，并严格证明了其在图商空间（Quotient Graph Space）上的有效性。
自适应方法： 引入了 SCQR，首次将分位数回归思想扩展到结构化图输出空间，实现了局部自适应的预测集，解决了异方差性问题。
实证验证： 在合成任务（图像到图）和真实世界任务（质谱图到分子识别）上进行了广泛实验，证明了该方法在保持高覆盖率的同时，能有效缩小预测集规模。

4. 实验结果 (Results)

实验在两个数据集上进行：

Synthetic Coloring (合成着色)： 从图像恢复图着色结构。
Metabolite Identification (MassSpecGym)： 从质谱图（MS/MS）识别代谢物分子结构。

关键发现：

覆盖率有效性： 在名义覆盖率 90% 的设置下，两种任务的实际覆盖率均接近 90%（例如 89.0% - 90.3%），验证了理论保证。
效率提升 (SCQR vs CP)：
- 在代谢物识别任务中，SCQR 表现尤为出色。使用谱嵌入（DREAMS 特征）作为条件时，平均预测集大小从标准 CP 的 24 降低到 15，同时覆盖率保持稳定。相对候选库的缩减率从 77.1% 提升至 84.8%。
- 在合成任务中，SCQR 也保持了与 CP 相当的性能，但在某些条件下能进一步减少集合大小。
距离度量的影响： 使用 FGW（融合结构 + 特征）比纯 Gromov-Wasserstein（仅结构）或仅特征距离效果更好，因为它利用了更细粒度的信息来区分相似的图。
分布形态： SCQR 显著减少了预测集大小的“长尾”分布，使得预测集大小更加集中和可控。

5. 意义与总结 (Significance)

填补空白： 该工作填补了结构化输出（特别是图数据）不确定性量化领域的空白，提供了一种无需假设数据分布的通用解决方案。
安全性与实用性： 在化学分子发现等关键领域，该方法不仅能给出预测，还能给出“置信范围”（即一组可能的分子结构），帮助研究人员优先验证高置信度的候选者，降低实验成本。
通用性： 框架不仅限于图，其基于 Z-network 和最优传输的思想可扩展到其他结构化输出空间，如点云、网格和分布数据。
技术突破： 成功解决了图同构带来的置换不变性难题，并展示了如何通过条件分位数回归在复杂非欧几里得空间中实现自适应不确定性量化。

总结： 本文通过结合 Z-Gromov-Wasserstein 距离的几何特性与共形预测的统计保证，提出了一套严谨、高效且自适应的图预测不确定性量化方案，为高风险的结构化预测任务提供了重要的理论支持和实践工具。