DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams

Overview

DenseStream is an incremental algorithm for detecting dense subtensors in tensor streams, and DenseAlert is an incremental algorithm for spotting suddenly emerging dense subtensors. They have the following properties:

Fast and Any Time: By maintaining and updating a dense subtensor, our algorithms detect a dense subtensor in a tensor stream significantly faster than batch algorithms.

Provably Accurate: Our algorithms provide theoretical guarantees on their accuracy, and show high accuracy in practice.

Effective: Our algorithms successfully identify anomalies, such as bot activities, rating manipulations, and network intrusions, in real-world tensors.

Paper

DenseStream and DenseAlert are described in the following paper:

DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams
Kijung Shin, Bryan Hooi, Jisu Kim, and Christos Faloutsos
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2017, Halifax, Canada [PDF][Supplementary Document][BIBTEX]