# Subset Node Anomaly Tracking over Large Dynamic Graphs

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2022.

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

- [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)
- [BotDGT: Dynamicity-aware Social Bot Detection with Dynamic Graph Transformers](https://mlsanity.com/paper/2404.15070/) (2024)
- [Revisiting Dynamic Graph Clustering via Matrix Factorization](https://mlsanity.com/paper/2502.06117/) (2025)
- [DP-DGAD: A Generalist Dynamic Graph Anomaly Detector with Dynamic Prototypes](https://mlsanity.com/paper/2508.00664/) (2025)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [3D-IDS: Doubly Disentangled Dynamic Intrusion Detection](https://mlsanity.com/paper/2307.11079/) (2023)
- [Online Detection of Anomalies in Temporal Knowledge Graphs with Interpretability](https://mlsanity.com/paper/2408.00872/) (2024)
- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)
- [Node Role-Guided LLMs for Dynamic Graph Clustering](https://mlsanity.com/paper/2603.13799/) (2026)
- [Coden: Efficient Temporal Graph Neural Networks for Continuous Prediction](https://mlsanity.com/paper/2602.12613/) (2026)
- [Online Test-Time Adaptation for Generalizable Dynamic Graph Anomaly Detection](https://mlsanity.com/paper/2608.19858/) (2026)

## Abstract (arXiv)

Tracking a targeted subset of nodes in an evolving graph is important for many real-world applications. Existing methods typically focus on identifying anomalous edges or finding anomaly graph snapshots in a stream way. However, edge-oriented methods cannot quantify how individual nodes change over time while others need to maintain representations of the whole graph all time, thus computationally inefficient. This paper proposes textscDynAnom, an efficient framework to quantify the changes and localize per-node anomalies over large dynamic weighted-graphs. Thanks to recent advances in dynamic representation learning based on Personalized PageRank, textscDynAnom is 1) textitefficient: the time complexity is linear to the number of edge events and independent on node size of the input graph; 2) textiteffective: textscDynAnom can successfully track topological changes reflecting real-world anomaly; 3) textitflexible: different type of anomaly score functions can be defined for various applications. Experiments demonstrate these properties on both benchmark graph datasets and a new large real-world dynamic graph. Specifically, an instantiation method based on textscDynAnom achieves the accuracy of 0.5425 compared with 0.2790, the best baseline, on the task of node-level anomaly localization while running 2.3 times faster than the baseline. We present a real-world case study and further demonstrate the usability of textscDynAnom for anomaly discovery over large-scale graphs.