# Adaptive DecayRank: Real-Time Anomaly Detection in Dynamic Graphs with Bayesian PageRank Updates
## 3 Background
### Dynamic PageRank Variant  
Our method extends the Dynamic PageRank [9] variant to effectively handle real-time anomaly detection in graph streams by incorporating temporal adaptability for real-time updates. Traditional PageRank algorithms often fail to address challenges in dynamic \begin{table}
\begin{tabular}{l l} \hline
**Symbol** & **Definition** \\ \hline \(G=(V,E)\) & Weighted graph with nodes, \(V\), and edges, \(E\). \\ \(\mathcal{G}=\{G_{t}\}_{t=1}^{T}\) & Dynamic graph as a sequence of snapshots at each timestamp, \(t\). \\ \(G_{t}=(V_{t},E_{t},W_{t})\) & Snapshot of the graph at time \(t\), with a set of vertices, \(V_{t}\), a set of edges, \(E_{t}\), and edge-weights, \(W_{t}\). \\ \(T\) & Total number of time steps. \\ \(W(e)\in\mathbb{R}\) & Weight function, \(W:E\rightarrow\mathbb{R}\), assigning a real-valued weight, \(W(e)\), to each edge, \(e\in E\). \\ \(V\) & Set of all vertices (nodes) in the graph. \\ \(v_{u}\) & Specific vertex, \(u\), in the graph, with an associated PageRank score. \\ \(\Delta E_{t}\) & Change in edges (insertions or deletions) between \(t\) and \(t+1\). \\ \(\Delta V_{t}\) & Change in nodes (additions or removals) between \(t\) and \(t+1\). \\ \(P\) & Row-normalized adjacency matrix, \(P\in\mathbb{R}^{n\times n}\), where \(P=D^{-1}A\). \\ \(D^{-1}\), \(A\) & Inverse degree matrix and adjacency matrix of the graph. \\ \(c\) & Damping factor of PageRank, commonly set to 0.85. \\ \(h\), \(h(t+1)\) & Starting probability vector, \((n\times 1)\), with potential changes over time. \\ \(f(v)\) & Node-level anomaly scoring function. \\ \(\hat{f}\) & Summary statistic (e.g., mean or median) of the score function, \\ \(f(v),\forall v\in V\). \\ \(c_{0}\) & Threshold for detecting anomalies based on score deviations. \\ \(|f(v^{\prime})-\hat{f}|\) & Absolute difference between the score,\(f(v^{\prime})\), and the summary statistic, \(\hat{f}\). \\ \(N,n\) & Number of nodes and edges in \(\mathcal{G}\). \\ \hline \end{tabular}
\end{table} 
Table 2: List of Notations. graphs, such as high-frequency updates, computational overhead, and the temporal decay of node relevance. These properties make Dynamic PageRank particularly well-suited for dynamic graphs, where the current node importance score, \(v^{i+1}\), can be updated incrementally from previous scores, \(v^{i}\), based on recent structural changes in the graph. This adaptability is especially critical in applications like intrusion detection and critical cyber-infrastructure monitoring, where edge or node insertions and deletions often signify anomalies or potential cyber-threats [2], requiring immediate attention. For example, consider a coordinated Distributed Denial-of-Service (DDoS) attack, where multiple computers collectively exhibit malicious behavior or a social network where a user's connections fluctuate daily. A standard PageRank algorithm treats the graph as static, missing short-term or evolving trends, such as a sudden influx of connections indicative of spam activity. Personalized Dynamic PageRank variants, like our proposed model, capture this behavior by incrementally updating scores with temporal decay (i.e., the gradual reduction in the influence of older node or edge interactions over time), thereby enabling timely anomaly detection. The formula to compute the dynamic PageRank score is shown below:  
\[v_{u}(t+1)=cP^{(t)}v_{u}(t)+(1-c)h(t+1) \tag{2}\]  
Equation (2) follows directly from Equation (1), where \(P^{(t)}\) is the stochastic transition matrix, defined as \(P^{(t)}=D^{-1}A^{\mathsf{T}}\). This matrix depends on the graph's structure at each time step, \(t\). The parameter \(c\) is the damping factor, and the indicator probability vector, \(h(t+1)\), allows the teleport vector to vary over time. This formulation enables incremental updates to the PageRank scores upon the insertion or deletion of edges, making it highly suitable for practical downstream tasks such as graph learning.