# Adaptive-GraphSketch: Real-Time Edge Anomaly Detection via Multi-Layer Tensor Sketching and Temporal Decay

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 15 Sep 2025.

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

- [F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams](https://mlsanity.com/paper/2011.04723/) (2020)
- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [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)
- [Fast Change Point Detection on Dynamic Social Networks](https://mlsanity.com/paper/1705.07325/) (2017)
- [Sketch-Based Anomaly Detection in Streaming Graphs](https://mlsanity.com/paper/2106.04486/) (2021)
- [Real-Time Anomaly Detection in Edge Streams](https://mlsanity.com/paper/2009.08452/) (2020)
- [A Formal Analysis of the Count-Min Sketch with Conservative Updates](https://mlsanity.com/paper/2203.14549/) (2022)

## Abstract (arXiv)

Anomaly detection in dynamic graphs is essential for identifying malicious activities, fraud, and unexpected behaviors in real-world systems such as cybersecurity and power grids. However, existing approaches struggle with scalability, probabilistic interpretability, and adaptability to evolving traffic patterns. In this paper, we propose ADAPTIVE-GRAPHSKETCH, a lightweight and scalable framework for real-time anomaly detection in streaming edge data. Our method integrates temporal multi-tensor sketching with Count-Min Sketch using Conservative Update (CMS-CU) to compactly track edge frequency patterns with bounded memory, while mitigating hash collision issues. We incorporate Bayesian inference for probabilistic anomaly scoring and apply Exponentially Weighted Moving Average (EWMA) for adaptive thresholding tuned to burst intensity. Extensive experiments on four real-world intrusion detection datasets demonstrate that ADAPTIVE-GRAPHSKETCH outperforms state-of-the-art baselines such as ANOEDGE-G/L, MIDAS-R, and F-FADE, achieving up to 6.5% AUC gain on CIC-IDS2018 and up to 15.6% on CIC-DDoS2019, while processing 20 million edges in under 3.4 seconds using only 10 hash functions. Our results show that ADAPTIVE-GRAPHSKETCH is practical and effective for fast, accurate anomaly detection in large-scale streaming graphs. Keywords: Anomaly Detection, Streaming, Real-time, Dynamic Graphs, Edge Streams, Tensor Sketching