Source-linked AI summary
Root cause analysis via difference graph discovery from linear time-series data
Anouk Ruer, Timothée Loranchet, Daria Bystrova, Charles K. Assaad
TL;DR
The paper addresses root cause analysis for linear time series by adapting difference graph discovery to compare normal and anomalous regimes. It develops time-series extensions for detecting effect-defying root causes and evaluates them on simulated and monitoring data, showing potential for localizing structural changes. The approaches are bounded by causal-model assumptions and increasing computational cost with system size and maximum lag.
Problem
Root cause analysis needs methods for identifying causal mechanisms behind anomalies in evolving systems, while existing difference graph discovery methods are mostly designed for static data.
Method
The paper extends DCI and LDiffPC to linear time-series data, comparing causal structures between preassigned normal and anomalous regimes.
Results
The proposed methods recover effect-defying root causes under stated assumptions and show practical relevance on simulated, IT-monitoring, and intensive-care monitoring datasets.
Takeaways & Limitations
Difference graph discovery can help localize structural changes associated with observed anomalies in time-series systems.
Takeaways & Limitations
The approaches rely on assumptions about causal structure and data generation, and their computational cost increases rapidly with the number of variables and maximum time lag.
Abstract
from arXiv · showhide
Root cause analysis aims to identify the mechanisms responsible for anomalies in complex dynamical systems. In this paper, we study root cause analysis in linear time-series through the lens of difference graph discovery. We focus on effect-defying root causes, corresponding to variables whose causal coefficients change between a normal and an anomalous regime. We formalize this problem using linear discrete-time dynamic structural causal models and adapt several methods originally introduced for discovering difference graphs between two populations to the time-series setting, where the two populations are replaced by a normal and an anomalous regime. We first evaluate the proposed approaches on simulated data, and then demonstrate their practical relevance on real-world datasets from IT monitoring and intensive care monitoring. Our results show how difference graph discovery can help localize causal mechanisms responsible for anomalous behavior.
1 Introduction
The paper frames root cause analysis as identifying mechanisms behind system changes and proposes time-series difference graph discovery to detect causal changes between normal and anomalous regimes.
- Root cause analysis identifies mechanisms responsible for observed changes across scientific and industrial domains.Applications include climate science, IT monitoring, and healthcare.
- Difference graph discovery methods identify changes in dependency or causal structures across datasets, but their root-cause-analysis potential remains largely unexplored.
- The paper extends DCI and LDiffPC from static data to time series, targeting dynamic structural changes between normal and anomalous regimes.It also provides theoretical correctness guarantees for the time-series setting.
- The proposed methods focus on effect-defying root causes, where causal coefficients change between normal and anomalous regimes, and are evaluated on simulated, IT-monitoring, and intensive-care data.
- The paper is organized around preliminaries, related work, time-series algorithm extensions, root-cause detection, experiments, and conclusions.
2 Background
The paper models normal and anomalous regimes with linear dynamic structural causal models and defines difference graphs through changed causal coefficients, emphasizing time-series-level effect-defying root causes.
- The model uses multivariate time series governed by an unknown linear discrete-time dynamic structural causal model.The model captures temporal and causal dependencies among time-indexed variables.
- The analysis assumes causal sufficiency, meaning noise terms are mutually independent and each affects only one observed variable.
- Observations are assigned beforehand to normal or anomalous regimes before difference graph discovery is applied.This regime-label assumption is shared by the difference-graph and root-cause-analysis settings described here.
- Within each regime, causal coefficients are time-invariant and noise is identically distributed over time, with a finite maximal lag ℓmax supplied or bounded by domain knowledge.
- The two illustrative settings differ by whether only red edges or both red and blue edges change, producing corresponding full-time difference graphs.
- Root causes are defined at the time-series level as variables whose changes trigger and propagate anomalies, rather than at individual time points.This matches applications where experts seek the malfunctioning process rather than the exact onset time.
- An effect-defying root cause is a variable whose causal coefficient changes across regimes, while a noise-defying root cause has a changed noise distribution.
- The full-time difference graph contains edges for parent-effect pairs whose causal coefficients differ between the normal and anomalous models.The framework assumes an acyclic difference graph and a common topological ordering.
3 Related Work
Related work includes root-cause methods that use predefined or learned causal graphs and difference-graph methods that compare mechanisms across environments.
- Existing root-cause methods either rely on a predefined causal graph or estimate causal relations from data.Examples include MicroCause, RCD, and T-RCA.
- The paper builds on difference-graph discovery methods that directly estimate how causal mechanisms vary across environments using equality tests.
- LDiffPC recovers a graph skeleton by testing equality of regression coefficients across environments, then orients edges using collider detection and Meek propagation.
- DCI uses the same skeleton procedure as LDiffPC but orients edges through changes in residual variances across environments.
- Other approaches use covariance differences or distributional invariance rather than equality tests.MBGH relies on covariance differences, while iSCAN targets nonlinear additive-noise models.
4 Difference graph discovery: from static to time-series
The paper extends difference graph discovery to linear time-series by adapting methods that compare causal or dependency structures between normal and anomalous regimes. The resulting algorithms provide partially oriented difference graphs with correctness guarantees under explicit faithfulness and variance assumptions.
- The proposed methods output partially oriented difference graphs, with directed and undirected edges representing changes between regimes.The methods do not return fully oriented FT-DFGs.
- tsLDiffPC: tsLDiffPC estimates the difference-graph skeleton by testing regression-coefficient equality across regimes, then orients lagged and selected instantaneous edges.It progressively increases conditioning-set size and uses temporal order and collider detection during orientation.
- tsLDiffPC: Diff-adjacency-faithfulness and diff-orientation-faithfulness are sufficient for tsLDiffPC correctness, improving on the stronger assumptions used originally for LDiffPC.Under these assumptions and perfect conditional equality information, the estimated skeleton matches the true skeleton and estimated directed edges are correct.
- tsDCI: tsDCI uses the same skeleton procedure as tsLDiffPC but orients instantaneous edges through invariance of residual variances across regimes.Its correctness requires diff-adjacency-faithfulness together with a residual-variance orientation assumption.
- tsDCI: tsDCI can orient certain isolated changed edges, whereas tsLDiffPC may leave them unoriented when temporal, collider, and Meek rules provide insufficient information.In Setting R, residual-variance invariance can orient the changed edge toward the affected variable.
- Augmented methods: The augmented tsLDiffPC2 and tsDCIPC transfer orientations learned by tPC from the normal regime to unresolved edges in the difference graph.They assume the anomalous graph is a subgraph of the normal graph; under their assumptions, their estimated skeletons are correct and directed edges are sound.
5 Difference graph discovery for detecting root causes
Once an FT-DFG is estimated, directed changed edges identify confirmed effect-defying root causes, while undirected edges yield potential root-cause pairs. Under the stated assumptions and perfect conditional equality information, the methods provide sound recovery guarantees, though some causes may remain unresolved.
- Directed edges returned by the algorithms identify confirmed effect-defying root causes because each corresponds to a true changed edge.
- Undirected changed edges indicate that at least one endpoint is a root cause, producing pairs of potential root causes.
- The estimated confirmed root causes are a subset of the true root causes, while every potential pair contains at least one true root cause.
- All unresolved root causes can be covered by selecting one variable from each detected potential pair, although certainty is not guaranteed.
6 Experiments
The experiments compare the proposed time-series difference-graph methods with root-cause baselines on simulated, IT-monitoring, and intensive-care data. Results show complementary strengths across simulated settings and identify plausible root causes in both real-world datasets.
- The study compares tsLDiffPC, tsLDiffPC2, tsDCI, and tsDCIPC with MicroCause, RCD, and naive temporal graph-discovery extensions.
- Simulated data: Simulations use random finite-lag causal graphs with 3, 5, 7, or 9 time-series and three anomaly settings based on changed incoming coefficients.
- Simulated data: Mean F1-score evaluates predicted confirmed root causes alone or confirmed plus potential root causes against the true root-cause set.
- Simulated data: tsDCI and tsDCIPC perform best overall in the first two settings for confirmed causes, while tsLDiffPC-based methods become competitive in the third setting.
- IT monitoring: On IT-monitoring data, all tsLDiffPC- and tsDCI-based methods detect ESB as an effect-defying root cause alongside three false positives.
- Intensive care monitoring: On the intensive-care record, tsLDiffPC-based methods identify RR, HR, PAPm, ABPm, and CVPm, while most algorithms agree on PAPm, CVPm, and RR.
7 Conclusion
The paper demonstrates the potential of difference-graph discovery for identifying structural changes associated with anomalies in time-series data, while noting assumptions and scalability constraints.
- The approaches rely on assumptions about the underlying causal structure and data-generating processes.
- Computational cost increases rapidly with the number of variables and the maximum time lag, limiting applicability to large-scale systems.
- A window graph provides a finite representation of a full-time DAG when causal stationarity and a maximum lag ℓmax hold.
- With ℓmax = 1, the window graph contains only time steps t−1 and t and is identical across regimes when the full-time DAG is unchanged.
- Diff-faithfulness can fail even when diff-adjacency-faithfulness and diff-orientation-faithfulness hold, because causal effects may cancel across paths.
B.2 Proofs for tsLDiffPC
The proofs establish correctness of the time-series difference-graph procedures by recovering the skeleton and orienting edges using conditional equality, temporal order, collider structure, variance criteria, and Meek rules.
- Skeleton construction: The skeleton phase removes Xt−ℓ−Yt exactly when a conditioning set S yields equal conditional coefficients across regimes.
- Skeleton construction: Every true difference edge is preserved, while every non-edge is removed under the stated assumptions and perfect conditional equality information.
- Orientations: Lagged edges are oriented according to temporal order, with Xt−ℓ→Yt for ℓ > 0.
- Orientations: Unshielded colliders are correctly oriented because the recovered skeleton preserves nonadjacency and separating sets exclude the collider node.
- Orientations: tsDCI orients remaining contemporaneous edges using variance equality, while Meek rules complete orientations subject to temporal order.
- Algorithms: The algorithms are implemented as procedures that initialize a complete undirected graph, remove edges using regime comparisons, orient lagged edges, and apply orientation rules.
D Sensitivity analysis
The sensitivity analysis repeats simulations at α = 0.01 and α = 0.1 and compares them with the main α = 0.05 results.
- Across α ∈ {0.01, 0.05, 0.1}, the relative ranking of the proposed methods remains largely unchanged.
- Figure 8 reports mean F1-score for eight methods as a function of the number of vertices across three settings at α = 0.1.
E Real Data Visualization
The real-data visualization shows IT and ICU monitoring time series, distinguishing normal and abnormal regimes and marking the presumed regime change point.
- Each visualization contains one time series per variable, with the normal regime in blue and the abnormal regime in red.
- A dashed orange line marks the presumed regime change point in both monitoring datasets.
F Inferred graph using real data
The paper compares FT-DFGs inferred by multiple difference-graph methods on IT monitoring and MIMIC-IV data. Isolated vertices are omitted to improve readability.
- FT-DFGs are reported for both the IT monitoring and MIMIC-IV patient applications.
- The graphical representations provide a direct comparison of structural changes identified by the evaluated methods.
- Isolated vertices are omitted from the displayed graphs for readability.
G.1 Root cause analysis
The paper situates its root cause analysis approach among causal-discovery and difference-graph methods, emphasizing effect-defying causes and comparisons across normal and anomalous regimes. It also illustrates the inferred graphs on IT monitoring and MIMIC-IV data.
- Many existing dynamical-system root cause methods require background knowledge, such as a predefined causal graph or system architecture.
- Causal-discovery approaches learn temporal causal relations from anomalous time series, but their ability to detect the paper’s targeted root causes may remain unclear.
- The paper focuses on effect-defying root causes, whereas several outlier methods address noise-defying causes from a single anomalous observation.
- Comparing causal graphs learned separately in each regime captures structural changes but misses coefficient changes that do not alter whether edges are present.
- LDiffPC and DCI discover partially oriented difference graphs in linear non-dynamic structural causal models using equality tests for regression coefficients.
- Other difference-graph methods use covariance-based recursive peeling or distributional invariance for nonlinear additive-noise models.