Sparse Laplacian Component Analysis

Sparse Laplacian Component Analysis (SLCA)

We consider the problem of anomaly detection in network traffic. It is a challenging problem because of high-dimensional and noisy nature of network traffic. A popularly used technique is subspace analysis. In particular, subspace analysis aims to separate the high-dimensional space of traffic signals into disjoint subspaces corresponding to normal and anomalous network conditions. Principal component analysis (PCA) and its improvements have been applied for this analysis. In this work, we take a different approach to determine the subspaces, and propose to capture the essence of the data using the eigenvectors of graph Laplacian, which we refer as Laplacian components (LCs). Our main contribution is to propose a regression framework to compute LCs followed by its application in anomaly detection. This framework provides much flexibility in incorporating different properties into the LCs, notably LCs with sparse loadings, which we exploit in detail. Furthermore, different from previous work that uses a sample graph to preserve local structure, we advocate modeling with a dual-input feature graph that encodes the correlation of the time series data and prior information. Therefore, the proposed model can readily incorporate the `physics' of some applications as prior information to improve the analysis. We perform experiments on volume anomaly detection using three real datasets. We demonstrate that the proposed model can correctly uncover the essential low-dimensional principal subspace containing the normal Internet traffic and achieve outstanding detection performance.

Publications:

M. Khatua, S.H. Safavi, Ngai-Man Cheung, “Sparse Laplacian Component Analysis for Internet Traffic Anomalies Detection", IEEE Transactions on Signal and Information Processing over Networks, Accepted for publication, 2018. [PDF] [Code]
M. Khatua, S.H. Safavi, Ngai-Man Cheung, “Detection of Internet Traffic Anomalies using Sparse Laplacian Component Analysis”, IEEE GLOBECOM 2017, pp. 1-6. [PDF] [DOI] [Code]