AAAI 2026 · arXiv 2511.08867 v2
Conformal Prediction for Multi-Source Detection on a Network
用共形预测给传播源检测输出一个节点集合：以至少 1−α 的概率，集合召回至少 1−β 比例的真源。它不需要传播模型的似然，只要一个预训练的预测器和一批校准数据，单源、多源都能用。
1研究问题
多源检测：观测到若干时刻全网节点的 S/I/R 状态，找出所有源。已有中心性方法只在树上有保证；GNN 方法效果好但没有统计保证；Dawkins 等的检验反演（本文称 ADiT）有保证，但只能做单源、只能用 SI 模型，而且每个节点都要做模拟检验，代价高。
本文目标：构造集合 Ĉ，满足
β=0 时就是"以 1−α 概率包含全部真源"；β 越大，集合越小。
2共形预测基础（分裂式）
- 准备一个点预测器 f，例如预训练 GNN，对每个节点输出"是源"的估计概率 π̂(v)。
- 定义非一致性分数 s(X, 候选答案)：越大表示越不像。
- 在 n 条校准数据上算出真答案的分数，取 (1−α)(1+1/n) 经验分位数 q̂。
- 新样本上，把分数不超过 q̂ 的答案都放进集合。
只要校准数据和测试数据可交换，覆盖就至少 1−α。这一保证与预测器好坏、数据分布都无关。
3方法：把"集合包含"变成一维分数
直接对所有节点子集做共形预测不可行（2^N 个候选）。作者的做法：
- 把节点按 π̂ 从大到小排序。对任一子集 U，定义 γ(X,U) 为"π̂ 不小于 U 中最小值的所有节点"，即把 U 补成一个排序前缀。
- 非一致性分数只依赖 γ(X,U)，且对前缀单调。作者给了三个例子：负的平均概率（setCP-pre，对应精确率）、前缀概率占全部的比例（setCP-rec，对应召回率）、负的最小概率（setCP-min，与共形风险控制等价）。
- 命题 1：在单调条件下，"真源集合 Y 被预测集合包含"等价于"Y 的分数不超过 q̂"。于是只需对每个节点单独判断，复杂度 O(N log N)。
- 要求部分召回（β>0）时，先把真源集合缩成"π̂ 最大的 (1−β) 部分"，再套用上面的构造（定理 3）。
4实验结果（论文报告值）
网络：highSchool（774 节点）、SFHH（403）、bkFratB（58）。传播用 NDlib 模拟离散时间 SIR/SI；输入是连续 16 个时刻的全网状态快照；骨干网络 SD-STGCN。
单源 SI（σ_inf=0.25，highSchool，α=0.1）
| 方法 | 包含率 | 平均集合大小 |
|---|---|---|
| setCP-rec | 0.901 | 23.3 |
| setCP-pre | 0.902 | 25.7 |
| setCP-min | 0.901 | 20.4 |
| ADiT（Dawkins 等） | 0.988 | 24.4 |
| ArbiTree | 0.896 | 624.4 |
多源（|Y|=7、10，α=0.1，β=0.3）
SI 下 setCP-rec 的集合约 29、40 个节点；ArbiTree 几乎输出全图（约 770）。SIR 下集合都更小，因为恢复状态提供了额外信息。
时间（400 个测试样本，单源 SI）
| 方法 | 秒 |
|---|---|
| setCP-min / rec / pre（单线程） | 1.2 / 1.4 / 1.6 |
| ArbiTree（并行） | 79.6 |
| ADiT（并行） | 792.2 |
另一个值得注意的结果：在表 I（多源、随机参数的 SIR）中，setCP-rec 在 β=0.1 时输出全部 774 个节点，集合失去信息量。
5细读要点
- 保证是"平均意义"的。可交换性下的覆盖，是对校准分布（随机源、随机参数）取平均。某个特定源位置的覆盖可以低于 1−α，这与 Dawkins 的"对每个固定源都成立"不同。
- 与 ADiT 的对比不完全对等。附录写明 ADiT 只用了 m_l = m_p = 20 条模拟路径（Dawkins 论文用 10000）。ADiT 的过覆盖（0.988）和大集合很可能部分来自这一点。
- 计时不含训练。表中时间只是测试阶段，不含 GNN 训练和生成校准数据的模拟成本。
- 观测很丰富。输入是全网所有节点连续 16 个时刻的状态，远多于"少数传感器"。
- 作者承认依赖校准数据，模型或参数失配时的影响留作未来工作。
6作者代码讲解
仓库 xcjian/Conformalized-Network-Source-Detection，提交 e861d51e。仓库共 20,664 个文件，含大量模拟数据和结果（单个结果文件可达约 100 MB，整体约 1.3 GB）；本节只读了源代码，没有下载数据、没有运行。
| 目录或文件 | 作用 |
|---|---|
main.py | 完整流程：加载 SD-STGCN 的测试输出，随机划分校准集与测试集，计算各方法的覆盖率、集合大小与耗时，重复 50 次后汇总 |
utils/score_convert.py | 非一致性分数：recall_score、avg_score（精确率版）、min_score，各有已知真源（校准）和未知真源（测试）两个版本；set_truncate 是缩集映射 ν；ArbiTree、PGM 的分数 |
utils/functions.py | 分位数 cpquantile、调用预训练模型的 get_test_results、ArbiTree 的树学习与消息传递 |
SD-STGCN/ | 第三方骨干网络（Sha 等 2021，TensorFlow），连同各网络的 SIR/SI 模拟脚本 |
DSI/ | Dawkins 等代码的副本，用作 ADiT 对照 |
batch_CP_process*.sh | 论文各表的运行命令 |
论文公式与代码的对应
- 排序前缀 γ：
*_gtunknown函数把节点按 π̂ 降序排列，沿前缀累加，一次得到所有节点的分数，这就是论文 O(N log N) 的来源。 - 校准分位数：
tail_prop = (1−α)(1+1/n)，阈值取校准分数的该分位数；测试时分数不超过阈值的节点进入集合（式 10、16）。 - 缩集映射 ν：
set_truncate保留真源中 π̂ 最大的 1−β 部分（式 17）。命令行参数--pow_expected就是 1−β。 - 覆盖的判定：每个测试样本若 |真源 ∩ 集合|/|真源| ≥
pow_expected记为覆盖，再对测试样本取比例。
论文没写清楚、代码里才有的细节
- 候选限制：所有分数在排序前都把"最早一个观测时刻未感染的节点"的 π̂ 置零，SIR 也一样。也就是说，候选源实际被限制在最早快照里的感染节点。
- 数据划分：默认 95% 样本作校准、5% 作测试，随机划分重复 50 次，固定种子 41。
- 表中"±"：是 50 次划分之间的标准差（代码用
np.std），不是标准误。 - ADiT 对照的设定：用 Dawkins 的
FixedTSI（固定感染数 T、每步均匀选一条边），T 取最早快照的感染数减一，m_l = m_p = 20。测试数据却来自 NDlib 的离散时间 SI，因此这个对照是在模型不匹配下运行的，Dawkins 方法的有效性保证此时并不成立。 - 运行需要 Python 3.8 与 TensorFlow 2.3 一套环境；SD-STGCN 的训练不在
main.py内，表 IV 的时间只含测试阶段。
7与你的方案（传感器部署 + 有效源集合）的关系
| 维度 | 本文 | 你的方案 |
|---|---|---|
| 观测 | 全网多时刻快照 | k 个传感器的首次到达时间 |
| 保证 | 对源分布平均，需校准集 | 逐源有效，需已知模型 |
| 多源 | 支持 | 先只做单源 |
| 部署 | 不涉及 | 核心 |
可作对照：把传感器记录当作输入 X，就能得到一个"传感器版共形集合"，作为同覆盖下比较集合大小的强基线。这种替换本身是直接应用，不能算创新。
需注意：比较时要说明两种保证的区别，并让两者用相同的模拟预算；不要沿用本文 m=20 的 ADiT 设置。