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.
Figures & tables
Figure 1: FT-DAG with a regime change at time t and ℓmax=1 . The vertices highlighted in orange are affected by a change in its causal mechanism; in this example, the time-series Y is an effect-defying root cause. We consider two settings depending on how the causal mechanism of Y changes: (i) Setting R, where only the red edges are changed, and (ii) Setting RB, where both the red and blue edges are changed. Note that the causal mechanism can also be changed through a lagged mechanism, such as Yt−1→Zt , where Z would be the root cause.
Figure 2: FT-DFGs corresponding to the FT-DAG in Figure 1 . The left panel shows the FT-DFG for Setting R, where only the red edges in Figure 1 are changed. The right panel shows the FT-DFG for Setting RB, where both the red and blue edges in Figure 1 are changed.
Figure 3: FT-DFGs recovered by the considered algorithms. The left panel shows the output of tsLDiffPC in Setting R. The middle panel shows the output of tsLDiffPC 2 and tsDCIPC in Setting R. Under the variance-invariance condition required by DCI, tsDCI recovers the same graph. The right panel shows the output of tsLDiffPC, tsLDiffPC 2 , and tsDCIPC in Setting RB; under the same condition, tsDCI recovers an identical graph.
Assumption
tsLDiffPC
tsLDiffPC 2
tsDCI
tsDCIPC
Linearity
✓
✓
✓
✓
Sufficiency (As. 1 )
✓
✓
✓
✓
Stationarity (As. 2 )
✓
✓
✓
✓
Anomalies (As. 3 )
✓
✓
✓
✓
Order (As. 4 )
✓
✓
✓
✓
D. a. faithful. (As. 5 )
✓
✓
✓
✓
Table 1: Assumptions required by each algorithm for soundness.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: window graph corresponding to the FT-DAG of Figure 1 , with ℓmax=1 . Only time steps t−1 and t are represented. In this case, the window graph is identical across both regimes.
Figure 6: The two causal graphs and the corresponding difference graph such that b,a,a′>0 , and a=a′ .
Figure 9: Time series of the eight bolt-level capacity metrics recorded in the IT monitoring system. The blue and red segments correspond to the Normal and Anomalous regimes respectively, as defined by the known changepoint at t=46683 (dashed orange line). Each metric is displayed on its own scale.
Figure 10: Time series of the nine physiological variables recorded for the selected MIMIC-IV patient. The blue and red segments correspond to the Normal and Anomalous regimes respectively, as defined by the changepoint detected on ST-V via PELT (dashed orange line). Each variable is displayed on its own scale.
Figure 11: FT-DFG discovered by tsLDiffPC/tsLDiffPC 2 /tsDCI/tsDCIPC on the IT monitoring data. Vertices that are not linked to anything are omitted. The graph inferred by tsiSCAN and tPCUnion is not shown because it contains many edges, while the graph inferred by tsMBGH is not shown because it is an empty graph.
Figure 12: FT-DFGs discovered by tsLDiffPC and tsLDiffPC 2 (left), by tsDCI and tsDCIPC (middle) and tsISCAN (right) on the MIMIC-IV patient. Isolated vertices are omitted. The graph inferred by tPCUnion is not shown because it contains many edges, while the graph inferred by tsMBGH is not shown because it is an empty graph.
German Research Center for Artificial Intelligence (DFKI), Kaiserslautern, Germany · Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Germany · Paul Wurth S.A, Luxembourg