A Causal Approach to Detecting Multivariate Time-series Anomalies and Root Causes
Authors: Wenzhuo Yang
Kun Zhang
Steven Hoi
Venue: Submitted to ICLR 2023 (2023)
Keywords: time series
anomaly detection
root cause analysis
causality

Abstract: Detecting anomalies and the corresponding root causes in multivariate time series plays an important role in monitoring the behaviors of various real-world systems, e.g., IT system operations or manufacturing industry. Previous anomaly detection approaches model the joint distribution without considering the underlying mechanism of multivariate time series, making them computationally hungry and hard to identify root causes. In this paper, we formulate the anomaly detection problem from a causal perspective and view anomalies as instances that do not follow the regular causal mechanism to generate the multivariate data. We then propose a causality-based framework for detecting anomalies and root causes. It first learns the causal structure from data and then infers whether an instance is an anomaly relative to the local causal mechanism whose conditional distribution can be directly estimated from data. In light of the modularity property of causal systems (the causal processes to generate different variables are irrelevant modules), the original problem is divided into a series of separate, simpler, and low-dimensional anomaly detection problems so that where an anomaly happens (root causes) can be directly identified. We evaluate our approach with both simulated and public datasets as well as a case study on real-world AIOps applications, showing its efficacy, robustness, and practical feasibility.

Under review as a conference paper at ICLR 2023
A CAUSAL APPROACH TO DETECTING MULTIVARIATE TEME-SERIES ANOMALIES AND ROOT CAUSES
Anonymous authors Paper under double-blind review
ABSTRACT
Detecting anomalies and the corresponding root causes in multivariate time series plays an important role in monitoring the behaviors of various real-world systems, e.g., IT system operations or manufacturing industry. Previous anomaly detection approaches model the joint distribution without considering the underlying mech- anism of multivariate time series, making them computationally hungry and hard to identify root causes. In this paper, we formulate the anomaly detection problem from a causal perspective and view anomalics as instances that do not follow the regular causal mechanism generate the multivariate data. We then propose causality-basse framework for detecting anomalies and root causes, first learns the causal structure from data and then infers whether instance is anomaly relative to the local causal mechanism whose conditional distribution can be di- rectly estimated from data. In light of the modularity property of causal systems (the causal processes to generate different variables are irrelevant modules). the original problem is divided into a series of separate, simpler, and low-dimensional anomaly detection problems so that where an anomaly happens (root causes) can be directly identified. We evaluate our approach with both simulated and public datasets as well as case study on real-world AIOps applications, showing its efficacy, robustness, and practical feasibility.
INTRODUCTION
Multivariate time series is ubiquitous in monitoring the behavior of complex systems in real-world applications. such as IT operations management, manufacturing industry and cyber security (Hund-) man et al., 2018 Mathur Tippenhauer 2016 Audibert et 2020). Such data includes the mea- surements of the monitored components, e.g., the operational KPI metrics such as CPU/Database us- ages in an system, important task in managing these complex systems is detect unexpected observations deviated from normal behaviors, figure out the root causes of abnormal behaviors, and notify the operators timely to resolve the underlying issues. Detecting anomalies and corresponding root causes in multivariate time series aims to accomplish this task and has been actively studied in machine learning, which automate the identification of issues and incidents for improving system availability in A1Ops (AI for IT Operations) (Dang et al. 2019).
Various algorithms have been developed to detect anomalies multivariate time series data. In gen- eral, there are two kinds of directions commonly explored, i.e., treating each dimension individually using univariate time series anomaly detection algorithms (Hamilton) 1994] TTyloo & Letham 2018 Ren al. 2019), and treating all the dimensions detection al ggorritmss (Zong et al.) 2018) Park et al.) 2017); Su et al. 2019). The first direction ignores the dependencies between different time series, so may be problematic especially when sudden changes of certain dimension do not necessarily mean failures of the whole system, or the relations among the time series become anomalous (Zhao et al. 2020). The second direction takes the de- pendencies into consideration, which are more suitable for real-world applications where the overall status of system more concerned about than a single dimension. Recently, deep learning receives much attention in anomaly detection, e.g., DAGMM (Zong et al. 2018), LSTM-VAE (Park et al.) 2017) and OmniAnomaly (Su et al. 2019), which infer dependencies between different time series and temporal patterns within one time series implicitly. Recently, Dai & Chen (202)) developed aaspp-eeggmeteed normalizing flow approach that models the joint distribution via the learned DAG. However, the dependencies inferred by deep learning models do not represent the underlying pro-
entity using multivariate time series anomaly

---

Under review as a conference paper at ICLR 2023
cess of generating the observed data and the causal relationships between time series are ignored; such methods do not provide a mechanistic understanding of anomalies and it is hard for them to identify the root causes when anomaly occurs.
In real-world applications, root cause analysis (RCA) traditionally treated as a module separated from anomaly detection, identifying potential root causes given the detected anomalous metrics by analyzing the dependencies between the monitored metrics (Soldani & Brogi (021]. Because RCA requires know which metric is anomalous, univariate (instead of multivariate) time series anomaly detection algorithms are mostly applied to detect anomalies, and then RCA analyzes system/serviee graphs obtained via domain knowledge or observed data to determine root causes. Both univariate and multivariate algorithms have drawbacks and cannot be integrated with RCA seamlessly.
To overcome these issues, we take causal perspective (Pearl 2009) Spirtes al.) 1993) natu- rally view anomalies in multivariate time series as instances that do not follow the regular causal mechanism, and propose a novel causality-based framework for detecting anomalies and root causes simultancously. Specifically, our approach leverages the causal structure discovered from data so that the joint distribution of multivariate time series factorized into simpler modules where each module corresponds to a local causal mechanism, reflected by the corresponding conditional distribution. Those local mechanisms are modular or autonomous (Pearl 2009). and can then be handled separately, which is known the modularity property of causal systems. In light of this property, the problem is then naturally decomposed into a series of low-dimensional anomaly detec- tion problems. Each sub-problem is concerned with local mechanism. Because focus issues with separate local causal mechanisms, the root causes of an anomaly can be identified at the same time. The main contributions of this paper are summarized below.
We reformulate anomaly detection and root cause analysis of multivariate time series from a causality perspective, which helps understand where and how anomalies happen and fa- cilitates anomaly detection light of the understanding.
We propose a novel framework that decomposes the multivariate time series anomaly de- tection problem into series of separate low-dimensional anomaly detection problems by exploiting the causal structure discovered from data, which not only detects the anomalies more accurately but also offers natural way to find their root causes.
We perform empirical studies of evaluating our approach with both simulation and public datasets as well as case study of an internal real-world AIOps application, validating its efficacy and robustness to different causal discovery techniques and settings.
Our formulation offers alternative understanding of anomalies: an anomaly is a data point that does not follow the regular data-gen tata-generating process. The modularity property makes our approach simpler to train, suitable for real-world applications and easier for root cause analysis. Our method can detect those anomalies that are hard for the approaches based on modeling marginal/joint distri- butions only, illustrating the benefit of the causal view and treatment of anomalies.
2 THE CAUSAL APPROACH
Given a multivariate time series X with length T and d variables, i.c., X [x,,X2.
x2)
xxxd let (t) be the observation of the ith variable measured at time t. The task in this paper is to detect anomalies after time step T that differ from the regular points in X significantly and identify the corresponding root causes, i.e., test whether X, for j > T follows its regular distribution or not.
2.1 WHY THE CAUSAL VIEW MATTERS
Let us consider simple example shown in Figure [ i.e., the measurements of three components a, y. = with causal structure x + y + 2. An anomaly labeled by a black triangle happens at time step 40, where the causal mechanism between and y becomes abnormal. Typically it is hard to find such an anomaly based on the marginal distributions or the joint distribution. But from local causal mechanism p(y]z), such anomaly becomes obvious, e.g., p(y|æ) is much lower than its normal values. In this example, at time step 40 the probability densities p(z) = 0.786, p(y) = 1.563, p(2) 1.695, p(x, y, p(r))())<))(((l)) 0.046 while p(ylar) 0.011,
2

---

Under review as a conference paper at ICLR 2023
meaning that it is easier to find this anomaly by examining the local causal mechanism p(ylæ=). A real-world motivation example can be found in Figure
0.5
-0.6
ply)
-0.5
pct
-10
-1.
-12
Figure I: The causal mechanism between An anomaly occurs at time step 40 labeled by a black triangle. The causal mechanism helps find the anomaly easily as the p-value w.r.t conditioned on is 0.011 (test whether follows its normal conditional distribution p(y[z)). The root cause of this anomaly is because only p(yla) (z) is anomalous.
is 0.5x + <1, = tanh(y²
If the causal structure of the underlying process is given, we can examine whether each variable in the time series follows its regular causal mechanism. The causal mechanism be represented by the structural equation model, i.c., (t) = f/ (F)( e (t)), , Vi 1, d, where fr are arbi-
trary measurable functions, (t) are independent noises and PA(x, (t)) represents the causal parents of (t) including both lagged and contemporaneous ones (Pearl 2009). This causal structure can also be represented by causal graph G whose nodes correspond to the variables 2; (;(() different time lags. In this paper, we assume the graph Ç is a directed acyclic graph (DAG) and that the causal relationships are stationary unless an anomaly occurs. According to the Markov factorization, the joint distribution of xt) can be factored as [P(x(t)] = I p (t) (t),Pt(x,(t)) where pe denotes the conditional distribution.
The local causal mechanisms, corresponding to these conditional distribution terms, are known to be irrelevant to each other in a causal system (Pearl 2009). An anomaly can then be identified according to the local causal mechanism. Therefore, we define anomalies as follows.
Definition 1 A point x(t) time step is anomaly if there exists least variable I; such that x, (t) violates the local generating mechanism, i.e. given PA(z,(t)). xx(t) does not fol- low po (A)rt)))(( which is the conditional distribution corresponding the regular causal mechanism.
This definition states that anomaly happens in the system if the causal mechanism between variable and its causal parents are violated, e.g., the local causal effect dramatically varies (Fig T big change happens variable and this change propagates to its children. Based on Definition [ the anomaly detection problem can be divided into several low-dimensional subproblems, c.g., by checking whether each variable follows its regular conditional distribution. Thank to this modularity property, the root causes can be naturally identified when an anomaly event occurs. Here is our definition of root causes.
Definition 2 The root causes of an anomaly point x(t) are those variables x, such that given PA(x;(t)), (t) does not follow (t)=((t))PA(=z(()) e.g., an anomaly happens on the local causal mechanism related to those variables.
Definition 2 indicates that z; is one the root causes if the local causal mechanism of variable x; xt(() is violated. In Figure [ variable is the root cause by our definition because the causal mechanism between y and normal while the causal mechanism between x and y violated.
2.2 METHOD
We consider the unsupervised learning setting where X is given as the training data for learn- ing the graph structures and the conditional distributions. (We will discuss the effects of pos- sible anomalies on the leamned causal structure in Section 2.2.4) For learning causal graphs, we exploit suitable causal discovery methods, as discussed in Section P.2.1 For learning condi- tional distributions, maximize the log likelihoods given the observation data, i.e., maximizing
3

---

Under review as a conference paper at ICLR 2023
(XX) Σi= log P (t)()))) Vi 1...., dd Specifically, let CR be the set of variables with no causal parents in G. There are two cases to be considered:
Variable with parents (i E CR): The conditional distribution of x: (!) given its causal par- ents needs to be estimated, i.e., p9 (c:(C)(PA(x:())))) is modeled via conditional density estimation, which can learned in a supervised manner.
Variable with no parents (i E CR): We model (t) by applying any existing method for modeling time series with the historical data (t(t) (r,( ,t,(t - 1)} of Ti. meaning that our framework can leverage the state-of-the-ee time series models.
The training step produces the causal graph and the estimated conditional distributions correspond- ing to local causal mechanisms (Section 2.2.2) For anomaly detection of local causal mechanism, we detect data points that do not follow regular conditional distributions. There are multiple possible ways to compute the final anomaly score; |Hard & Rubin-Delanchy (2018) compared six methods for combining p-values from individual tests, and showed that taking the minimum sensitive to the smallest p-value, which is suitable for reporting anomalies that any of the metrics is abnormal. Hence the anomaly score is defined as one minus the minimum value of these estimated probabili- ties. Intuitively, the purpose of using the minimum function is that we expect the algorithm to report an anomaly if any of the metrics (root variables) or local causal mechanisms (conditional probabili- ties) becomes abnormal, i.e., data point is labeled as anomaly if its anomaly score is larger than a certain threshold. If an anomaly event is detected, the root cause scores are computed for each variable and then the variables with the top scores are selected as the root causes (Section 2.2.3). Algorithm I outlines our approach. The anomalies in training data may decrease the performance. We discuss this issue and provide a solution for handling training anomalies in Section 2.2.4
Algorithm 1 The causality- based approach for detecting anomalies and root causes
Input: training data X = (x, ) E Rxx, test data Y = [yr) E Txdd and threshold X;
Training procedure:
1: Infer the causal graph G via causal discovery techniques, e.g., FGES (Chickering 2003 2002
Meek 1995) and PC (Spirtes & Glymour 1991). If the G is a partial DAG, convert it into
DAG by the method (Dor & Tarsi] 1992); (Section 2.2.1
2: For variable train a model M, estimating conditional distribution 1 [x. (z. (t) with training data (x, (PA(),(t))) where (f) can be an empty set. (Section 2.2.2
Detection procedure:
1: for t = 1 to f do
2: Compute anomaly score: A(y(t)==14 = 1 (M
.d):
3: Set anomaly label 4 = 1 if (t)) > or O otherwise:
4: If anomaly label 4 is 1, computes root cause scores (t) via Eq for each variable i,
and set root causes R, be the variables with the top-k root cause scores. (Section) 2.2.3)
5: end for
2.2.1 CAUSAL DISCOVERY
Our approach needs to exploit the causal structure underlying the data. A traditional way to find causal relations is to use interventions or randomized experiments, which are generally too expen- sive and tome-consuming. Discovering causal information by analyzing purely observational data, known as causal discovery, is then an important problem (Spirtes & Glymour, 1991] Peters et al.) 2017 Spirtes& & Zhang/ (016)). Multiple algorithms have been developed for causal discovery from independent and identically distributed (i.i.d) or time series data, and their results are asymptotically guaranteed under corresponding assumptions. In this paper. we choose causal discovery algorithms such as PC (Spirtes & Glymour 1991). FGES (Chickering) 2003 2002 Meek 1995), depending on whether we are given temporal data (with time-delayed causal re relations) and whether the causal relations are linear nonlinear. For example, we apply FGES with SEM BIC score if the variables are linearly related and apply FGES with generalized score function (Huang et al. 2018 if they are non-linearly correlated. One concern is whether the missing or incorrect causal links in the inferred
4

---

Under review as a conference paper at ICLR 2023
causal graph have big impact on the performance of our approach. We performed empirical study of this impact with public datasets, which shows that interestingly, our approach is robust to the inferred causal graph. The complexity of PC and GES highly depends the density of the causal graph. Specifically, FGES is highly scalable when dealing with linear models (Ramsey et al.) 2016). In real-world applications, e-g-, the public datasets in the experiments, even though the vari- ables may not be exactly linearly correlated, FGES can still generate reasonable causal graphs that are good enough for our approach.
2.2.2 ANOMALY DETECTION
After the causal Markov factorization, it becomes easier to model the joint distribution compared to the previous approaches, e.g., the conditional distributions representing local causal mechanisms can be estimated using simpler ML models.
For modeling po (t) IPA (zv(())),, one can apply kernel conditional density estimation (Hastic et al. 2200)), conditional VAE (CVAE) (Sohn et al. 20155) or even prediction models such MLP or CNN (Binkowski et al. 2018). Let Tj be the causal time lag for a parent Ty and T be the maximum time lag in G; then define (x,
2t Tÿ) I PA). Time lag 7, 0 æ.j is a contemporaneous causal parent of 2,. For causal parent 2., more of its historical data can also be included, e.g., window with size k: (1, (1 k + 1),... I1 - TT) | PA). Therefore, the problem becomes estimating the conditional distribution from the empirical observa- tions (t), (t))) where (t) PA (t) In this paper, we apply CVAE to model such conditional distribution. The reason why choosing CVAE is that it can be trained fast with a simple architecture and achieve good performance as shown in our experiments. The empirical variational lower bound of CVAE is
{æ,(t (t-r").
L(r,0,,00) 1
log (xlc, 2x) -K----- (Lgg(() po(2|c)),
where (z(2|2, c). po(e)e,2)) are MLPs and (=(c)) is Gaussian distribution. Given (x,((),e;,t))
CVAE outputs (,(t) (t) reconstruction of (t), and then ((z((t)(c(tt) is measured by the distribution
of (t) (t)l-
If (A(x (t)) is empty, i.., E CR. one way to estimate distribution (t) is to handle x, (t) via univariate time series models, e.g., ARIMA (Hamilton) 1994), SARIMA (Hyndman & Athana- sopoulos 2018). The other way is to handle the variables in CR together by utilizing the models for multivariate time series anomaly detection, c.g., Isolation Forest (IF) (Liu et al. 2008), AE (Baldi) 2012). LSTM-VAE (Park et al. 2017). The training data for such models includes all the observa- tions of the variables in CR, i.e., {t)(t)
E CR C=) For example, the training data for forecasting based method is (xx,tt), {x,(t - k).... 1 1)bbis E Cj Y:m where (t,() is predicted by
window of its previous data points.
Our approach reduces to the previous univariate/multivaiii time series AD approaches if the causal graph is empty, i.e., no causal relationships are considered. When the causal relationships are avail- able obtained by domain knowledge or data-driven causal discovery techniques, our approach can easily utilize such information and reduces the efforts in joint distribution estimation.
2.2.3 ROOT CAUSE ANALYSIS
Root cause analysis (RCA) aims to identify root causes when an anomaly event happens. RCA in real-world applications such as AIOps can be very challenging. One practical issue for identifying root causes that an anomaly occurs a variable often makes its causal children variables abnormal due to anomaly propagation. Specifically, based on Definition 2] we propose the following practical algorithm. For variable r;, define its initial root cause score at time t by (tzx = 1 M,(xx(t)) Suppose that N (t)( is the set of the causal children of 2t(t), the final root cause score is define in PageRank (Page et al. 1999 Wu al. 2020)) way:
RS( (1) = ((x:(1) +
Σ
RS(x,(1)), Vi = 1,, ,d.
(1)
[xx:)]
(a()))
We assume the reconstruction error is additive, e.g., == f(c) + that P(z(c) Pa(x f(c)). Hence we the distribution of the reconstruction error for detecting anomalies.
5

---

Under review as a conference paper at ICLR 2023
where is a weight parameter satisfying 0 I a < 1. When M(x;) is empty, set (z) (t), Here the final root cause score of a variable is the weighted combination of its initial root cause score and the final root cause scores of its children to handle the anomaly propagation issue. The root causes at time / are identified by picking the variables with top IRS scores.
2.2.4 NEGATIVE EFFECT OF TRAINING ANOMALIES
The existence of anomalies in the training data may decrease the detection performance. Our em- pirical results show that this issue does not affect the anomaly detection performance much, which is expected to be the case when there are relatively few anomalies in the data. Typically, there are two possible cases where anomalies in training data may have obvious negative impacts on perfor- mance. One case is that the value of metric at certain timestamps becomes extremely large, which can affect the conditional probability estimation. In this case, one can simply remove those values based statistical rules, e.g., removing them if the absolute value is larger than some threshold in the preprocessing step. The other case is that the proportion of anomalies is relatively large. In this case, we can consider an iterative solution that iteratively updates the causal graph and anomaly detection model, i.e., 1) estimate causal graph G and train models M, with the training data, and 2) remove the anomalies detected by M₁ in the training data and then go to Step (1). We repeat the above two steps until the estimated causal model (including the estimated causal structure and quan- titative model, e.g., causal coefficients the linear case) converges. We conducted an experiment with a simulation dataset to empirically study this iterative solution (SectionAA A.7)
EXPERIMENTS
This section evaluates the performance of our proposed approach and compares it to several other ap- proaches. The experiments include: 1) evaluating our approach with simulation and public datasets, 2) analyzing how different causal graphs affect the performance, and 3) a case study demonstrating the application of our approach for real-world anomaly detection in AIOps.
The anomaly detection performance is assessed by the precision, recall and Fl-score metrics in a point-adjust manner, i.c., all the anomalies of anomalous segment are considered correctly detected if at least one anomaly of this segment is correctly detected while the anomalies outside the ground truth anomaly segment are treated normal. By default, we apply FGES (Chickering 2003) to discover the causal graph. For & CR. we choose CVAE (Sohn et al.) 2015). For E CR. we tested the univariate model and other methods such as IF (Liu et al. 2008). AE (B12) LSTM- VAE (Park et al., 2017) in our experiments. We compare our approach with several unsupervised approaches, e.g., AE (Baldi 2012), DAGMM (Zong al. 2018). OmniAnomaly (Su et al. 2019). USAD (Audibert et al. 2020). GANF (Dai & Chen 2022
3.1 SIMULATION DATASETS
Section A.3 discusses how generate simulation datasets. We consider linear/nonlinear causal rela- tionships and three types of anomalies. The first type is a "measurement" anomaly where the causal mechanism is normal but the observation is abnormal due to measurement errors, i.e., randomly pick a node v,, a time step t and a scale s, and then set x; (t) = [x;(t) median [z;)] * s + median(x;). The second type is "intervention" anomaly, i.e., after generating anomalies for some nodes, those anomaly values propagate to the children nodes according to the causal relationships. The third type an "effect" anomaly where anomalies only happen on the nodes with causal children.
Performance comparison. In the experiments, we consider six settings derived from the combi- nations of "linear/nonlinear" and mmessuremeniinneeeettonefeeeeeee
The simulated time series has 15 variables with length 20000, where the first half is the training data and the rest is the test data. The percentage of anomalies is 10%. Table shows the performance of different unsupervised multivariate time series anomaly detection methods with the generated simulated dataset. Clearly, our method outperforms all the other methods. It achieves significantly better Fl scores when the relationships are nonlinear or the anomaly type is "intervention" e.g., ours obtains F1 score 0.759 for "nonlinear, intervention". while the best Fl score achieved by the others is 0.589. In "linear,

---

Under review as a conference paper at ICLR 2023
Table 1: Performance comparison (Fl-scores) the simulation datasets.
Lies/
Line/r
Lin//Effect
/eaau.
Nonlin./Inter.
Monlin//Effee
IF
0.374
0.403
0.220
0.336
0.422
0.367
AE
0,386
0.359
0.240
0.392
0.390
0.363
VAE
0,343
0.328
0.208
0.396
0.377
0.306
LST
0.457
0.454
0.485
0.581
0.545
0.393
DAGMM
0.746
0,542
0.721
0,456
0.589
0.359
USAD
0.252
0.260
0.220
0.346
0.302
0.279
GANF
0.292
0.340
0.213
0.355
0.316
0.286
Ours
0.791
0.757
0.740
0.757
0.759
0.637
measurement/effead" DAGMM has similar performance with ours because the data can be mod- eled well by applying dimension reduction followed by Gaussian mixture model. But when the relationships become nonlinear, it becomes harder for DAGMM model the data. This experiment shows that the causal mechanism plays important role in anomaly detection. Modeling joint distribution without considering causality can lead a significant performance drop.
We use the same simulation datasets as anomaly detection to evaluate the RCA performance mea- sured by the top-k hit ratio, i.e., the predicted top-k root causes are correct as long as one of them the groundtruth root cause. Table 2 shows the RCA performance of our approach and the baseline. The baseline ignores the causal relationships while samples root causes based on the probabilities proportional the anomaly scores. Our approach achieves HR @3 0.95 and HR@3 > 0.75
Table 2: RCA performance comparison (top-k hit-ratio) on the simulation datasets.
Top 1
Top 2
Top 3
Top 4 0.148
Linear/Measu. (Baseline)
0.406 0.182
0.573 0.182
0.617 0.160
0.631
Linear/Measu. (Ours)
0.654 + 0.117
0.916 = 0.075
0.965 + 0.040
0.993 + 0.010
Lincar/Inter. (Baseline)
0.463 + 0.182
0.551 = 0.6
0.596 + 0.171
0.614 + 0.
Linear/Inter. (Ours)
0.637 1 0.178
0.815 0.126
0.960 1 0.032
0.988 0.020
Nonlinear/Meass (Baseline)
0.253 1 0.042
0.449
0.040
0.571 1: 0.074
0.644 1: 0.049
Nonlincar/Measu. (Ours)
0.577 + 0.081
0.656
0.056
0.764 + 0.091
0.847
0.088
Nonlincar/Inter. (Baseline)
0.262 + 0.048
0.439 = 0. 0.1
0.589
0.114
0.635
0.102
Nonlincar/Inter. (Ours)
0.541 = 0.152
0.623 = 0.115
0.776 0.077
0.867 = 0.118
for the "lincar" and "nonlinear" settings, respectively, which significantly better than the baseline.
3.2 PUBLIC DATASETS
Four public datasets were used in experiments: 1) Secure Water Treatment (SWaT) (Mathur & Tippenhauer] 2016): consists of 11 days of continuous operation, i.c., 7 days collected under normal operations and 4 days collected with attacks, 2) Water Distribution (WADI) (Mathur & Tippenhauer] 2016): It consists 16 days of continuous operation, which 14 days were collected under normal operation and 2 days with attacks. 3) Soil Moisture Active Passive (SMAP) satellite and Mars Science Laboratory (MSL) rover Datasets (Hundman et al. 2018). which are two public datasets expert-labeled by NASA.
Performance comparison. Table 3 shows the results on four representative datasets. Overall, IF, AE, VAE and DAGMM have relatively lower performance because they neither exploit the tempo- ral information nor leverage the causal relationships between those variables. LSTM-VAE, Omni- Anomaly and USAD perform better than these four methods since they utilize the temporal infor- mation via modeling the current observations with the historical data, while the DAG-based method GANF does not perform well except for SWaT. Our approach exploits the causal relationships be- sides the temporal information, achieving significantly better results than the other methods in all the datasets, e.g., ours has the best Fl score 0.918 for SWaT and 0.818 for WADI, while the best Fl scores for SWaT and WADI by other methods are 0.846 and 0. 0.767, respectively. For each public datasets, Table 4 reports the best metrics that can be achieved by choosing the best thresholds in the test datasets. Clearly, if we are allowed to choose better thresholds, the metrics achieved by
7

---

Under review as a conference paper at ICLR 2023
Table 3: Performance comparison of our approach and other methods on the public datasets.
SMAP
MSL
SWaT
WADI
Methods
Prec.
Recall
F1
Prec.
Recall
F1
Prec.
Recall
Ft
Prec.
Recall
F1
IF
0,815
0.591
0.685
0.854
0.922
0.887
0.998
0.669
0.801
0.541
0.794
0.644
AE
0.806
0.585
0.678
0.858
0.892
0.875
0,999
0.656
0.792
0.595
0.762
0.668
VAE
0.808
0.588
0.681
0.771
0.656
0.709
0.999
0.656
0.792
0.616
0.855
0.716
LSTM VAE
0.818
0,591
0.686
0.859
0.911
0.884
0.997
0.689
0.815
0.658
0.920
0.767
DAGMM
0.800
0.877
0.837
0.900
0.864
0.882
0.829
0.767
0.797
0.639
0.501
0.412
OmniAnom
0.758
0.975
0.853
0.901
0.889
0.895
0.722
0.983
0.833
0.265
0.980
0.417
USAD
0.769
0,983
0.863
0.861
0.964
0,910
0.987
0,740
0.846
0.645
0.322
0.430
GANF
0.692
0.549
0.612
0.285
0.773
0.416
0.964
0.706
0.815
0.576
0.596
0.586
Ours
0.874
0,982
0.925
0.867
0.961
0.912
0.945
0.892
0.918
0.749
0.901
0.818
(std)
10.0011
1:0.006
1.0.003
1.0.003
1.0.011
100007
1.0.009
100016
1.0.008
1.00211
1:0.029
1.0023
approach can be much higher, e.g., Fl-score 0.946 for SMAP and 0.913 for MSL. We also report
the running time of our approach in Section A.8
Table 4: The best performance of our approach with the public datasets.
Dataset
SMAP
MSL
SWaT
WADI
Precision
0.951 = 0.011
0.903 = 0.029
0.929 + 0.018
0.883 = 0.021
Recall*
0.930 + 0.011
0.951 + 0.033
0.965 + 0.009
0.947 + 0.020
F|
0.940 0.004
0.926 + 0.017
0.946 0.007
0.913 + 0.008
Ablation study M, for i E Cr. This experiment evaluates the effect of the causal information on anomaly detection. For an anomaly detection method A such as IF and AF, we compare A with our approach "ours + -A" that uses CVAE for i of CR (estimates 1 (z and AA for i E CR (estimates Ik (t].. We report the metrics as mentioned above and the best metrics achieved by choosing the best thresholds in the test datasets. Table 5 shows the performance of
Table 5: Performance of our method using different models for A in SWaT and WADI. "*" means the best metrics. A 0 means anomalies are detected by & CR only without using E CR.
SWaT
WADI
Prec.
Rec.
F1
Prec.*
Rec.* *
F1
Prec.
Rec.
F1
Prec.*
Rec.*
9
F1
0.952
0.874
0.911
0.950
0.929
0.940
0.749
0.920
0.826
0.873
0.979
0.923
IF
0.947
0.893
0.919
0.946
0.945
0.945
0.738
0.920
0.819
0.948
0.920
0.934
AE
0.958
0.900
0.928
0.963
0.920
0.941
0.789
0.920
0.850
0.931
0.979
0.955
LSTM-VAE
0.954
0.874
0.912
0.951
0.936
0.944
0.748
0.920
0.825
0.949
0.920
0.934
our approach with different A, where A = 0 means that the anomalies are detected by of CR. only without using E CR- By comparing this table with Table we can observe that "ours A" performs much better than using A only, e.g., "ours + AE" achieves F1 score 0.850 for WADI, while AE obtains 0.668 for WADI. If A is not used in anomaly detection, we get a performance drop in terms of Fl score. For example, the best Fl score drops from 0.934 to 0.923 for WADI.
Ablation study on causal discovery and causal mechanism estimation. We also studied the effects of different parameters for discovering causal graphs on the performance of our approach. The experiments (in Section A.9) shows that our approach is robust to the changes of the inferred causal graph. In practice, the causal graph is not required to be accurate, namely, we just need to ensure that it doesn't 't contain too many missing links or false positive links. Besides FGES, other methods such as the PC algorithm (Spirtes & Glymour, 1991) can also be applied to infer the causal graphs. The causal graphs inferred by PC are probably different from those computed by FGES. Our experiments show that our anomaly detection approach is stable even though the causal graphs are different. Table o compares the performance of our approach with FGES, GES and PC. For SWaT, using FGES, GES and PC have similar performance. For WADI, using PC performs worse than using GES and FGES, but the Fl-score 0.768 is still better than the other approaches. The performance drop is because the causal graph discovered by FGES is more accurate than PC in
8

---

Under review as a conference paper at ICLR 2023
Table 6: Performance comparison (Fl-sc with the public datasets, e.g., GES PC vs FGES for causal discovery, and CVAE vs MLP vs KMN for causal mechanism estimation.
Methods
SWaT
WADI
Methods
SWaT
WADI
Ours (GES)
0.895 + 0.013
0.802 + 0.015
Ours (CVAE)
0.918 0.008
0.818
0.023
Ours (PC)
0.912 + 0.007
0.768 = 0.020
Ours (MLP)
0.909 0.010
0.739 0.041
Ours (FGES)
0.918 + 0.008
0.818 = 0.023
Ours (KMN)
0.900 + 0.007
0.634 + 0.029
WADI, As shown in Table 6 we also tested different methods for estimating causal mechanisms (conditional distributions), c.g., CVAE, MLP and KMN (Ambrogioni et al. 2017). CVAE works better than the others in SWaT and WADI choose CVAE by default.
3.3 CASE STUDY: REAL-WORLD APPLICATION IN AIOPS
Our last experiment is to apply our method for a real-world anomaly detection task in AlOps, where the goal is to monitor the operational key performance indicator (KPI) metries of database services for alerting anomalies and identifying root causes in order to automate remediation strategies and improve database availability in cloud-based services. In this application, we monitor total of 61 time series variables measuring the KPI metrics of database services, e.g., read/write IO requests, CPU usage, DB time. The data in this case study consists of the one-month measurements. Accord- ing to the feedback from domain experts, most of the inferred causal relationships shown in Figure 2 are consistent with the known domain knowledge. For example, the discovered links Redo (redo size) -> Lfpw (log file parallel write) -> Lfs (log file sync) -> COMT (commit) are exactly the same as the domain knowledge.
Lipw
CNGT
PRTIBY
PRTIO
PWTIBY
PITTIO
Redo
UsrC
DB
DBCPU
ROCPU
JOYNT
CPU
Us
CLS
OCP
ACT
ToIPGA
AvySL
DTHR
APPL
CONG
100
TwhCkk
USIO
5010
CLS
UTIL
Figure 2: Example on real-world AIOps case, showing 8 out of 61 time variables (left) and part of the causal graph (right). The deeper colors of nodes in the graph indicate higher root cause scores.
The incidences that happened are relatively rare, e.g., major incidences one month, and our anomaly detection approach correctly detect these incidences. Therefore, we focus on the root cause analysis in this case study. Figure 2 shows an example of one major incidence, showing sev- eral abnormal metrics such as DBt (DB time), Lfs (log file syne), APPL (application). TotPGA (total PGA allocated) and a part of the causal graph. The root cause scores computed by our method are highlighted. We observe that the top root causes metrics are APPL, DBt and TotPGA, all of which correspond to application or database related issues for the incident as validated by domain experts. More results can be found in Appendix.
4 CONCLUSIONS
Most previous approaches for multivariate time series anomaly detection model the joint distribution directly without considering the underlying causal process the observed time series data. This paper presented a new definition and formulation of anomalies in multivariate time series from causal perspective, and proposed a novel approach that exploits the causal structures discovered from data to help detect anomalies more accurately and identify the root causes robustly according to the local causal mechanism. Our experiments on both simulation and real datasets demonstrated the efficacy, robustness and practical feasibility of the proposed approach in real-world applications.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Luca Ambrogioni, Umut Güeclüi Marcel A. J. van Gerven, and Eric Maris. The kernel mixture network: A nonparametric method for conditional density estimation of continuous random vari- ables, 2017. URL URLtttts:://// http:/::///aii...o// org abs///b//////// aww.a70...a.... 07111
Fabrizio Angiulli and Clara Pizzuti. Fast outlier detection in high dimensional spaces. In Principles of Data Mining and Knowledge Discovery, pp. 15-27, 2002.
Julien Audibert, Pietro Michiardi, Frédéric Guyard, Sébastien Marti, and Maria A. Zuluaga. Usad: Unsupervised anomaly detection multivariate time series. In The 26th ACM SIGKDD Intl Conference on Knowledge Discovery & Data Mining, KDD 20, pp. 3395-3404, 2020.
Pierre Baldi. Autoencoders, unsupervised learning, and deep architectures. ICML Workshop on Unsupervised and Transfer Learning, volume 27 of PMLR, pp. 37-49. PMLR, 2012.
Mikolaj Binkowski, Gautier Marti, and Philiipee Donnat. Autoregressive convolutional neural net- works for asynchronous time series. In Proceedings of the 35th International Conference on Machine Learning. volume 80 of PMLR, pp. 580-589. PMLR, 2018.
Kailash Budhathoki, Lenon Minorics, Patrick Bloebaum, and Dominik Janzing. Causal structure- based root cause analysis of outliers. In Kamalika Chaudhuri, Stefanie Jegelka, Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 2357-2369. PMLR, 17-23 Jul 2022. URL budhathoki 22a l
mlr press/v162/
Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. 41(3), 2009.
Wanpracha Art Chaovalitwongse, Ya-Ju Fan, and Rajesh C. Sachdeo. On the time series k-nearest neighbor classification of abnormal brain activity. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 37(6): 1005-1066, 2007.
Pengfei Chen, Yong Qi, and Di Hou. Causeinfer: Automated end-to-end performance diagnosis with hierarchical causality graph in cloud environment. JEEE Transactions on Services Computing, 12 (2):214-230, 230, 2019. doi: 10. 19111999...200222777799..
David Maxwell Chickering. Learning equivalence classes of Bayesian-network structures. J. Mach. Learn. Res., 2(3):445-498, 2002. ISSN 1532-4435; 1533-7928/e.
David Maxwell Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3(3):507-554, 2003. ISSN 1532-4435; 1533-7928/e.
Enyan Dai and Jie Chen. Graph-augmented normalizing flows for anomaly detection of multiple time series. In International Conference on Learning Representations, 2022. URL https:
//openzeview. htt.://wweee///ooorraaadsss-....
Yingnong Dang, Qingwei Lin, and Peng Huang. Aiops: real-world challenges and research innova-
tions. In 2019 IEEE/ACM 41st International Conference on Software Engineering: Companion Proceedings (ICSE-Companioe pp. 4-5, IEEE, 2019.
Dorit Dor and Michael Tarsi. A simple algorithm construct a consistent extension of a partially oriented graph. Technical report, 1992.
James Douglas Hamilton. Time Series Analysis. Princeton University Press, 1994.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference and prediction. Springer, 2009.
N A Heard and P 105(1):)39 246,229992442222 Jan 2018. ISSN 1464-3510. doi: 10.1093/bimme/aax007. URL htttp://// doi wtw.org/110. /0/gg/10..o 10.00.19993660 omet /aax076
Choosing between methods of combining p-values. Biometrika,
10

---

Under review as a conference paper at ICLR 2023
Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM SIGKDD International Confer- on Knowledge Discovery & Data Mining, KDD '18. pp. 1551-1560, 2018.
Kyle Hundman, Valentino Constantinou, Christopher Laporte, Ian Colwell, and Tom Soderstrom. Detecting spacecraft anomalies using Istms and nonparametric dynamic thresholding. In 24th ACM SIGKDD Inil Conf. on Knowledge Discovery & Data Mining, pp. 387-395, 2018.
Robin John Hyndman and George Athanasopoulos. Forecasting: Principles and Practice. OTexts, 2nd edition, 2018
Myunghwan Kim, Roshan Sumbaly, and Sam Shah. Root cause detection in service-oriented ar- chitecture. In Proceedings of the ACM SIGMETRIISS/nnermatiion Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 13, pp. 93-104, New York, NY, USA, 2013. 19003. doi: 00.11455226555222466555.5 URL wttpt:tp:///mmm pnttps:://oi...om http::///oooogg.../// 11450..4554222559999 2465753
Association for Computing Machinery. ISBN
Nikolay Laptev, Saeed Amizadeh, and Ian Flint. Generic and scalable framework for automated
time-series anomaly detection. KDD '15, pp. 1939-1947, 2015.
JinJin Lin, Pengfei Chen, and Zibin Zheng. Microscope: Pinpoint performance issues with causal graphs in micro-service environments. In ICSOC, 2018.
Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In 2008 Eighth IEEE Interna- tional Conference on Data Mining, pp.
2008
Meng Ma, Weilan Lin, Disheng Pan, and Ping Wang. Ms-rank: Multi-metric and self-adaptive root cause diagnosis for microservice applications. In 2019 IEEE International Conference on Web Services (ICWS), pp. 60-67, 2019. doi: 10.1 N0.1109/CCSS.201 N.NSS.009.0002..
Meng Ma, Jingmin Xu, Yuan Wang, Pengfei Chen. Zonghua Zhang, and Ping Wang. AutoMAP: Diagnose Your Microservice-asse Web Applications Automatically, pp. 246-258. Association for Computing Machinery, New York, NY, USA, 2020. ISBN 9781 9781450370233.. URL https:
//doi. 1ttp://....14/3322..3333333
Larry M. Manevitz and Malik Yousef. One-class svms for document classification. J. Mach. Learn. Res., 2:139-154, March 2002.
Leonardo Mariani, Cristina Monni, Mauro Pezzé, Oliviero Riganelli, and Rui Xin. Localizing faults in cloud systems. In 2018 IEEE / Ith International Conference on Software Testing, Verification and Validation (ICST), pp. 262-273, 2018.
doi: 10. 1091CST.200 8,00034
Aditya P. Mathur and Nils Ole Tippenhauer. Swat: water treatment testbed for research and training on ics security. In 2016 International Workshop on Cyher-physicul Systems for Smart Water Networks (CySWater), pp. 31-36, 2016.
Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI'95, pp- 403-410. Morgan Kaufmann Publishers Inc., 1995.
Yuan Meng, Shenglin Zhang, Yongqian Sun, Ruru Zhang, Zhilong Hu, Yiyin Zhang, Chenyang Jia, Zhaogang Wang, and Dan Pei. Localizing failure root causes in a microservice through causality inference. In 2020 JEEE/ACM 28th International Symposium on Quality of Service (IWQoS), pp-
1-10, 2020.
doi: 10.1 1LL11000094449952220000099
Hiep Nguyen, Yongmin Tan, and Xiaohui Gu. Pal: Propagation-aware anomaly localization for cloud hosted distributed applications. SLAML '11, New York, NY. USA, 2011. Association for Computing Machinery. ISBN 9781450309788.
doi: 10.1145/203863.22386444 URL https:
//doi. otg000. 145 /044//03322 033.03333333333 222.2233333.226633333 2038634
Hiep Nguyen, Zhiming Shen, Yongmin Tan, and Xiaohui Gu. Fehain: Toward black-box online fault localization for cloud systems. In 2013 IEEE 33rd International Conference on Distributed Computing Systems, pp. 21-30, 2013. doi: 00.1009/CCDCSS.2013322

---

Under review as a conference paper at ICLR 2023
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999. URL Previous number SIDL-WP- 1999-0120.
httt://ilpubs. stanford. : 80900 422/
Dachyung Park, Yuuna Hoshi, and Charles Kemp. A multimodal anomaly detector for robot-assisted feeding using Istm-based variational autoencoder. IEEE Robotics and Automation Letters, PP, 11 2017.
Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, USA, 2nd edition, 2009.
J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference Foundations and Learning Algorithms. Adaptive Computation and Machine Learning Series. The MIT Press, Cambridge, MA, USA, 2017.
Huida Qiu, Yan Liu, Niranjan A. Subrahmanya, and Weichang Li. Granger causality for time-series anomaly detection. In IEEE Intl Conf. on Data Mining, pp. 1074-1079, 2012.
Juan Qiu, Qingfeng Du, Kanglin Yin, Shuang-Li Zhang, and Chongshu Qian. causality mining and knowledge graph based method of root cause diagnosis for performance anomaly in cloud applications. Applied Sciences, 10(6), 2020.
Joseph Ramsey, Madelyn Glymour, Ruben Sanchez-Ronee and Clark Glymour. A million vari- ables and more: the fast greedy equivalence search algorithm for learning high nigh-dimensional graphical causal models, with application to functional magnetic resonance images. Inter- national Journal of Data Science and Analytics, 3:121-129, 2016.
Hansheng Ren, Bixiong Xu, Yujing Wang. Chao Yi, Congrui Huang, Xiaoyu Kou, Tony Xing, Mao Yang, Jie Tong, and Qi Zhang. Time-serics anomaly detection service microsoft. In 25th ACM SIGKDD Intl Conf. on Knowledge Discovery & Data Mining, pp. 3009-3017, 2019.
Areeg Samir and Claus Pahl. Dla: Detecting and localizing anomalies in containerized microservice architectures using markov models. In 20/9 7th International Conference Future Internet of Things and Cloud (FiCloud), pp. 205-213. 2019. doi: 10.1 10.11099Flloud.2019.0000
Huasong Shan, Yuan Chen, Haifeng Liu, Yunpeng Zhang, Xiao Xiao, Xiaofeng Hc, Min Li, and Wei Ding. e-diagnosis: Unsupervised and real-time diagnosis of small- window long-tail la- tency in large-scale mieroservice platforms. In The World Wide Web Conference, WWW '19,
pp. 3215-3222, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748. doi: 71114//3308558.3316633 URL https::/cci.ors 1145/ 13385558.313355
Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28, 2015.
Jacopo Soldani and Antonio Brogi. Anomaly detection and failure root cause analysis in (micrr))ervicee-bssed cloud applications: A survey, 2021. URL httpss://axxiv.org/////////
21C5.12378
Spirtes and K. Zhang. Causal discovery and inference: concepts and recent methodological advances. Applied Informatics, 3, 2016. htts:://do..rr//10 http:///.......111//445511-11010 1186/40535-016--00188
Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. Spring- Veeinn Lectures in Statistics, 1993.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 911::22-7,, 1991.
Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei. Robust anomaly detection for multivariate time series through stochastic recurrent neural network. In 25th ACM SIGKDD Inil Conference on Knowledge Discovery & Data Mining, KDD' 19, pp. 2828-2833 2019.
12

---

Under review as a conference paper at ICLR 2023
Sean J. Taylor and Benjamin Letham. Forecasting scale. The American Statistician, 72(1):37-45, 2018.
Jörg Thalheim, Antonio Rodrigues, Istemi Ekin Akkus, Pramod Bhatotia, Ruichuan Chen, Bimal Viswanath, Lei Jiao, and Christof Fetzer. Sieve: Actionable insights from monitored metrics in distributed systems. In Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference, Middleware '17, pp. 14-27, New York, NY, USA, 2017. Association for Computing Machin- cry. ISBN 9781450347204. doi: 10.1145/1135974:3139777 URL https: /ttps:://do... org/10. 1145/3135974.31 3135977
Ping Wang, Jingmin Xu, Meng Ma, Weilan Lin, Disheng Pan, Yuan Wang, and Pengfei Chen. Cloudranger: Root cause identification for cloud native systems. 2018 18th IEEE/ACM Inter- national Symposium on Cluster, Cloud and Grid Computing (CCGRID), pp. 492-502, 2018. doi: 10.1109/CCGRID.201 00076.
Li Wu, Johan Tordsson, Erik Elmroth, and Odej Kao. Microrca: Root cause localization of per- formance issues in microservices. NOMS 2020 2020 IEEE/IFIP Network Operations and Management Symposium, pp. 1-9, 2020.
doi: 10. 1000000077777882200000000
Chuxu Zhang, Dongjin Song. Yuncong Chen, Xinyang Feng, Cristian Lumezanu, Wei Cheng, Jingchao Ni, Bo Zong. Haifeng Chen, and Nitesh V. Chawla. A deep neural network for un- supervised anomaly detection and diagnosis in multivariate time series data. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 20/9, pp. 1409-1416, 2019.
Hang Zhao, Yujing Wang, Juanyong Duan, Congrui Huang, Defu Cao, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Multivariate time-series anomaly detection via graph attention network. CoRR, 0tbs/2009.0204444 2020.
Bo Zong, Qi Song. Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Dacki Cho. and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In Inter- national Conference on Learning Representations, 2018.
Álvaro Brandón, Mare Solé, Alberto Hućlamo, David Solans, María S. Pérez, and Victor Muntés- Mulero. Graph-based root cause analysis for service-oriented and microservice architectures. Journal of Systems and Software, 159:1 10432, 2020. ISSN 0164-1212. doi: https://doi.
org/10. 1stii.1001/iisss221...... 10432. URL https: www.w/iiicediieeeeccccc.c.cc.cce com/ com/science/
articieepjl1/00111122222222222
A APPENDIX
A.1 RELATED WORK
Anomaly detection methods for univariate time series can be applied to each dimension of multi- variate time series. Popular univariate anomaly detection techniques include statistical distance- based methods, e.g., KNN (Chaovalitwongse et al., 2007) Angiulli & Pizzuti] 2002). One-Class SVM (Manevitz & Yousef 2002), and probabilistic methods (Chandola al. 2009). These meth- ods are computationally efficient and suitable for high dimensional data. But their performance degrades faced with long-term anomalies since the temporal patterns within time series ig- nored. To address this issue, temporal prediction methods, e.g., ARIMA, SARIMA (Hamilton, 1994.. Prophet (Taylor & Letham 2018). SR-CNN (Ren al.] 2019) and DONUT (Laptev al., However, these meth- ods treat each dimension individually and ignore the correlations between different time series. As shown in Figure I they cannot identify the anomaly corresponding to the abnormal causal mecha- nism.
2015 have been proposed to model temporal deppendenciev/aurccorelaaai
Recent years have seen the increasing popularity of unsupervised methods using deep learning tech- niques, which can infer the correlations between time series. For example, DAGMM (Zong et al. 2018) combines autoencoder with Gaussian mixture model to model the joint distribution. MSCRED (Zhang et all, 2019) utilizes the system signature matrix to model the correlations and temporal patterns. LSTM-VAE (Park al. 2017) combines LSTM with VAE and models temporal
13

---

Under review as a conference paper at ICLR 2023
dependencies through LSTM. OmniAnomaly (Su et al. 2019) learns robust time series representa- tions with a stochastic variable connection and a planar normalizing flow. USAD (Audibert et al. 2020) uses adversely trained autoencoders inspired by GANs, providing fast training. However, these methods model the joint distribution directly without considering the process behind multi- variate time series, and an anomaly that happens to a local mechanism in the process might not change the joint distribution dramatically. Besides, it is difficult for them to leverage the domain knowledge of the monitored system, e.g., the known causal dependencies between time series, and to provide explanations that are crucial for root cause analysis and remediation when an anomaly occurs. Finally, our work also differs substantially from existing studies (Qiu et al., [012 2020) which though explore causality in anomaly detection in different ways, but do not use the causal mechanism to model anomalies in time series.
Root cause analysis (RCA) methods leverage the KPI metrics monitored on those services to de- termine the root causes when an anomaly event detected. The key idea behind RCA with KPI metrics is to analyze the relationships dependencies between these metrics and then utilize these relationships to identify root causes when an anomaly occurs. Typically, there are two types of ap- proaches: 1) identifying the anomalous metrics in parallel with the observed anomaly via metric data analysis, and 2) discovering topology/causal graphs that represent the causal relationships between the services.
Nguyen et al. 2011 2013) propose two similar RCA methods by analyzing low-level system met- rics, e.g., CPU, memory and network statistics. Both methods first detect abnormal behaviors for each component via a change point detection algorithm when a performance anomaly is detected, and then determine the root causes based on the propagation patterns obtained by sorting all critical change points in a chronological order. Shhan et al. (2019) developed a low-cost RCA method called e-Diagnosis to detect root causes of smnllwwindow long-tail latency for web services. c-Diagnosis assumes that the root cause metrics of an abnormal service have significantly changes between the abnormal and normal periods. But these methods don't consider the causal relationships between KPI metrics or the dependencies between services in an application.
The second type of RCA approaches leverages such dependencies, which usually involves two steps, i.e., constructing topology/causal graphs given the KPI metrics and domain knowledge, and extract- ing anomalous subgraphs or paths given the observed anomalies. Such graphs can either be recon- structed from the topology (domain knowledge) of certain application (Thalheim et al., 2017 Wu
et al. 2020 Álvaro Brandón et al. 2020 Samir & Pahl, 2019) or automatically estimated from the metries via causal discovery techniques Waan et al. |
Mariani et al. 2018 Chen et al. 2019 Meng et al. 2020 Lin et al. 2018 Ma et al. 2019 2020). To identify the root causes of the observed anomalies, random walk (e.g., Kim et al. (2013); Meng et al. (200); Wang et al. (2018)), page-rank (e.g./Wu et al. (2020) other analysis methods can be applied over the discovered topology/causal graphs. Recently, Budhathoki et al. (2022) proposed a method based counterfactual analysis which identifies the root cause of detected anomaly/outiie by computing the contribution of each noise term to the anomaly score. But these methods only accept univariate time series anomaly detectors, i..., detecting anomalies for each metric separately.
A.2 EXPERIMENTAL SETUP AND PARAMETERS SETTINGS
For the implementation of our approach, we employ the CVAE to model conditional distributions 1e (((((())FFF((;((()) We choose the same parameters for all the experiments on both simulated and public real datasets. The encoder and decoder in CVAE are both MLPs with hidden sizes [10, 20, 10). The latent size is 5 and the prior distribution po(2|c) is assumed to be the standard normal distribution (doesn't 't depend on c). For training CVAE, the optimizer is ADAM with learning rate 0.001, batch size 1024 and epoch num 80.
For modeling I (t), there are several options to choose in practical applications. For the simulated datasets and our internal AIOps dataset, we choose a univariate anomaly detection method based on CNN forecasting model. The CNN forecasting model consists of 4 resid- ual blocks with 1D convolutional layers, i.e., the "(input channels, output channels)" pairs are (1,8), (8, 16), (16, 32), (32, 64), followed by the concatenate of ID adaptive average pooling and ID adaptive max pooling. The output layer is a linear layer. For each residual block, it has two convolutional layers "(input channels, output channels) -> (output channels, output channels)". We
14

---

Under review as a conference paper at ICLR 2023
choose ADAM the optimizer with learning rate 0.001 (with decay), batch size 1024 and epoch num 50. The window size of the historical data for prediction is 20. For the public datasets, besides this CNN forecasting model, we can also choose isolation forest (IF) and autoencoder (AE). For IF, the max number of samples is 10000. For AE, the hidden sizes of the encoder are [25, 10, 5]. the latent size is 5, and the hidden sizes of the decoder are [5, 25).
For the simulated datasets, we apply FGES and set "max degree 5 and "penalty discount = 20" For the public datasets SWaT and WADI, we apply FGES and set "max degree 10" and "penalty discount = 100". For SMAP and MSL, we apply the PC algorithm with the default parameters. The library for causal discovery we used in this project is Tetrad I Smaller "max degree" or larger "penalty discount" in FGES leads to more sparse graphs with less edges. Table the number of the edges the causal graphs discovered with different parameters.
The reason why we choose these parameters such as CVAE hidden sizes = [10, 20, 10] is as follows. For all the simulation datasets, the "max-degree" is set to 5 in FGES and the causal relations are instantaneous, meaning that the number of causal parents of each variable is at most 5 so that the input dimensions the parent variables in CVAEs for modeling conditional probabilities are at most 5. For the public datasets, the "max-degree" is 10 and we found that there are instantaneous causal influences but not time-delayed ones, so the input dimensions of the parent variables in CVAEs are at most 10. That's why choose those parameters for the encoder and decoder. For a new dataset, if one considers a similar setting for causal discovery, he/she can use our parameters as default. In general, the input dimensions of CVAEs are most "max-degree" * "time-lag", the hidden sizes around this number. For modeling conditional probabilities, one can construct a validation set by splitting the training dataset. Under the Gaussian distribution assumption in CVAE, the overfitting issue can be found and avoided by measuring the reconstruction MSE loss.
one choose
For all the experiments, the detection thresholds are inferred by taking the nth percentile of the detection scores in the test data, e.g., we choose n = 95 for SWaT and WADI, n = 98 for SMAP and MSL. For the other methods (except ours) in the simulated datasets, the reported precision, recall and F1 Fl-score metrics are the best metrics that can be achieved in the test datasets (by choosing the best threshold).
Table 7: The number of the edges in the causal graphs generated by FGES with different parameters.
SWaT
max degree (penalty discount 100)
penalty discount (max degree 10)
d=5
6
9
10
p=20
40
60
80
100
120
Edge num
70
79
88
95
98
102
139
122
115
111
102
93
WADI
max degree (penalty discount = 100)
penalty discount (max degree = 10)
d=5
6
7
8
9
10
p=20
40
60
80
100
120
Edge num
152
180
195
211
227
249
331
308
278
262
249
225
A.3 SIMULATION DATASET
The simulated time series data can be generated in the following steps:
1. Generate an Erdös Rényi random graph & with number of nodes/variables n and edge creation probability p. then convert it into DAG. We choose p 0.1.
2. For the variables with no parents in G. randomly pick a signal type from "harmonic", "pseudo periodic" and "autoregressive" and generate time series with length T accord- ing to this type. We use the Python library "TimeSynth" to generate such signals. When generating these signals, the stop time is set to 100. For "harmonic", the frequency and the noise std are uniformly drawn from 10 1.0) and (0.1, 0.3), respectively. For "pseudo periodic", the frequency is uniformly drawn from [100 6.0). "freqSID" and "ampSD" are set to 0.0 and 0.1. For "autoregressive", "ar-param" is uniformly sampled from [0.3, 1.0] and "sigma" uniformly sampled from [0.01,
hhttps//gitubb.co/mmmupiiiii http::///gtttttooooom////my/t//t
15

---

Under review as a conference paper at ICLR 2023
3. For variable 2; with parents PA(x;) in G, consider both linear relationship 2; Σjepa(u:) Wyry + e and nonlinear relationship F; = EjEzA((,) my tanh(zz) + 6, where Wj is uniformly sampled from [0.5, 2.0) and is uniformly sampled from [-0.1,0.1] The time series for those variables are generated in topological order.
4. Add anomalies into the generated time series: We consider three types of anomalies. The first one is a "measurement" anomaly, i.e., randomly pick a variable Iú, a time step 6, scale s (uniformly sampled from [0, 3)) and duration (uniformly sampled from [5, 20), and then set (t t + d) [r,(t) median(a;)) * + median(z:). The second one is an "intervention" anomaly, i.e., after generating "measurement" anomalies for some vari- ables, those anomaly values propagate to the children according to the causal mechanisms. The third one is an "effect" anomaly where anomalies only happen on the variables with causal children.
Figure 3 shows the generated causal graph which contains 15 variables. According to this causal graph, we can generate multivariate time series by following the procedure mentioned above, as shown in Figure Figure where some of the abnormal time steps in the test dataset are labeled by blue triangles.
Figure 3: An example of the ground truth causal graph in the simulated datasets.
25
VVVVVV
VVVVV
Figure An example of the simulated training datasets.
A.4 MIXED RELATIONSHIPS: LINEAR NONLINEAR
We also consider a mix linear and nonlinear relationships. i.c., randomly pick a relationship from [linear, nonlinear] during time series generation, where the probability of selecting "linear" is 0.7.
16

---

Under review as a conference paper at ICLR 2023
Figure 5: An example of the simulated datasets. Some of the abnormal time steps are labeled by blue triangles.
Table shows the experimental results when the relationships are a mix of linear and nonlinear. Compared with the linear case, mixed relationship makes the anomaly detection problem harder, e.g., the performance of most approaches drops. Our approach still has the best performance com- pared the other methods.
Table 8: Performance comparison with the simulated dataset. The relationships a mix of linear and nonlinear.
Mix, Measurement
Mix, Intervention
Mix. Effect
Methods
Precision
Recall
Precision
Recall
F1
Precision
Recall
Fl
IF
0.401
0.542
0.461
0.241
0.618
0.347
0.223
0.329
0.266
AE
0.314
0.669
0.427
0.277
0.406
0.329
0.229
0.436
0.301
VAE
0.364
0.479
0.414
0.241
0.621
0.347
0.181
0.440
0.256
LAT
0.519
0.595
0.555
0.425
0.522
0.468
0.230
0.560
0.326
DAGMM
0.603
0.601
0.602
0.638
0.494
0.557
0.619
0.582
0.600
USAD
0.252
0.454
0.324
0.217
0.315
0.257
0.154
0.467
0.231
Ours
0.751
0.720
0.735
0.635
0.794
0.706
0.805
0.591
0.682
A.5 MIXED DATA TYPES: DISCRETE CONTINUOUS
This experiment considers the case that the generated multivariate time series contains both discrete and continuous values. The generation procedure for this kind of time series data has the following differences. For the variables without parents in G, we randomly pick a signal type from "harmoni" "pseudoperiodic" and "autoregressive" For a variable x; with parents P(x:) in G, we first randomly pick a data type, i.e., choosing "discrete" with probability 0.4 and "continuous" with probability 0.6. For "discrete", T. E)EP((;) Wy + e, i.e., linear relationship. When generating anomalies for "discrete", take (t t d) ceil([=,(t) median(x;)) * median(x;)) )] for time step t, duration d and scale Figures 6 and 7 give example of the generated training data and test data in this case.
1[=jep((;)) Wyæ, + >> 0J. i.c., logistic regression. For "continuous",
Table 9 shows the experimental results with the "discrete/comtimmous" datasets. Compared with the "continuous" case. the performance of all the methods decreases because inferring correlations or doing causal discovery becomes relatively harder with the mixed data types. Our approach still significantly outperforms the other ones in this case.
17

---

Under review as a conference paper at ICLR 2023
MMM VMMMV
03
Figure 6: An example of the simulated training datasets with mixed data types.
Figure 7: example of the simulated test datasets with mixed data types. Some of the abnormal time steps are labeled by blue triangles.
Table 9: Performance comparison with the simulated dataset. The data types are mix of discrete and continuous.
DC, Measurement
DC,
Intervention
DC, Effect
Methods
Precision
Recall
Precision
Recall
FI
Precision
Recall
F1
0.218
0.584
0.317
0.212
0.713
0.327
0.195
0.727
0.308
AE
0.437
0.251
0.319
0.494
0.376
0.427
0.324
0.392
0.355
VAE
0.207
0.602
0.308
0.340
0.390
0.363
0.245
0.557
0.341
LSTM-VAE
0.291
0.484
0.363
0.365
0.633
0.463
0.282
0.547
0.372
DAGMM
0.315
0.447
0.479
0.329
0.604
0.564
0.833
0.376
0.318
USAD
0.236
0.363
0.286
0.352
0.348
0.350
0.268
0.313
0.289
Ours
0.591
0.715
0.647
0.837
0.574
0.681
0.644
0.666
0.655
A.6
REAL-WORLD MOTIVATING EXAMPLE
Figure shows why causality matters with real-world example. In SWaT (Mathur Tippenhauer, 2016), at timestamp 491, our causality-based approach detects true anomaly where the causal mechanism between Metrics 1, 0 and 9 is violated (Metrics and 9 are the causal parents of Metric
1). We plot the probability density of the reconstruction error based the causal mechanism (top left figure), where the black triangle the anomaly. Clearly, this anomaly can be easily identified w.r.t. the p-value. But if check the probability density of the "joint" reconstruction emror by AE
18

---

Under review as a conference paper at ICLR 2023
(top right figure), this anomaly cannot be found w.r.t the p-value. The bottom figure plots the time series data these three metrics. Intuitively, we can observe that Metric has a peak value when Metric 0 is low, and Metric 1 is low when Metric 0 is high. In the range (450, 550), this causal mechanism is violated, e.g.. Metric high while Metric is also high. This type of anomalies is hard to be identified by checking joint marginal distributions.
Ours
Autoencoder
2.5
0.012
2.0
Density
Prob Density
0.008
Prob
1.0
0.006
0.004
0.5
0.002
0.000
200
600
Conditional reconstruction error (causality-based)
Joint reconstruction
Metric 2
500
1000
1500
2000
2500
3000
3500
4000
Metric
0
500
1000
1500
2000
2500
3000
3500
4000
Metric
500
1000
1500
2000
2500
3000
3500
4000
Timestamp
Figure 8: A motivation example in the real-world dataset SWaT (Mathur & Tippenbauer 2016). At timestamp 491, our causality-basse approach detects a true anomaly where the causal mechanism between metrics 1, O and 9 is violated (metries 0 and 9 are the causal parents of metric 1).
A.7 TRAINING ANOMALIES
When the fraction of anomalous points is large in the training data, these anomalies may decrease detection performance since the discovered causal graph may not be accurate. this case, we apply the solution discussed in Section 2.2.4, updating the causal graph and anomaly detection model iteratively. In this experiment, the training and test data are generated under the setting "linear/measurementt" and large proportion of noises are added into the training data, i.e., adding additional Gaussian noises to the first 20% data points in the training data. These noisy data points makes estimating accurate causal graphs harder via causal discovery algorithms. In each iteration, 3% data points are detected as anomalies and removed. Figure shows the detection performance on the test dataset measured by the Fl scores over each iteration. the beginning the discovered causal graph has more errors due to the noises in the training data, leading to the low F1 score. After each iteration, our approach removes the detected anomalies from the training data, making the discovered causal graph more accurate in the next iteration, so that the detection performance increases consistently. This experiment empirically verifies our "iterative updates" approach in the case where the training data has large portion of anomalies. Figure ())) plots the difference between the adjacency matrices of two consecutive estimated causal graphs, which increases first then decreases and converges to 0 since the distribution of training data gradually changes from
19

---

Under review as a conference paper at ICLR 2023
mix of noises and regular points regular points only. This experiment considers extreme
F1 score test dataset
Difference between two consecutive graphs
0.80
0.75
(b)
0.70
1
2
3
4
5
6
7
8
9
Figure 9: Empirical study on our "iterative updates" approach discussed Section 2.2.4 for handling large noise in the training data. (a) The detection performance (F1 scores) the test data iterations. (b) The difference between the adjacency matrices of two consecutive discovered causal graphs.
that the proportion of anomalies and the magnitude anomalies are large. In practical applications where the proportion of anomalies in training data is relatively small., e.g., the public datasets, there no need to apply this iterative approach, i.e., one iteration is good enough.
A.8 RUNNING TIME
Table I0 shows the running time of our approach. The most time consuming step is local causal mechanism estimation (conditional distribution estimation). After training, our approach detects anomalies and root causes fast.
Table 10: The running time of our approach (wall clock time).
Stage
SWaT
WADI
Training (Causal discovery)
10.27s
42. 42.18s
Training (Conditional distribution estimation)
415.37s
1026.59s
Inference (anomaly detection)
0.279ms per point 0.636ms per point
A.9 ABLATION STUDY ON CAUSAL GRAPH G
We also studied the effects of different parameters for discovering causal graphs on the performance of our approach. The parameters that we investigated are "max degree" and "penalty discount" in FGES, both of which affect the structure the causal graph, e.g., sparsity, indegree, outdegree. In this experiment, [20, 40, 60, 80, 100, 120]. Smaller "max degree" or larger "penalty discount" leads more sparse graphs with less edges, e.g., for SWaT, the number of the edges in G is [70, 79, 88, 95, 98, 102] when "max degree" = [5. 6, 8, 9, 10), respectively.
6 different "max degree" [5, 6, 7,8, 9, 10] and 6 different "penalty discount"
Figure I0 plots the detection precision, recall and Fl score obtained with different "max degree" and "penalty discount". For SWaT, these two parameters don't affect the performance much. For WADI, when "max degree" decreases (the causal graph becomes decreases (the causal graph has more false positive links), the performance also decreases but it doesn' it drop much, i.e., the worst Fl score still above 0.65, When "max degree" and "penalty discount" > 40, we got similar performance, e.g., the Fl score is around 0.8, showing that our approach is robust the changes of the inferred causal graph. practice, the causal graph is not required to be accurate, namely, we just need to ensure that it doesn't 't contain too many missing links or false positive links.
sparse) "penalty discount"
A.10 DETECTED ANOMALIES IN PUBLIC DATASETS
Figures show the detection results by approach where did downsampling for better demonstration. The left figures plot the ground truth labels. The right figures plot the detected anomalies in point-adjust way.
20

---

Under review as a conference paper at ICLR 2023
Max degree
Penalty discount
Max degree
Penalty discount
1.0
1.0
0.8
0.8
0.8
0.8
SWaT
0.6
0.6
WADI
0.6
0.6
0.4
Recall
Precision
0.4
Precision Recall
0.4
Precision
Recall
0.4
Precision
Recall
0.2
F1
0.2
0.2
0.2
0.0
5
6
10
0.0
20
40
60
80
100
120
0.0
5
6
7
10
0.0
20
40
60
80
100
120
Figure 10:
Precision, Recall and Fl score as a function of "max degree" and "penalty discount". The first and second rows plot the metrics for SWaT and WADI, respectively.
20003
5003
60000
80000
2002
10000
50002
-20
-25
20000
40003
60000
00000
20003
40030
00003
Figure 11: SWaT detection results. Left: Ground-truth labels. Right: Detected anomalies.
50
30000
20000
23000
30000
33000
30000
15000
20000
20000
53000
5000
30000
15000
20000
22000
20000
20000
5000
10000
15000
20008
20000
20000
20006
hW
W
WWW
www
Wf
-2
19002
20600
12000
20000
19200
1000
1200e
15000
20008
20000
20000
h000
33000
Figure 12: WADI detection results. Left: Ground truth labels. Right: Detected anomalies.
B CASE STUDY: REAL-WORLD APPLICATIONS IN AIOPS
Root Cause Analysis (RCA) in real-world applications such as A1Ops can be very challenging. One practical issue for identifying root causes is that anomaly occurs in parent often makes its contemporaneous causal children abnormal due to the estimation errors in conditional distributions. To handle this issue, we developed the following practical algorithm.
21

---

Under review as a conference paper at ICLR 2023
1000g0
300032
100000
100002
100000
X0003
50000
100000
220000
30000
500000
25-
25-
100099
200000
400000
100000
200000
X0000
400000
Figure 13: SMAP detection results. Left: Ground-trutt labels. Right: Detected anomalies.
302
X000
SC8c0
(0200
20022
13020
50000
02032
-5.0022
2000
X000
400C8
00000
33022
13023
2000
2000
90020
70006
-2.0000
-0.0075
-0.3255
01
Figure 14: MSL detection results. Left: Ground-truth labels. Right: Detected anomalies.
Specifically, for a variable 24, recall that its root cause score at time t is
(tz, = 1 - (t).
(2)
Suppose that (t)(t)) is the set of the contemporaneous causal children of 2x(t), the final root cause score is define by
=(z((t + [(xx))
Rt(2,(t)), Vi= 1.... ,d,
(3)
((()))N((s))
where ar is a weight parameter satisfying 0 S a < 1. When N(x;) is empty, we set (R)();(()) S(x;(()) Here the final root cause score of a variable the combination between its original root cause score and the root cause scores of its children. The final root cause scores for all the variables can be computed by these linear equations. When a = O, it is reduced to the ideal scenario discussed above. When a + 0, the above approach improves the ranking of root causes from a global view. Then the root causes at time t can be identified by picking the variables with top root cause scores.
Figure 15 shows another major incidence. The top abnormal variables are SYIO (system I/O), USIO (user I/O), Lfpw (log file parallel write), UTIL (I/O utilization). All of them are related to I/O issues, meaning that the root causes are the components related I/O.
22

---

Under review as a conference paper at ICLR 2023
Lfow
PRTIBY
PWTIO
Redo
Lips
UTL
USCC
DBI
DBCPU
BOCPU
CPU
OCP
ToPGA
AveRi
ARPL
COND
USIO
SV10
UTIL
Figure 15: Case study in A1Ops. out of 61 time variables (left) and part of the causal graph (right). The anomaly scores are indicated by the colors, e.g., deeper colors indicate larger anomaly scores.
23


Reviews:
[{"review_id": "wVynptAlyD", "reviewer": "Reviewer_8A4e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In the present manuscript, author(s) offer a causality based solution to anomaly detection in multivariate time series data. Such data can be ubiquitously found in real world scenarios and one might be interested in finding any anomaly in this data and its cause. Existing set of solutions either perform separate univariate anomaly detection and ignore the dependences between the various dimensions or a direct multivariate anomaly detection which does capture the inter-dimensional dependencies however is still incapable of learning the underlying data generating process and thus require a separate root cause analysis for anomaly cause detection. The present work attempts to detect anomalies and their cause simultaneously while capturing dependencies between the dimensions of the time series data by factorizing the joint distribution (data) into simpler, local mechanisms which are modular. \n\nOn a high level, the proposed framework, from the training data first generates a causal graph using data appropriate choice of causal graph discovery algorithms (e.g. PC, FCI, GES, etc). The inferred causal graph is then used to factorize the joint distribution using the Markov factorization. These factorizations are conditional probabilities corresponding to local mechanisms, which can be computed using methods such as kernel density estimation. Now for the non-training input (multivariate time series data), the anomaly score is computed as an aggregation of individual p-values, one for each variable and its corresponding mechanism. Anomaly score greater than a certain threshold is considered as anomaly and the variable with highest root cause score is deemed the cause of anomaly. Authors follow existing approaches from Heard & Rubin-Delanchy (2018) compute the anomaly score and ranking based algorithm for root cause score.\n\nThe experiments are thorough but not exhaustive. Experiments with more complex data generating processes are not explored, which is where the causal graph discovery methods are put to test. \n", "summary_of_the_review": "This is a well-written paper with some clear advantages in terms of explainability and modeling of anomalies. However, there are limitations in terms of the size of the window, which are not discussed in the paper.", "strength_and_weaknesses": "Strengths:\n\n- Novel framework which can be enhanced with advances in causal discovery methods. \n- Authors provide the required background of causal inference, making this work accessible to readers new to the domain. \n- The manuscript is well-written with minimal to no clerical errors, accompanied with simple examples and plots which makes it a moderately easy read for non-experts. The structure of the paper is good and easy to follow.\n\nWeaknesses: \n\n- Method highly sensitive to causal graph discovery method, which in itself is sensitive to the quality of data (which in this case are anomalies). Some more discussion on this is needed.\n- Proposed approach uses a window of time to extract samples for analysis, this does capture the time dependences between data dimensions however, it cannot capture the temporal dimension beyond the window of time chosen.\n- There are some limitations related to the size of the window and the underlying assumption that the causality is localized within that window. What happens if the data has periodicity? What would be the appropriate window size in that case?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KQOx8KWJOCK", "reviewer": "Reviewer_oDPS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on anomaly detection from time series. Specifically, this paper tackles this problem from a causal perspective. It first learns a causal structure from the data. The causal structure is assumed to be a directed acyclic graph (DAG) which captures stationary causal structure. The anomaly then can be defined as data points that do not follow the probability conditional on its causal parents. By learning the causal structure, the root cause of the anomaly can also be detected. Empirical evaluation with both simulation and public datasets shows that the proposed method obtains impressive results.", "summary_of_the_review": "Overall, this paper offers a new perspective to tackle the anomaly detection problem for time series data. The idea is reasonable. The proposed method is overall sound, although some parts of the methodological design need stronger justification and more explanations. The empirical evaluation shows that the proposed method is impressive.", "strength_and_weaknesses": "Strengths:\n- Modeling the anomaly detection problem from the causal perspective is quite interesting and important. The detection of root causes also makes the model more explainable.\n- The performance obtained using multiple datasets is very impressive.\n\nWeaknesses:\n- I am not fully convinced by the assumption that the causal structure is a DAG. First, the DAG may not be able to capture the time lag of the causal relationship. Second, there could be positive/negative feedback loops over time. For example, in economics, lowering investment causes lowering income after a certain lag, and in turn, causes lowering investment after some lags. In the summary causal graph, there could be cycles. Could some patterns be captured and modeled as well?\n- It seems that the detection algorithm relies heavily on the preset threshold $\\lambda$. It is not clear how much it impacts the performance and how the users should select the best hyperparameter.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JKcibYtHxqh", "reviewer": "Reviewer_FAmL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is based on the insight that anomaly detection can be treated as a causal discovery problem, to both improve detection and to facilitate root cause analysis. An anomaly is defined as a datum that does not fit the discovered data-generating process, in short an instance where the process is non-stationary. The graph decomposition of the timeseries by structure learning has heuristic value to pin-point the variable that causes the anomaly. The proposed method is demonstrated on simulation data and an extensive set of public datasets. \n", "summary_of_the_review": "The paper is a poorly developed approach to a good idea, that cannot support the empirical claims made by the paper. Without a better understanding, offered by a consistent mathematical argument why the results were obtained, there remain too many questions about the results, and detract from their credibility.  ", "strength_and_weaknesses": "The fundamental notion addressed by this paper is sound, and the conceptual approach is well thought out. This is a novel application that showcases the wide applicability of causal reasoning, both for discovering properties in data, and for understanding the real-world phenomena that the data represent. I tend to believe that this approach is better than the current methods. \n\nHowever the the paper does not elucidate a coherent method that fits into a mathematical model. What I see is a jumble of ideas, inconsistent and inaccurately presented. There are an overwhelming number of misperceptions that do not recommend the work:\n\n- p.2 p(z) = 1.695  THis is not a probability. Probabilities are bounded between 0 and 1\n-  p(y|x) cannot be considered a \"p -value\".  A p-value is a kind of tail probability of a statistical test.\n- In the probability p(y|x) x is the cause. Conventionally the influence goes from x, the cause, to y, the effect. \n- Why use a p-value test [ Heard & Rubin-Delanchy (2018)] when you have likelihoods, the proper Bayesian solution to this problem? This avoids the need to set a threshold on a value -- the likelihood of the anomaly can be reported instead. \n-The structure learning methods cited, although informally referred to as \"causal discovery\" methods are just structure learning (\"Markov factorization\") methods, and cannot generate causal claims without additional assumptions, or domain input. \n- The authors propose several ways to treat of temporal dependencies within one time-series, e.g. such as ARMA, without realizing that these dependencies fit into the structure learning paradigm used between timeseries. The autocorrelation within a time-series is just another dependency that, to make a consistent, comprehensive model should be incorporated into the learned network.  Then the method could detect changepoints -- something the current method appears to overlook. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3KyPz8EOLuC", "reviewer": "Reviewer_UaBN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a two-step procedure to perform root-cause analysis (RCA):\n1. Learn a causal graph from the data,\n2. Identify the root causes based on the changes in the local mechanisms (conditional probabilities).\n\nThe paper is simple and easy to read. The experiments look extensive. There are doubts about the novelty of the idea though.", "summary_of_the_review": "The authors propose a two-step procedure to perform root-cause analysis (RCA):\n1. Learn a causal graph from the data,\n2. Identify the root causes based on the changes in the local mechanisms (conditional probabilities).\n\nThe paper is simple and easy to read. The experiments look extensive. There are doubts about the novelty of the idea though.", "strength_and_weaknesses": "### Strengths\n1. The idea is simple, makes sense, and should work. \n2. The paper is well-written and easy to follow.\n\n### Weaknesses\n1. The authors seem to miss a similar paper. Can you describe the relationship of the paper to the idea of the following paper?\n    * Budhathoki, K., Minorics, L., Blöbaum, P., & Janzing, D. (2022). Causal structure-based root cause analysis of outliers. In _International Conference on Machine Learning_.\n2. The authors should comment on the error propagation from the DAG learning step. They have a set of ablation experiments on this topic, but might not be convincing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject