# Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2016.

## Built on by (most cited first, 30 of 37)

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation](https://mlsanity.com/paper/2112.10063/) (2021)
- [Anomaly Detection in Dynamic Graphs via Transformer](https://mlsanity.com/paper/2106.09876/) (2021)
- [Kairos: Practical Intrusion Detection and Investigation using Whole-system Provenance](https://mlsanity.com/paper/2308.05034/) (2023)
- [threaTrace: Detecting and Tracing Host-based Threats in Node Level Through Provenance Graph Learning](https://mlsanity.com/paper/2111.04333/) (2021)
- [MAGIC: Detecting Advanced Persistent Threats via Masked Graph Representation Learning](https://mlsanity.com/paper/2310.09831/) (2023)
- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [A Rule Mining-Based Advanced Persistent Threats Detection System](https://mlsanity.com/paper/2105.10053/) (2021)
- [Graph Anomaly Detection with Unsupervised GNNs](https://mlsanity.com/paper/2210.09535/) (2022)
- [On the Detection of Reviewer-Author Collusion Rings From Paper Bidding](https://mlsanity.com/paper/2402.07860/) (2024)
- [GCWSNet: Generalized Consistent Weighted Sampling for Scalable and Accurate Training of Neural Networks](https://mlsanity.com/paper/2201.02283/) (2022)
- [TREC: APT Tactic / Technique Recognition via Few-Shot Provenance Subgraph Learning](https://mlsanity.com/paper/2402.15147/) (2024)
- [OCR-APT: Reconstructing APT Stories from Audit Logs using Subgraph Anomaly Detection and LLMs](https://mlsanity.com/paper/2510.15188/) (2025)
- [Hack Me If You Can: Aggregating AutoEncoders for Countering Persistent Access Threats Within Highly Imbalanced Data](https://mlsanity.com/paper/2406.19220/) (2024)
- [ANUBIS: A Provenance Graph-Based Framework for Advanced Persistent Threat Detection](https://mlsanity.com/paper/2112.11032/) (2021)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [Anomaly Detection in Graph Structured Data: A Survey](https://mlsanity.com/paper/2405.06172/) (2024)
- [Motif-Consistent Counterfactuals with Adversarial Refinement for Graph-Level Anomaly Detection](https://mlsanity.com/paper/2407.13251/) (2024)
- [OMNISEC: LLM-Driven Provenance-based Intrusion Detection via Retrieval-Augmented Behavior Prompting](https://mlsanity.com/paper/2503.03108/) (2025)
- [HRGCN: Heterogeneous Graph-level Anomaly Detection with Hierarchical Relation-augmented Graph Neural Networks](https://mlsanity.com/paper/2308.14340/) (2023)
- [Deep Learning-based Intrusion Detection Systems: A Survey](https://mlsanity.com/paper/2504.07839/) (2025)
- [TBDetector:Transformer-Based Detector for Advanced Persistent Threats with Provenance Graph](https://mlsanity.com/paper/2304.02838/) (2023)
- [Online Detection of Anomalies in Temporal Knowledge Graphs with Interpretability](https://mlsanity.com/paper/2408.00872/) (2024)
- [Structural-Temporal Coupling Anomaly Detection with Dynamic Graph Transformer](https://mlsanity.com/paper/2505.08330/) (2025)
- [Insider Threat Detection Using GCN and Bi-LSTM with Explicit and Implicit Graph Representations](https://mlsanity.com/paper/2512.18483/) (2025)
- [PIDSMaker: Building and Evaluating Provenance-based Intrusion Detection Systems](https://mlsanity.com/paper/2601.22983/) (2026)
- [Flurry: a Fast Framework for Reproducible Multi-layered Provenance Graph Representation Learning](https://mlsanity.com/paper/2203.02744/) (2022)
- [Temporal Egonet Subgraph Transitions](https://mlsanity.com/paper/2303.14632/) (2023)
- [Pb-Hash: Partitioned b-bit Hashing](https://mlsanity.com/paper/2306.15944/) (2023)

## Abstract (arXiv)

Given a stream of heterogeneous graphs containing different types of nodes and edges, how can we spot anomalous ones in real-time while consuming bounded memory? This problem is motivated by and generalizes from its application in security to host-level advanced persistent threat (APT) detection. We propose StreamSpot, a clustering based anomaly detection approach that addresses challenges in two key fronts: (1) heterogeneity, and (2) streaming nature. We introduce a new similarity function for heterogeneous graphs that compares two graphs based on their relative frequency of local substructures, represented as short strings. This function lends itself to a vector representation of a graph, which is (a) fast to compute, and (b) amenable to a sketched version with bounded size that preserves similarity. StreamSpot exhibits desirable properties that a streaming application requires---it is (i) fully-streaming; processing the stream one edge at a time as it arrives, (ii) memory-efficient; requiring constant space for the sketches and the clustering, (iii) fast; taking constant time to update the graph sketches and the cluster summaries that can process over 100K edges per second, and (iv) online; scoring and flagging anomalies in real time. Experiments on datasets containing simulated system-call flow graphs from normal browser activity and various attack scenarios (ground truth) show that our proposed StreamSpot is high-performance; achieving above 95% detection accuracy with small delay, as well as competitive time and memory usage.