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]

Promotion Video

Code

The source code used in the paper is available. [Github Repository]

Datasets

People

• Kijung Shin (Carnegie Mellon University)
• Bryan Hooi (Carnegie Mellon University)
• Jisu Kim (Carnegie Mellon University)
• Christos Faloutsos (Carnegie Mellon University)