📊 statistics

Root Cause Analysis of Outliers in Unknown Cyclic Graphs

This paper proposes a method to identify a short list of potential root causes for outliers in unknown cyclic causal graphs by leveraging strong perturbations and structural equation propagation, without requiring prior knowledge of the graph structure.

Original authors: Daniela Schkoda, Dominik Janzing

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniela Schkoda, Dominik Janzing

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a giant, complex factory. Inside, hundreds of machines are connected by conveyor belts, gears, and pipes. Sometimes, these connections form loops: Machine A feeds Machine B, which feeds Machine C, which feeds back into Machine A. This is a cyclic graph.

One day, the factory goes haywire. Alarms are blaring, and dozens of machines are acting strangely. Your job is Root Cause Analysis (RCA): You need to find the one (or few) machine that broke first, causing the chain reaction.

The problem? You don't have a blueprint of the factory. You don't know which machine connects to which. And you only have one snapshot of the chaos (one "anomalous sample") to work with.

This paper presents a clever new method to solve this mystery without needing the blueprint. Here is how it works, explained simply:

1. The "Normal" vs. The "Glitch"

First, the method learns what the factory looks like when everything is running smoothly. It studies the "normal" data to understand the usual relationships between machines.

The Analogy: Think of this as learning the normal rhythm of a song. You know how the drums usually beat and how the guitar usually strums.

Then, the glitch happens. The paper assumes that the rules of the factory haven't changed, except for a few specific spots. The gears are still the same size, and the belts are still the same length; only a few machines are being pushed or pulled by an outside force (the "root cause").

The Analogy: Imagine someone suddenly kicking the drum. The song is still the same song, but the drum is hitting a different note. The rest of the band is just reacting to that kick.

2. The Magic "Filter" (The Precision Matrix)

The authors use a mathematical tool called a precision matrix. Think of this as a special pair of glasses or a filter.

When you look at the chaotic factory through these glasses, the noise of the "normal" machines cancels out.
However, the machines that were kicked (the root causes) and the machines directly connected to them (their parents) light up brightly.
The Result: You get a short "shortlist" of suspects. It's not just the one machine that was kicked; it might also include the machine that feeds into it (if they are in a loop). But it filters out all the machines that are just reacting further down the line.

3. Dealing with Hidden Machines (Latent Variables)

Sometimes, there are machines in the factory you can't see (hidden variables). They are connected to the visible ones, but you can't measure them.

The Analogy: Imagine a ghost in the machine room. You can't see it, but it's pushing a lever that affects Machine A and Machine B.
The paper shows that even with these invisible ghosts, the math still works. The "filter" will highlight the visible machines that are being pushed by the ghost, or the machines that are connected to the ghost in a specific zig-zag pattern. It effectively "projects" the hidden chaos onto the visible machines so you can still spot the trouble.

4. Why This is a Big Deal

Before this paper, most methods had two big problems:

They needed the blueprint: They required you to already know exactly how every machine was connected.
They hated loops: They assumed the factory was a straight line (Machine A $\to$ B $\to$ C). If there was a loop (A $\to$ B $\to$ A), the math broke.

This new method is like a detective who can solve the crime without a blueprint and even if the suspect ran in circles. It works with just one snapshot of the disaster, whereas other methods often needed hundreds of snapshots to figure it out.

5. Does it actually work?

The authors tested this on:

Simulated factories: They created fake computer models with loops and hidden machines. Their method found the culprit much faster and more accurately than previous methods.
Real-world data: They tested it on:
- Cloud computing: Finding which microservice caused a crash in a complex web of apps.
- Biology: Identifying which gene was perturbed in a network of genes (where feedback loops are very common).
- Gene expression: Looking at patient data to find the source of a disease.

The Bottom Line

This paper gives us a mathematical "flashlight" to shine on a chaotic system. Even if we don't know the map, and even if the system has confusing loops, this flashlight can pinpoint the small group of machines that started the trouble, allowing us to fix the root cause instead of just treating the symptoms.

Key Limitation: The method assumes that the "rules" of the factory (the connections between machines) didn't change, only the inputs to a few machines did. If the factory completely rewired itself during the glitch, this method wouldn't work. But in many real-world scenarios (like a gene network or a cloud server), the structure usually stays the same while a specific part gets overloaded or broken.

Technical Summary: Root Cause Analysis of Outliers in Unknown Cyclic Graphs

Problem Statement
Root Cause Analysis (RCA) aims to identify the specific nodes in a causal system where an anomaly originates, distinguishing them from nodes that merely exhibit symptoms due to propagation. While existing methods often rely on learning a ground-truth causal graph or assume acyclic structures (Directed Acyclic Graphs or DAGs), real-world systems frequently exhibit cyclic feedback loops (e.g., in gene regulatory networks or microservice architectures). Furthermore, many existing approaches require multiple anomalous samples or restrictive assumptions about the graph structure. This paper addresses the challenge of identifying root causes in unknown cyclic graphs using linear Structural Equation Models (SEMs) and only a single anomalous sample, without prior knowledge of the causal graph.

Methodology
The authors propose a method based on the invariance of structural equations between the normal and anomalous regimes, except for a sparse additive perturbation at the root cause nodes.

Model Formulation:
- The system is modeled as $X = AX + N$, where $A$ is a coefficient matrix (potentially containing cycles) and $N$ is a noise vector with uncorrelated components.
- An anomalous sample $\tilde{X}$ is modeled as $\tilde{X} = A\tilde{X} + N' + \Delta$ , where $\Delta$ is a sparse vector representing the perturbation at the root cause nodes.
- The method assumes the linear relations (matrix $A$ ) remain unchanged; only the noise term is perturbed.
Causally Sufficient Cyclic Model:
- The core insight involves the precision matrix $\Theta_{XX} = \Sigma_{XX}^{-1}$ .
- By applying the precision matrix to the outlier vector ( $\xi = \Theta_{XX}\tilde{X}$ ), the authors derive that the resulting vector $\xi$ deviates from its normal distribution only at the root cause nodes and their parents.
- Theorem 3.1: For generic parameters, the set of nodes where $\xi_i$ differs in distribution from the normal case is a subset of the root causes $R$ union their parents $pa(R)$.
- Theorem 3.2: This list can be further refined by intersecting with nodes that are themselves anomalous in the observed data ( $\tilde{X}_i$ ), yielding a shortlist of root causes and parents that are also descendants.
Handling Latent Variables:
- The method extends to scenarios with unobserved (latent) variables by marginalizing them out. This results in a projected SEM where the noise terms of observed variables may become correlated.
- The precision matrix of the observed variables is derived, and the support of the perturbation is shown to include nodes connected to observable root causes via "zig-zag" structures (sequences of latent paths).
Implementation and Statistical Control:
- The algorithm estimates the precision matrix from normal samples (using Graphical Lasso or direct inversion).
- It computes a score vector $\xi$ for the anomalous sample.
- To control the False Discovery Rate (FDR) when selecting candidates, the method employs e-values (specifically, the squared Z-score normalized by the variance) rather than p-values, allowing for robust multiple testing correction even with dependencies.
- A final score is assigned by setting scores to zero for nodes that are not themselves outliers (based on a threshold $\tau$ ).

Key Contributions

Cyclic Graph Capability: The paper provides the first provable method for RCA in unknown cyclic graphs using a single anomalous sample, overcoming the acyclic assumption of prior work (e.g., Li et al., 2025).
No Ground Truth Required: The approach does not require the causal graph to be known or learned beforehand; it relies solely on the covariance structure of the normal data.
Theoretical Guarantees: The authors prove that the method identifies a "shortlist" of candidates containing the true root causes and their parents (specifically those lying on a cycle with the root cause).
Latent Variable Robustness: The framework is extended to handle latent variables, identifying "observable root causes" (the earliest observed nodes infected by the anomaly).
Computational Efficiency: By avoiding expensive combinatorial searches (such as permutation searches used in previous methods), the proposed method is computationally efficient, dominated by the cost of precision matrix estimation.

Results

Simulations: In synthetic experiments with 50 and 100 nodes (both cyclic and acyclic, with and without latent variables), the proposed method (using Graphical Lasso or Inverse Covariance) consistently outperformed the Cholesky-decomposition-based method (Li et al., 2025) and the BARO benchmark. It achieved higher accuracy in ranking the true root cause, particularly in cyclic settings and larger graphs, while being significantly faster.
Real-World Data: The method was evaluated on diverse benchmarks including:
- Microservice Systems: PetShop, Sock Shop, Online Boutique, and Train Ticket.
- Biological Data: Gene expression data from patients with Mendelian diseases.
- Synthetic Benchmarks: CIRCA and RCD datasets.
- Findings: The method performed competitively or superiorly to existing baselines (Cholesky, Z-Score, BARO). Notably, it outperformed Cholesky on gene expression data and continuous microservice data, while handling high-dimensional cases (where features > samples) via shrunk covariance estimators.

Significance and Claims
The authors claim this is the only method that provably works for unknown cyclic graphs using a single anomalous sample. The significance lies in its ability to operate under the "Sparse Mechanism Shift" hypothesis, where distributional shifts are attributed to changes in only a few mechanisms (the root causes), while the rest of the system's structural equations remain invariant. The paper emphasizes that this assumption is critical for defining the RCA task; without it, any node could theoretically be a root cause. The method offers a practical, computationally efficient solution for reliability engineering in complex, cyclic systems where ground-truth graphs are unavailable.