# Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2020.

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

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs](https://mlsanity.com/paper/2206.10071/) (2022)
- [Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation](https://mlsanity.com/paper/2112.10063/) (2021)
- [Raising the Bar in Graph-level Anomaly Detection](https://mlsanity.com/paper/2205.13845/) (2022)
- [Graph Out-of-Distribution Generalization via Causal Intervention](https://mlsanity.com/paper/2402.11494/) (2024)
- [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)
- [Sketch-Based Anomaly Detection in Streaming Graphs](https://mlsanity.com/paper/2106.04486/) (2021)
- [Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction](https://mlsanity.com/paper/2211.08378/) (2022)
- [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)
- [TGM: a Modular and Efficient Library for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2510.07586/) (2025)
- [Isconna: Streaming Anomaly Detection with Frequency and Patterns](https://mlsanity.com/paper/2104.01632/) (2021)
- [3D-IDS: Doubly Disentangled Dynamic Intrusion Detection](https://mlsanity.com/paper/2307.11079/) (2023)
- [Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms](https://mlsanity.com/paper/2405.17182/) (2024)
- [Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness](https://mlsanity.com/paper/2602.02512/) (2026)
- [tegdet: An extensible Python Library for Anomaly Detection using Time-Evolving Graphs](https://mlsanity.com/paper/2210.08847/) (2022)
- [Temporal Egonet Subgraph Transitions](https://mlsanity.com/paper/2303.14632/) (2023)
- [Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies](https://mlsanity.com/paper/2603.01841/) (2026)
- [Filter-then-Verify: A Multiphase GNN and ModernBERT Framework for Social Engineering Detection in Email Networks](https://mlsanity.com/paper/2605.17201/) (2026)

## Abstract (arXiv)

Given a dynamic graph stream, how can we detect the sudden appearance of anomalous patterns, such as link spam, follower boosting, or denial of service attacks? Additionally, can we categorize the types of anomalies that occur in practice, and theoretically analyze the anomalous signs arising from each type? In this work, we propose AnomRank, an online algorithm for anomaly detection in dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics for anomalousness. Each metric tracks the derivatives of its own version of a 'node score' (or node importance) function. This allows us to detect sudden changes in the importance of any node. We show theoretically and experimentally that the two-pronged approach successfully detects two common types of anomalies: sudden weight changes along an edge, and sudden structural changes to the graph. AnomRank is (a) Fast and Accurate: up to 49.5x faster or 35% more accurate than state-of-the-art methods, (b) Scalable: linear in the number of edges in the input graph, processing millions of edges within 2 seconds on a stock laptop/desktop, and (c) Theoretically Sound: providing theoretical guarantees of the two-pronged approach.