# Sketch-Based Anomaly Detection in Streaming Graphs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 71 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 18 of 18)

- [Deep Learning for Anomaly Detection: A Survey](https://mlsanity.com/paper/1901.03407/) (2019)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [A Survey of Network-based Intrusion Detection Data Sets](https://mlsanity.com/paper/1903.02460/) (2019)
- [MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams](https://mlsanity.com/paper/1911.04464/) (2019)
- [ExGAN: Adversarial Generation of Extreme Samples](https://mlsanity.com/paper/2009.08454/) (2020)
- [F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams](https://mlsanity.com/paper/2011.04723/) (2020)
- [Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach](https://mlsanity.com/paper/2011.13085/) (2020)
- [Semi-supervised Anomaly Detection on Attributed Graphs](https://mlsanity.com/paper/2002.12011/) (2020)
- [MSTREAM: Fast Anomaly Detection in Multi-Aspect Streams](https://mlsanity.com/paper/2009.08451/) (2020)
- [DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams](https://mlsanity.com/paper/1706.03374/) (2017)
- [Mining Persistent Activity in Continually Evolving Networks](https://mlsanity.com/paper/2006.15410/) (2020)
- [EdgeCentric: Anomaly Detection in Edge-Attributed Networks](https://mlsanity.com/paper/1510.05544/) (2015)
- [Real-Time Anomaly Detection in Edge Streams](https://mlsanity.com/paper/2009.08452/) (2020)
- [Densest Subgraph in Dynamic Graph Streams](https://mlsanity.com/paper/1506.04417/) (2015)
- [Higher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations](https://mlsanity.com/paper/1901.11261/) (2019)
- [Near-Optimal Fully Dynamic Densest Subgraph](https://mlsanity.com/paper/1907.03037/) (2019)
- [Metric Sublinear Algorithms via Linear Sampling](https://mlsanity.com/paper/1807.09302/) (2018)
- [AugSplicing: Synchronized Behavior Detection in Streaming Tensors](https://mlsanity.com/paper/2012.02006/) (2020)

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

- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via Self-Supervised Learning](https://mlsanity.com/paper/2402.11933/) (2024)
- [Online Detection of Anomalies in Temporal Knowledge Graphs with Interpretability](https://mlsanity.com/paper/2408.00872/) (2024)
- [ARES: Anomaly Recognition Model For Edge Streams](https://mlsanity.com/paper/2511.22078/) (2025)
- [Fast Mining and Dynamic Time-to-Event Prediction over Multi-sensor Data Streams](https://mlsanity.com/paper/2601.04741/) (2026)
- [Multi-Aspect Mining and Anomaly Detection for Heterogeneous Tensor Streams](https://mlsanity.com/paper/2602.04917/) (2026)
- [Analyzing the Evolution of Graphs and Texts](https://mlsanity.com/paper/2411.06295/) (2024)
- [Adaptive-GraphSketch: Real-Time Edge Anomaly Detection via Multi-Layer Tensor Sketching and Temporal Decay](https://mlsanity.com/paper/2509.11633/) (2025)
- [LoReTTA: A Low Resource Framework To Poison Continuous Time Dynamic Graphs](https://mlsanity.com/paper/2511.07379/) (2025)

## Abstract (arXiv)

Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? For example, in intrusion detection, existing work seeks to detect either anomalous edges or anomalous subgraphs, but not both. In this paper, we first extend the count-min sketch data structure to a higher-order sketch. This higher-order sketch has the useful property of preserving the dense subgraph structure (dense subgraphs in the input turn into dense submatrices in the data structure). We then propose 4 online algorithms that utilize this enhanced data structure, which (a) detect both edge and graph anomalies; (b) process each edge and graph in constant memory and constant update time per newly arriving edge, and; (c) outperform state-of-the-art baselines on 4 real-world datasets. Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.