Graph-Augmented Normalizing Flows for Anomaly Detection of Multiple Time Series
Authors: Enyan Dai
Jie Chen
Venue: ICLR 2022 Spotlight (2022)
Keywords: Anomaly Detection
Normalizing Flow
DAG
Multiple Time Series

Abstract: Anomaly detection is a widely studied task for a broad variety of data types; among them, multiple time series appear frequently in applications, including for example, power grids and traffic networks. Detecting anomalies for multiple time series, however, is a challenging subject, owing to the intricate interdependencies among the constituent series. We hypothesize that anomalies occur in low density regions of a distribution and explore the use of normalizing flows for unsupervised anomaly detection, because of their superior quality in density estimation. Moreover, we propose a novel flow model by imposing a Bayesian network among constituent series. A Bayesian network is a directed acyclic graph (DAG) that models causal relationships; it factorizes the joint probability of the series into the product of easy-to-evaluate conditional probabilities. We call such a graph-augmented normalizing flow approach GANF and propose joint estimation of the DAG with flow parameters. We conduct extensive experiments on real-world datasets and demonstrate the effectiveness of GANF for density estimation, anomaly detection, and identification of time series distribution drift.

Published as a conference paper at ICLR 2022
GRAPH-AUGMENTED NORMALIZING FLOWS FOR ANOMALY DETECTION OF MULTIPLE TIME SERIES
Enyan Dai*
Jie Chen
Pennsylvania State University edu
MIT-IBM Watson AT Lab, IBM Research chen ji e@us. 1omm com
ABSTRACT
Anomaly detection is a widely studied task for broad variety of data types: among them, multiple time series appear frequently in applications, including for example, power grids and traffic networks. Detecting anomalies for multiple time series, however, is a challenging subject, owing to the intricate interdependencies among the constituent series. We hypothesize that anomalies occur in low density regions of a distribution and explore the use of normalizing flows for unsupervised anomaly detection, because of their superior quality in density estimation. More- over, we propose a novel flow model by imposing a Bayesian network among con- stituent series. A Bayesian network is a directed acyelic graph (DAG) that models causal relationships; it factorizes the joint probability of the series into the prod- uct of casy-to-evaluate conditional probabilities. We call such a graph-au graph-augmented normalizing flow approach GANF and propose joint estimation of the DAG with flow parameters. We conduct extensive experiments on real-world datasets and demonstrate the effectiveness of GANF for density estimation, anomaly detec- tion, and identification of time series distribution drift.
INTRODUCTION
Anomaly detection (Pimentel al., 2014; Ruff al. 2018) is the task of identifying unusual sam- ples that significantly deviate from the majority of the data instances. It is applied in a broad variety of domains, including risk management (Aven 2016), video surveillance (Kiran et al. 2018 adver-
sarial example detection (Grosse et al.] [017]. and fraud detection (Roy & George 2017). Repre-
sentative classical methods for anomaly detection are one-class support vector machines (Schölkopf
let al. 2001) and kernel density estimation (Parzen 1962. Kim & Scott 2012). These methods rely on handcrafted features and often are not robust for high-dimensional data (e.g., images, speech signals, and time series). In recent years, inspired by the success of deep learning for complex data, many deep anomaly detection methods were proposed and they are remarkably effective in applications (Ruff et al. 2018 (abooroou et al. 2018 Goyal al., 2020).
Apart from these demonstrated applications, increasing demand exists for the anomaly detection of even more complex data; i.e., multiple time series. They contain a set of multivariate time series that often interact with each other in system. A prominent example of the source of multiple time se- ries is the power grid, where each constituent series is the grid state over time, recorded by sensor deployed at certain geographic location. The grid state includes many attributes; e.g., current mag- nitude and angle, voltage magnitude and angle, and frequency. Time series readings from sensors at nearby locations are often correlated and their behavior may be causal under cascading effects. Anomaly detection amounts to timely identifying abnormal grid conditions such as generator trip and insulator damage.
Anomaly detection of multiple time series is rather challenging, due to high dimensionality, interde- pendency, and label scarcity. First, a straightforward approach is to concatenate the constituent series along the attribute dimension and apply a detection method for multivariate time series. However, when the system contains many constituents, the resulting data suffer high dimensionality. Second, constituent series bear intricate interåependencies, which may be implicit and challenging to model. When an explicit graph topology is known, graph neural networks are widely used to digest the rela-
"hii work was done while E. Dai was an intern at MIT-IBM Watson AI Lab, IBM Research.
1 To whom correspondence should be addressed.

---

Published as a conference paper at ICLR 2022
2018 Zhao et al. 2019). However, graph may not always be known (because, for example, it is sensitive information) and hence graph structure learning becomes indispensable component of the solution (Kipf et al.] 2018 Wu et al.) 2020 Shang et al. 2021 Deng & Hooi| 2021). Third, labeling information is often limited. Even certain labels are present, in practice, many anomalies may still stay unidentified because labeling is laborious and expensive. Hence, unsupervised approaches are the most suitable choice. However, albeit many unsupervised detection methods were proposed (Ruff et al. 2018 (abokrouu al., 2018 Malhotra et al. 2016 Hendrycks et al., 2019), they are not effective for multiple time series.
tional information (Seo et al.
2016 Li al. 2018b Yu et al.
In this work, we explore the use of normalizing flows (Dinh et al. 2016 Papamakarios et al. 2017) for anomaly detection, based on a hypothesis that anomalies often lie on low density regions of the data distribution. Normalizing flows are a class of deep generative models for learning the underlying distribution of data samples. They are unsupervised and they resolve the label scarcity challenge aforementioned. An advantage of normalizing flows is that they are particularly effective in estimating the density of any sample. A recent work by |asul al. (202T) extends normalizing flows for time series data by expressing the density of series through successive conditioning on historical data and applying conditional flows to learn each conditional density, paving ways to build sophisticated flows for multiple time series.
We address the high dimensionality and interdependency challenges by learning the relational struc- ture among constituent series. To this end, Bayesian networks (Pearl 9855 2000) that model causal relationships of variables are a principled choice. A Bayesian network is directed acyclic graph (DAG) where a node is conditionally independent of its non-descendents given its parents. Such a structure allows factorizing the intractable joint density of all graph nodes into product of casy- to-evaluate conditional densities of each node. Hence, learning the relational structure among con- stituent series amounts to identifying DAG that maximizes the densities of observed data.
We propose novel framework, GANF Crraph-Augmented Normalizing Flow), augment nor- malizing flow with graph structure learning and to apply it for anomaly detection. There are non- trivial technical problems resolve to materialize this framework: (i) How does one inject graph into a normalizing flow, which essentially maps one distribution to another? (ii) How does one learn DAG, which is discrete object, inside continuous flow model? The solution we take is to factorize the density of multiple time series along the attribute, the temporal, and the series dimensions and use graph-based dependency encoder to model the conditional densities resulting from factorization. Therein, the graph adjacency matrix is continuous variable and we impose a differentiable constraint to ensure that the corresponding graph acyelic (Zheng et al.] [2088] Yu et al. 2019). We propose joint training algorithm to optimize both the graph adjacency matrix and the flow parameters.
In addition to resolving the high dimensionality and interdependency challenges, an advantage of modeling the relational graph structure among constituent series is that one can easily observe the dynamics of the data distribution from the graph. For time series datasets that span a long period, one naturally questions if the distribution changes over time. The graph structure is a useful indicator of distribution drift. We will study the graph evolution empirically observed.
We highlight the following contributions of this work:
We propose a framework augment a normalizing flow with graph structure learning. to model interdependeneies exhibited inside multiple time series.
We apply the augmented flow model to detect anomalies in multiple time series data and perform extensive empirical evaluation demonstrate its effectiveness on real-world data sets.
We study the evolution of the learned graph structure and identify distribution drift in time series data that span a long time period.
RELATED WORK
Anomaly detection is a widely studied subject owing to its diverse applica- tions. Recently, inspired by the success of deep learning, several deep anomaly detection methods are proposed and they achieve remarkable success on complex data, such as individual time se- ries (Malhotra et al. 2016), images (Sabokrou et al. 2018), and videos (Ionescu et al. 2019). These
Anomaly Detection.
2

---

(2017) view an autoregressive model as a normalizing flow. To model temporal data, Rasul iet al. [222I) use sequential models to parameterize conditional flows. Moreover, graph normalizing flows are proposed handle graph structured data and improve predictions and generations (Liu et al. 2019). In contrast, normalizing flows for multiple time series are rarely studied in the litera- flow for density estimation and anomaly detection Published as a conference paper at ICLR 2022
methods generally fall under three categories: deep one-class models, generative model-based meth- ods, and transformation-basee methods. Deep one-class models (Ruff et al. 201 8 Wu et al. 2019) treat normal instances as the target class and identify instances that do not belong to this class. In generative model-based methods (Malhotra et al., 2016 Nguyen et al. 2019 Li et al. 201 8a), an autoencoder a generative adversarial network is used model the data distribution. Then, an anomaly measure is defined, such as the reconstruction error in autoencoding. Transformation- based methods (Golan & El- El-vaniv 2018 [endrryck et al. 2019) are based on the premise that transformations applied to normal instances can be identified while anomalies not. Various transfor- mations such as rotations and affine transforms have been investigated. On the other hand, anomaly detection of multiple time series is under explored. Recently, Deng & Hooi ( study the use of graph neural networks combination with structure learning to detect anomalies. Our method substantially differs from this work in that the learned structure is Bayesian network, which allows density estimation. Morcover, the Bayesian network identifies conditional dependencies among the constituent series and induces better interpretation of the graph as well as the data distribution.
Normalizing Flows. Normalizing flows are generative models that normalize complex real-world data distributions to "standard" distributions by using sequence of invertible and differentiable transformations. Dinh et al.] (2016) introduce a widely used normalizing flow architecture
RealNVP for density estimation. Various extensions and improvements are proposed (Papamakar-
ios et al. 2017 [Hogeboom et al.] 2019 Kingma & Dhariwal 2018). For example, [Papamakarios
al.
ture. this work, we develop a of multiple time series.
3 PRELIMINARIES
We first recall key concepts and familiarize the reader with notations to be used throughout the paper.
3.1 NORMALIZING FLOWS
Let x E Rº be a D-dimensional random variable. A normalizing flow is vector-valued invertible mapping f(x) TR.D - RDD that normalizes the distribution of x to a "standard" distribution (or called base distribution). This distribution is usually taken to be an isotropic Gaussian or other ones that are easy to sample from and whose density is easy to evaluate. Let z = f(x) with probability density function q()). With the ohange-of-variabll formula, we can express the density of the x, p(x). by:
logp(x) = log ((((x)) + log det vxf(x)).
(1)
In practical uses, the Jacobian determinant in ( needs be easy to compute, so that the density p(x) can be evaluated. Moreover, as a generative model, the invertibility of allows drawing new stances = (z) through sampling the base distribution. One example of such f is the masked au- toregressive flow (Papamakarios et al. 2017), which yields z = [æ1,...; from x = [x1,..., TD through
2 = (z; - as (x)==)))) exp(a; (x
where j and a are neural networks such as the multilayer perceptron.
A flow may be augmented with conditional information h E IRd with a possibly different dimension. Such a flow is a conditional flow and is denoted by RD x Rd + R.. The log-density of conditioned on h admits the following formula:
logp(x(h) = log (f((x; h)) + log det vxf(x; h)).
(3)
We now consider normalizing flow for time series. Let X of lenghh T, where x, E D. Through successive conditioning, the density of the time series can be written as:
[xi, X xT] denote a time series
pXx= = p(x: (p(x) -(xx(xxx))
(4)
where X denotes all variables before time t. When the conditional probabilities are parameterized, Rasul et al. (2021) propose model each o(xx/x<) p(x,[h-1)) 1), where h summarizes the
3

---

Published as a conference paper at ICLR 2022
past information x-t. For example, hę-1 is the hidden state of recurrent neural network before accepting input X5, Then, a conditional normalizing flow can be applied to evaluate each p (x-))b)
3.2 BAYESIAN NETWORKS
Let X' denote general random variable, either scalar valued, vector valued, or even matrix valued. A Bayesian network of n variables (X',..., x)) ) is a directed acyelic graph of the variables as nodes. Let A denote the weighted adjacency matrix of the graph, where Aij 0 if X is the parent of X A Bayesian network describes the conditional independence among variables. Specifically, a node X is conditionally independent of its non-descendents given its parents. In other words, the density of the joint distribution of (X1 "..., x"),, is
((1 X") II xX pa(X')),
(5)
where pa(x*)= {X): Aij #0 denotes the of parents of X
4 PROBLEM STATEMENT
In this paper, focus on unsupervised anomaly detection with multiple time series. The training set D consists of only unlabeled instances and we assume that the majority of them are not anomalies. Each instance X' E 'D contains constituent series with D attributes and of length T; i.e., X' (X', X ..... X") where X E IRT T' We use a Bayesian network (DAG) to model the relational structure of the constituent series X and augment normalizing flow to compute the density of X through a factorization in the form S). Let A E R"x* be the adjacency matrix of the DAG and let denote the augmented flow. Because anomaly points tend have low densities, we propose to conduct unsupervised anomaly detection by evaluating the density of multiple time series computed through the augmented flow. The problem is formulated as the following.
F: (X' A)
Problem 1. Given a training set D {x of multiple time series, we aim simultaneously learn the adjacency matrix A of the Bayesian Network that represents the conditional dependencies among the constituent series, as well as the correspondingly graph-augmented normalizing flow F A) + Z, which is used to estimate the density of an instance X. Here, Z is random variable with a "simple" distribution, such as the anisotropic Gaussian.
5 METHOD
In this section, we materialize the in the problem statement and use it to compute the density of a multiple time series X. The central idea is factorization: we factorize p(X)) along the series dimension by using a Bayesian network and then factorize along the temporal dimension by using conditional normalizing flows Then, we employ a novel graph-based dependency encoder to parameterize the conditional probabilities resulting from the factorization. The DAG used for factorization is a discrete object and is usually intractable to learn; however, the discrete structure is reflected in the dependency encoder through graph adjacency matrix A that is differentiable. Moreover, the requirement that A must correspond to a DAG can be expressed as a differentiable equation. Hence, one can jointly optimize A and the flow components by using gradient based optimization. Once F is learned, the density p(Xt) is straightforwardly evaluated for anomaly detection. An illustration of the framework GANF is shown in Figure I
normalizing flow F (X, + introduced
5.1 FACTORIZATION
Figure I shows a toy example of Bayesian network as DAG. Based on (5), the density of
multiple time series X' (X1 X2 ,2,...,"" X can be computed as the product of p(X' >a(X:) for all nodes, where recall that pa(X') denotes the set of parents of X Then, following Rasul et al.
(02T)) we further factorize each conditional density along the temporal dimension. Specifically, for
time step I, x3 depends on its past history as well as its parents in the DAG. We write
T
p(x) = II X
pa x
=
p(x) pa(x")) Dice, x(x-1);
(6)
1=1 t=1
4

---

Published as a conference paper at ICLR 2022
Summarize (pa(x))
(x(lpa(x))
X
H
RNN
X
X1
Graph Convolution
X
de
-O.)))
Adjacency Matrix Under CAG constraint
Dependency Encoder
A Bayesian Network
Overall framework
Figure I: Illustration of a Bayesian network and the proposed framework GANF.
where x denotes the history of node i before time t, and pa(x') 11: (x/ Aij 0}. In the subsection, will parameterize each conditional density p(x pa( ( )1 xix--) by using a graph-based dependency encoder. Note that so far the factorization (6) has been based on the discrete structure of the Bayesian network. The dependency encoder introduce next, however, uses the adjacency matrix A in differentiable manner, which is sufficient to ensure that x will not depend on nodes other than its parents and itself.
5.2 NRURAL NETWORK PARAMETERIZATION
According to Sec. 3.1 conditional densities p(x² pa(x') xi can be learned by using ditional normalizing flows. However, the conditional information pa(x') )1: and xi.r-1 cannot be directly used for parameterization, because its size not fixed. Therefore, as illustrated in Fig- ure [ design graph-based dependency encoder to summarize the conditional information into a fixed length vector di E Rd Then, a conditional normalizing flow is used to evaluate p(x]]d)), which is equivalent to p(x(| pa(x*) (1:x xi--1).
Dependency Encoder. Since the history has an arbitrary length, we first employ recurrent neural network (RNN) to map multiple time steps to vector of fixed length. For time series xia, the recurrent model abstracts it into a hidden state h E IRd through the following recurrence
hj RNN (x,; h;-1),
where he summarizes the time series up to step t. The RNN can be any sequential model, such as the LSTM (Hochreiter & Schmidhuber 1997) and in broad sense transformer (Vaswani et al.) 2017]. We let the RNN parameters be shared across all nodes in the DAG avoid overfitting and to reduce computational costs.
With 7 the conditional information of x is all summarized in (h- Aij * ( Inspired by the success of GCN (Kipf & Welling 2016) node representation learning through neighbor- hood aggregation, we design a graph convolution layer to aggregate hidden states of the parents for dependency encoding. This layer produces dependency representations D, = (d.....,dd ) for all constituent series at time t:
D. ReLU + H.- W3.
where H, (h/.... h") contains all the hidden states at time t. Here, W1 E Rdxd and W₂ dddd parameters transform the aggregated representations of the parents and the node's historical information, respectively; while W3 E IRddd is an additional transformation to improve the dependency representation.
Density Estimation. With the dependency encoder, we obtain the representations di of the condi- tional information. Then, a normalizing flow f D Rd RD conditioned dž applied to model each p(x+l pa(x*) xi=-1). Similar to the computation of the hidden states, the param- eters of the conditional flow are also shared among nodes, avoid overfitting. Based on B the conditional density of x can be written as:
log p(x) pa(x') Ia, xf.c-1) = log p(x d;) = log ((((x/: d()) + log det Vxj f(x) d(),, (9)
where (zz) is chosen to be the standard normal I, with z E R The conditional flow f can be any effective proposed by the literature, such RealNVP (Dinh al. 2016) and
5

---

Published as a conference paper at ICLR 2022
MAF (Papamakarios al. 2017). time series X::
Combining 9 and (6). obtain the log-density of a multiple
T
logp(X) Σ
log (f(()x); + log det Vxx [xx:: dill
(10)
Anomaly Measure. Because anomalies deviate significantly from the majority of the data instances, hypothesize that their densities are low. Thus, we use the density computed by (TO) the anomaly measure, where a lower density indicates a more likely anomaly. Apart from evaluating the density for the entire X, the computation also produces conditional densities log p( pa(X)))
Ei= log p(x] (d)) for each constituent series X We use this conditional density as the anomaly measure for constituent series. A low density p(X² is caused by or few low conditional densi- ties pX pa( (')) in the Bayesian network, suggesting that abnormal behaviors could be traced to individual series.
5.3 JOINT TRAINING
Learning a Bayesian network is a challenging combinatorial problem, due to the intractable search space superexponential in the number of nodes. recent work by Zheng et al. (2018) proposes the equation tr(eAcA) matrix exponential and denotes element-wise multiplication. We will impose this equation as constraint in the training of GANF.
that characterizes the acyclicity of the corresponding graph of A, where
Training Objective. Following the training of a usual normalizing flow, the joint density (likeli- hood) of the observed data is the training objective, which is equivalent to the Kullback-Leibler divergence between the true distribution of data and the flow recovered distribution. Together with the DAG constraint, the optimization problem reads
IPI
min A,0
C(A. 0)
log (()))
D
(11)
s.t. h(A) = tr(cAoA) n 0,
where 0 contains all neural network parameters, including those of the dependency encoder and the normalizing flow. Here, the DAG constraint h(A) admits easy-to-evaluate gradient Vh(A)
(cA o 2A, which allows a gradient based optimizer to solve
Training Algorithm. Problem 11 is nonlinear equality-constraingg optimization. Such problems are extensively studied and the augmented Lagrangian method (Bertsekas, 1999. Yu et al. 2019) is one of the most widely used approaches. The augmented Lagrangian is defined
C. C(A, 0) + AA(A) + マ I((A))
(12)
where À and e denote the Lagrange multiplier and the penalty parameter, respectively. The general idea of the method is to gradually increase the penalty parameter to ensure that the constraint eventually satisfied. Over iterations, À as dual variable will converge to the Lagrangian multiplier of TT]. The update rule at the kth iteration reads the following:
if|h(At) 7(((A+1))
k 0h = arg min Cek; A.
x++1 A + + dhA(A));
chil=
1+1
dh
else,
(13)
where 77 (o,+ and y (0, 1) are hyperparameters to be tuned. We set 1 and 7 as 10 and 0.5, respectively. The subproblem of optimizing A and can be solved by using the Adam opti- mizer (Kingma & Ba 2014). The training algorithm is summarized in Appendix A
6 EXPERIMENTS
In this section, we conduct a comprehensive set of experiments to validate the effectiveness of the proposed GANF framework. In partieular, they are designed answer the following questions:
Q1: Can GANF accurately detect anomalies and estimate densities?
Q2: Does the proposed graph structure learning help? the framework sufficiently flexible to include various normalizing flow backbones?
Q3: What can one observe for a dataset spanning a long time? E.g., does the graph pattern change?

---

Published as a conference paper at ICLR 2022
6.1 SETTINGS
Datasets. To evaluate the effectiveness of GANF for anomaly detection and density estimation, we conduct experiments on two power grid datasets, one water system dataset, and one traffic dataset.
PMU-B and PMU-C: These datasets correspond to separate interconnects of the U.S. power grid, containing time series recorded by 38 and 132 phasor measurement units (PMUs), respectively. We process one-year data the frequency of one second form a ten-month training set, one-month validation set, and one-month test set. Each multiple time series is obtained by shifting one-minute window. Additionally, to investigate distribution drift, we shift a one-month window to obtain multiple training/valiin valiintiovidttin//esst sets (12 in total, because of availability of two- year data). Sparse grid events (anomalies) labeled by domain experts exist for evaluation; but note that the labels are both noisy and incomplete. These datasets are proprietary.
SWaT: We also use public dataset for evaluation. The Secure Water Treatment (SWaT) dataset originates from an operational water treatment test-bed coordinated with Singapore's Public Util- ity Board (Goh et al. 2016). The data collects 51 sensor recordings lasting four days, at the frequency of one second. total of 36 attacks were conducted, resulting approximately 11% time steps anomaly ground truths. We use sliding window of 60 seconds to construct series data and perform a 60/20/20 chronological split for training, validation, and testing, respectively.
This dataset also public; it contains speed records of 207 sensors deployed on the highways of Los Angles, CA (Li et al.) 20185). No anomaly labels exist however and we use this dataset for exploratory analysis only. Results are deferred Appendix
METR-LA:
Evaluation metrics (under noisy labels). For SWaT, which offers reliable ground truths, we the standard ROC and AUC metrics for evaluation. For the two PMU datasets, however, the resolution of the time series and the granularity of the events result in rather noisy ground truths. Hence, we adapt ROC for noisy labels. We smooth the time point of a "ground truth" event (anomaly) by introducing probabilities to the label. Specifically, the probability that multiple time series starting
at time t is a ground truth anomaly is max, maxx,fcxp (cxp(- (B-2,)² }}. where tę is the starting time of the (oxp(-11-1)3
ith labeled anomaly. Then, when computing the confusion matrix, we sum probabilities rather than counting 0/1s. The smoothing window a is chosen to be 6 time steps.
Baselines. We compare with the following representative, state-of-the-art deep methods.
EncDecAD (Malhotra et al.) 2016): In this method, an autoencoder based on LSTM trained. The reconstruction error is used as the anomaly measure.
DeepSVDD (Ruff et al. ) This method minimizes the volume of a hypersphere that encloses
the representations data. Samples distant from the hypersphere center are considered anomalies.
ALOCC (Sabokrou et al. 2020): In this GAN-based method, the generator learns to reconstruct normal instances, while the discriminator works as an anomaly detector.
DROCC (Goyal et al. 2020): This method performs adversarial training to learn robust represen- tations of data and identifies anomalies.
DeepSAD (Ruff et al. 2020 This method extends DeepSVDD with semi-supervised loss term for training. We use noisy labels as supervision.
To apply these baselines multiple time series, concatenate the constituent series along the attribute dimension (resulting in high-dimensional series) and use LSTM or CNN as the backbones. On the other hand, for the proposed method, we use LSTM the RNN model and MAF as the normalizing flow. See Appendix C for more implementation details.
6.2
PERFORMANCE OF ANOMALY DETECTION AND DENSITY ESTIMATION
Table 1: AUC-ROC (%) of anomaly detection.
Dataset
EncDecAD
DeepSVDD ALOCC
DROCC
DeepSAD
GANF
PMU-B
55.6111.8
55.613.3
62.912222
58.613.00
63.7400.9
67.5-008
PMU-C
53.7+:0.5
56.9+0.9
60.9+1.8
61.9+22.7
60.1+1..
70.6=3.3
SWaT
76.5
68.8.12.0
75.4.2..
73.311..6
75.4
7..6

---

Published as a conference paper at ICLR 2022
1.0
1.0
True Positive Rate
0.6
True Positive Rate
0.8
True Positive Rate
0.8
GAMF
GANF DeapSAD
GAM
0.4
0.4
0.4
DeapSAD
0.2
ALOOC
0.2
ALOCC
0.2
ALOCC
DeepSVDD
DeepSVDD EncDwcAD
DeepSVD0
En:DecAD
En:DecAD
0.0.0
0.00
0.2
0.4
0.6
0.8
1.0
8,0
False Positive
False
Rate
False Positive Rate
(a) PMU-B
(b) PMU-C
(c) SWaT
Figure 2: ROC curves of anomaly detection on various datasets.
Anormaly Measure
10
Labeled Anomaly
Timestamp
104
104
17
1ot
13
16
Anormaly Measure logidensity)
16
15
11:03
Time
(a)
(b)
Figure 3: Qualitative evaluation of GANF on PMU-C. (a) Distribution of log-densities on the test set (note in log scale). (b) Anomaly detection results for a week in the test set.
To answer Q1, we evaluate quantitatively and qualitatively datasets with labels.
Anomaly detection. We compare GANF with the aforementioned baselines in Table where standard deviations of the AUC scores are additionally reported through five random repetitions of model training. The table suggests overwhelmingly high AUC score achieved by GANF. Obser- vations follow. (i) GANF outperforms generative model-based methods (EncDecAD and ALOCC). Being a generative model as well, normalizing flows augmented with graph structure leverage the interdependencies of constituent series more effectively, leading to substantial improvement in detection. (ii) GANF significantly outperforms deep one-class models (DeepSVDD and DROCC), corroborating the appeal of using densities for detection. (iii) GANF also performs better than the semi-supervised method DeepSAD, probably because such methods rely on high quality labels for supervision (especially in the case of label scarcity) and they are less effective facing noisy labels.
Besides single score, we also plot the ROC curve in Figure One sees that the curve of GANF dominates those others. This behavior is generally more salient in the low false-alarm regime.
Density estimation. We investigate the densities estimated by GANF, shown in Figure 3 Distribu- tions of the log-densities the test set are shown Figure Bal We use log-density as the anomaly measure; the lower the more likely. Note that the vertical axis is in the log-scale. One sees that log-density of 16 approximately separates the majority normal instances from the minority anoma- lies. To cross-verify that the instances with low densities are suspiciously anomalous, we investigate Figure 3b) which is temporal plot of log-densities for week, overlaid with given labels. From this plot,
that the noisily labeled series generally have low densities time step. Additionally, GANF discovers a few suspicious time steps with low densities undetected earlier. These discoveries raise interest power system experts for analysis and archiving.
near low density
6.3 ABLATION STUDY
Table 2: Performance of variants of the proposed method.
Dataset
Metrics
GANF
GANF
GANF(T
GANFRNvP
GANF
AUC-ROC
0.641
0.643
0.653
0.661
0.678
PMU-B
Log-Demn DogDennitty
15.31
8.70
15.09
15.90
16.22
AUC-ROC
0.630
0.544
0.688
0.703
0.705
PMU-C
log-Density
15.55
8.94
15.70
17.06
16.98
8

---

Published as a conference paper at ICLR 2022
(a) Initial graph
(b) One-month shift
(c) Two-month shift
(d) Three-month shift
Figure 4: Evolution of the learned DAG on PMU-B over time.
Month Shift
0
0.6
4
6
8
10
16
21
16
76-
86
91
101
108
111
116.
Edge
Figure Evolution of edge weights the DAG learned by GANF over time (PMU-B).
To answer Q2, we conduct an ablation study (including varying architecture components) to in- vestigate impacts of DAG structure learning and the flexibility of the GANF framework. To in- vestigate the power of modeling pairwise relationship, train variant GANFAG that factorizes p(X) I (X*); i.e., assuming independence among constituent series. To investigate the effectiveness of graph structure learning, train variant GANF D that decomposes the joint density as p()) = II==1 p(X (X"))""); i.c., a full decomposition without a DAG. It is equivalent to concatenating the series along the attribute dimension and running MAF on the resulting series. To verify the contribution of joint training of A and 0, we train a variant GANFAT where A is separately learned by using NOTEARS (Zheng al., 2018). To prove the flexibility of GANE, we replace the MAF-based normalizing flow by RealNVI, denoted as GANFRNVP.
Results are presented in Table Apart from AUC-ROC, the log-density is also reported. Ob- servations follow. (i) GANF significantly outperforms GANFI G and GANF) D. corroborating the importance of interdependency modeling among constituent series. Note that GANF D results in particularly poor performance in general, likely because the high dimensional input (resulting from concatenating too many series) impedes the learning of normalizing flows. (iii) GANF T is slightly better than GANF G, because of the presence of relational modeling, but it cannot match the per- formance of GANFRNVE and GANF that jointly train the DAG and the flow. (ii) These latter two models are the best for both datasets and both metries. MAF works more often better than RealNVP.
6.4 EVOLUTION THE DAG STRUCTURE
To answer Q3, we investigate how the learned DAG evolves by shifting the train/validation/test sets month by month. The graphs within the first three-month shiftings are shown Figure 4 and more can be found in Appendix F In addition to the graph structure, we plot in Figure 5 the learned edge weights over time, one column per edge. The appearance and disappearance of edges demonstrate changes of the conditional independence structure among constituent series over time, suggesting data distribution drift (i.e., a change of internal data generation mechanism). It is interesting to observe the seasonal effect. The columns (edges) in Figure[5]can be loosely grouped in three clusters: those persisting the entire year, those appearing in the first half of the year, and those existing more briefly (e.g., within a season). Such a pattern plausibly correlates with electricity consumption, which is also seasonal. Were spatial information of the PMUs known, these identified DAGs would help mapping the seasonal patterns geography and help planning a more resilient grid.
CONCLUSIONS
In this paper, we present a graph-augmented normalizing flow GANF for anomaly detection of multiple time series. The graph is materialized as Bayesian network, which models the conditional dependencies among constituent time series. A graph-based dependency decoder is designed to summarize the conditional information needed by the normalizing flow that calculates series density. Anomalies are detected through identifying instances with low density. Extensive experiments on real-world datasets demonstrate the effectiveness of the framework. Ablation studies confirm the contribution the learned graph structure in anomaly detection. Additionally, we investigate the evolution of the graph and offer insights of distribution drift over time.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENT AND DISCLAIMER
This material is based upon work supported by the Department of Energy under Award Number(s) DE-0E0000910. This report was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government nor any agency thereof, nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or re- sponsibility for the accuracy, completeness, usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specific commercial product, process, service by trade name, trademark, manufac- turer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government any agency thereof. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Govermment or any agency thereof.
REFERENCES
Terje Aven. Risk assessment and risk management: Review of recent advances their foundation. European Journal of Operational Research, 253(1):1-13, 2016.
Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition, 1999.
Ailin Deng and Bryan Hooi. Graph neural network- betwork-based anomaly detection in multivariate time series. In AAAI, 2021.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint 16X5:06600008880 2016.
Jonathan Goh, Sridhar Adepu, Khurum Nazir Junejo, and Aditya Mathur. dataset support
research in the design of secure water treatment systems. In International conference on critical information infrastructures security, pp. 88-99. Springer, 2016.
Izhak Golan and Ran Ylniv..v. Deep anomaly detection using geometric transformations. arXiv preprint arXiv:1805.109)) 2018.
Sachin Goyal, Aditi Raghunathan, Moksh Jain, Harsha Vardhan Simhadri, and Prateck Jain. Droce: Deep robust one-class classification. In International Conference on Machine Learning, pp- 3711-3721. PMLR, 2020.
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick McDaniel. On the (statistical) detection of adversarial examples. arXiv preprint arXiv:1702.06288, 2017.
Dan Hendrycks. Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self-super learning can improve model robustness and uncertainty. arXiv preprint arXiv: 12340, 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Emiel Hoogeboom, Rianne Van Den Berg, and Max Welling. Emerging convolutions for generative normalizing flows. In International Conference on Machine Learning, pp. 2019.
PMLR,
Radu Tudor lonescu, Fahad Shahbaz Khan, Mariana-luliant Georgescu, and Ling Shao. Object- centric auto-encoders and dummy anomalies for abnormal event detection in video. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7842-7851, 2019.
JooSeuk Kim and Clayton D Scott. Robust kernel density estimation. The Journal of Machine Learning Research, (3(1):2529-256) 2012.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988. 2014.
Diederik Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible Ixl convolutions. arXiv preprint arXiv: 2018.
10

---

Published as a conference paper at ICLR 2022
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In ICML, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- 2016.
works. arXiv preprint arXiv;
Ravi Kiran, Dilip Mathew Thomas, and Ranjith Parakkal. An overview of deep learning based methods for unsupervised and semi-supervised anomaly detection in videos. Journal of Imaging, 4(2):36, 2018.
Dan Li, Dacheng Chen, Jonathan Goh, and See-kiong Ng. Anomaly detection with generative adversarial networks for multivariate time series, arXiv preprint arXiv:1809.04755 2018a.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net-
work: Data-driven traffic forecasting. In ICLR, 2018b.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. 2019.
arXiv preprint
Pankaj Malhotra, Anusha Ramakrishnan, Gaurangi Anand, Lovekesh Vig, Puneet Agarwal, and
Gautam Shroff. Lstm-based encoder-decoder for multi-sensor anomaly detection. arXiv preprint 1rXiv:1607.0014 2016.
Duc Tam Nguyen, Zhongyu Lou, Michael Klar, and Thomas Brox. Anomaly detection with multiple-hypotheses predictions. In International Conference on Machine Learning, pp. 4800- 4809. PMLR, 2019.
George Papamakarios, Theo Pavlakou, and Iain Murray. Masked autoregressive flow for density estimation. arXiv preprint arXiv: 2017.
Emanuel Parzen. On estimation of a probability density function and mode. The annals of mathe- matical statistics, 33(3):1065-1076, 1962.
Judea Pearl, Bayesian networks: model of self-activated memory for evidential reasoning. In Proceedings of the 7th Conference of the Cognitive Science Society, 1985.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000.
Marco AF Pimentel, David A Clifton, Lei Clifton, and Lionel Tarassenko. A review of novelty detection. Signal Processing, 99:215-249 2014.
Kashif Rasul, Abdul-Saboor Sheikh, Ingmar Schuster, Urs Bergmann, and Roland Vollgraf. Multi- variate probabilistic time series forecasting via conditioned normalizing flows. In ICLR, 2021.
Riya Roy and K Thomas George. Detecting insurance claims fraud using machine learning tech- niques. In 2017 International Conference Circuit, Power and Computing Technologies (IC- CPCT), pp. 1-6. IEEE, 2017.
Lukas Ruff, Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexan- der Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In International conference on machine learning, pp. 4393-4400 PMLR, 2018
Lukas Ruff, Robert A. Vandermeulen, Nico Gömitz, Alexander Binder, Emmanuel Müller, Klaus- Robert Müller, and Marius Kloft. Deep sumi-super anomaly detection. In International Conference Learning Representations, 2020. URL /tIl/httpps:/oppeeevieeee net/ www.ti/oroeeemmeem forum?
id Hd=kgHHOTEYWH
Mohammad Sabokrou, Mohammad Khalooci, Mahmood Fathy, and Ehsan Adeli. Adversarially learned one-class classifier for novelty detection. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3379-3388, 2018
Mohammad Sabokrou, Mahmood Fathy, Guoying Zhao, and Ehsan Adeli. Deep end-to-end one- class classifier. IEEE transactions on neural networks and learning systems, 32(2):675-684, 2020.
11

---

Published as a conference paper at ICLR 2022
Bernhard Schölkopf. John C Platt, John Shawe-Taylor, Alex J Smola, and Robert C Williamson. Estimating the support a high-dimensional distribution. Neural computation, 13(7):143314471, 2001.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. arXiv:1612.07659 2016.
Chao Shang, Jie Chen, and Jinbo Bi. Discrete graph structure learning for forecasting multiple time series. In ICLR, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Peng Wu, Jing Liu, and Fang Shen. A deep one-class neural network for anomalous event detection in complex scenes. IEEE transactions on neural networks and learning systems, 31(7):2609- 2622, 2019.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang. Con- necting the dots: Multivariate time series forecasting with graph neural networks. KDD, 2020.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In ICCAI, 2018.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: DAG structure learning with graph neural networks. In ICML, 2019.
Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. T-GCN: temporal graph convolutional network for traffic prediction. IEEE Transactions on Intelligent Transportation Systems, 2019.
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. DAGs with NO TEARS: Con- tinuous optimization for structure learning. NeurlPS, 2018
12

---

Published as a conference paper at ICLR 2022
A TRAINING ALGORITHM
We summarize the training method in Algorithm
Algorithm Training Algorithm GANF
Input: Training set D, hyperparameters 1/ and 7/ Output: GANF F and adjacency matrix A of the DAG
1: Initialize с + and initialize randomly
2: for k = 2........ do
3:
Compute A and 0 as minimizer of (12) by using the Adam optimizer, where the loss
L and the constraint h are defined in (11), the log-density log p(X)( is defined in (10), the
dependency representation dj is defined in (8. the hidden state h is defined in 77. and the conditional flow f is RealNVP or MAF
4:
Update Lagrange multiplier +- + ch(AA)
5: if l > 0 and [h{ A 7 [M 1-1) then
6:
7:
end if
8:
if (A = then
9:
break
10: end
11:
end for
12: return A and F (including f, the neural network (8) and the RNN
B CODE
Code is available /ttttess//gttttb..mm//nnnn
C ADDITIONAL DETAILS OF EXPERIMENT SETTINGS
C.I IMPLEMENTATION DETAILS OF GANF,
An LSTM is used the RNN model in the dependency encoder. For normalizing flows, MAF with six flow blocks. All hidden dimensions as set as 32. The initial learning rate is set as 0.001 for the adjacency matrix A and the model parameters O. Learning rate decay 0.1. To avoid gradient explosion, we clip the gradients whose values are larger than 1.0.
For hyperparameter tuning, we select the hyperparameters that yield the highest log-density on the validation set. Specifically, we conduct grid search by varying the number of normalizing flow blocks from {1, 2, 4, 6, 8), the learning rate from (0.003, 0.001, 0.0003, 0.0001}, and the hidden dimension from {16, 32, 64, 128].
C.2 IMPLEMENTATION DETAILS OF BASELINES.
EneDecAD (Malhotra et al. 2016): This method is applied for anomaly detection on time series. Thus, concatenate constituent series along the attribute dimension and adopt the code released by the authors in hhttps://github.com com/ http://aw.ccomcccccceeeeettttt.. http:/cciicebbs...eer....
RNN-Time- serineee-eeiss-ee Sateriiessnnmmmlll
DeepSVDD Ruff et al. 2018): To handle time series data, we replace the backbone an LSTM based on the official implementation
Deep-SVDD-PyTorel
ALOCC (Sabokrou et al. 2020): We use the official implementation released by the authors in /ettps:/ggithe com/ kha ooe /ALOCC- CVPR2018 We replace the two-dimensional
convolution to one-dimensional convolution to build a GAN for time series data.
DROCC (Goyal al. 2020:: Similar to other baselines, this method is proposed for tabular data and image data. We replace the backbone to LSTM to deal with multiple time series by revising the encoder in https: //tpthub..tt//t/// thub.
httpssfffttt/e/////// CreeeeeeeMMeeeeeeeeeeeeeeee matee/man www.ee/amaateeetttoreeeeoe
DeepSAD (Rfff et al. 2020): This is semi-supervised approach, which requires labeling.
We utilize the noisy labels in PMU-B and PMU-C supervision. We LSTM the
13

---

Published as a conference paper at ICLR 2022
backbone, based the official implementation in https:///otaab..cmm//ukkuce Deep- Pyy--
All hyperparameters of the baselines are tuned based the validation set make fair comparisons.
D TIME COMPLEXITY ANALYSIS
The GANF framework involves Bayesian network structure learning, which is known to be highly challenging, owing to the intractable search space superexponential in the number of graph nodes. In this work, we formulate continuous optimization of the graph structure, so that the training of GANF is more scalable. In what follows, we analyze the time complexity.
Recall that each instance X' of the multiple time series dataset contains n constituent series with D attributes and of length T; i.e., X' = (X' .X?..... X") where X RT*D, In the evaluation of the model, the dominant costs appear in running the dependency encoder and the normalizing flow. For the dependency encoder, an RNN is first deployed to map the multiple time series to hidden vectors; the time complexity (nT Then, graph convolution conducted to obtain dependency vectors; the convolution cost is Onn²T). For the normalizing flow module, the time complexity is On. Therefore, the time complexity of computing log-density of one instance is O(n((D n.).. If we a batch size B for training, the time cost of calculating the augmented Lagrangian L(A. 0) in (12) is (nBBT (D + n)). Additionally, the time cost of calculating the
constraint h (A) is (n²)). Thus, the overall time complexity of one training iteration is BTn + ))
E RESULTS FOR METR-LA
METR-LA contains speed records of 207 sensors deployed on the highways of Los Angles, CA al. 2018b). The records are four months the frequency of five minutes. We shift one-hour window to obtain multiple time series. The first three months are used for training and the last month split in halves for validation and testing. No anomaly labels exist however and we use this dataset for exploratory analysis only.
Speed (mi/h)
(dgndenstty)
30.3
29.9
Road
Road
29.5
Road
29.1
12 16
20
24
4
16 Time
12
20
Time
(a) Average speed of the main roads.
(b) Estimated log-density.
Figure 6: Density estimation for METR-LA.
Figure ba| shows the traffic speed on four main highways on June 13, 2012. Each speed is the average over all sensors on the same highway. We observe that despite spatial proximity, the speeds vary significantly around 4PM (rush hour) but they are unanimously high around 5AM and 8PM- 12AM. The estimated densities, shown in Figure 6b] tracks this pattern rather closely, with rush hours corresponding to low density and night traffics corresponding to high density. Note the nature of traffic: speed varies smoothly the macroscopic level and hence does density, too. Such phenomenon is in striking contrast to power systems where events are rare and abrupt.
14

---

Published as a conference paper at ICLR 2022
F ADDITIONAL ANOMALY DETECTION RESULTS ON PMU DATASETS
See Figure 7 and Figure S for additional anomaly detection results on the test sets of PMU-C and PMU-B, respectively. The observations are rather similar to those of Figure 3b
Anormalyy Mcasure
18
Labeled Anomaly
Score of Timestamp
16
15
2017-11-10
2017-11-12
2017-11-14
Time
Anormaly Measure
18
Labeled Anomaly
Score of Timestamp
16
2017-11-15
2017-11-17
2017-11-19
2017-11-21
Time
Figure 7: Additional anomaly detection results on the test set of PMU-C.
Anormaly Measure
18
Labeled Anomaly
Score of Timesamp
14
12
2016-12-00
2016-12-05
2016-12-07
2016-12-09
Time
Anormaly Measure
18
Labeled bed Anomaly
Score of Timeslamp
14
12
2016-12-11
2016-12-12
2016-12-14
2016-12-16
Time
Anormaly Measure
18
Labeled Anomaly
Score of Timestamp
16
14
12
2016-12-16
2016-12-18
2016 12-20
2016-12-22
Time
Figure 8: Anomaly detection results on the test set PMU-B.
15

---

Published as a conference paper at ICLR 2022
G ADDITIONAL RESULTS FOR DAG EVOLUTION
(a) Four-month shift
(b) Five-month shift
(c) Six-month shift
(d) Seven-month shift
(c) Fight-month shift
(f) Nine-month shift
(g) Ten-month shift
(h) Eleven-month shift
Figure 9: Evolution of the learned DAG on PMU-B over time.
16


Reviews:
[{"review_id": "yF6uIHhkDN", "reviewer": "Reviewer_ofqA", "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": "## Strength\n\nThe problem of anomaly detection from multivariate time series is relevant. In particular, anomaly detection in a fully unsupervised manner is technically challenging and an important research topic. Many existing methods (implicitly) assume availability of partial supervised information, such as normal profile, even if they are said to be unsupervised, while we cannot often assume such a situation in practice.\n\n## Weakness\n\nThis paper is overall not well-written, and there are several concerns regarding presentation, quality and evaluation.\n\n- First, I cannot understand the problem setting. The authors say that a give dataset is $(\\mathbf{X}^1, ..., \\mathbf{X}^n)$, and each $\\mathbf{X}^i \\in \\mathbb{R}^{T \\times D}$. In the typical setting of multivariate time series, there are $D$ each time series, and the length (the number of time stamps) of each time series is $T$. Then a given dataset can be treated as a single matrix $X \\in \\mathbb{R}^{T \\times D}$. Therefore it is not clear why there are $n$ such matrices in the problem setting introduced in this paper? What is each $i$ here? Moreover, it is said that there are $|\\mathcal{D}|$ such $(\\mathbf{X}^1, ..., \\mathbf{X}^n)$ as a dataset. Since repeated sampling is fundamentally impossible in time series analysis, it is also not clear what does such a dataset mean. In addition, the authors assume a DAG structure over such indices from 1 to $n$ ($n$ variables?), while its interpretation is also not clear. Please note that it makes sense if a DAG structure exists over $D$ time series or $T$ time stamps, while the setting in this paper is different.\n\n- I am also confused with the anomaly measure. It is defined for each $\\mathbf{X}^i$ as explained in Sec.5.2. However, the goal of anomaly detection for time series is usually to find anomalous regions of time stamps, and it seems that this task is actually considered in experiments (in Fig. 2b). Since the proposed measure cannot directly achieve the task, some clarification is required.\n\n- There are also concerns regarding the experimental protocol. The authors say that a dataset is divided into training/validation/test sets. However, since the problem is unsupervised, such separation does not make sense, and one can just use the entire dataset excluding the ground truth labels for training and evaluate the prediction performance using the ground truth.\n\n- Parameter sensitivity is not examined in experiments. Since parameter tuning is fundamentally difficult in unsupervised learning (as one cannot use CV), at least the sensitivity should be examined, otherwise it is not clear how the obtained results are useful and robust w.r.t. parameter changes. \n\n- Figure 4 has almost no information in its current state. Illustration should be improved.\n", "summary_of_the_paper": "This paper proposes to combine learning of the DAG structure between variables and learning of distribution using normalizing flows for unsupervised anomaly detection from multivariate time series. Once the distribution is learned, one can detect anomalies as low density regions. The effectiveness of the proposed method is empirically evaluated on real-world datasets.", "summary_of_the_review": "Although this paper studies a relevant problem, the quality, presentation, and evaluation of this paper are not convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "tNUlrNAvW6x", "reviewer": "Reviewer_J4SV", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n- Good solution to a problem that has applications in many diverse areas\n- Authors model correlations between time series, which is often ignored in multivariate time series work\n- Authors effectively integrate mature components from a variety of different subfields in statistics, representation learning, and neural networks\n- Despite all the different moving parts, the model is clearly explained\n- Authors evaluate their methods in relevant datasets\n\nWeaknesses:\n- It is not clear how to quantitatively select the threshold for flagging something as an anomaly\n- The chosen evaluation metric is difficult to interpret\n- No discussion on scalability\n\nExtended comments:\nI found the presented model to be quite interested, and I believe that it addresses some of the weaknesses of existing anomaly detection methods in novel ways. Particularly, I believe that combining a Bayesian network with and RNN to jointly learn dependencies across time and constituencies adds great value to multivariate time series modeling. The fact that the model is able to learn the structure of the Bayesian network as a continuous optimization problem is quite advantageous as well.\n\nI was also quite pleased with the presentation of the paper. Despite the fact that the authors are combining components from various ML and statistics subfields, the description is easy to follow.\n\nWhere I think the paper could improve is in the Experiments section. I understand that there is noise in ground truth labeling in anomaly detection datasets; however, the proposed evaluation metric to address this source of noise is difficult to interpret and frankly seems to be an afterthought. I would prefer to see a \"hard\" label; the authors could declare an anomaly as \"successfully detected\" if it falls within some time window of the prediction, where the size of that time window is application-specific.\n\nAnother weakness of the paper is on selecting the threshold to flag something as an anomaly. This is not a weakness specific to the paper, and potential solutions have been studied before. I think it would strengthen the paper if the authors propose heuristics to numerically choose a threshold, without having to pick and choose from a histogram (which is very subjective). Since there is a Gaussian distribution at the end of the model, would it be possible to say that an observation is anomalous if the probability of seeing such extreme values is less than 0.05 (or some other threshold)?\n\nFinally, I would say that the ablation study is inconclusive. There is a marginal increase in performance; however, couldn't this be explained merely by the fact that GANF has more parameters (and hence more expressibility) than the models where you take out one of the components?", "summary_of_the_paper": "The authors propose a model for anomaly detection on multivariate, high-dimensional time series data, where there are statistical dependencies across the different time series (referred to as \"constituents\" in the paper). The authors model statistical dependence using a Bayesian network and temporal dependence using an RNN. One key feature of the proposed model is that it simultaneously learns the structure of the Bayesian network AND a representation of the temporal state. The authors combine these two representations, which then gets used as input to a normalized flow technique, which makes computation of the likelihood of the data mathematically and computationally feasible.\n\nThe authors show that the proposed model has improved performance for the anomaly detection task compared to recently-proposed neural-network anomaly detection methods.", "summary_of_the_review": "Given my comments above, I think that there are enough strong points in the paper to put it above the acceptance threshold. I am open to being more optimistic about it after the author response.", "strength_and_weaknesses": "", "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": "UbLN_Kv0Xs", "reviewer": "Reviewer_mBgF", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I liked this paper and read it with great interest. The strength of this paper rests in a) an excellent problem setup, and b) well chosen methods that address real challenges in the field and provide useful insights into problems. The paper does not make unrealistic assumptions. The evaluation datasets are well chosen and the baselines do not seem like \"strawman\" comparisons. \n\nI am particularly impressed with Figure 4. Finding the temporal shifts for anomalies, in particular anomalies that develop slowly is a valuable contribution, and being able to quantify that with with a Bayesian graph is a novel contribution that deserves to be called out. Overall, I would be interested to hear more about the explainable side of this work - Bayesian networks are often useful for counterfactual reasoning which makes me optimistic that these methods are not only useful for detecting anomalies, but also potentially explainable. \n\nThere are some places where I think the evaluation could be improved. ROC-AUC is useful real-valued metric, but in practice, there are always questions about the choice of threshold and inclusion of of some ROC curves, along with uncertianty bounds on those curves would make this work even stronger.\n\nThis paper also suffers from complexity and I somewhat question its reproducability. I don't doubt the numerical results, but with a complex system such as this one, there would need to be a significant investment of effort if anyone else wanted to use these methods and I don't think sufficient details are provided in . Providing a code repository would address this. \n\nIf I have a major complaint about this paper it is that their main hypothesis: \"Anomalies lie on low density regions of the data distribution\" remains untested. ", "summary_of_the_paper": "This paper focuses on unsupervised anomaly detection in multivariate time series. This is a important problem because anomalies are rare and labeling anomalies for supervised learning is labor intensive. To make progress in this challenging domain, they  use learned graph structure and normalizing flows, which seem well suited for the task. They evaluate their methods on multiple datasets, and compare against multiple modern deep networks. ", "summary_of_the_review": "This is a strong paper and I recommend it for acceptance. It addresses a real problem in a manner that is both novel and pragmatic. I hope the authors will not take my constructive criticism too harshly, the paper is strong in its current form and my suggested improvements are only suggestions for ways I think it could be made even stronger. I would love to see this work see application in other areas and my comments reflect ways to speed that process. ", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MpI0kCsazZB", "reviewer": "Reviewer_tq1S", "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": "Strengths of the paper:\n(1) The paper is clearly written and describes a novel technique. The combination of the DAG and the normalizing flow is a very interesting approach, and the application to the multiple time-series anomaly detection problem is a novel contribution. \n\n(2) For the analyzed dataset, the proposed method appears to significantly outperform the baselines. \n\n(3) The authors provide an ablation study to demonstrate that all of the components of the algorithm contribute to the improved performance.\n \nWeaknesses of the paper:\n(1) The quantitative results are only derived for one dataset (which is unfortunately proprietary). The labels for this dataset are noisy, making the significance of the results more difficult to assess. The experiments on the traffic dataset seem incomplete and it is difficult to conclude much from them. \n\n(2) There are no measures of variability or confidence intervals for the provided results. There are no tests to determine if the performance differences are statistically significant. The authors calculate AUC-ROCs, but do not display the ROCs, meaning that the comparison to baselines boils down to a single number. \n\n(3) The absence of synthetic data or well-understood data means that it is difficult to determine whether the derived DAGs are meaningful.  \n\nMAIN REVIEW\n\nThe paper addresses a very interesting and challenging problem and provides an elegant and intriguing solution. The combination of the RNN, the DAG to capture the dependency structure, and the normalizing flow appears to be a promising way to represent multiple time-series. The experimental results suggest that the joint learning, with enforcement of an acyclic graph, can lead to better performance. \n\nMethodologically, I think the paper presents a novel, technically sound, and well-motivated approach. There have been some recent approaches in the multivariate time-series forecasting literature to combine latent representations and normalizing flow, but I am unaware of any work that incorporates a DAG in a similar way. \n\nThe experiments are the weaker portion of the paper.\n\n(1) I think the paper would have benefited significantly from the inclusion of an analysis of synthetic data. With control over the ground truth, the performance of the algorithm could be explored and better understood. In particular, one could assess how well the DAGs are being estimated. \n\n(2) In the absence of synthetic dataset, the experiments would be considerably more compelling if more datasets were analyzed (preferably with at least one public dataset). \n\n(3) It is highly desirable that some form of confidence interval (or alternative measure of variability) is provided for the obtained performance. Statistical significance tests should also be conducted. \n\n(4) Compressing the performance metrics to a single number is undesirable. I would have been very interested to see a comparison of the actual estimated ROCs. Often the AUC can give a misleading picture because one is more interested in relative performance in the low false-alarm regime. Figures such as 2(b) are very useful, but the paper does not provide the equivalent figures for any baseline algorithms, making comparison difficult.\n\n(5) More details about hyperparameter tuning process would be welcome. The statement “The hyperparameters are all tuned based on the log-density on the validation set” is not sufficient to reproduce the results unless it is clear which hyperparameters were tuned, how they were tuned and over what ranges. For example, it is not clear if all architectural choices are included (hidden dimensions, number of flow blocks) \n\n(6) The experiments for the traffic data seem incomplete, and it is difficult to draw much of a conclusion from them. \n\nQuestions:\n\n(1) Is it possible to provide some form of measure of the variability in the results, e.g. bootstrapped confidence intervals?\n\n(2) Some of the forecasting architectures come closer to having an A matrix that is applied to previous states, i.e. AH_{t-1} W_2. With this form there is no need to enforce a DAG structure, but predictive relationships are learned. There may also be sparsity encouragement during the training process. I thought this form might be one of the ablation studies to demonstrate the importance of the modeling of contemporaneous dependencies, but my understanding was that the two ablation cases investigating alternative dependencies were different from this approach. Could you comment – do you have insight into the importance of learning a contemporaneous as opposed to a predictive A? Please clarify if my understanding of one of the ablation settings is wrong. \n", "summary_of_the_paper": "The paper addresses the task of detecting anomalies in multiple time-series, for the setting where multiple instances of a fixed time-window are available for learning. The authors propose a method that involves using a directed acyclic graph (DAG) to model the (contemporaneous) dependencies between the variables in the time-series. An RNN is applied to form a representative state for each time-series at each point in time. A mapping is applied using the DAG to process the states from the previous time-step and the ancestor states from the current time-step to construct a “dependency representation” vector for each time series. A normalizing flow is then applied to map to a base distribution so that the log-density of the instance (the observed multiple time-series) can be evaluated. The conditional densities for each time series can also be evaluated. The paper includes an evaluation of the performance of the approach on a proprietary dataset, with a comparison to state-of-the-art baselines. Some qualitative results are also included for the task of density estimation for a public traffic dataset. ", "summary_of_the_review": "** After the authors' response and the improvements to the paper, I have changed the score to a \"6\"; marginally above the acceptance threshold. \n\n-----------------------------------------------------\nI have recommended “marginally below the acceptance threshold”. \n\n\nI like the methodology that is presented in the paper, but I think there is a need for more extensive experimentation. Synthetic data would provided a much more controlled testing environment. An examination over more datasets would provide more compelling evidence that the proposed method is advantageous, and perhaps highlight the types of problems where the approach provides a major benefit, as opposed to those where it offers a less significant improvement (or is perhaps even detrimental due to its flexibility). More details concerning the experimental methodology are required. Results that provide a more detailed comparison between the proposed methods and baselines would be helpful (some figures rather than just a single number). Measures of variability in the results and statistical significance tests would be beneficial in understanding how dramatic an improvement has been made.  \n", "strength_and_weaknesses": "", "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": "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": {}}]

Author rebuttal:

Meta-review: The paper tackles the problem of detecting anomalies in multiple time-series. All the reviewers agreed that the methodology is novel, sound and very interesting. Initially, there were some concerns regarding the experimental evaluation, however, the rebuttal and subsequent discussion cleared up these concerns to some extent and all reviewers are eventually supporting or strongly supporting acceptance.
Decision: Accept (Spotlight)