# Root Cause Analysis of Outliers with Missing Structural Knowledge
> [!abstract] 概要
> 根本原因分析(RCA)の目的は、異常がなぜ発生したかを、障害が発生した箇所を特定することで説明することである。最近の複数の研究は、異常イベントを根本原因における因果機構の変化（ソフト介入）の結果としてモデル化している。RCA はどの因果機構が変化したかを特定するタスクとして大まかに理解できる。実世界の応用では、介入後分布からのサンプルが少数または単一しか得られないことが多く、これはほとんどの手法にとって深刻な制限となる——それらの手法は分布を知っているか推定できることを仮定するためである。しかし、そうでない手法でも、低確率密度領域での回帰モデルの探索が必要なため統計的に不良設定となる。本論文では、根本原因が単一であり因果グラフがポリツリーである場合に、これら両方の困難を克服するシンプルで効率的な手法を提案する。因果グラフが既知のとき、周辺異常スコアのみを必要とし任意の異常スコア閾値の設定に依存しない探索アルゴリズムについて保証を与える。因果グラフが未知のとき、最高の周辺異常スコアを持つ変数を根本原因候補として同定するヒューリスティックが因果的に正当化されることを示す。この目的のために、ポリツリーにおいてスコアが小さい異常がスコアの大きい異常を引き起こす可能性は低いことを証明し、非単調な異常スコアを持つ因果経路の尤度の上界を与える。
## 論文情報
- **タイトル**: Root Cause Analysis of Outliers with Missing Structural Knowledge
- **著者・所属**:
- William Roy Orchard（University of Cambridge）— 第一著者（共同）
- Nastaran Okati（Max Planck Institute for Software Systems, Kaiserslautern）— 第一著者（共同）
- Sergio Hernan Garrido Mejia（Max Planck Institute for Intelligent Systems、Amazon, Tübingen）
- Patrick Blöbaum（Amazon, Tübingen）
- Dominik Janzing（Amazon, Tübingen）
- **媒体**: NeurIPS 2025（第 39 回 Neural Information Processing Systems）
- **コード**: https://github.com/amazon-science/RCAWithMissingStructuralKnowledgeCode
- **OpenReview**: https://openreview.net/forum?id=7Nxq4RQApu
## 概要
本論文は、因果グラフがポリツリーかつ根本原因が単一であるという仮定の下で、**単一の異常サンプルのみから**根本原因を特定する 2 つのアルゴリズム（SMOOTH TRAVERSAL と SCORE ORDERING）を提案する理論的 RCA 論文である。核心的な貢献は、条件付き確率の推定を必要とせず周辺異常スコアのみを使って根本原因を同定できることを証明した点であり、これにより統計的に不良設定な条件付き分布の推定問題を回避する。合成データと実世界データ（PetShop・Sock-shop・ProRCA）での評価でも競合手法と同等以上の性能を示した。
## 問題設定
- **入力**: 変数 $(X_1, \ldots, X_n)$ の単一サンプル $(x_1, \ldots, x_n)$。そのうち $X_n$ の値 $x_n$ が異常として検知されている
- **出力**: 根本原因となる変数 $X_j$（$j \in \{1, \ldots, n\}$）の特定
- **前提**:
1. 因果関係は因果的ベイズネットワーク(CBN)でモデル化され、因果 DAG に従い結合分布が分解できる
2. 異常は根本原因 $X_j$ の因果機構 $P(X_j | PA_j)$ が $\tilde{P}(X_j | PA_j)$ に変化するソフト介入として発生
3. 根本原因は単一（希少機構変化仮説: sparse mechanism shift hypothesis）
4. 因果 DAG はポリツリー（骨格がツリーである DAG）
- **既存手法の困難**:
- 多くの手法は異常後分布の複数サンプルを要求する
- 条件付き確率の推定は低密度領域でのプローブが必要なため統計的不良設定
- SCM 全体（構造方程式）の同定は一般に観測データだけでは不可能
## 提案手法
### 情報理論的(IT)異常スコア
異常スコアを p 値的に定義する。特徴写像 $\tau: \mathcal{X} \to \mathbb{R}$ に対し、
$S(x_n) := -\log P(\tau(X_n) \geq \tau(x_n))$
これはイベントの「驚き度」を情報理論的に捉えたものであり、小さい p 値（強い異常）が大きいスコアに対応する。**周辺異常スコア**（観測値の絶対的な稀少性）と**条件付き異常スコア** $S(x_n | pa_n) := -\log P(\tau(X_n) \geq \tau(x_n) | PA_n = pa_n)$（因果機構から見た稀少性）を区別する。
### スコア典型性(Score Typicality)
二変数 $X \to Y$ の観測 $(x, y)$ が**スコア典型性**を満たすとは：
$S(y|x) \geq |S(y) - S(x)|_+$
これが成立するとき、$X$ で大きくない異常が $Y$ でより大きな異常を引き起こす確率に上界を導ける（補題 3.3: $p \leq e^{-|S(y)-S(x)|_+}$）。スコア典型性は連続分布では近似的にほぼ成立（補題 3.4）し、注入性・単調性の仮定下では厳密に成立（補題 3.5）する。
### ポリツリーへの拡張
ポリツリー（骨格が木であるDAG）では、各変数の親が**周辺独立**となる。これを利用し、親の合同スコアを：
$S_{joint}(pa_i) := \sum_j S(pa_i^j) - \log \sum_{l=0}^{k-1} \frac{(\sum_j S(pa_i^j))^l}{l!}$
と定義することで、ポリツリー問題を二変数問題に帰着できる（Fisher の方法に対応）。
### SMOOTH TRAVERSAL（因果グラフ既知）
```
Algorithm 1: SMOOTH TRAVERSAL
入力: スコア S(x_1),...,S(x_n), 因果DAG G
出力: 最大スコア差を持つ変数 Xk
for X_n の各祖先 X_i:
score_diff = max(0, S(x_i) - max_{親} S(親))
argmax を返す
```
親との最大スコア差を持つノードを根本原因とする。閾値設定不要。
定理 3.12: スコア差の最大値 $\delta_{\max}$ が大きいとき、最大スコア差のノードが根本原因でない確率は $p \leq 1 - (1 - e^{-\delta_{\max}})^{n-1}$。
### SCORE ORDERING（因果グラフ未知）
```
Algorithm 2: SCORE ORDERING
入力: スコア, 最大入次数 d_max, 信頼度 1-α
出力: 根本原因を含む候補集合 L
スコア順に変数を並べ、n * d_max * e^{-Δ_k} ≤ α を満たす最小 k を返す
```
定理 3.13: ポリツリーにおいて、根本原因が上位 k スコア集合に含まれない確率は $p \leq n \cdot d_{\max} \cdot e^{-\Delta_k}$（$\Delta_k$ はスコアのギャップ）。
### 反実仮想貢献分析との接続
付録 A で、Budhathoki ら [ICML 2022] の反実仮想 Shapley 貢献分析との接続を示す。トポロジカル順序 $\pi$ では、貢献 $C^\pi(j)$ が観測的条件付き分布のみで計算可能（命題 A.1）。根本原因が「支配的」（どの順序でも最大貢献）であれば SCM 不要で同定できる。
## 新規性
| 側面 | 既存手法 | 本手法 |
|---|---|---|
| 必要サンプル数 | 複数の異常サンプル | **単一サンプル** |
| 条件付き確率推定 | 必要（不良設定） | **不要**（周辺スコアのみ） |
| SCM の知識 | Counterfactual 系では必要 | **不要** |
| 因果グラフ | Traversal/Circa では必要 | SCORE ORDERING は**不要** |
| 理論保証 | パラメトリック仮定あり | **非パラメトリック保証** |
既存の主要ベースラインとの比較:
- **Traversal** [CauseInfer, Microscope]: 閾値（異常か否か）の設定が必要 → SMOOTH TRAVERSAL は閾値フリー
- **Circa** [KDD 2022]: 線形 SCM を仮定し条件付き分布を推定 → 本手法は仮定なし
- **Counterfactual** [Budhathoki, ICML 2022]: SCM 全体が必要 → 本手法は不要
- **Cholesky** [Li+, 2024]: 線形 SCM 仮定 → 本手法はノンパラメトリック
## 実験設定
- **環境**: Apple M1 MacBook Pro (16GB)
- **合成データ**: 50ノード DAG（非線形 SCM: ランダムフィードフォワードNN 80%+線形 20%、加法ガウスノイズ）
- 評価軸: 異常強度（2.0〜3.0σ）、グラフサイズ（20〜100ノード）、グラフ誤指定（SHD）、実行時間
- 評価指標: 上位 1 位再現率（top-1 recall）、100回試行
- **実世界データ**:
- **PetShop** [Hardt+, CLeaR 2024]: マイクロサービスアプリ、68件の性能障害注入、レイテンシ・可用性メトリクス
- **Sock-shop 2** [Pham+, ASE 2024]: 125件の障害注入（CPU/メモリ/ディスク/ネットワーク遅延/パケットロス）
- **ProRCA** [Dawoud+, arXiv 2025]: 小売サービスの半合成データ、4種類の異常
## 実験結果
**図N: SMOOTH TRAVERSAL と SCORE ORDERING の合成データ上での性能（異常強度別）**
![[_attachments/neurips-2025-rca-outliers/fig1-tpr-vs-anomaly-strength.png]]
(図1. 異常強度に対する根本原因特定の真陽性率。強い性能は SMOOTH TRAVERSAL > Traversal > Counterfactual > SCORE ORDERING > Cholesky ≈ Circa の順。)
**図N: ポリツリー vs 一般 DAG の構造差**
![[_attachments/neurips-2025-rca-outliers/fig2-polytree-vs-dag.png]]
(図2. (a) 一般 DAG は無向サイクルを含みうる。(b) ポリツリーは骨格がツリーであり無向サイクルを含まない。)
**図N: 因果グラフ誤指定に対するロバスト性**
![[_attachments/neurips-2025-rca-outliers/fig8-robustness-graph-misspecification.png]]
(図8. 真のグラフからの SHD が増加するにつれた top-1 再現率の変化。SMOOTH TRAVERSAL・Traversal・Counterfactual は SHD/|E|=1 でも 0.6〜0.7 を維持する。)
### 主な定量結果
| シナリオ | SMOOTH TRAVERSAL | SCORE ORDERING | Traversal | Counterfactual |
|---|---|---|---|---|
| 合成（x=3.0, n=50）| ~0.90 | ~0.75 | ~0.90 | ~0.85 |
| PetShop 低トラフィック・可用性 top-1 | 0.75 | **0.75** | 0.42 | 0.00 |
| PetShop 高トラフィック・可用性 top-1 | **1.00** | **1.00** | 0.33 | 0.00 |
| Sock-shop delay top-1 | 0.72 | **0.80** | **0.80** | 0.28 |
| ProRCA FulfillmentSpike top-1 | 0.28 | **0.94** | 0.94 | 0.98 |
- グラフ既知・線形 SCM では Circa が最良（Fig. 5）
- グラフサイズ増大（n=20〜100）では SMOOTH TRAVERSAL・Traversal・Counterfactual は安定、他は低下
- 単一サンプル制約のない RCD（100 サンプル使用）は強力だが、少サンプル設定では SCORE ORDERING が優位
## 考察
- **理論と実験のギャップ**: 理論はポリツリーを仮定するが、実験は一般 DAG で行っており SMOOTH TRAVERSAL は頑健に機能する。付録 E でポリツリー仮定を外した場合でも「スコアが下流で大きくなるケースは稀」であることを線形 SCM で証明している
- **SCORE ORDERING の限界**: ProRCA の ReturnSurge (score=0.00) や ExcessiveDiscount など、スコア順位に根本原因が現れない状況では失敗する。これは「根本原因が必ずしも最も高いスコアを持つわけではない」ケースに対応する
- **スコアのタイ問題**: PetShop では少ないサンプル数のため多数の変数が最高スコアでタイになる。評価結果は楽観的に見える可能性があり、より長い正常期間のデータがあれば解消する
## 強み / 弱点・課題
**強み**:
- 単一異常サンプルからの RCA に初めて非パラメトリックな理論保証を与えた
- SMOOTH TRAVERSAL は閾値設定不要で実装が単純、高速
- SCORE ORDERING は因果グラフすら不要という最も弱い入力要件
- 反実仮想 Shapley 貢献分析 [Budhathoki, ICML 2022] との等価性も示し、理論的一貫性が高い
**弱点・課題**:
- ポリツリー仮定は強い。実世界の密結合マイクロサービスでは成立しない可能性がある
- SCORE ORDERING は ProRCA 等で失敗するケースがあり、スコア順序と根本原因の乖離が問題
- 「根本原因は単一」という仮定が実際の複合障害に対応しない
- PetShop のタイ問題: 正常データが少ないと IT スコアの識別力が著しく低下する