Graph Based Tensor Recovery For Accurate Internet Anomaly Detection

Kun Xie State University of New York at Stony Brook, USA
Xiaocan Li Stony Brook University, New York, USA
Xin Wang Stony Brook University, USA
Gaogang Xie Institute of Computing Technology, Chinese Academy of Sciences, P.R. China
Jigang Wen Chinese Academy of Science & Institute of Computing Technology, P.R. China
Dafang Zhang Hunan University, P.R. China


Detecting anomalous traffic is a crucial task of managing networks. Many anomaly detection algorithms have been proposed recently. However, constrained by their matrix-based traffic data model, existing algorithms often suffer from low detection accuracy. To fully utilize the multi-dimensional information hidden in the traffic data, this paper takes an initiative to investigate the potential and methodologies of performing tensor factorization for more accurate Internet anomaly detection. Only considering the low-rank linearity features hidden in the data, current tensor factorization techniques would result in low anomaly detection accuracy. We propose a novel Graph-based Tensor Recovery model (Graph-TR) to well explore both low rank linearity features as well as the non-linear proximity information hidden in the traffic data for better anomaly detection. We encode the non-linear proximity information of the traffic data by constructing nearest neighbor graphs and incorporate this information into the tensor factorization using the graph Laplacian. Moreover, to facilitate the quick building of neighbor graph, we propose a nearest neighbor searching algorithm with the simple locality-sensitive hashing (LSH). We have conducted extensive experiments using Internet traffic trace data Abilene and G ` EANT. Compared with the state of art algorithms on matrix-based anomaly detection and tensor recovery approach, our Graph-TR can achieve significantly lower False Positive Rate and higher True Positive Rate.

You may want to know: