# Adaptive DecayRank: Real-Time Anomaly Detection in Dynamic Graphs with Bayesian PageRank Updates
## 4 Proposed Method
### Algorithm  
Algorithm 2 implements the Adaptive-DecayRank framework. The algorithm processes a dynamic graph represented by the **input**, \(A\), which is an array of outEdges serving as the transition matrix. Each node maintains a list of outgoing edges, denoted as \(\mathbf{A[i].out}=\{j_{1},j_{2},\ldots,j_{k}\}\), with corresponding weights, \(\mathbf{A[i].weight}=\{w_{1},w_{2},\ldots,w_{k}\}\), where \(w_{k}\) is the weight associated with the edge connecting to each neighboring node, \(j_{k}\). Additionally, the last observed timestamp (denoted as \(\mathbf{A[i].timestamp}\) in algorithm line 5) represents the last time node \(i\) was updated in the graph stream. In Equation (7), this timestamp corresponds to \(A_{u}^{(T)}\), which represents the last time step at which node \(u\) was modified. For example, if node \(A\) has outgoing edges to nodes \(B\) and \(C\) with weights 0.5 and 0.2, respectively, and the timestamp is 10, this implies that node \(A\)'s connections were last updated at time step 10. The edge weights are assigned dynamically based on edge updates in the evolving graph stream, while the adaptive decay factor, \(\delta\), reduces edge influence over time.  
```
0:\(A\): Array of dynamic graph outEdges, \(\mathbf{v}\): Array of PageRank scores, \(\mathbf{n}\): Number of nodes, \(\mathbf{numSteps}\): Streaming timesteps
0:\(\mathbf{v}\): Anomaly scores \(\{v^{(0)},\ldots,v^{(T)}\}\) \(\triangleright\)Initialization of Parameters \((\delta,\alpha,\beta)\):
1: Initialize DecayRank values \(v[i]\leftarrow\frac{c}{n}\) for all nodes \(i\)
2:while each timestep step from 0 to \(numSteps-1\)do
3:\(\triangleright\)Power Iteration:
4: Update scores based on graph structure.
5:\(\triangleright\)Applying Adaptive Decay Factor:
6:for\(i=0\) to \(n-1\)do
7: time_diff \(\leftarrow\) step \(-A[i].\)timestamp
8: observed_changes \(\leftarrow\) (new_nq\([i]-\)old_nq\([i]\))
9:\(\alpha[i]\)\(+=o\)
10:\(\beta[i]\)\(+=(1-o)\)
11:\(\delta[i]\)\(\leftarrow\frac{\Gamma(\alpha[i])}{\Gamma(\beta[i])}\)
12: Adaptive_Decay\([i]\)\(\leftarrow\) min\((\delta[i],1.0)\)
13: new_nq\([i]\)\(*=\) exp\((-\delta[i]\)\(\times\) time_diff)
14:endfor
15:\(\triangleright\)Dynamic Updating of DecayRank Scores:
16:for\(i=0\) to \(n-1\)do
17:\(v[i]\)\(+=\) new_nq\([i]\)
18:endfor
19:\(\triangleright\)Convergence Check:
20:if\(\sum_{i=0}^{n-1}(\)new_nq\([i]-\)old_nq\([i])\)\(<\) EPSILON then
21:break
22:endif
23:endwhile
24:\(\triangleright\)Normalization:
25:return\(v\)\(\leftarrow\) normalizeDecayRank\((v,n)\)
```  
**Algorithm 2**Adaptive-DecayRank: Node Anomaly Scoring  
The **output**, \(\mathbf{v}\), is the sequence of stochastic vectors for node scores. The algorithm initializes node scores uniformly as \(v[i]=c/n\), where \(c\) is the damping factor, and \(n\) is the total number of nodes (as shown in _line 1_). At each time step, the algorithm iteratively updates these scores based on the structure of \(A\) using power iteration (_lines 2_-3).  
The **adaptive-decay factor**\(\delta[i]\) (as shown in lines 7-9) is dynamically adjusted using Bayesian inference to reflect observed changes in the graph structure, enhancing sensitivity to recent interactions while mitigating noise. The decay factor is computed as \(\delta[i]\) in _line 9_, where \(\alpha[i]\) represents the _prior update_, and \(\beta[i]\) represents the _posterior update_, both of which are updated based on observed changes (see details in Section 4.2.3). The scores, \(v[i]\), (updated in _line 14_) are adjusted with the computed decay values (\(\mathbf{new_{u}q[i]}\)), and the process continues until the **convergence criterion** (_line 16-19_) is satisfied. In _line 16_, the EPSILON is set to 0.0001 to balance accuracy and computational efficiency. After completing all iterations, the scores are **normalized** as \(v[i]\) to maintain consistency across nodes and ensure comparability, preventing high-degree nodes from dominating anomaly detection results (see details in Section 4.4.1).