Abstract
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 DynAnom, 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, DynAnom is efficient, effective, and flexible. Experiments demonstrate these properties on both benchmark graph datasets and a new large real-world dynamic graph. Specifically, DynAnom achieves an accuracy of 0.5425 compared with 0.2790 for the best baseline on node-level anomaly localization while running 2.3 times faster.
Introduction
In the real world, graphs—such as social networks, communication logs, or transaction records—are inherently dynamic. Nodes constantly change their "context" or behavior. For instance, when a public figure transitions into a new political role, their interaction patterns shift dramatically. Existing anomaly detection methods often fail to capture these nuances. Edge-focused methods look for unusual connections but miss status changes where a node's neighborhood shifts without a single anomalous edge. Conversely, graph-focused methods detect overall network instability but cannot pinpoint the specific responsible individuals.
Furthermore, traditional node embedding techniques are often too slow for massive graphs, requiring full retraining for every update. This retraining frequently leads to "stochastic drift," where embeddings are not aligned across time steps, making direct comparisons impossible.
The DynAnom Framework
DynAnom addresses these challenges by treating a node’s Personalized PageRank (PPR) vector as its representation. PPR measures the "proximity" of all other nodes to a target node, capturing its broader structural context.
Technical Innovations
- Generalized Dynamic Forward Push: The framework extends the "Forward Push" algorithm to weighted graphs, allowing for incremental updates as edges are added, deleted, or modified. This process is independent of the total graph size, focusing only on local changes.
- Invariant Maintenance: The authors proved a mathematical invariant property that ensures approximate PPR remains accurate over long sequences of updates.
- DynNodeRep (Aligned Embeddings): High-dimensional PPR vectors are compressed into low-dimensional vectors using deterministic universal hashing. This ensures the embedding space remains aligned across all time steps, allowing for direct distance calculations (e.g., $\ell_1$ distance) to quantify change.
Experimental Evaluation
The paper evaluates DynAnom on several benchmarks, including DARPA (DDoS attacks), ENRON (email communications), and a new massive dataset, PERSON. The PERSON dataset contains 3.2 million nodes and nearly 1,200 weekly snapshots (2000–2022), tracking public figures' interactions with events and locations.
Key Results
- Superior Accuracy: On the DARPA dataset, DynAnom achieved a precision of 0.5425, significantly outperforming the best baseline, AnomRank (0.2790).
- Efficiency: DynAnom ran 2.3 times faster than the leading baseline, with update complexity linear to edge events rather than total nodes.
- Real-World Case Study: In the PERSON graph, DynAnom successfully tracked the careers of public figures. For example, the anomaly scores for Joe Biden showed distinct spikes corresponding to his election as Vice President in 2008 and President in 2020.
Conclusion and Future Work
DynAnom provides a scalable, accurate solution for tracking node-level anomalies in massive dynamic graphs. By ensuring embedding alignment and leveraging incremental updates, it overcomes the limitations of previous methods. Future research will explore automatic subset selection to identify interesting nodes to track and the integration of temporal decay factors to better distinguish between sudden shocks and long-term trends.
Summary updated