🤖 AI

Root cause analysis via difference graph discovery from linear time-series data

This paper proposes a root cause analysis framework for linear time-series data that identifies effect-defying anomalies by adapting difference graph discovery methods to detect changes in causal coefficients between normal and anomalous regimes, demonstrating its effectiveness on both simulated and real-world datasets from IT and intensive care monitoring.

Original authors: Anouk Ruer, Timothée Loranchet, Daria Bystrova, Charles K. Assaad

Published 2026-08-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anouk Ruer, Timothée Loranchet, Daria Bystrova, Charles K. Assaad

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

In the complex machinery of modern life, from the servers that power our digital world to the monitors tracking a patient's vital signs in a hospital, systems are constantly in motion. These systems generate streams of data that ebb and flow, revealing patterns of normal operation. But when something goes wrong, the data shifts. A sudden spike in temperature, a drop in pressure, or a glitch in a network can signal a crisis. The challenge for engineers and doctors is not just to see that something is wrong, but to find out exactly why. This is the task of root cause analysis: tracing a chaotic symptom back to the single broken mechanism that started it all. To do this, researchers often look at how different parts of a system influence one another over time. They map out these relationships, creating a picture of who affects whom. When a system breaks, the way these parts interact often changes. The goal is to spot those specific changes in the relationships, rather than just looking at the symptoms themselves.

A team of researchers at Sorbonne Université in Paris has developed a new way to find these hidden causes by focusing on the differences between how a system behaves when it is healthy and how it behaves when it is sick. They call their approach "difference graph discovery." Imagine two maps of the same city: one drawn when the traffic is flowing smoothly, and another drawn during a massive gridlock. The streets and intersections are the same, but the rules of the road have changed. Perhaps a specific intersection that usually allows cars to turn left now forces them to go straight, or a bridge that was open is now closed. By comparing these two maps, one can pinpoint exactly where the rules have shifted. In the same way, the researchers compared the "map" of relationships in a computer system or a human body during normal times against the map during an anomaly. They were looking for the specific connections that had changed their strength or direction, as these changes point directly to the source of the trouble.

The researchers focused on systems that can be described by straight-line relationships, where one variable influences another in a predictable, linear way. They tested their method on two very different kinds of real-world data. First, they looked at data from an IT monitoring system, which tracks the flow of messages through a complex pipeline of computer components. In this system, they found that their method could successfully identify a specific component responsible for a failure, distinguishing it from other parts of the system that were merely reacting to the problem. Second, they applied the technique to data from an intensive care unit, tracking nine different physiological signals from a patient, such as heart rate, blood pressure, and oxygen levels. Here, the method helped narrow down a list of potential causes for a sudden change in the patient's condition, highlighting a small group of variables that were behaving differently than usual.

To ensure their findings were solid, the team also created thousands of simulated scenarios where they knew exactly which part of the system was broken. They fed this fake data into their new algorithms and compared the results against other existing methods. The results showed that their approach was particularly good at finding the true cause, especially when they combined their difference-finding technique with standard methods for mapping causal relationships. In many cases, other methods either missed the cause entirely or flagged too many variables as suspects, leaving the investigator with a long, unhelpful list. The new method, however, was able to isolate the specific mechanism that had changed, providing a much clearer path to the root of the problem.

The researchers also explored how their method handles different types of changes. Sometimes, a problem arises because a single connection between two variables changes. Other times, multiple connections change at once. Their analysis showed that the method works best when there are enough changes to create a clear pattern, allowing the algorithm to figure out the direction of influence. For instance, if two variables both start affecting a third variable in a new way, the method can use that structure to determine the direction of the change with high confidence. While the method relies on certain assumptions about how the data is generated, such as the idea that the underlying rules of the system remain steady within each state, the experiments suggest it is a robust tool for understanding dynamic systems.

This work does not claim to solve every mystery in system monitoring. The researchers acknowledge that their method requires a significant amount of data and can become computationally heavy if the system has too many variables or if the time delays between causes and effects are very long. They also note that their approach is designed for linear systems, where the relationships between variables are straightforward, and may not apply to systems with highly complex, non-linear interactions. However, for the vast number of systems that operate within these linear bounds, the study offers a powerful new lens. By shifting the focus from the symptoms of a failure to the structural changes in the system's relationships, the researchers have provided a way to cut through the noise and find the true source of an anomaly. Whether it is a server farm struggling to keep up with demand or a patient's heart rate dipping unexpectedly, the ability to see exactly which connection has broken changes the game from guessing to knowing.

Technical Summary: Root Cause Analysis via Difference Graph Discovery from Linear Time-Series Data

Problem Definition

Root cause analysis (RCA) aims to identify the mechanisms responsible for anomalies in complex dynamical systems. While existing methods often rely on predefined causal graphs or static data, many real-world systems (e.g., IT infrastructure, intensive care monitoring) evolve over time. This paper addresses the challenge of performing RCA in linear time-series data where the system transitions from a normal regime ( $N$ ) to an anomalous regime ( $\bar{N}$ ).

The authors specifically focus on detecting effect-defying root causes. These are defined as time-series variables whose causal coefficients (the strength of the relationship between a cause and its effect) change between the normal and anomalous regimes. The goal is to leverage difference graph discovery—originally developed for static populations—to identify these structural changes in a dynamic, time-series setting.

Methodology

The paper formalizes the problem using Linear Discrete-Time Dynamic Structural Causal Models (DT-DSCM). The system is represented by a Full-Time Directed Acyclic Graph (FT-DAG), where vertices are time-indexed variables and edges represent direct causal relationships (both instantaneous and lagged).

The core contribution is the adaptation of two static difference graph discovery algorithms, LDiffPC and DCI, to the time-series domain. The authors propose four specific algorithms:

tsLDiffPC: A time-series extension of LDiffPC.
- Skeleton Estimation: It iteratively removes edges between variables $X_{t-\ell}$ and $Y_t$ if their regression coefficients are statistically equal across regimes ( $N$ and $\bar{N}$ ) given a conditioning set $S$ .
- Orientation: It orients lagged edges based on temporal order. Instantaneous edges are oriented using collider detection rules (if $X_{t-\ell} - Z_t - Y_t$ forms a collider, $Z_t$ is the common effect) and Meek's orientation rules.
- Assumptions: Relies on diff-adjacency-faithfulness and diff-orientation-faithfulness.
tsDCI: A time-series extension of DCI.
- Skeleton Estimation: Identical to tsLDiffPC.
- Orientation: Instead of collider rules, it exploits changes in residual variances. If the residual variance of $Y_t$ is invariant across regimes given a set $S$ (where $Y_t \notin S$ ), the edge is oriented $X_t \to Y_t$ .
- Assumptions: Relies on diff-adjacency-faithfulness and var-orientation-faithfulness (invariance of residual variances).
tsLDiffPC2 and tsDCIPC: Augmented variants.
- These methods first run the respective base algorithm (tsLDiffPC or tsDCI) to find the difference graph skeleton.
- They then apply a standard causal discovery algorithm (tPC) to the normal regime data alone to infer orientations.
- These inferred orientations are projected onto the difference graph to resolve ambiguities (e.g., orienting edges that the difference graph alone could not).
- Assumption: Requires that the anomalous graph is a subgraph of the normal graph ( $E_{\bar{N}} \subseteq E_N$ ), implying anomalies modify existing mechanisms rather than creating entirely new ones.

Key Contributions

Formalization of Time-Series Difference Graphs: The authors define the Full-Time Difference Graph (FT-DFG), a directed graph where edges represent causal coefficients that differ between two regimes. They provide theoretical guarantees (Theorems 1 and 2) for the correctness of the proposed algorithms under specific faithfulness and stationarity assumptions.
Algorithmic Adaptation: The paper extends static difference graph methods (LDiffPC, DCI) to handle temporal dependencies, explicitly handling lagged and instantaneous effects.
Root Cause Identification Framework: The authors establish that any variable targeted by a directed edge in the recovered FT-DFG is a confirmed effect-defying root cause. Undirected edges indicate a pair of potential root causes.
Theoretical Guarantees: The paper proves that under perfect conditional equality information and the stated assumptions, the algorithms recover the true skeleton of the difference graph and a subset of the true directed edges.

Experimental Results

The proposed methods were evaluated on simulated data and two real-world datasets: IT monitoring (Ingestion pipeline) and Intensive Care Monitoring (MIMIC-IV).

Simulated Data:
- The algorithms were compared against baselines including MicroCause, RCD, and direct extensions like tPCUnion.
- tsDCI and tsDCIPC generally achieved the highest F1-scores when only confirmed root causes were considered.
- tsLDiffPC often failed to orient edges in simple settings (single changed parent) but performed competitively when multiple parents changed (facilitating collider detection).
- When considering "potential" root causes (including undirected edges), the performance of tsLDiffPC improved significantly, highlighting that its primary limitation is the partial orientation of the graph.
Real-World Data (IT Monitoring):
- On the Ingestion dataset, all tsLDiffPC and tsDCI variants consistently identified ESB (Elasticsearch writing) as the effect-defying root cause, aligning with expert knowledge and the EasyRCA method.
- Baselines like tPCUnion and tsiSCAN identified almost all variables as root causes (high false positives), while tsMBGH detected none.
Real-World Data (Intensive Care):
- Applied to ICU patient signals (e.g., blood pressure, heart rate), the methods identified a consensus set of candidate root causes: RR (Respiratory Rate), HR (Heart Rate), PAPm, ABPm, and CVPm.
- While ground truth is unavailable, there was significant agreement among the difference graph methods on these physiological variables, whereas other baselines (like RCD) selected variables not identified by the proposed methods.

Significance and Claims

The paper claims that difference graph discovery is a powerful, under-explored tool for root cause analysis in time-series data. By shifting the focus from identifying which variable is anomalous to identifying which causal mechanism has changed, the proposed methods can localize the structural drivers of system failures.

The authors emphasize that their approach is particularly suited for effect-defying root causes, where the relationship between variables shifts between regimes. They acknowledge limitations, noting that the methods rely on assumptions such as causal sufficiency (no unmeasured confounders), linearity, and stationarity within regimes. Furthermore, they note that computational costs increase with the number of variables and the maximum time lag, which may restrict applicability to very large-scale systems.

Ultimately, the work demonstrates that adapting difference graph discovery to linear time-series provides a rigorous framework for diagnosing dynamic system anomalies, offering a middle ground between purely statistical anomaly detection and full causal discovery.