# Adaptive DecayRank: Real-Time Anomaly Detection in Dynamic Graphs with Bayesian PageRank Updates
## 2 Related Work
MIDAS-R [26] detects microcluster anomalies in edge streams using Count-Min Sketches (CMSs) to track the frequency of edge occurrences at each timestamp and, subsequently, utilizes the Chi-squared test to assess the extent of deviation from typical edges in order to calculate anomaly scores. F-FADE [27] discovers anomalies by estimating edge patterns using the maximum likelihood rule of observed instances for each incoming interaction, while AnoEdge [28], an extension of MIDAS-R, focuses on higher-order sketches. However, these methods (F-FADE, MIDAS-R, and AnoEdge) require high computational time for large graph streams and primarily target the detection of edge-level or subgraph-level anomalies. In contrast, our method captures both node-level and structural anomalies in real time, offering a more comprehensive approach to anomaly detection in dynamic graph streams. _Matrix factorization methods_ decompose high-dimensional matrices into lower-dimensional forms, revealing evolving patterns in graphs. Recent methods include EdgeMonitor [29], an edge-detection approach that models dynamic graph evolution as a first-order Markov process. However, a major drawback is its reliance on consistent node ordering across all time steps, and it assumes a constant number of nodes per snapshot, which is often violated in large-scale graphs. DenseAlert [30] is an incremental and continuously updating method for detecting dense subtensors in tensor streams. LAD [31] applies the Laplacian spectrum for change detection by computing the singular value decomposition (SVD) of the graph Laplacian to obtain a low-dimensional graph representation. MultiLAD [32] generalizes LAD to multi-view graph detection. Despite the successes of matrix factorization-based methods like EdgeMonitor, DenseAlert, LAD, and Multi-LAD, these approaches are computationally intensive, require manual extraction of graph properties, and are highly susceptible to noise. In contrast, Adaptive-DecayRank dynamically updates node scores in real time without requiring global recomputation, ensuring scalability and efficiency for large-scale graph streams. _Deep graph learning methods_ leverage neural networks to extract and learn graph representations. H-VGRAE [33] employs graph autoencoders for embedding and node-level detection, constructing a hierarchical model by combining a variational graph autoencoder with a recurrent neural network (RNN). ROLAND [34] extends classical graph neural networks (GNNs) to capture dynamic graph structures by leveraging a hierarchical node state update mechanism. It allows static GNNs to be adapted for dynamic graphs usingrecurrent updates and an incremental training approach. However, ROLAND and other deep learning approaches, such as H-VGRAE, assume that node embeddings can be incrementally updated without complete recomputation, leading to information loss over long sequences. In contrast, Adaptive-DecayRank is designed for real-time anomaly detection in dynamic graphs. Unlike deep learning-based methods, it does not require retraining from scratch or extensive hyperparameter tuning, making it computationally efficient and scalable for large graph streams. Additionally, Transformer models, such as Graphomer [35] and TADDY [36], have also been utilized for dynamic graph representation learning. However, these methods face limitations when dealing with highly irregular and evolving topologies, as they often struggle to capture local structural dependencies efficiently. In summary, our method, Adaptive-DecayRank, addresses a broader range of anomalies by detecting both node-level and structural anomalies in streaming graphs. Adaptive-DecayRank aligns with distance-based and similarity-based approaches, leveraging dynamic PageRank with a _decay factor_ and _Bayesian updating_ as a similarity metric to assign node importance scores and conduct structural analysis.