# MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2019.

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

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [TimeSeriesBench: An Industrial-Grade Benchmark for Time Series Anomaly Detection Models](https://mlsanity.com/paper/2402.10802/) (2024)
- [Graph Anomaly Detection in Time Series: A Survey](https://mlsanity.com/paper/2302.00058/) (2023)
- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Unveiling the potential of Graph Neural Networks for robust Intrusion Detection](https://mlsanity.com/paper/2107.14756/) (2021)
- [SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via Self-Supervised Learning](https://mlsanity.com/paper/2402.11933/) (2024)
- [MemStream: Memory-Based Streaming Anomaly Detection](https://mlsanity.com/paper/2106.03837/) (2021)
- [A Generalizable Anomaly Detection Method in Dynamic Graphs](https://mlsanity.com/paper/2412.16447/) (2024)
- [Sketch-Based Anomaly Detection in Streaming Graphs](https://mlsanity.com/paper/2106.04486/) (2021)
- [Spear and Shield: Adversarial Attacks and Defense Methods for Model-Based Link Prediction on Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2308.10779/) (2023)
- [Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction](https://mlsanity.com/paper/2211.08378/) (2022)
- [Cybersecurity Anomaly Detection in Adversarial Environments](https://mlsanity.com/paper/2105.06742/) (2021)
- [Learning-Based Link Anomaly Detection in Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2405.18050/) (2024)
- [Anomaly Detection in Graph Structured Data: A Survey](https://mlsanity.com/paper/2405.06172/) (2024)
- [GraphAnoGAN: Detecting Anomalous Snapshots from Attributed Graphs](https://mlsanity.com/paper/2106.15504/) (2021)
- [Beyond Sparse Supervision: Diffusion-Guided Learning for Few-Shot Graph Fraud Detection](https://mlsanity.com/paper/2606.28134/) (2026)
- [Isconna: Streaming Anomaly Detection with Frequency and Patterns](https://mlsanity.com/paper/2104.01632/) (2021)
- [FadMan: Federated Anomaly Detection across Multiple Attributed Networks](https://mlsanity.com/paper/2205.14196/) (2022)
- [Simple yet Effective Node Property Prediction on Edge Streams under Distribution Shifts](https://mlsanity.com/paper/2504.00328/) (2025)
- [ARES: Anomaly Recognition Model For Edge Streams](https://mlsanity.com/paper/2511.22078/) (2025)
- [Multi-Aspect Mining and Anomaly Detection for Heterogeneous Tensor Streams](https://mlsanity.com/paper/2602.04917/) (2026)
- [tegdet: An extensible Python Library for Anomaly Detection using Time-Evolving Graphs](https://mlsanity.com/paper/2210.08847/) (2022)
- [A Frequency-Structure Approach for Link Stream Analysis](https://mlsanity.com/paper/2212.03804/) (2022)
- [Anomaly Detection in Cooperative Vehicle Perception Systems under Imperfect Communication](https://mlsanity.com/paper/2501.17329/) (2025)
- [Low-Resource Neural Machine Translation Using Recurrent Neural Networks and Transfer Learning: A Case Study on English-to-Igbo](https://mlsanity.com/paper/2504.17252/) (2025)
- [Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies](https://mlsanity.com/paper/2603.01841/) (2026)
- [Beat the Counter First: A Baseline for Temporal-Graph Anomaly Detectors](https://mlsanity.com/paper/2608.15965/) (2026)
- [RankShift: In-Database Detection and Explanation of Categorical Shifts](https://mlsanity.com/paper/2608.28922/) (2026)

## Abstract (arXiv)

Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? Existing approaches aim to detect individually surprising edges. In this work, we propose MIDAS, which focuses on detecting microcluster anomalies, or suddenly arriving groups of suspiciously similar edges, such as lockstep behavior, including denial of service attacks in network traffic data. MIDAS has the following properties: (a) it detects microcluster anomalies while providing theoretical guarantees about its false positive probability; (b) it is online, thus processing each edge in constant time and constant memory, and also processes the data 162-644 times faster than state-of-the-art approaches; (c) it provides 42%-48% higher accuracy (in terms of AUC) than state-of-the-art approaches.