Graph Out-of-Distribution Detection via Test-Time Calibration with Dual Dynamic Dictionaries¶

会议: AAAI 2026
arXiv: 2511.13541
代码: 无
领域: 图异常检测 / OOD检测
关键词: 图OOD检测, 测试时校准, Graphon混合, 双动态字典, 优先队列

一句话总结¶

提出 BaCa 框架，在测试阶段通过 graphon 估计 + mixup 策略生成边界感知的合成图拓扑，结合双优先队列动态字典和注意力机制自适应校准 OOD 分数，无需微调预训练模型或引入辅助OOD数据，在全部 10 个数据集上超越 GOODAT，平均 AUC 提升 8.37%。

研究背景与动机¶

领域现状：图级别的 OOD 检测旨在判断测试图样本是否来自与训练数据不同的分布。现有方法分为端到端方法（从头训练OOD感知GNN）和后处理方法（在已训练GNN上加检测器），核心都是定义基于模型输出或潜在特征的OOD评分函数。
现有痛点：
仅在 ID 数据上训练的 GNN 难以识别特征接近 ID 流形的 OOD 样本（如共享相似拓扑结构时）
Outlier Exposure（OE）需要外部 OOD 数据，违反了"仅用 ID 数据训练"的标准假设
GOODAT 虽引入测试时设定，但需在推理时优化可学习图掩码器，稳定性受限
图数据的潜在结构受多种因素控制，决策边界附近 ID 和 OOD 的分数分布高度重叠
核心矛盾：预训练 GNN 缺乏对分布边界的建模能力，导致 ID/OOD 分数重叠严重，尤其在边界附近的模糊样本上表现差。
本文要解决什么：如何在测试阶段（不修改预训练模型、不引入辅助OOD数据）建模 ID/OOD 分布边界并有效校准 OOD 分数？
切入角度：从直觉出发——如果一个样本比 OOD 分布中最偏向 ID 的样本更偏 OOD，那它应被判为 OOD，反之亦然。因此关键在于准确捕获边界处最具辨别力的样本表示。
核心 idea：在测试时动态维护 ID 和 OOD 两个表示字典（优先队列实现），持续收集边界附近最具代表性的样本特征，通过注意力机制校准 OOD 分数，同时用 graphon 估计和 mixup 生成合成样本增强边界表示的多样性。

方法详解¶

整体框架¶

BaCa（Boundary-aware Calibration）的流程： 1. 用预训练 GNN 计算测试样本的初始 OOD 分数 \(S_{Pre}\) 2. 基于初始分数将样本分为 ID/OOD 两组 3. 分别估计每组的 graphon，通过 graphon mixup 生成多样性的合成样本 4. 用优先队列维护双动态字典，持续收集边界附近的代表性特征 5. 通过注意力机制计算校准分数 \(S_{Attn}\)，最终分数 \(S_{BaCa} = S_{Pre} + \beta \cdot S_{Attn}\)

关键设计¶

模块一：边界感知的潜在模式建模

做什么：基于初始判断划分子组 → 估计每组的 graphon → graphon mixup 生成带有辨别性拓扑的合成图
核心思路：
Graphon 是对称可测函数 \(W: \Omega^2 \to [0,1]\)，描述了节点间边存在的概率，是图序列的极限对象
使用 USVT 估计器将 graphon 近似为阶梯函数 \(W \in [0,1]^{N \times N}\)
在同一组内（ID 或 OOD）进行 graphon 凸组合：\(W_s = \lambda W_i + (1-\lambda)W_j\)
从 \(W_s\) 采样生成合成图，填充边界低密度区域
随机采样目标大小 \(r \in [2,N]\)，增加结构多样性
设计动机：
测试时无法获取真实 OOD 样本，但可以通过 graphon mixup 在同组内插值来增强边界表示
定理 1 证明了混合 graphon 保留了来源组的辨别性拓扑特征，偏差受 \(\lambda\) 和 cut-norm 距离约束
这在测试初期（字典尚未充分填充时）尤为重要

模块二：双动态字典（优先队列）

做什么：维护固定长度的 ID 字典和 OOD 字典，用优先队列实现，持续收集边界附近最具辨别性的样本特征
核心思路：
OOD 字典 \(\mathcal{K}^{ood}_l\)：收集 OOD 分数分布的左尾（最接近 ID 边界的 OOD 样本）——队列前端始终是最靠近边界的 OOD 样本
ID 字典 \(\mathcal{K}^{id}_l\)：收集 ID 分数分布的右尾（最接近 OOD 的 ID 样本）
新候选插入条件：OOD 分数超过队列前端元素
合成样本也参与字典更新，增加潜在模式的多样性
设计动机：边界处的样本最具信息量——它们定义了 ID/OOD 的分界线。固定长度优先队列解耦了字典大小与 mini-batch 大小，支持跨 batch 复用。随着迭代进行，KL 散度逐步增大，表明 ID/OOD 分布逐渐分离

模块三：注意力校准

做什么：对每个测试样本，通过注意力机制计算其与 ID/OOD 字典中 Top-\(\mathbb{K}\) 条目的相似度，输出校准分数
核心思路：
查询 \(q = f(G)\)，键/值来自字典中 Top-\(\mathbb{K}\) 最相关条目
OOD 字典注意力输出 \(S_{out}(G) = \text{ATTN}_{out}(Q,K,V)\)
ID 字典注意力输出 \(S_{in}(G) = -\text{ATTN}_{in}(Q,K,V)\)
最终校准分数 \(S_{Attn} = S_{in} + S_{out}\)
ID 样本与 ID 字典高相似/与 OOD 字典低相似 → \(S_{Attn}\) 低；OOD 反之

\[S_{BaCa} = S_{Pre} + \beta \cdot S_{Attn}(G)\]

设计动机：仅看 Top-\(\mathbb{K}\)（而非全部字典条目）既提高效率又减少噪声，注意力权重的可学习性允许自适应捕获不同图结构的相关模式

损失函数 / 训练策略¶

双 BCE 损失监督注意力参数 \(W_Q, W_K, W_V\)：

\[\mathcal{L} = -\mathbb{E}_{\mathcal{K}^{id}}[\log(\text{ATTN}_{in}) + \log(1-\text{ATTN}_{out})] - \mathbb{E}_{\mathcal{K}^{ood}}[\log(1-\text{ATTN}_{in}) + \log(\text{ATTN}_{out})]\]

仅训练注意力模块的少量参数，不更新预训练 GNN，计算复杂度极低（线性于字典大小和特征维度）。

实验关键数据¶

主实验¶

在 10 对 ID/OOD 数据集上的 AUC（%），与 GOODAT（同为测试时方法）对比：

数据集对	GOODAT	BaCa	提升
BZR/COX2	-	✓	-
PTC/MUTAG	-	✓	-
ClinTox/LIPO	-	✓	+20.11
平均 10 对	-	SOTA	+8.37

BaCa 在全部 10 个数据集上超越 GOODAT 和所有其他基线（包括 graph kernel 方法和端到端方法）。

消融实验¶

图 1(d) 迭代曲线显示：随测试时迭代进行，Total（完整 BaCa）的 AUC 持续提升并收敛，Attn 单独也有效但低于 Total，Base（仅预训练）保持平直
KL 散度随迭代增大，验证了校准确实在拉大 ID/OOD 分布差距
去掉 graphon mixup → 性能下降（尤其在早期迭代），去掉优先队列 → 边界建模不稳定

关键发现¶

测试时校准范式有效：不修改模型、不引入外部 OOD 数据，仅利用测试样本自身即可显著提升检测性能
Graphon mixup 不仅增强多样性，还提供了理论保证（定理 1：混合 graphon 保留辨别性拓扑）
Graph kernel 方法（PK-LOF/OCSVM）在图 OOD 任务上接近随机（AUC ~50%），说明传统核方法不适合此问题

亮点与洞察¶

优先队列动态字典：用最简单的数据结构解决了"如何在测试时持续捕获边界信息"的问题，设计极其优雅
Graphon 估计 + mixup 的组合在图 OOD 检测中首次使用，理论推导严谨（Theorem 1 的同态密度保持）
完全不依赖辅助 OOD 数据和模型微调，实用性强
计算复杂度分析完善：字典操作 \(O(d \cdot l)\)，队列更新 \(O(\log l)\)，注意力 \(O(2\mathbb{K}d)\)

局限性 / 可改进方向¶

初始分组质量依赖预训练模型的 \(S_{Pre}\)——如果初始判断极差（如 ID/OOD 完全混杂），后续校准可能受限
Graphon USVT 估计对稀疏图的效果可能不佳
超参数较多（字典大小 \(l\)、Top-\(\mathbb{K}\)、mixup 系数 \(\lambda\)、校准权重 \(\beta\)），调参成本未充分讨论
仅评估无监督图级 OOD 检测，节点级和边级 OOD 检测待探索

评分¶

⭐⭐⭐⭐ (4/5)

理由：方法设计优雅（优先队列 + graphon + 注意力校准三位一体），理论推导扎实，实验全面且提升显著。扣一分因为超参数较多且对初始分组质量的依赖未充分讨论。