# Adaptive DecayRank: Real-Time Anomaly Detection in Dynamic Graphs with Bayesian PageRank Updates
## 2 Related Work  
In this section, we review existing methods for detecting anomalies in dynamic graphs. We categorize these methods into four groups based on their algorithmic structures. For a more comprehensive understanding of anomaly detection in dynamic graphs, we refer readers to the following reviews [1,2]. _Distance and similarity-based methods_ measure similarities between nodes using time-evolving metrics to detect anomalies. Common metrics include PageRank [13] and Betweenness Centrality [14]. However, these similarity-based methods rely on static graphs, making them less effective in capturing real-time changes in dynamic graphs. The concept of ranking nodes by their importance or influence has been extensively studied in network science. [PERSON] et al. [15] provide a comprehensive review of node centrality measures, including various personalized PageRank (PPR) [16] approaches, which have also been adapted for anomaly detection in dynamic graphs. Many methods in this category focus on identifying vital nodes to maximize influence propagation (for example, in social networks or epidemic spreading models [17]), but their applicability to streaming anomaly detection remains limited due to computational constraints. SedanSpot [18] is a randomized algorithm for detecting sparsely connected edges and identifying anomalies based on edge occurrence. However, SedanSpot processes input streams linearly, making it highly computationally expensive. In contrast, our method scales efficiently on large graphs in seconds. GBAD [19] leverages the Minimum Description Length (MDL) principle and a probabilistic approach to detect graph-based structural anomalies. AnomRank [20] applies personalized PageRank to capture both structural and edge-weight anomalies. However, in contrast to our method, AnomRank computes a global PageRank score, which does not scale efficiently for edge streaming processing. [PERSON] and [PERSON] [21] introduced the concept of \"Temporal Networks\", which highlights the challenges of detecting anomalies in streaming graphs with evolving nodes and edges. In contrast, our work focuses on anomaly detection in dynamic graphs; temporal networks provide a strong theoretical foundation for understanding evolving structures. SnapSketch [22] is a sketch-based approach; however, it struggles with detecting sudden structural changes in dynamic graphs, a limitation our method addresses by incorporating adaptive sensitivity to micro-changes in evolving graph states. DYNWATCH [5] uses the Line Outage Distribution Factors (LODFs) sensitivity measure for real-time detection in power grid sensors. DYNWATCH constructs a graph from active grid devices such as nodes and performs temporal weighting based on graph distances for anomaly detection. However, DYNWATCH relies on predefined sensitivity measures like LODF, making it less adaptive to dynamic network topologies beyond power grids. DynAnom [23] is a method to track node-level and graph-level anomalies using personalized PageRank (PPR) in large graphs. It dynamically weights node representations to reflect evolving graph structures. However, it is limited by its reliance on PPR, which can introduce bias toward high-degree nodes and is less effective in capturing rapid structural changes in graphs. _Probabilistic methods_ use probabilistic models to represent neighborhood relationships in graphs. RHSS [24] employs Count-Min sketches to approximate graph properties and generate probabilistic error bounds on each edge outlier scoring function. However, RHSS has a limitation in its reliance on fixed probabilistic bounds, which may lead to overestimation or underestimation of anomaly scores due to hash collisions. In contrast, our method not only captures evolving patterns but also adjusts node importance scores in real time. PENminer [25] explores the persistence of activity snippets in edge streams, which is relevant for short sequences of recurring edge updates; however, it is not equipped to detect subgraph- or graph-level anomalies.