# DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams

arXiv: https://arxiv.org/abs/1706.03374 · HTML: https://mlsanity.com/paper/1706.03374/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2017.

## Built on by (most cited first, 13 of 13)

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [Sketch-Based Anomaly Detection in Streaming Graphs](https://mlsanity.com/paper/2106.04486/) (2021)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Fast and Multi-aspect Mining of Complex Time-stamped Event Streams](https://mlsanity.com/paper/2303.03789/) (2023)
- [Discriminative Graph-level Anomaly Detection via Dual-students-teacher Model](https://mlsanity.com/paper/2308.01947/) (2023)
- [Robust Graph Clustering via Meta Weighting for Noisy Graphs](https://mlsanity.com/paper/2311.00322/) (2023)
- [Text-Attributed Graph Anomaly Detection via Multi-Scale Cross- and Uni-Modal Contrastive Learning](https://mlsanity.com/paper/2508.00513/) (2025)
- [Court of LLMs: Evidence-Augmented Generation via Multi-LLM Collaboration for Text-Attributed Graph Anomaly Detection](https://mlsanity.com/paper/2508.00507/) (2025)
- [CyberCScope: Mining Skewed Tensor Streams and Online Anomaly Detection in Cybersecurity Systems](https://mlsanity.com/paper/2503.00871/) (2025)
- [Isconna: Streaming Anomaly Detection with Frequency and Patterns](https://mlsanity.com/paper/2104.01632/) (2021)
- [Multi-Aspect Mining and Anomaly Detection for Heterogeneous Tensor Streams](https://mlsanity.com/paper/2602.04917/) (2026)
- [Adaptive-GraphSketch: Real-Time Edge Anomaly Detection via Multi-Layer Tensor Sketching and Temporal Decay](https://mlsanity.com/paper/2509.11633/) (2025)

## Abstract (arXiv)

Consider a stream of retweet events - how can we spot fraudulent lock-step behavior in such multi-aspect data (i.e., tensors) evolving over time? Can we detect it in real time, with an accuracy guarantee? Past studies have shown that dense subtensors tend to indicate anomalous or even fraudulent behavior in many tensor data, including social media, Wikipedia, and TCP dumps. Thus, several algorithms have been proposed for detecting dense subtensors rapidly and accurately. However, existing algorithms assume that tensors are static, while many real-world tensors, including those mentioned above, evolve over time. We propose DenseStream, an incremental algorithm that maintains and updates a dense subtensor in a tensor stream (i.e., a sequence of changes in a tensor), and DenseAlert, an incremental algorithm spotting the sudden appearances of dense subtensors. Our algorithms are: (1) Fast and 'any time': updates by our algorithms are up to a million times faster than the fastest batch algorithms, (2) Provably accurate: our algorithms guarantee a lower bound on the density of the subtensor they maintain, and (3) Effective: our DenseAlert successfully spots anomalies in real-world tensors, especially those overlooked by existing algorithms.