Correlation-aware Deep Generative Model for Unsupervised Anomaly Detection

To explore the correlation among non-structure data samples for feature learning, we explicitly construct a graph structure to correlate the similar samples from the feature space. More specifically, given a set of input samples $\boldsymbol{\mathcal{X}}=\{x_{i}|i=1,...,N\}$, we employ $K$-NN algorithm on sample $x_{i}$ to determine its $K$ nearest neighbors $\boldsymbol{\mathcal{N}}_{i}=\{x_{i_{k}}|k=1,...,K\}$ in the feature space. Then, an undirected edge is assigned between $x_{i}$ and its neighbor $x_{i_{k}}$. Finally, an undirected graph $\boldsymbol{\mathcal{G}}=\{\boldsymbol{\mathcal{V}},\boldsymbol{\mathcal{E}},\boldsymbol{\mathrm{X}}\}$ is constructed, with $\boldsymbol{\mathcal{V}}=\{v_{i}=x_{i}|i=1,...,N\}$ being the node set, $\boldsymbol{\mathcal{E}}=\{e_{i_{k}}=(v_{i},v_{i_{k}})|v_{i_{k}}\in\boldsymbol{\mathcal{N}}_{i}\}$ being the edge set, and $\boldsymbol{\mathrm{X}}\in\mathbb{R}^{N\times F}$ being the feature matrix of nodes. Based on the constructed graph, the feature affinities among samples are captured explicitly, which can be used during feature learning by performing message propagation mechanism on them.

In order to obtain sufficient representative high-level sample embedding, Dual-Encoder consists of a feature encoder and a graph encoder to encode the original feature of samples and the correlation among them respectively.

To encode the original sample features $\boldsymbol{\mathrm{X}}$, feature encoder employs a $L_{\mathrm{X}}$ layers Multi-Layer Perceptron (MLP) to conduct a non-linear feature transform, which is as follows:

where $\textbf{Z}^{\boldsymbol{\mathrm{X}}(l_{\mathrm{X}}-1)}$, $\textbf{Z}^{\boldsymbol{\mathrm{X}}(l_{\mathrm{X}})}$, $\textbf{W}^{\boldsymbol{\mathrm{X}}(l_{\mathrm{X}}-1)}$ and $\textbf{b}^{\boldsymbol{\mathrm{X}}(l_{\mathrm{X}}-1)}$ are the input, output, the trainable weight and bias matrix of ($l_{\mathrm{X}}$-$1$)-th layer respectively, $l_{\mathrm{X}}\in\{1,2,...,L_{\mathrm{X}}\}$, and $\textbf{Z}^{\boldsymbol{\mathrm{X}}(0)}=\textbf{X}$ is the initial input of the encoder. $\sigma(\bullet)$ denotes an activation function such as ReLU or Tanh. Finally, the final feature embedding $\textbf{Z}^{\boldsymbol{\mathrm{X}}}$=$\textbf{Z}^{\boldsymbol{\mathrm{X}}(L_{\mathrm{X}})}$ is obtained from the output of the last layer in MLP.

To encode the correlation among the samples, a graph attention layer [16] is employed to adaptively aggregate the representation from neighbor nodes, by performing a shared attentional mechanism on the nodes:

where $w_{i,j}$ indicates the importance weight of node $\boldsymbol{v}_{i}$ to node $\boldsymbol{v}_{j}$, $attn(\bullet)$ denotes the neural network parametrized by weights $\textbf{a}\in\mathbb{R}^{D^{c}}$ and $\boldsymbol{\mathrm{W}}^{c}\in\mathbb{R}^{\frac{D^{c}}{2}\times F}$ that shared by all nodes and $D^{c}$ is the number of hidden neurons in $attn(\bullet)$, $||$ denotes the concatenate operation. Then, the final importance weight $\alpha_{i,j}$ is normalized through the softmax function:

where $\boldsymbol{\mathcal{N}_{i}}$ denotes the neighbors of node $\boldsymbol{v}_{i}$, which is provided by adjacency matrix $\boldsymbol{\mathrm{A}}$, and the final node embedding $\boldsymbol{{\mathrm{Z}}^{\mathcal{V}}}=\{\boldsymbol{{\mathrm{Z}}_{i}^{\mathcal{V}}}\}$ can be obtained by the weighted sum based on the learned importance weights as follows:

Given the learned embedding $\textbf{Z}^{\boldsymbol{\mathrm{X}}}$ and $\boldsymbol{{\mathrm{Z}}^{\mathcal{V}}}$, a fusion module is designed to fuse the embeddings from heterogeneous data source into a shared latent space, followed by a fully connected layer to obtain the final sample embedding $\textbf{Z}^{f}\in\mathbb{R}^{N\times D}$:

where W and b are the trainable weight and bias matrix, and $\oplus$ indicates the element-wise plus operator of two matrices.

Feature decoder aims at reconstructing the sample features from the latent embedding $\textbf{Z}^{f}$:

where $\textbf{Z}^{\boldsymbol{\hat{\mathrm{X}}}(l_{\hat{\mathrm{X}}}-1)}$, $\textbf{Z}^{\boldsymbol{\hat{\mathrm{X}}}(l_{\hat{\mathrm{X}}})}$, $\textbf{W}^{\boldsymbol{\hat{\mathrm{X}}}(l_{\hat{\mathrm{X}}}-1)}$ and $\textbf{b}^{\boldsymbol{\hat{\mathrm{X}}}(l_{\hat{\mathrm{X}}}-1)}$ are the input, output, the trainable weight and bias matrix of ($l_{\hat{\mathrm{X}}}$-$1$)-th layer of decoder respectively, $l_{\hat{\mathrm{X}}}\in\{1,2,...,L_{\hat{\mathrm{X}}}\}$, and $\textbf{Z}^{\boldsymbol{\hat{\mathrm{X}}}(0)}=\textbf{Z}^{f}$ is the initial input of the decoder. Finally, the reconstruction $\boldsymbol{\hat{\mathrm{X}}}$ is obtained from the last layer of decoder:

To estimate the density of the input samples, a Gaussian Mixture Model is leveraged in CADGMM over the learned latent embedding. Inspired by DAGMM [23], a sub-network consists of several fully connected layers is utilized, which takes the reconstruction error preserved low-dimentional embedding as input, to estimate the mixture membership for each sample. The reconstruction error preserved low-dimentional embedding Z is obtained as follows:

where $\textbf{Z}^{r}$ is the reconstruction error embedding and $\text{Dist}(\bullet)$ denotes the distance metric such as Euclidean distance or cosine distance. Given the final embedding Z as input, estimate network conducts membership prediction as follows:

where $\textbf{Z}^{\boldsymbol{\mathcal{M}}(l_{\mathcal{M}}-1)}$, $\textbf{Z}^{\boldsymbol{\mathcal{M}}(l_{\mathcal{M}})}$, $\textbf{W}^{\boldsymbol{\mathcal{M}}(l_{\mathcal{M}}-1)}$ and $\textbf{b}^{\boldsymbol{\mathcal{M}}(l_{\mathcal{M}}-1)}$ are the input, output, the trainable weight and bias matrix of ($l_{\mathcal{M}}$-$1$)-th layer of estimate network respectively, $l_{\mathcal{M}}\in\{1,2,...,L_{\mathcal{M}}\}$, $\textbf{Z}^{\boldsymbol{\mathcal{M}}(0)}=\textbf{Z}$, and the mixture-component membership $\boldsymbol{\mathcal{M}}$ is calculated by:

where $\boldsymbol{\mathcal{M}}\in\mathbb{R}^{N\times M}$ is the predicted membership of $M$ mixture components for $N$ samples. With the predicted sample membership, the parameters of GMM can be calculated to facilitate the evaluation of the energy/likelihood of input samples, which is as follows:

where $\boldsymbol{\mu_{m}}$ and $\boldsymbol{\Sigma}_{m}$ are the means and covariance of the $m$-th component distribution respectively, and the energy of samples is as follows:

where $|\bullet|$ indicates the determinant of a matrix.

The training objective of CADGMM is defined as follows:

where the first term is reconstruction error used for feature reconstruction, the second is sample energy, which aims to maximize the likelihood to observed samples, the third is covariance penalization, used for solving singularity problem as in GMM [23] by penalizing small values on the diagonal entries of covariance matrix, and the last is embedding penalization, which serves as a regularizer to impose the magnitude of normal samples as small as possible in the latent space, to deviate the normal samples from the abnormal ones. $\lambda_{1}$, $\lambda_{2}$, and $\lambda_{3}$ are three parameters which control the trade off between different terms.

The anomaly score is the sample energy $E_{\textbf{Z}}$, and based on the measured anomaly scores, the threshold $\lambda$ in Eq. 1 can be determined according to the distribution of scores, e.g. the samples of top-k scores are classified as anomalous samples.

Three benchmark datasets are used in this paper to evaluate the proposed method, including KDD99, Arrhythmia, and Satellite. The statistics of datasets are shown in Table 1.

• •

  KDD99 The KDD99 10 percent dataset [2] contains 494021 samples with 41 dimensional features, where 34 of them are continuous and 7 are categorical. One-hot representation is used to encode the categorical features, resulting in a 120-dimensional feature for each sample.

• •

  Arrhythmia The Arrhythmia dataset [2] contains 452 samples with 274 dimensional features. We combine the smallest classes including 3, 4, 5, 7, 8, 9, 14, 15 to form the outlier class and the rest of the classes are inliers class.

• •

  Satellite The Satellite dataset [2] has 6435 samples with 36 dimensional features. The smallest three classes including 2,4,5 are combined to form the outliers and the rest are inliers classes.

• •

  One Class Support Vector Machines (OC-SVM) [4] is a classic kernel method for anomaly detection, which learns a decision boundary between the inliers and outliers.

• •

  Isolation Forests (IF) [8] conducts anomaly detection by building trees using randomly selected split values across sample features, and defining the anomaly score as the average path length from a specific sample to the root.

• •

  Deep Structured Energy Based Models (DSEBM) [21] is a deep energy-based model, which aims to accumulate the energy across the layers. DSEBM-r and DSEBM-e are utilized in [21] by taking the energy and reconstruction error as the anomaly score respectively.

• •

  Deep Autoencoding Gaussian Mixture Model (DAGMM) [23] is an autoencoder based method for anomaly detection, which consists of a compression network for dimension reduction, and an estimate network to perform density estimation under the Gaussian Mixture Model.

• •

  AnoGAN [13] is an anomaly detection algorithm based on GAN, which trains a DCGAN [12] to recover the representation of each data sample in the latent space during prediction.

• •

  ALAD [20] is based on bi-directional GANs for anomaly detection by deriving adversarially learned features and uses reconstruction errors based on the learned features to determine if a data sample is anomalous.

The parameter settings in the experiment for different datasets are as follows:

• •

  KDD99 For KDD99, CADGMM is trained with 300 iterations and $N$=1024 for graph construction with $K$=15, which is the batch size for training. $M$=4, $\lambda_{1}$=0.1, $\lambda_{2}$=0.005, $\lambda_{3}$=10.

• •

  Arrhythmia For Arrhythmia, CADGMM is trained with 20000 iterations and $N$=128 for graph construction with $K$=5, which is the batch size for training, $M$=2, $\lambda_{1}$=0.1, $\lambda_{2}$=0.005, $\lambda_{3}$=0.001.

• •

  Satellite For Satellite, CADGMM is trained with 3000 iterations and $N$=512 for graph construction with $K$=13, $M$=4, $\lambda_{1}$=0.1, $\lambda_{2}$=0.005, $\lambda_{3}$=0.005.

The architecture details of CADGMM on different datasets are shown in Table 2, in which, $\text{FC}(D_{in},D_{out})$ means a fully connected layer with $D_{in}$ input neurons and $D_{out}$ output neurons. Similarly, $\text{GAT}(D_{in},D_{out})$ means a graph attention layer with $D_{in}$-dimensional input and $D_{out}$-dimensional output. The activation function $\sigma(\bullet)$ for all datasets is set as Tanh. For the baseline methods, we set the parameters by grid search. We independently run each experiment 10 times and the mean values are reported as the final results.

As in previous literatures [21, 23, 20], in this paper, Precision, Recall and F1 score are employed as the evaluation metrics. Generally, we expect the values of these evaluation metrics as big as possible. The sample with high energy is classified as abnormal and the threshold is determined based on the ratio of anomalies in the dataset. Following the settings in [21, 23], the training and test sets are split by 1:1 and only normal samples are used for training the model.

The experimental results shown in Table 3 demonstrate that the proposed CADGMM significantly outperforms all baselines in various datasets. The performance of CADGMM is much higher than traditional anomaly detection methods such as OC-SVM and IF, because of the limited capability of feature learning or the curse of dimensionality. Moreover, CADGMM also significantly outperforms all other deep learning based methods such as DSEBM, DAGMM, AnoGAN, and ALAD, which demonstrates that additional correlation among data samples facilitates the feature learning for anomaly detection. For small datasets such as Arrhythmia, we can find that traditional methods such as IF are competitive compared with conventional deep learning based method such as DSEBM, DAGMM, AnoGAN, and ALAD, which might because that the lack of sufficient training data could have resulted in poorer performance of the data hungry deep learning based methods, while CADGMM is capable of leveraging more data power given the limited data source, by considering the correlation among data samples.

In this section, we study the impact of noise data for the training of CADGMM. To be specific, 50% of randomly split data samples are used for testing, while the rest 50% combined with 1% to 5% anomalies are used for training.

As shown in Table 4, with the increase of noise data, the performance of all baselines degrade significantly, especially for OC-SVM, which tends to be more sensitive to noise data because of its poor ability of feature learning on high-dimensional data. However, CADGMM performs stable with different ratios of noise and achieves state-of-the-art even 5% anomalies are injected into the training data, which demonstrates the robustness of the proposed method.

In this section, we evaluate the impact of different $K$ values during the graph construction on CADGMM.

More specifically, we conduct experiments on all three datasets by varying the number of $K$ from 5 to 19, and the experimental results are illustrated in Fig. 3. During training, the batch sizes are set as 1024, 128, and 512 for KDD99, Arrhythmia, and Satellite, respectively, the experimental results show that the changing of $K$ value causes only a little fluctuation of performance on all datasets with different settings, which demonstrates that CADGMM is less sensitive to the $K$ value and easy to use.

In order to explore the quality of the learned embedding, we make a comparison of the visualization of sample representation for different methods in Fig. 4. Specifically, we take the low-dimensional embeddings of samples learned by DAGMM and CADGMM, as the inputs to the t-SNE tool [9]. Here, we randomly choose 40000 data samples from the test set of KDD99 for visualization, and then we generate visualizations of the sample embedding on a two-dimensional space, in which blue colors correspond to the normal class while orange the abnormal class. We can find that CADGMM achieves more compact and separated clusters compared with DAGMM. The results can also explain why our approach achieves better performance on anomaly detection task.