Root Cause Analysis of Outliers with Missing Structural Knowledge¶

会议: NeurIPS 2025 arXiv: 2406.05014 代码: amazon-science/RCAWithMissingStructuralKnowledgeCode 领域: causal_inference 关键词: Root Cause Analysis, 因果推断, 异常检测, 信息论异常分数, Polytree

一句话总结¶

提出仅用边际异常分数即可做根因分析的两个简单高效算法——已知因果图时用 SMOOTH TRAVERSAL（沿因果路径找分数跳变最大的节点），未知因果图时用 SCORE ORDERING（按分数排序取 top-k），在 polytree 结构下给出非参数概率保证，仅需单个异常样本即可工作。

研究背景与动机¶

领域现状: 根因分析 (RCA) 在云服务监控、工业故障诊断、医疗等领域应用广泛。因果视角下，RCA 被建模为"识别哪个因果机制发生了软干预（soft intervention）"。
现有痛点:
多数方法假设可以获取或估计"异常分布"（post-intervention distribution），但实际中常常只有单个异常样本
即使不依赖多样本，传统方法需要估计条件概率 P(Xi|PAi)，这在高维 / 低密度区域是统计病态问题（ill-posed）
基于遍历的方法（Traversal）需要人为设定异常阈值，缺乏理论保证
核心矛盾: 想要在最少信息（单个异常样本 + 可能未知的因果图）下做有保证的根因分析
本文要解决什么？: 避免条件概率估计，仅用边际异常分数 S(xi) 实现单根因识别
切入角度: 利用信息论异常分数（IT score）的数学性质，证明"异常不太可能沿因果路径放大"（anomalies rarely cause larger anomalies）
核心 idea 一句话: 在 polytree 因果图中，边际异常分数的差值可以替代条件异常分数来检验因果机制是否被破坏

方法详解¶

整体框架¶

本文建立在因果贝叶斯网络 (CBN) 框架上。正常分布 P(X1,...,Xn) 按因果 DAG 分解为因果条件 ∏P(Xi|PAi)。异常被建模为某个节点 Xj 的因果机制被替换为 P̃(Xj|PAj)，目标是从单个观测 (x1,...,xn) 中识别 j。

核心工具是信息论 (IT) 异常分数: - 边际异常分数: S(xn) = -log P(τ(Xn) ≥ τ(xn))，即观测值的"惊讶度" - 条件异常分数: S(xn|pan) = -log P(τ(Xi) ≥ τ(xn) | PAn = pan)，即控制父节点后的残差惊讶度 - 估计器: Ŝ(xn) = -log(1/k · |{i: τ(xᵢ) ≥ τ(xⁿ)}|)，基于正常期的 k 个样本

关键设计¶

Score Typicality 条件: 定义 S(y|x) ≥ |S(y) - S(x)|₊，即条件异常分数不小于边际分数之差的正部分。这是从边际分数推断条件分数的桥梁。Lemma 3.4 证明该条件对随机选取的 x 近似成立；Lemma 3.5 证明在单调可逆映射下精确成立。
"异常不太可能导致更大异常" (Lemma 3.3): 对因果对 X→Y，在 score typicality 下，X 处异常强度为 S(x) 导致 Y 处异常强度 S(y) 的概率至多 e^{-|S(y)-S(x)|₊}。这意味着边际分数沿因果路径不应"跳变式增大"，若发生则说明该处机制被破坏。
Polytree 下的推广: Polytree 中任意节点的父节点们互相边际独立，因此可以把多父节点问题归约为二元问题。用联合分数 S_joint(pai) = ΣS(paᵢⱼ) - log(Σ(ΣS)^l / l!) 来整合父节点信息（类似 Fisher 合并 p-value）。
SMOOTH TRAVERSAL 算法（需要因果图）: 对目标节点的每个祖先 Xi，计算 δi = |S(xi) - max_{parent} S(parent)|₊，选 δ 最大的节点作为根因。避免了传统 Traversal 需要手选异常阈值的问题。Theorem 3.12 给出 p-value 上界 p ≤ 1 - (1 - e^{-δ_max})^{n-1}。
SCORE ORDERING 算法（不需要因果图）: 将所有节点按边际异常分数从大到小排序，返回 top-k 个节点的集合。Theorem 3.13 证明根因不在 top-k 中的概率 ≤ n · d_max · e^{-Δk}，其中 Δk = S(x_π(1)) - S(x_π(k+1))。给定置信度 1-α 和最大入度 d_max，即可确定所需的 k。

损失函数 / 训练策略¶

本文无需模型训练。两个算法仅需： - 正常期数据估计边际 IT 异常分数（Eq. 5 的简单排序估计器） - SMOOTH TRAVERSAL 额外需要因果图 - SCORE ORDERING 额外需要最大入度 d_max 的上界估计

实验关键数据¶

主实验：异常强度对 Top-1 Recall 的影响¶

（合成数据，随机 DAG n 个节点，非线性 SCM，100 次重复）

方法	需要因果图	需要 SCM	x=2.0 TPR	x=3.0 TPR	特点
SMOOTH TRAVERSAL	✓	✗	~0.65	~0.72	与 Traversal 和 Counterfactual 并列最优
Traversal	✓	✗	~0.65	~0.72	需要人为设定异常阈值
Counterfactual	✓	✓	~0.65	~0.72	需要完整 SCM
Circa	✓	✗	~0.35	~0.40	假设线性，非线性场景差
Cholesky	✗	✗	~0.30	~0.35	假设线性，非线性场景差
SCORE ORDERING	✗	✗	~0.45	~0.50	不需任何图结构信息

消融 / 鲁棒性实验¶

实验维度	结果
图规模 n=20→100	SMOOTH TRAVERSAL / Traversal / Counterfactual 性能稳定；SCORE ORDERING / Cholesky / Circa 随 n 增大性能下降
因果图误指定（边增删/翻转）	SMOOTH TRAVERSAL 与 Traversal 鲁棒性相当，Circa 衰退更快
仅线性 SCM	Circa 和 Cholesky 性能大幅提升，与 SMOOTH TRAVERSAL 接近
DAG 限为 Polytree	SCORE ORDERING 性能提升，理论保证完全成立
运行时间（n 增大）	SMOOTH TRAVERSAL 和 Traversal 最快，其余方法运行时间相当

真实数据¶

数据集	最佳方法	备注
PetShop (Hardt et al.)	多种方法各有优势	微服务监控场景
Sock-shop 2 (Pham et al.)	SCORE ORDERING 表现良好	容器化应用故障定位
ProRCA 半合成	各方法表现交替	多种注入场景

关键发现¶

SMOOTH TRAVERSAL 在需要因果图的方法中是唯一不需要设定异常阈值的，性能与最优方法持平
SCORE ORDERING 是最弱输入需求的方法（无需因果图、无需 SCM），却有非参数概率保证
非线性场景下，假设线性的方法（Circa、Cholesky）性能骤降
在真实数据中，SCORE ORDERING 作为"first pass heuristic"表现稳健

亮点与洞察¶

理论优雅: "异常不太可能导致更大异常"这个直觉被严格数学化，且推导简洁（基于 p-value 的信息论解释）
实用性强: 两个算法实现极简，SCORE ORDERING 只需排序异常分数，SMOOTH TRAVERSAL 只需一次图遍历
最弱假设下的保证: SCORE ORDERING 可能是目前假设最弱的有理论保证的 RCA 方法
Score Typicality 桥接: 用边际分数替代条件分数的关键技巧，避免了条件密度估计的统计困难

局限性 / 可改进方向¶

Polytree 假设: 核心理论依赖 polytree 结构（即 skeleton 是树），一般 DAG 中可能出现下游异常分数大于根因的情况（Li et al. 2024 给出了反例条件）
单根因假设: 假设仅一个机制被破坏，多根因场景需要进一步扩展
真实数据表现不稳定: 在某些真实数据集上被 Cholesky 或 Circa 超越，说明简单性有代价
IT 异常分数的估计精度: 需要足够多的正常期样本（至少 e^s 个样本才能估计值为 s 的分数）

评分¶

新颖性: ⭐⭐⭐⭐ 用边际分数替代条件分数做 RCA 的理论贡献扎实，Score Typicality 是新颖的技术工具
实验充分度: ⭐⭐⭐⭐ 合成实验覆盖多维度，真实数据评估全面，但真实数据表现不总是最优
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰，从二元到 polytree 的递进式展开非常流畅
价值: ⭐⭐⭐⭐ 对工业界 RCA 实践有直接指导价值，SCORE ORDERING 可作为任何 RCA 流程的快速预筛