Research map / Probabilistic and scientific modeling / Causal discovery
Root Cause Analysis of Outliers with Missing Structural Knowledge
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SMOOTH TRAVERSAL and SCORE ORDERING, two RCA methods that use only marginal information-theoretic anomaly scores from a single anomalous sample, with probabilistic guarantees for polytree causal graphs.
Problem
Root cause analysis of a single anomalous sample when the post-intervention distribution is unknown or only one sample is available, and conditional probability estimation is statistically ill-posed.
Approach
Defines information-theoretic (IT) anomaly scores as negative log tail probabilities, shows that score jumps along causal paths are bounded (anomalies rarely cause much larger anomalies), and uses marginal score differences with a known DAG (smooth traversal) or top-scoring anomalies without a DAG (score ordering) to find the root cause with guarantees in polytrees.
Key results
- On synthetic data, SMOOTH TRAVERSAL, Traversal and Counterfactual are the strongest methods and outperform SCORE ORDERING across anomaly strengths 2.0 to 3.0.
- SMOOTH TRAVERSAL and Traversal are the fastest methods in runtime scaling experiments.
- On real-world and semi-synthetic data, SCORE ORDERING often performs well but both proposed methods are sometimes outperformed by Cholesky, Circa or Counterfactual.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Smooth Traversal (score-difference traversal, requires causal graph) instead of threshold-based traversal | Root cause analysis with known DAG · Synthetic random DAGs | top-1 recall | No clear effect |
| Use Score Ordering (top-scoring marginal anomalies, no causal graph) instead of graph-based methods | Root cause analysis without known DAG · Synthetic random DAGs | top-1 recall | Hurt |
| Use Score Ordering instead of graph-based methods | Root cause analysis without known DAG · Real-world and semi-synthetic data | top-1 recall | Mixed |
| Increase anomaly strength injected at root cause (2.0 to 3.0) | Score Ordering · Synthetic random DAGs | top-1 recall | Helped |
| Increase graph size from 20 to 100 nodes | Score Ordering, Cholesky, Circa · Synthetic random DAGs, x=3 | top-1 recall | Hurt |
| Increase graph size from 20 to 100 nodes | Smooth Traversal, Traversal, Counterfactual · Synthetic random DAGs, x=3 | top-1 recall | No clear effect |
| Graph misspecification (random edge additions/removals/reversals) on n=50, x=3 | Smooth Traversal vs Circa · Synthetic random DAGs | top-1 recall | Hurt |
| Graph misspecification (random edge additions/removals/reversals) on n=50, x=3 | Smooth Traversal · Synthetic random DAGs | top-1 recall | No clear effect |
Surprising findings
- SCORE ORDERING performance improves slightly as anomaly strength increases while other approaches stay roughly constant.
- Circa and Cholesky perform considerably worse on synthetic data, apparently due to the linearity assumption.
Limitations
- Guarantees are proven only for polytree causal graphs with a single root cause; the main experiments include general DAGs where guarantees may not hold.
- Score typicality assumption is needed for the main bounds, holding only approximately for random samples in general.
- SCORE ORDERING performance decays as graph size grows, and it is weaker than traversal-based methods on synthetic data.
Experimental setup
Datasets: PetShop Sock-shop 2 ProRCA semi-synthetic datasets
Benchmarks: PetShop Sock-shop 2 ProRCA semi-synthetic
Metrics: top-1 recall true positive rate runtime
Baselines: Cholesky Traversal Circa Counterfactual RCD epsilon-Diagnosis
Builds on: Budhathoki et al. contribution analysis (Shapley-based RCA) traversal-based RCA Cholesky-based RCA Circa Fisher's method Tippett's method
Closest papers by meaning
- Root Cause Analysis of Measurement and Mechanistic Anomalies (NeurIPS 2026 · similarity 0.92)
- Robust Root Cause Diagnosis using In-Distribution Interventions (ICLR 2025 · similarity 0.86)
- Where Root Cause Analysis Fails: A Retrieval-Reranking Decomposition (NeurIPS 2026 · similarity 0.86)
- PRIM: Meta-Learned Bayesian Root Cause Analysis (NeurIPS 2026 · similarity 0.85)
- Local Identifying Causal Relations in the Presence of Latent Variables (ICML 2025 · similarity 0.85)
- Identification of Causal Structure in the Presence of Missing Data with Additive Noise Model (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.