#  Anomaly Detection in Dynamic Graphs: A Comprehensive Survey

Ocheme Anthony Ekle<EMAIL_ADDRESS>https://orcid.org/0009-0003-6204-0657
Tennessee Technological University1020 Stadium Drive, 406.CookevilleTNUSA38505
and  William Eberle<EMAIL_ADDRESS>https://orcid.org/0009-0009-1303-6102
<EMAIL_ADDRESS>Tennessee Technological UniversityCookevilleTNUSA

###### Abstract.

This survey paper presents a comprehensive and conceptual overview of anomaly
detection using dynamic graphs. We focus on existing graph-based anomaly
detection (AD) techniques and their applications to dynamic networks. The
contributions of this survey paper include the following: i) a comparative
study of existing surveys on anomaly detection; ii) a Dynamic Graph-based
Anomaly Detection (DGAD) review framework in which approaches for detecting
anomalies in dynamic graphs are grouped based on traditional machine-learning
models, matrix transformations, probabilistic approaches, and deep-learning
approaches; iii) a discussion of graphically representing both discrete and
dynamic networks; and iv) a discussion of the advantages of graph-based
techniques for capturing the relational structure and complex interactions in
dynamic graph data. Finally, this work identifies the potential challenges and
future directions for detecting anomalies in dynamic networks. This DGAD
survey approach aims to provide a valuable resource for researchers and
practitioners by summarizing the strengths and limitations of each approach,
highlighting current research trends, and identifying open challenges. In
doing so, it can guide future research efforts and promote advancements in
anomaly detection in dynamic graphs.

Graphs, Anomaly Detection, dynamic networks, Graph Neural Networks (GNN), Node
anomaly, Graph mining.

††copyright: none

##  1\. Introduction

Anomaly detection involves identifying patterns in data that deviate
significantly from a well-defined notion of normal behavior (Chandola et al.,
2009). In the works of Pang et al. (Pang et al., 2019), an anomaly is defined
as a data point that deviates from the majority of other data points. These
anomalies can manifest as patterns, observations, or data points that do not
conform to the typical patterns observed in data. Anomaly Detection is an
important task in both static and dynamic networks or graphs. Unlike static
networks, where the topology remains constant, dynamic networks are constantly
(or periodically) changing their node entities and edges (Ranshous et al.,
2015). Dynamic networks have the ability to capture the temporal evolution of
relationships in graphs, such as the insertion and deletion of nodes (Yoon et
al., 2019), the insertion and deletion of edges (Zheng et al., 2019), and
sudden pattern changes of sub-graphs or graph cliques (Alsentzer et al., 2020;
Yuan et al., 2023).

More interestingly, in the work of Michail et al. (Michail and Spirakis,
2018), modern dynamic networks have proven to exhibit additional structural
and algorithmic properties that go beyond the simple generalization of graphs
. Yet, while the challenges of modeling dynamic networks as dynamic graphs are
greater than on static graphs, the advantages of a dynamic representation are
important. In Figure 1, the dynamic graph $\mathcal{G}$ is shown, illustrating
two possible forms of graph representation at each time step. (1a) illustrates
discrete dynamic changes occurring over distinct time intervals
$\mathcal{G}=(G_{1},G_{2},\dots,G_{T})$, while (1b) presents a snapshot of the
evolving dynamic graph ($\mathcal{G}=(V_{t},E_{t},\mathcal{T})$), embedding
changes through continuous evolution in transitioning graph streams, with
$V_{t}$ as the node sets, $E_{t}$ representing evolving edges, and
$\mathcal{T}$ indicating the sequence of time steps.

Figure 1.  Dynamic Graph Representation: (1a) illustrates change in the
dynamic graph $\mathcal{G}=(G_{1},G_{2},\dots,G_{T})$, in which changes occur
in distinct time intervals (that is, changes are not continuous but rather at
specific time points, signifying a pattern of discrete changes over time).
(1b) captures a snapshot of an evolving dynamic graph
($\mathcal{G}=(V_{t},E_{t},\mathcal{T})$), where $V_{t}$ represents the node
set, $E_{t}$ signifies the evolving edge set, and $\mathcal{T}$ denotes the
sequence of time steps over which the dynamic graph evolves. The illustration
is embedded within a continuous temporal context, reflecting changes that are
not confined to specific time points but instead manifest as continuous
transformations.

Graph algorithms have significant real-life applications in areas such as drug
discovery (Gaudelet et al., 2021), distributed systems (Md et al., 2021), IoT
(Chen et al., 2021), protein design (Ingraham et al., 2019), fraud detection
(Zhang et al., 2022b), social network analysis (Fan et al., 2019), power grids
(Li et al., 2021), and so on. Each of these domains has the property of being
represented as a dynamic network. However, one of the predominant challenges
in dynamic networks is detecting anomalous patterns (Ranshous et al., 2015),
including nodes, edges, subgraphs, motifs, clusters, etc.

Early research on graph-based anomaly detection heavily relied on domain-
specific knowledge and the utilization of statistical techniques (Kim et al.,
2022). Existing anomaly detection methods include density-based local outlier
factor (LOF) (Breunig et al., 2000; Na et al., 2018; Salehi et al., 2016),
based on tree structures and detecting anomalies as randomly separated points,
and Isolation Forest (IF) (Liu et al., 2008; Hariri et al., 2019). Other
anomaly detection approaches encompass traditional and similarity-based
methods. Examples include the Reachable Distance Function for KNN
classification (Zhang et al., 2022a), Quantum KNN for neighbor selection (Li
et al., 2023), and Semi-Supervised learning for semantic similarities of
clusters (Zhou et al., 2023).

However, Isolation Forest methods use tree-based structures defined by the
maximum depth parameter and the sliding window’s size, and they have
constraints in capturing anomalies in long-range dependence that occur in
streaming graphs. Deep learning methods have also been proposed for anomaly
detection problems, such as autoencoders (Gong et al., 2019; Zong et al.,
2018; Zhou and Paffenroth, 2017), generative adversarial networks (GANs) (Yang
et al., 2021; Bashar and Nayak, 2020), and Recurrent Neural network
(RNN)-based approaches (Saurav et al., 2018; Su et al., 2019). In recent
years, researchers have also explored new emerging techniques for graph
representation learning, such as reinforcement learning (Bikos and Kumar,
2021), federated learning (Pei et al., 2022), and quantum computing approaches
(Akbar and Saritha, 2020; Kukliansky et al., 2024; Rosenhahn and Hirche,
2024). However, it is crucial to note that each method comes with varying
challenges, such as speed, computational complexity, and scalability.

Despite the advancements made with deep learning, modern deep-learning
frameworks are limited in their ability to process streaming data, and they
are tailored to handle data in the form of sequences, images, and grid data.
(Li and Leskovec, 2022; Liu et al., 2020). Despite their success, they are
susceptible to over-fitting and inductive errors when dealing with a large
number of parameters (Yarotsky, 2017; Liang et al., 2017).

Graph-based algorithms have demonstrated their effectiveness in capturing
changing relationships and dynamic changes between different structural parts
and features through embedding and model learning by mapping how nodes and
edges are connected (Pazho et al., 2022). Graphs are well-suited for dynamic
network tasks due to their inherent ability to effectively model
interconnected relationships and patterns among entities (such as nodes,
edges, and cliques) in both static and dynamic graphs.

Why use a GNN for Anomaly Detection?

Graph-based approaches are considered for several reasons, including but not
limited to the following:

  1. i.

Adaptation to Topological Structure: In anomaly detection, the topological
structure of dynamic graphs is important. Graph-based architectures, as
exemplified by ST-GCN (Yan et al., 2018), excel in this regard. They
dynamically propagate information through neighboring nodes, a feature
particularly valuable when the network’s structure evolves. This adaptability
stands in contrast to other deep learning architectures such as CNN (Gehring
et al., 2017), LSTM (Hochreiter and Schmidhuber, 1997), GAN (Goodfellow et
al., 2020) and ResNet (He et al., 2016), which often assume fixed inputs like
matrices or sequences.

  2. ii.

Integration of Multimodal Data: GNNs have demonstrated the capability to
integrate multimodal data with varying cardinalities and shapes, as proposed
in MGNN by Gao et al. in 2020 (Gao et al., 2020). This versatility is crucial
for handling diverse and complex information, often encountered in real-life
dynamic graph scenarios. Therefore, GNNs and graph-based models are most
suitable for enhancing the efficacy of anomaly detection across multimodal
data types.

  3. iii.

Scalability on Large-scale Networks: Deep GNNs have shown good scalability on
large-scale networks and complex graph representations. This was demonstrated
in GNNautoScale by Fey et. al. in 2021 (Fey et al., 2021). GNNautoScale
leverages the localized message-passing algorithms to prune entire sub-trees
of the computation graph by utilizing historical embeddings from prior
training iterations, leading to constant GPU memory consumption with respect
to input node size without dropping any data. Deep GNNs have proven effective
in scaling to handle the intricacies of dynamic networks, a key aspect in
anomaly detection for real-world graph networks.

  4. iv.

Efficiency in Model Interpretability: Graph-based approaches demonstrate high
efficiency in deep model interpretability and explainability. Recent
contributions include the works of Füßl et al. in 2022 (Füßl and Nissen, 2022)
on the interpretability of knowledge graphs and the interpretable learning of
dynamic graph-convolutional networks (GCNN) by Zhu et al. in 2022 (Zhu et al.,
2022). Graph-based interpretability has become particularly relevant in
anomaly detection tasks, where understanding and interpreting the model’s
decisions is crucial for practical deployment and decision-making.

  5. v.

Incorporation of Self-Attention and Transformers: Recent studies have
indicated that GNNs can be integrated with self-attention (Shaw et al., 2018)
and transformers (Vaswani et al., 2017) as special cases, highlighting their
adaptability. Examples include GAT by Velickovic et al.(Velickovic et al.,
2017) in 2017, Graph-Transformer by Yun et al. (Yun et al., 2019) in 2017, and
Graphomer by Ying et al. (Ying et al., [n. d.]) in 2021 (detailed explanations
are provided in Section 5 and Table 4). The adaptability of the Graph
Transformer is crucial for extending existing deep-learning architectures for
anomaly detection in dynamic graphs. GNNs can capture intricate patterns and
complex graph dependencies in dynamic networks, thereby enhancing their
anomaly detection capabilities.

###  1.1. Existing Surveys on Anomaly Detection

Previous survey studies done on anomaly detection (AD) have dealt with the
subject from different perspectives. Chandola et al. (Chandola et al., 2009)
provides a structural review on Anomaly detection, (Pang et al., 2021b, a;
Chalapathy and Chawla, 2019) focused on deep learning approaches. (Ruff et
al., 2021) conducts a unifying review that connects traditional shallow and
deep learning methods. (Thudumu et al., 2020; Habeeb et al., 2019) focuses on
anomaly detection on real-time big data. Some survey works capture specific
domains such as fake news detection in social networks (Ahmed et al., 2022),
financial domains (Ahmed et al., 2016), IoT and sensor networks (Kyle et al.,
2023), distributed systems (Pazho et al., 2022), time series (Ho et al.,
2023), etc. A recent study (Wang et al., 2021) focuses on attributed graph
queries, while (Ding et al., 2022a) conducts a review on data augmentation
approaches for deep graph representation learning, and (Waikhom and Patgiri,
2021) aims to classify graph-based semi-supervised learning techniques based
on their embedding methods (shallow graph embedding and deep graph embedding).
(Zhou et al., 2020) provides a broad pipeline of graph neural networks (GNNs)
and discusses the variants of each module. The survey also presents research
on both theoretical and empirical analyses of GNN architectures.

Despite the increasing number of surveys targeted at graph-based AD, most
techniques are focused on GNN models and anomaly techniques in static graphs.
Ranshous et al. (Ranshous et al., 2015) provides one of the first surveys on
anomaly detection in dynamic graphs. The article gives a broad overview on
data mining in dynamic networks by introducing four common variants of
anomalies associated with dynamic networks namely, node, edge, subgraph, and
event-level anomalies. The authors in (Ranshous et al., 2015) further
categorize graph-based models into five primary groups, originating from the
underlying ideas behind each approach: communities, compression,
decomposition, distance, and probabilistic model-based methods.

The authors in (Holme and Saramäki, 2012; Holme, 2015) provide an introductory
review of temporal networks, including an overview of methods, modeled
entities, and challenges associated with temporal networks, but with no
detailed analysis of the dynamic network evolution or algorithms pertaining to
real-world systems. Kazemi et al. (Kazemi et al., 2020) present a theoretical
approach to representation learning for dynamic graphs, with a focus on time-
dependent embedding techniques designed to capture the fundamental
characteristics of nodes and edges within evolving graphs.

Most recently, Skarding et al. (Skarding et al., 2021) provides an outline of
dynamic network models using GNNs. In this work, the authors categorize
dynamic models into statistical, stochastic actor-oriented, and dynamic
network representation learning. Furthermore, the authors in (Skarding et al.,
2021) captures the deep learning approaches for encoding a dynamic topology
and an overview of an encode-decoder framework in dynamic link prediction.
However, the techniques outlined in (Ranshous et al., 2015; Skarding et al.,
2021) do not provide separate explanations for each learning setting on static
and dynamic graphs.

In contrast to the existing works, our study offers a more comprehensive
survey of the current frameworks used for anomaly detection (AD) in dynamic
graphs. We organize the current methods for AD in dynamic graphs into four
categories: traditional machine-learning models, matrix transformations,
probabilistic approaches, and deep-learning approaches. We also provide a
chronological timeline of these dynamic graph models.

Furthermore, we present an in-depth discussion of the different ways dynamic
graphs are being represented in real-world data and a highlight of the current
datasets and metrics used in the literature.

Table 1. A Comparison Between Existing Surveys on Anomaly Detection. We mark
edge and sub-graph detection as in our survey because we review more deep
learning based works than any previous surveys.

Surveys Year Research Emphasis and Description Graph Graph Level Tasks Network
Based Node Edge Subgraph Types Chandola et al. (Chandola et al., 2009) 2009
Traditional AD techniques - - - - - Holme et al. (Holme and Saramäki, 2012)
2012 A study of temporal networks and dynamic graphs ✓ - - - Dynamic Holme et
al. (Holme, 2015) 2015 Methods for analyzing and modeling temporal networks. -
- - - Dynamic Ranshous et al (Ranshous et al., 2015) 2015 In-depth review of
Dynamic Graph AD up to 2015. ✓ ✓ ✓ ✓ Dynamic Ahmed et al. (Ahmed et al., 2016)
2016 Clustering based AD methods in Financial Domain - - - - - Yu et al. (Yu
et al., 2016) 2016 Social Media AD techniques ✓ - - - Static Habeeb et al.
(Habeeb et al., 2019) 2019 Real-time big data for AD - - - - - Thudumu et al.
(Thudumu et al., 2020) 2020 AD techniques for Big data - - - - - Zhou et al.
(Zhou et al., 2020) 2020 A review of DL & GNN for graph learning tasks ✓ - - -
- Kazemi et al. (Kazemi et al., 2020) 2020 Embedding techniques for dynamic
graph representation. ✓ - - - Dynamic Pang et al. (Pang et al., 2021b) 2021 DL
for Anomaly Detection - - - - - Pang et al. (Pang et al., 2021a) 2021 Deep AD
techniques - - - - - Wang et al. (Wang et al., 2021) 2021 Survey of attributed
graph queries ✓ - ✓ ✓ Static Ruff et al. (Ruff et al., 2021) 2021 Deep and
shallow learning for AD - - - - - Waikhom et al. (Waikhom and Patgiri, 2021)
2021 Survey on GNN models, applications, and learning techniques. ✓ - - -
Static Skarding et al. (Skarding et al., 2021) 2021 GNN & DGNN techniques for
dynamic graph. ✓ - ✓ - Dynamic Ahmed et al. (Ahmed et al., 2022) 2022 AD
techniques for Social Network Fake News - - - - - Pazho et al. (Pazho et al.,
2022) 2022 DAD & Graph-based AD in Distributed systems ✓ - ✓ - Dynamic Ding et
al. (Ding et al., 2022b) 2022 GNN & Data augmentation for deep graph learning
✓ - - - Static Ho et al. (Ho et al., 2023) 2023 DAD & Time Series AD
techniques ✓ ✓ ✓ ✓ - DeMedeiros et al. (Kyle et al., 2023) 2023 Deep AD
techniques in IoT and Sensor Networks ✓ - - - Both Our Survey (DGAD) 2023
Current AD techniques for Dynamic Graph (2016 -2023) ✓ ✓ ✓ ✓ Dynamic *AD:
Anomaly Detection, DL: Deep Learning, DAD: Deep Anomaly Detection, DGAD:
Dynamic Graph-Based Anomaly Detection *GADL: Graph Anomaly Detection with Deep
Learning, TSAD: Time Series Anomaly Detection Learning,

###  1.2. Proposed Framework and Structure

In Table 1, we present a comparative outline of existing surveys on anomaly
detection. The table outlines the method utilized in each study and highlights
common trends. The focus areas of these surveys are also examined,
distinguishing between static and dynamic contexts, and their coverage across
different domains is noted. Notably, the inclusivity of specific anomaly
patterns in graphs, such as nodes, edges, and sub-graph levels, is emphasized.

We aim to provide an overview of our survey categorization approach for
anomaly detection in dynamic graphs. This is illustrated in Figure 2. We will
provide a more detailed explanation of each individual component of our
framework in Section 5.

Figure 2.  An Overview of Survey Framework on Dynamic Graph-based Anomaly
Detection (DGAD).

###  1.3. Contributions

In summary, the contributions of this survey are as follows:

  * •

First, we provide a high-level overview of existing surveys on anomaly
detection, graph data mining, and graph representation learning, as presented
in Table 1.

  * •

We then introduce the concept of anomalies and discussed the three main types:
point, contextual, and collective anomalies. After that, we provide a detailed
mathematical definition of anomalies in both static graphs (including some
recent works) and dynamic graphs. This definition includes tasks at the node,
edge, and sub-graph levels, which are the most common graph-based tasks found
in the literature.

  * •

We further provide an extensive overview of the existing techniques and
methods used for detecting anomalies in dynamic graphs, along with a
comparative analysis of these methods. This is illustrated in Figure 2 and in
a detailed summary in Table 4.

  * •

Additionally, we discuss the representation of dynamic graph patterns in data,
covering both discrete and continuous graphs. See the summary in Table 3.

  * •

Finally, we discuss the potential challenges and future directions in dynamic
graph anomaly detection.

Given the current growth in graph-based research, our DGAD survey approach is
anticipated to be valuable to the graph-learning research community by
providing valuable resources for researchers and practitioners by summarizing
the strengths and limitations of each approach, highlighting current research
trends, and identifying open challenges.

The rest of the paper is organized as follows: Section 2 provides a background
study and important definitions of terminologies. In Section 3, we give an
overview of the architecture of graph neural networks (GNNs). Section 4
discusses the different representations of dynamic networks. Our survey
approach, DGAD methods, and application are presented in Section 5. In Section
6, we present datasets and evaluation metrics used in the literature. Finally,
in Section 7, we discuss the comparison, challenges, current trends, and
future directions of dynamic graph research.

##  2\. Background

In this section, we introduce the fundamental concept of anomalies, beginning
with an exploration of their types and definitions. Subsequently, we defined
anomalies in both static and dynamic graphs, paving the way for a
comprehensive understanding of anomalies in dynamic networks.

To enhance clarity, we will use the terms “graphs” and “networks”
interchangeably throughout this discussion.

###  2.1. Understanding Anomalies

Anomalies in real-world data manifest infrequently and come in diverse forms
and structures. They tend to be domain-specific, encompassing anomalies like
irregular intrusion patterns, fraudulent transactions, outliers in social
networks, and the detection of unusual patterns in industrial machinery, among
others. In line with existing survey by Chandola et al. (Chandola et al.,
2009), we categorize anomalies into three main types: point anomalies,
contextual anomalies, and collective anomalies, taking into account their
characteristics and prevalence in the data.

However, in 2.4, we will elaborate on various categories of anomalies,
specifically within graph data.

####  2.1.1. Point Anomalies

Also referred to as individual or atomic anomalies, point anomalies represent
data points that stand out from the typical or expected data distribution
within a dataset. These anomalies are typically isolated instances and do not
depend on the surrounding dataset. Detecting point anomalies often involves
applying statistical methods and predefined thresholds.

Among the common algorithms employed for point anomaly detection in the
literature is the Z-score (standard score) (Çelik et al., 2011), which
measures the degree of standard deviations a data point deviates from the
dataset’s mean. Additionally, density-based clustering algorithms are valuable
for grouping data points into individual clusters; this is shown in the works
of Almuzaini et al. (Almuzaini et al., 2010). In real-world situations, point
anomalies could be found in different domains, such as unusual fraudulent
transactions (Zhang et al., 2022b), unexpected data packets in a network
traffics such as F-FADE (Chang et al., 2021), DYNWATCH (Li et al., 2021),
MIDAS (Bhatia et al., 2022) and many others, abnormal medical diagnostic
results (Ahmedt-Aristizabal et al., 2021), abrupt changes in stock market
prices (Hooi et al., 2017), etc.

####  2.1.2. Contextual Anomalies

Also known as conditional anomalies, in this scenario, a data point exhibits
an anomaly within a particular context. The idea of context derives from the
inherent structure of the dataset. For instance, examining network traffic
patterns based on time, where an abrupt increase in multiple login attempts
occurs during non-business hours. Another example of a contextual anomaly
might arise if network traffic suddenly originates from an unusual geographic
location outside the company’s usual operational coverage, among other
scenarios.

Commonly used techniques for detecting contextual anomalies include
statistical models (Song et al., 2007), rule-based methods (Roy, 2010),
Gaussian threshold-based models (Wang et al., 2011), and machine learning,
just to name a few.

####  2.1.3. Collective Anomalies

Also referred to as group anomalies or global anomalies, collective anomalies
occurs when a subset of data instances or groups exhibits unusual patterns
that deviate from the entire data set. These kinds of anomalies focus on the
collective behavior of groups rather than isolated data points (Chandola et
al., 2009). Real-world examples can be found in coordinated distributed denial
of service (DDoS) attacks, where multiple computers collectively exhibit
malicious behavior. Another instance can be found in the work of Zhang et al.
((Zhang et al., 2024b)), who used Bayesian graph local extrema convolution for
bot detection in 2024. Their work addressed the detection of coordinated bot
attacks on social media platforms, specifically those aimed at propagating
fake news or engaging in online manipulation.

Frequently used methods in the literature, including clustering-based (Wang et
al., 2022), density-based (Na et al., 2018; Salehi et al., 2016), matrix
factorization methods (Sun et al., 2006; Teng et al., 2017; Yu et al., 2017),
and graph-based algorithms (Li et al., 2021; Fang et al., 2023; Gao et al.,
2023), have proven effective in recent research.

###  2.2. Anomaly Detection in Static Graph

In Section 1, we introduced the concepts of static graphs, which depict
networks with a fixed structure, and dynamic graphs, which evolve over time.
Here, we present the mathematical formulation for static graphs and the
definition of anomalies in static networks. We will also briefly review a
handful of pieces of literature in this area; however, it’s worth noting that
our survey does not focus on anomaly detection in static networks.

It is imperative to establish a more formal definition of the term “Graph” to
provide a precise conceptual foundation.

###### Definition 0.

A graph ${G}=(\mathcal{V},\mathcal{E})$ is defined as a pair consisting of a
set of nodes $\mathcal{V}$ and a set of edges connecting these nodes
$\mathcal{E}$. Here, $\mathcal{V}=\\{v_{1},v_{2},\ldots,v_{n}\\}$ represents
the node set, where each $v_{i}$ represents an individual node or vertex
within the graph. The set of edges, denoted by $\mathcal{E}$, is a subset of
the Cartesian product of $\mathcal{V}$ with itself, i.e.,
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$, and it defines the
relationships or connections between the nodes.

In a simple graph, we represent an edge from node $u\in\mathcal{V}$ to node
$v\in\mathcal{V}$ as $(u,v)\in\mathcal{E}$. A graph, denoted as ${G}$, can be
either undirected or directed in nature. In an undirected graph, an edge
$(u,v)$ forms an unordered pair of vertices, and the relationships between
nodes are symmetric. In contrast, in a directed graph (or digraph), each edge
has a specific direction, creating asymmetric relationships between nodes.

####  2.2.1.  What is an anomaly in a static graph?

Anomalies in static networks could be classified by the anomalous entities
that are spotted, such as nodes, edges, subgraphs, motifs, etc. We provide
formal definitions for anomalies within a static network in Definition 2.2 and
Definition 2.3.

###### Definition 0 (Node Anomaly in static graph:).

Given a static graph ${G=({V},{E})}$ from definition 2.1, with the node set
${V}$ and edge set ${E}$, we can define a node-level anomaly if there exists a
node $u\in{G}$ and a statistical measure denoted as
$\mathbb{N_{\omega}}(n)>\theta$, which exceeds a predefined threshold value
$\theta$.

In simpler terms, $\mathbb{N_{\omega}}(n)>\theta$ indicates that node
$\mathfrak{u}$ is anomalous in the graph ${G}$.

Furthermore, static networks can also be modeled as a static attributed graph
$G=(V,E,A_{e})$, where ${V}$ is the set of nodes, $E$ is set of edges with
$e\in{E}:e=(u,v)\hskip 5.69046pt\forall u,v\in V$. $A_{e}$ is the set of
attributes with edges, denoted as a function
$A_{e}:E\rightarrow\mathbb{R}^{n}$, where $n$ is the number of attributes per
edges. In other words, for all edges $e\in E$, the attribute matrix $A_{e}(e)$
provides an attribute vector.

###### Definition 0 (Edge Anomaly in Attributed static graph:).

Given an attributed static graph $G=(V,E,A_{e})$ as defined above, an edge
$e\in E$ is considered anomalous with respect to its attributes if it exhibits
a deviation from the expected attribute vector distribution of edges in the
entire graph $G$. Let $\mathbb{M}(A_{e}(e))$ denote the statistical measure of
deviation (e.g., standard deviation, Z-score) of a given edge $e$ from the
normal distribution of edge attributes, and if this deviation exceeds a
predefined threshold $\theta_{e}$, then $e$ is labeled as an anomalous edge.

####  2.2.2. Existing works in Static Graphs:

The majority of the proposed methods on graph data mining for unusual patterns
have largely focused on modeling static networks (You et al., 2022).

Among methods focusing on static graphs are CATCHSYNC (Jiang et al., 2016a) by
Jiang et al. on anomalous node detection. The model computes the node
characteristic features of the graph, putting into consideration the node
degree centrality and authoritative nodes (or Ego node), and subsequently
identifies nodes whose neighbors exhibit close proximity in the feature space.
In 2022, Liu et al. (Liu et al., 2022) proposed BOND, an unsupervised node
detection approach for static attributed graphs. BOND aims to evaluate the
performance of different GNN-based algorithms in detecting both structural and
contextual anomalies. Zhao et al. (Zhao et al., 2021) in 2021 developed the
PAMFUL framework, which synergistically combines pattern mining algorithms and
feature learning via a GNN encoder for graph anomaly detection, effectively
leveraging both local and global structural patterns. PAMFUL uses the GNN
encoder to perform feature aggregation and leverages the Random Walk algorithm
to capture the global pattern of the graph structure.

Wang et al. introduced the EGNN model (Gong and Cheng, 2019), an Edge Feature
in GNN that utilizes a Doubly Stochastic Edge Normalization instead of the
symmetric normalization approaches used in GCN (Kipf and Welling, 2016) and
GAT (Velickovic et al., 2017). By utilizing multi-dimensional positive-valued
edge features, EGNN (Gong and Cheng, 2019) eliminates the challenges faced by
GAT (Velickovic et al., 2017), which can only handle binary edge indicators,
and the limitations of GCN (Kipf and Welling, 2016), which can only handle
one-dimensional edge features.

Other frameworks targeted at static graph data include FRAUDAR (Hooi et al.,
2017) by Hooi et al., a Graph-Based Fraud Detection in the Face of Camouflage.
The FRAUDAR fraud detection algorithm incorporates the greedy algorithm and
density-based metrics to detect both camouflaged and non-camouflaged fraud in
real-world data. CATCHSYNC (Jiang et al., 2016b) by Jiang et al. is a graph
mining approach, a parameter-free and scalable method for automatically
detecting suspicious nodes in large directed graphs based on synchronized
behavior and rare connectivity patterns. Zhang and Chen (Zhang and Chen, 2018)
focus on link prediction based on Graph Neural Networks (GNN), where they
employ a heuristic approach involving the extraction of a local subgraph
around each target link and learning a function to map the subgraph pattern to
the existence of each link.

In 2021, You et al. (You et al., 2021) introduced the ID-GNN framework, a
class of message passing techniques called Identity-aware Graph Neural
Networks. ID-GNN extends existing GNN models by inductively incorporating
nodes’ identities into the message-passing process. When embedding a specific
node, ID-GNN starts by extracting the ego (or authority) network centered
around that node and subsequently conducts multiple rounds of heterogeneous
message passing. Throughout this procedure, distinct sets of parameters are
applied to the central node in contrast to the other nodes within the ego
network. Similar to You et al.’s work (You et al., 2021), Sengupta (Sengupta,
2018) developed an anomaly detection framework for static networks based on
statistical inferences using the egonet method. This approach is effective for
detecting anomalous cliques and subgraphs in static networks, with a two-step
process: firstly, detecting the presence of a small anomalous clique, and
secondly, identifying the node that forms the clique. Widely adopted graph
representation techniques, such as DeepWalk (Perozzi et al., 2014), Node2Vec
(Grover and Leskovec, 2016), and LINE (Tang et al., 2015), have demonstrated
their capability in generating node representations across graph networks and
have been used to validate the performance of anomaly detection (Ma et al.,
2021).

Recent and classical methods on anomaly detection on static graphs include
SCALA (He et al., 2024) by He et al., published in 2024, an unsupervised
multi-view contrastive learning approach for anomaly detection in attributed
networks. SCALA leverages the sparsification of networks, which filters the
abnormal relationships based on the similarity between the nodes. This
approach reduces the divergence on graph-level embedding caused by anomalous
nodes. In 2024, Xu et al. introduced ADVANCE (Xu et al., 2024), a novel view-
level unsupervised contrastive learning framework for detecting anomalies on
an attributed static graph. The framework combines graph contractive learning-
based and network reconstruction-based modules, improving anomaly detection
efficiency through the joint optimization of these complementary components.
This method offers strong assurance of the safety of consumer electronics. In
2023, Penghui et al. introduced LRAGAD (Penghui et al., 2023), a local
information recognition system for attribute graph anomaly detection. LRAGAD
employs anomaly score estimation to predict outliers based on the contextual
structural information of the graph. Simultaneously, it utilizes a deep self-
encoder to reconstruct both the structural and attribute information of the
static attribute graph by generating various substructures from the target
nodes.

In 2024, Jing et al. introduced SCN$\\_$GNN (Chen et al., 2024), a Strongly
Connected Nodes-Graph Neural Network designed for fraud detection. Their
approach proposes two node sampling strategies, incorporating strong node
information and graph topology information fusion. Specifically, it includes
the Structured Similarity-Aware Module (SSAM) for up-sampling sparse graph
nodes and the Strong Node Module (SNM) for down-sampling based on strong node
information and original features. These techniques enhance the detection of
neighboring nodes, adding value to the overall learning task.

Other classical anomaly detection approaches for static graphs include XGBOD
(Zhao and Hryniewicki, 2018), Bayesian models, spectral analysis, and
relational learning. Additionally, widely utilized standard graph neural
networks (GNNs) such as GraphSAGE (Hamilton et al., 2017), GAT (Huang et al.,
2021), PNA (Corso et al., 2020), RGCN, and specialized GNNs like CARE-GNN (Dou
et al., 2020), AMNet (Chai et al., 2022), and BWGNN (Tang et al., 2022) have
been prevalent in the field. For a more comprehensive exploration of static
graph approaches, it is recommended to consult GADBench, a recent benchmark
paper on supervised graph anomaly detection authored by Jainheng et al. (Tang
et al., 2024) in 2023.

While there exist several methods aimed at anomaly detection in static graphs
across various domains, we have chosen only to spotlight a select few as real-
world networks are dynamic in nature and constantly evolving, which is the
primary focus of this work.

###  2.3. Anomaly Detection in Dynamic Graph

Dynamic graphs are frequently used to model real-world networks, capturing
their ever-changing patterns and relationships. These changes can manifest
through the detection or addition of nodes, edges, or subgraphs. In this
section, we establish the mathematical formulation for dynamic graphs and
present the types of anomalies that can be found in them.

It is worth noting that throughout our survey, we use the terms “graph” and
“network” interchangeably to refer to the same evolving graph concept.
However, it is important to acknowledge that in some literature, the term
“graph” is more commonly used within the machine learning community, while
“network” is historically used in data mining and network science.

The full set of symbols and notations can be found in Table 2. In subsection
2.4, we start by introducing the three major anomaly tasks prevalent in the
dynamic graphs literature: node, edge, and subgraph-level tasks, along with
their corresponding mathematical representations.

###### Definition 0 (Dynamic graph:).

Given a graph $G=(V,E)$, where $V=\\{v_{1},\dots,v_{n}\\}$ is the node set and
$E\subseteq V\times V$ is the edge multi-set, a dynamic graph
$\mathcal{G}=\\{G_{t}\\}_{t=1}^{T}$ can be defined as a sequence of ordered
sets of graph snapshots at different time steps $t$, where $T$ is the total
number of time steps. Each snapshot is considered as a static graph
$G_{t}=(V_{t},E_{t}\subseteq(V_{t}\times V_{t}))$ with vertex set
$V_{t}=\\{v\in V\|i_{v}=t\\}$ and edge set $E_{t}=\\{e\in E\|i_{e}=t\\}$,
which may consist of plain or labeled edges.

Table 2. List of Notations Symbol |  Meaning
---|---
$G$ |  a graph with a set of nodes ${V}$ and edges ${E}$.
$V$ |  represents the node set $\\{v_{1},v_{2},\dots,v_{n}\\}$, where $v_{i}$ are individual vertices.
$E$ |  the set of edges.
$\mathcal{G}$ |  denotes a dynamic graph.
$G_{t}$ |  a sequence of snapshots $\\{G_{t}\\}_{t=1}^{T}$ at different time steps $t$.
$T$ |  the total number of time steps.
$V_{t}$ |  the vertex set for the graph at time point $t$.
$f:V\rightarrow\mathbf{R}$ |  a function that maps elements from the set of vertices $V$ to a real numbers $\mathbf{R}$
$\forall v^{\prime}\in V^{\prime}$ |  the condition applies to each vertex (or node) $v^{\prime}$ in the set $V^{\prime}$.
$E_{t}$ |  the edge set at time point $t$.
$|f(v^{\prime})-\hat{f}|$ |  the absolute difference between the score assigned to vertex $v^{\prime}$ by the scoring function $f(v^{\prime})$
$\Phi_{\omega}$ |  node-level anomalous scoring function
$\Phi_{e_{ij}(t)}$ |  edge-level anomalous scoring function

###  2.4. Types of Anomalies in Dynamic Graph

Anomalies can take on various forms within dynamic graphs due to the evolving
and dynamic nature of network data. In this context, we will explore common
types of anomalies, including node-level anomalies, edge anomalies, and sub-
graph or clique anomalies.

####  2.4.1. Node-level Anomalies:

The goal of anomalous node (or vertex) detection is to identify a group of
vertices or nodes where each vertex in this group exhibits a ’unique’ or
’unusual’ evolution when compared to the entire vertices within the graph
(Rida et al., 2022; Ranshous et al., 2015). In contrast to static graphs,
which only represent a single snapshot of the whole graph $G$, it is easy to
detect unusual nodes or vertices using techniques like degree centrality and
egonet density (Jiang et al., 2016a), density-based techniques (You et al.,
2021), and others. Dynamic graphs, on the other hand, allow the inclusion of
temporal dynamics in the evaluation of vertex behavior (Ranshous et al.,
2015). A formal definition is provided below.

###### Definition 0.

Node Anomaly in dynamic graph (from (Ranshous et al., 2015)) Given a dynamic
graph $G_{t}$, the total vertex set $V=\cup_{t=1}^{T}V_{t}$, and a specified
scoring function $f:V\rightarrow\mathbf{R}$, the set of anomalous vertices
$V^{\prime}\subseteq V$ is a vertex set such that $\forall v^{\prime}\in
V^{\prime}$, $|f(v^{\prime})-\hat{f}|>c_{0}$, where $\hat{f}$ is a summary
statistic of the score $f(v),\forall v\in V$.

Alternative Definition: Given a dynamic graph $\mathcal{G}_{t}$ at time $t$,
let $t$ belong to a set of discrete time points $T$, and let $v_{i}$ denote a
node in the dynamic graph $\mathcal{G}_{t}$ at time $t$. We utilize an
anomalous scoring function $\Phi_{\omega}=A(v_{i},t)$ to measure the deviation
of node $v_{i}$ at time $t$. Node $v_{i}$ is considered an anomalous node at
time $t$ if $A(v_{i},t)\geq\theta$. It’s important to note that nodes with a
scoring function $\Phi_{\omega}\geq\theta$ are classified as anomalous, and
$\theta$ represents the threshold for this classification.

####  2.4.2. Edge-level Anomalies:

Unlike node anomaly detection, edge-level anomaly detection focuses on
identifying unusual or irregular patterns in the edges or relationships
between elements in a network. A formal definition is provided below.

###### Definition 0.

Edge Anomaly in dynamic graph (from (Ranshous et al., 2015)) Given a dynamic
graph $G_{t}$, the total edge set $E=\cup_{t=1}^{T}E_{t}$, and a specified
scoring function $f:E\rightarrow\mathbb{R}$, the set of anomalous edges
$E^{\prime}\subseteq E$ is an edge set such that $\forall e^{\prime}\in
E^{\prime},|f(e^{\prime})-\hat{f}|>c_{0}$, where $\hat{f}$ is a summary
statistic of the scores $f(e),\forall e\in E$.

Alternative Definition: Given a dynamic graph $\mathcal{G}_{t}=(V,E_{t})$,
where $V$ is the set of vertices, and $E_{t}$ is the set of edges at time $t$,
each edge $e_{ij}(t)\in E_{t}$ represents a tuple $(i,j)$ at time $t$. Let the
edge-level scoring function be $\Phi_{e_{ij}(t)}=f(e_{ij}(t))$, an edge-level
anomaly is detected in $\mathcal{G}_{t}$ when the scoring function
$\Phi_{e_{ij}(t)}>\theta$ exceeds a predefined threshold $\theta$.

####  2.4.3. Subgraph-level Anomalies

In subgraph-level anomaly detection, the focus is on identifying anomalous
subgraphs or community structures within the dynamic graph. These structures
might exhibit characteristics, behaviors, or patterns that deviate from what
is typical in the evolving graph. Some common types of network subgraphs or
cliques include triangles, quadrilaterals, and bipartite subgraphs (Yuan et
al., 2023). Subgraph anomalies can be found in a wide range of biological
(Yuan et al., 2023), fruadulent (Zhang et al., 2022b), social (Eswaran et al.,
2018), technological networks (Bhatia et al., 2021), etc.

###### Definition 0.

Subgraph Anomaly in dynamic graph (from (Ranshous et al., 2015)) Given a
dynamic graph $G_{t}$, a subgraph set $H=\cup_{t=1}^{T}H_{t}$, where
$H_{t}\subseteq G_{t}$ and a specified scoring function
$f:H\rightarrow\mathbb{R}$, the set of anomalous subgraphs
$H^{\prime}\subseteq H$ is a subgraph set such that $\forall h^{\prime}\in
H^{\prime},|f(h^{\prime})-\hat{f}|>c_{0}$, where $\hat{f}$ is a summary
statistic of the scores $f(h),\forall h\in H$.

###  2.5. New and Emerging Anomaly Variants in Dynamic Graphs

Recent real-world dynamic social networks have experienced new and emerging
anomaly variants beyond the basic types (node, edge, and subgraph anomalies).
Here we will explore some additional types of anomalous patterns in dynamic
graphs.

####  2.5.1. Attribute-based Anomalies:

This analyzes node or edge attributes or features beyond just their
connections. Deviations from expected attribute values, such as a sudden
change in a user’s location or purchase behavior, could indicate anomalies.

In real-world scenarios, diverse sets of information can be modeled as
attributed graphs (Liu et al., 2022), incorporating structural relationships
and attribute information. Consider the Twitter (or X) social network. For
instance, users are connected through various social relationships, and they
possess multiple profile details like age, gender, location, and income. This
is illustrated in the work of Xuexiong et al.(Luo et al., 2022), titled
“ComGA: Community-Aware Attributed Graph Anomaly Detection.” The authors
consider graph anomalies in attributed graphs as local, global, and structural
anomalies, which makes it beneficial to spot existing structural and complex
anomalous nodes. Anomalies in this kind of graph network are different from
normal node-level anomalies in both structural and attribute aspects. Hence,
we classify this kind of diversity in graph networks as attribute-based
anomalies.

###### Definition 0.

Attribute-based Anomaly in Dynamic Graph Given an attributed graph as
$G=(V,E,X)$, with the vertex set $V=\cup_{t=1}^{T}V_{t}$ and the total edge
set $E=\cup_{t=1}^{T}E_{t}$. Let $A$ be the set of attributes associated with
the vertices $V$, and $f:V\times A\rightarrow\mathbf{R}$ be the specified
scoring function that evaluates the vertex-attribute pair. The set of
attribute-based anomalous vertices $V^{\prime}_{\text{attribute}}\subseteq V$
is defined such that for every vertex $v^{\prime}\in
V^{\prime}_{\text{attribute}}$ and associated attribute $a\in A$, the anomaly
score function with a threshold $C_{\text{attribute}}$ is defined as:
$|f(v^{\prime},a)-\hat{f}|>C_{\text{attribute}}$, where $\hat{f}$ is a summary
statistic of the score $f(v,a)$ for all $v\in V$ and $a\in A$.

####  2.5.2. Context-aware Anomaly:

This kind of anomaly incorporates additional or contextual information,
thereby providing a broader understanding of the dynamic behavior of graph
network data, such as time-series data or external events. Context-aware
anomalies can manifest in various forms, including temporal information (such
as time-series data, timestamps, and seasonal changes) and external events
(such as weather conditions, holidays, and news events). Additionally, these
anomalies may be observed in multimodal data, such as sensor readings and
video footage, as shown in the work of Kim et al. (Kim and Kim, 2023) on
contextual anomaly detection for high-dimensional data with a variational
autoencoder.

Real-world scenarios of context-aware anomalies are evident in historical and
temporal changes in network traffic data (Chang et al., 2021), involving
factors like packet size and source and destination IP addresses within
different timestamps (hours, days, weeks, etc.). Another context-aware anomaly
example can be found in user purchase history and product ratings within
Recommender Systems (Zhang et al., 2022b). The relevant context in this
scenario includes temporal changes and user demographics, such as age,
location, and browsing history.

####  2.5.3. Community Anomaly:

This kind of anomaly in dynamic graph networks focuses on groups of nodes that
exhibit unusual and collective behaviors deviating from the typical community
structure of the network. While individual nodes or edges within the community
might not be inherently anomalous, the combined deviation of the entire
community suggests an anomaly. Real-world scenarios include a sub-community
within an online social platform that exhibits abnormal posting patterns (Fan
et al., 2019) and a group of individuals in a specific geographic location
showing an unusual pattern of disease infection compared to the surrounding
areas (Yuan et al., 2023).

Community anomalies differ from subgraph anomalies; the latter tends to focus
more on specific substructures or subgraphs of the network that deviate from
the expected pattern. In contrast, community anomalies focus on the collective
behavior of nodes within the network community, considering group-level
dynamics.

Another example of community anomalies can be observed in a research group
within a collaboration network, which shows significantly fewer connections
outside their group domain compared to other research groups, suggesting a
lack of collaboration with other groups.

####  2.5.4. Multi-Layer Anomaly:

Multi-layer anomalies arise when graph networks have multiple layers of
information, where each layer represents a different type of data (e.g.,
social network connections and communication data). Anomalies might arise from
inconsistencies or unusual interactions between the layers. Detecting multi-
layer anomalies in dynamic graphs has gained increased attention in recent
years. Recent techniques include the 2023 works of Xie et al. (Xie et al.,
2023) on multi-view change point detection, and MultiLAD by Huang et al.
(Huang et al., 2023a). MultiLAD leverages the Laplacian approach to detect
change point anomalies in multi-view dynamic graphs. Bhatia et al. (Bhatia et
al., 2021) also proposed MSTREAM in 2021 for multi-aspect stream anomaly
detection.

Identifying multi-layer anomalies can be challenging due to inconsistent
attributes in data, unexpected interactions in graph layers, and the evolving
nature of the network. However, in order to detect such anomalies, researchers
need to go beyond traditional methods by considering the richness and
complexity of multi-layered graph data.

Summary: It is important to note that different types of anomalies in dynamic
graphs are network-dependent, and they tend to address diverse aspects,
including individual node behavior (node anomalies), relationships and
connections (edge anomalies), structural patterns (i.e., an overall change of
the graph structure), attribute information (i.e., attribute-based anomalies),
community patterns, context of the network, multi-layer interactions, and
overall graph structure. Detecting these anomalies requires specialized
approaches tailored to the unique characteristics of each anomaly type,
emphasizing the need for comprehensive anomaly detection methods in dynamic
graph analysis.

##  3\. Graph Neural Networks Overview

In this section, we will introduce the concept of a graph neural network
(GNN), which is a general architectural framework for modern deep graph
learning representations. (Readers already familiar with the architecture of a
GNN can skip this section.) In 1997, Sperduti et al (Sperduti and Starita,
1997) applied the concept of neural networks to directed acyclic graphs, which
sparked the first research in this area. A GNN was first proposed in the work
by Gori et al. (Gori et al., 2005) in 2005 and subsequently expanded upon in
the research by Scarselli and their team in 2009 (Scarselli et al., 2008), as
well as by Gallicchio et al. in 2010 (Gallicchio and Micheli, 2010). These
initial variants are classified as recurrent graph neural networks (RecGNNs).

###  3.1. The Basic GNN Architecture

The core idea of graph neural networks (GNNs) involves generating suitable
node representations that depend on the graph structure and feature
information. GNNs learn a node’s embedding by iteratively encoding its
neighboring information into target nodes until a stable fixed vector point is
established. The embedding space can be used for several downstream tasks,
such as node classification, link prediction, and anomaly detection.

GNNs are designed to work with graph data structures, unlike classical deep
learning models such as CNN and LSTM, (Li and Leskovec, 2022) which are
optimized for sequences of images, grids, and text. The basic GNN models have
been derived as a generalization of convolutions to non-Euclidean data
(Hamilton, 2020), and they rely on two fundamental principles: the message-
passing mechanism and the information-aggregation function.

Figure 3.  An Overview of how a single target node $U$ aggregates messages
from its local neighborhood (recreated from Leskovec et al. lecture slide
(Leskovec, [n. d.])). Given an input graph, the model computes the
neighborhood embedding $h_{U}^{(2)}$ by aggregating the messages from $U$’s
local neighbors (nodes $Z,Y,V$), and these incoming messages are based on the
information aggregated from their respective layers’ representations,
$h_{Z}^{(1)}$ for node $Z$, $h_{Y}^{(1)}$ for node $Y$, and $h_{V}^{(1)}$ for
node $V$.

###  3.2. GNN Message Passing

In GNNs, message passing is the fundamental mechanism by which information is
propagated and aggregated throughout the graph structure to learn
representations for nodes or edges. The core concept of message-passing is
that, in each iteration, nodes aggregate information from their nearby
neighbors (Hamilton, 2020). As these iterations continue, the node embeddings
become increasingly updated about distant portions of the graph, which is
often referred to as the ”k-hops neighborhood.” The ”k” in ”k-hops
neighborhood” refers to the number of hops or steps away from a given node in
a graph. The k-hop neighborhood of a node includes the node itself, all its
immediate neighbors (1-hop), their neighbors (2-hops), and up to k-hops. In
Figure 3, for node U, $k=2$-hops with local neighbors (nodes $Z,Y,V$). In
simpler terms, over time, a node’s embedding contains information not only
about its immediate neighbors but also about the features of nodes further
away in the graph.

In every phase of GNNs message passing, a hidden embedding layer
${h}_{u}^{(k)}$ for each node $u\in V$ undergoes an update that relies on the
information accumulated from the neighborhood $\mathcal{N}(u)$ of $u$. A
single-layer message passing is depicted in Figure 3, and its mathematical
representation is given by Equations 1 and 2. At the initial phase $k=0$, the
node embedding is ${h}_{u}^{0}=x_{u},\forall u\in V,$

(1)
$m_{\mathcal{N}(u)}^{(k)}=\boldsymbol{f}_{\textit{aggregate}}^{(k)}\left({h}_{v}^{(k)}:\forall
v\in\mathcal{N}(u)\right),$

(2)
${h}_{u}^{(k)}=\boldsymbol{f}_{\textit{update}}\left({h}_{u}^{(k-1)},m_{\mathcal{N}(u)}^{(k)}\right),$

where $m_{\mathcal{N}(u)}^{(k)}$ is the message-passing function that
aggregates the neighborhood $\mathcal{N}(u)$ of node $u$, ${h}_{u}^{(k)}$ is
the updated hidden embedding of node $u$ at layer $k$, and ${h}_{u}^{(k-1)}$
is the hidden embedding of node $u$ from the previous layer $k-1$. At each
step $k$, the aggregation function $\boldsymbol{f}_{\textit{aggregate}}$ in
Equation 1 takes the set of embeddings ${h}_{v}^{(k)}$ for all neighbors
$v\in\mathcal{N}(u)$ as input and generates an aggregated message for the
neighborhood $\mathcal{N}(u)$. The update function
$\boldsymbol{f}_{\textit{update}}$ in Equation 2 updates the message
$m_{\mathcal{N}(u)}^{(k)}$ with the previous embedding $h_{u}^{(k-1)}$ of node
$u$ to generate the current embedding $h_{u}^{(k)}$.

###  3.3. GNN Aggregation

The aggregation function is also a critical component of the message-passing
process as shown in equation 1. It defines how the node neighborhood
information is combined into a single fixed vector or target node. There are
several aggregation methods depending on the GNN variants. The following are a
few of them.

####  3.3.1. Sum and Mean Aggregation

These techniques were employed within GraphSAGE (Hamilton et al., 2017) GNN
variation. In the case of sum aggregation, the information passed between
nodes is straightforwardly added up. In mean aggregation, it involves
computing the average of messages originating from node u’s neighbors. Sum and
mean aggregation are simple to implement, computationally efficient, and
suitable for capturing global graph properties, as illustrated in the works of
Shiyi et al. (Huang et al., 2023b) on capturing molecular-level (global)
message passing in a GNN. However, sum and mean aggregation may be limited in
preserving node-specific information and sensitive to outliers in dynamic
graph networks. The mathematical expressions for the sum and mean aggregation
are illustrated in Equations 3 and 4 respectively:

(3)
$\boldsymbol{f}_{\text{aggregate}}\left(\\{h_{u}:u\in\mathcal{N}(v)\\}\right)=\sum_{u\in\mathcal{N}(v)}h_{u},$

(4)
$\boldsymbol{f}_{\textit{aggregate}}\left(\\{h_{u}:u\in\mathcal{N}(v)\\}\right)=\frac{1}{\mathcal{N}(v)}\sum_{u\in\mathcal{N}(v)}h_{u},$

where $\boldsymbol{f}_{\text{aggregate}}$ is the aggregation function, and the
expression $\\{h_{u}:u\in\mathcal{N}(v)\\}$ is the set of embeddings of the
neighbors of node $v$. Here, $h_{u}$ represents the embedding of neighbor $u$,
and $\mathcal{N}(v)$ denotes the set of all neighbors of node $v$. In Equation
3, $\sum_{u\in\mathcal{N}(v)}h_{u}$ denotes the summation operation over all
neighbors $u$ in the neighborhood $\mathcal{N}(v)$ of node $v$, and in
Equation 4, $\frac{1}{|\mathcal{N}(v)|}$ is the normalization factor, which is
the inverse of the number of neighbors of node $v$. This factor ensures that
the mean aggregated embedding is the average of the neighbors’ embeddings.

####  3.3.2. Graph Convolutional Network (GCN) Aggregation

This technique was first introduced in the GCN paper by Kipf et al. (Kipf and
Welling, 2016). GCN aggregations are most suitable for GNN tasks involving the
normalization of node-level graph tasks; they have also been shown to be
effective in semi-supervised learning tasks (Kipf and Welling, 2016), as
illustrated in Graph Convolutional Extreme Learning Machines by Zhang et al.
(Zhang et al., 2023a). The major limitation of GCN aggregation is that it
struggles with capturing long-range dependencies. The mathematical expression
for GCN aggregation is illustrated in Equation 5 below:

(5)
$\boldsymbol{f}_{aggregate}\left(\\{h_{u}:u\in\mathcal{N}(v)\\}\right)=\frac{1}{\sqrt{|\mathcal{N}(v)|\cdot|\mathcal{N}(u)|}}\sum_{u\in\mathcal{N}(v)}Wh_{u},$

where $\boldsymbol{f}_{\text{aggregate}}$ is the aggregation function, the
expression $\\{h_{u}:u\in\mathcal{N}(v)\\}$is the set of embeddings of the
neighbors of node $v$, $h_{u}$ denotes the embedding of neighbor $u$, and
$\mathcal{N}(v)$ denotes the set of all neighbors of node $v$. The fraction
$\frac{1}{\sqrt{|\mathcal{N}(v)|\cdot|\mathcal{N}(u)|}}$ is the normalization
factor, which is the inverse of the square root of the product of the degrees
of nodes $v$ and $u$. This factor helps to scale the contributions of
neighboring nodes appropriately. $\sum_{u\in\mathcal{N}(v)}Wh_{u}$ is the
summation operation over all neighbors $u$ in the neighborhood
$\mathcal{N}(v)$ of node $v$, where $W$ is the learnable weight matrix applied
to the embeddings $h_{u}$ of the neighbors.

The GCN aggregator in Equation 5 is different from the sum and mean
aggregators in Equations 3 and 4 because it has a normalization factor and a
weight matrix that can be learned. This allows it to scale the contributions
of neighboring nodes and learn weighted representations, thereby enhancing its
ability to capture complex node relationships.

####  3.3.3. Graph Attention (GAT) Aggregation

This approach was initially introduced in the Graph Attention paper by
Velickovic et al. (Velickovic et al., 2017). In this method, messages are
assigned weights based on attention scores before they are aggregated. GAT
aggregations are suitable for tasks where capturing influential node degrees
is important, and situations where an attention mechanism is used to improve
GNNs, such as node classification with graph attention (Velickovic et al.,
2017), node prediction with graph transformers (Chen et al., 2021), and node
and subgraph detection in hybrid-order graphs (Huang et al., 2021). Another
strength of GAT aggregation is the adaptability in capturing different
importance levels of node neighbors. However, they are computationally more
expensive compared to simple aggregations (sum and mean), and they could be
sensitive to hyperparameter choices. The mathematical expression for GAT
aggregation is illustrated in Equation 6 below:

(6)
$f_{\textit{aggregate}}\left(\\{h_{u}:u\in\mathcal{N}(v)\\}\right)=\sum_{u\in\mathcal{N}(v)}\text{softmax}(e_{uv})h_{u},$

where $\boldsymbol{f}{\textit{aggregate}}$ is the aggregation function,
${h_{u}:u\in\mathcal{N}(v)}$ represents the set of embeddings of the neighbors
of node $v$. Here, $h_{u}$ denotes the embedding of neighbor $u$, and
$\mathcal{N}(v)$ denotes the set of all neighbors of node $v$. The
$\text{softmax}(e{uv})$ is the attention coefficient for the edge between
nodes $u$ and $v$, computed using the softmax function. This coefficient
determines the importance of node $u$’s contribution to node $v$. The sum
$\sum_{u\in\mathcal{N}(v)}$ represents the summation operation over all
neighbors $u$ in the neighborhood $\mathcal{N}(v)$ of node $v$, and $e_{uv}$
is the attention score for the edge between nodes $u$ and $v$, which is
typically computed as a function of the embeddings of nodes $u$ and $v$.

The GAT aggregation in Equation 6 is superior to mean, sum, and GCN
aggregation because it assigns different importance to each neighbor using
attention coefficients (Luong et al., 2015), allowing it to dynamically focus
on the most relevant neighbors and capture more nuanced relationships within
the graph.

Other aggregation functions, such as LSTM Aggregation employed for sequential
message passing, were utilized in GraphSAGE (Hamilton et al., 2017). The LSTM
aggregation is mostly suitable for dynamic graph tasks with temporal
dependencies and is also applicable in sequential tasks in graph
representation learning. This is illustrated in AddGraph by Zheng et al.
(Zheng et al., 2019) for capturing node and edge structural information and
temporal dependencies in evolving graphs. However, they could be
computationally intensive compared to simple aggregations.

It is important to emphasize that the choice of aggregation function is
dependent on the GNN framework utilized and the nature of the graph-related
problem at hand. In the literature, researchers often explore various
functions to enhance performance.

Basic GNN Message Passing: Equations 1 and 2 offer a high-level perspective on
the Aggregation and Update functions within GNN frameworks. The message
passing mechanism in the original GNN model, as introduced by Gori et al.
(Gori et al., 2005) and Scarselli et al. (Scarselli et al., 2008), is formally
expressed in Equation 7:

(7)
$h_{u}^{(k)}=\sigma\left({W}_{\textit{self}}^{(k)}h_{u}^{(k-1)}+{W}_{\textit{neighbor}}^{(k)}\sum_{v\in\mathcal{N}(u)}h_{v}^{(k-1)}+{b}^{(k)}\right),$

where $h_{u}^{(k)}$ denotes the updated embedding of node $u$ at layer $k$,
$h_{u}^{(k-1)}$ is the node embedding of $u$ from the previous layer $k-1$,
${W}_{\textit{self}}^{(k)}$ and ${W}_{\textit{neighbor}}^{(k)}$ are trainable
weights in $\mathbb{R}^{d^{(k)}\times d^{(k-1)}}$, and $\sigma$ represents the
non-linear function, such as ReLU or tanh. As in other deep learning models,
$b^{(k)}$ serves as the bias term at layer $k$. The key idea underlying basic
GNN message passing, as described in Equation 7, is its analogy to the
standard multi-layer perceptron (MLP) (Hamilton, 2020). This analogy stems
from its reliance on linear operations followed by a single element-wise non-
linearity.

For a deeper understanding of the GNN framework, including the intricacies of
message passing, self-loop operations, and generalized neighborhood
aggregation in Graph Neural Networks (GNNs), we recommend referring to the
work by Hamilton (Kazemi et al., 2020) which provides comprehensive insights
into these concepts.

Deep Graph Neural Network (GNN) node embedding representations have
demonstrated remarkable success in tackling various network-related tasks.
Some of these tasks are node classification, which involves labeling nodes
with their corresponding categories; link prediction, which detects patterns
in densely connected node clusters; and network similarity assessment, which
measures how similar are different sub-networks.

##  4\. Dynamic Graph Representation

Dynamic graph networks in real-world scenarios include social networks
(facilitating the spread of news or information among friends), transportation
(monitoring traffic flow on roads), financial (tracking the movement of money
through an economy), network traffic, electricity grid dynamics, and
biological processes. These networks can be represented in diverse ways, and
the success of graph learning tasks relies heavily on the topology or
structure of the networks, specifically the arrangement of nodes and edges
(Skarding et al., 2021).

Dynamic systems come in discrete-time and continuous-time forms and may
exhibit either deterministic or stochastic characteristics (Newman, 2018). In
these sections, we provide details on the dynamic graph representation.

Table 3. Comparison of Dynamic Graph Representations: Discrete vs. Continuous Networks Dynamic layouts |  Temporal Properties |  Network Types
---|---|---
Discrete |  Distinct time & Fixed intervals, Sparse changes, represent abstract relationships |  Snapshots, Time Slices, incremental updates
Continuous |  Event-based, Continuous evolution, represent spatial relationships |  Graph Streams, Transitioning graphs

###  4.1. Discrete Representation

A discrete graph representation tends to model a system where the
relationships between entities change over time in a discrete manner (Newman,
2018). In such graphs, the structure of the graph evolves at distinct time
steps, or snapshots, to capture the dynamic nature of the network. A discrete
representation is illustrated in Figure 1 and shown in Equation 4 as

(8) $\mathcal{G}=\\{G^{1},G^{2},\dots,G^{T}\\},$

where $G^{i}$ represents graph snapshots, and ${T}$ denotes the sequence of
time steps for each snapshots.

Modeling dynamic networks as graph snapshots allows for static analysis at
individual time steps and, collectively, provides insights into the entire
network (Skarding et al., 2021). Several dynamic graph algorithms capture
snapshots using techniques such as sliding windows (Yuan et al., 2023), multi-
layered networks (You et al., 2022; Goyal et al., 2018; Liu et al., 2021), the
spectrum of Laplacian matrix or tensors (Huang et al., 2020), first-order
Markov process (Wang et al., 2017), and many more. See Section 5 for details
on how these techniques apply the snapshot approach in modeling dynamic
graphs.

###  4.2. Continuous Representation

A continuous graph representation, on the other hand, extends traditional
graph structure to model systems where relationships between entities evolve
continuously over time as opposed to discrete time steps. A continuous
representation captures exact temporal information and is more complex to
model mathematically (Skarding et al., 2021). This representation is
particularly relevant in applications such as neuroscience, physics, the
spread of infectious diseases, and social dynamics, where changes in
connections or attributes of graph elements occur smoothly and continuously.
We illustrate the evolution of a continuous graph in Figure 1.

Mathematically, the continuous evolution of graph networks is frequently
modeled based on network topologies, and the continuous graph evolution can be
described through differential equations, integrals, or other mathematical
frameworks. Let $\mathcal{G}(t)$ be a continuous graph representation with a
set of nodes $V(t)$ and edges $E(t)$ at time $t$. The evolution of a graph can
be modeled by a system of differential equations

(9) $\derivative{V}{t}=f_{V}(V,E,t),$

(10) $\derivative{E}{t}=f_{E}(V,E,t),$ (11)
$\derivative{W}{t}=f_{W}(V,E,W,t),$

where $W(t)$ represents the edge weight function at time $t$, $f_{V}$,
$f_{E}$, and $f_{W}$ are functions describing the continuous changes of
vertices, edges, and edge weights, respectively. For more details, we have
highlighted the comparison of discrete and continuous dynamic graph
representations in Table 3.

###  4.3. Hybrid Representation

In subsections 4.1 and 4.2, we introduced two distinct approaches to dynamic
graph representation: discrete and continuous. While discrete representation
tends to model the qualitative aspects of the network interactions and
transitions per timestep, continuous representation focuses on modeling the
quantitative aspects of the dynamic graph entities as they evolve continuously
over time. This includes capturing evolving and temporal information over
timestamps as opposed to discrete time snapshots.

In emerging complex graph networks, there is a possibility of a hybrid
representation that serves as a bridge between the qualitative and
quantitative dimensions of graph networks. A hybrid graph representation
allows for the seamless integration of both discrete and continuous
information. This mapping facilitates a holistic understanding of dynamic
graph behavior, enhancing the ability to detect anomalies that may manifest in
various forms.

Real-world instances of hybrid representations include (1) Event-driven
anomaly detection in financial systems by considering discrete irregularities
and continuous fluctuations in market behavior; this is illustrated in the
works of Wu et al. (Wu et al., 2021) on multivariate time-series. (2) Anomaly
detection and fault diagnosis in smart grids by considering both discrete
disruptions and continuous variations in power grid systems; this was shown in
the works of Li et al. (Li et al., 2021) DYNWATCH in 2021. (3) Sensor network
detection in environmental monitoring by considering both sudden changes in
sensor status and temporal variations (Kyle et al., 2023). This scenario can
also be found in cyber-physical systems for detecting polymorphic malware
(malicious attacks that can change its code) and intrusion attempts; this is
shown in the works of Jeffrey et al. (Jeffrey et al., 2024) in 2024.

##  5\. Anomaly Detection Methods

In this section, we aim to introduce and compare different Dynamic Graph-Based
Anomaly Detection (DGAD) methods.

In our survey approach, we categorize our DGAD methods into four major groups
based on their respective approaches and core algorithms for identifying
anomalous patterns in dynamic graphs. These groups include traditional machine
learning-based, matrix transformation, probabilistic, and deep learning
methods. We further subdivide these categories to provide a more narrow
description of the algorithms. It is important to note that certain methods in
our survey topology in Figure 2 and Table 4 may overlap with other groups.
Nevertheless, our survey aims to capture recent trends in anomaly detection
techniques for dynamic graphs while also highlighting commonly used dynamic
graph datasets and evaluation metrics.

The summary of the current papers, paper descriptions, specific graph learning
tasks, the datasets utilized, and the evaluation metrics are presented in
Table 4.

###  5.1. Traditional Machine Learning Methods

Traditional machine learning (ML) methods for anomaly detection involve the
use of established algorithms and techniques (Ma et al., 2021). These methods
rely on predefined rules or patterns to identify anomalies in datasets.
Examples of these techniques include statistical, tree-based, clustering,
distance-based approaches, and many others. Over the decade, traditional ML
techniques have proven to be effective for many downstream tasks, such as
anomaly detection and link prediction in graphs; however, they are faced with
challenges in handling high-dimensional or complex graph data, and more
advanced methods are often considered in such cases.

In our survey, we categorize the traditional ML methods into tree-based,
density-based, and distance-based. (See Table 4 for details.)

####  5.1.1. Tree-based and Density-based Methods

Tree-based and density-based anomaly detection methods are two distinct
approaches for detecting anomalies. Tree-based methods involve constructing a
decision tree or an ensemble of decision trees, such as Random Forest or
Isolation Forest, to isolate and identify anomalies (Na et al., 2018; Salehi
et al., 2016). While density-based methods focus on identifying anomalies
based on the density of data points in the feature space. Density-based models
include DBSCAN (Density-Based Spatial Clustering of Applications with Noise),
LOF (Local Outlier Factor), and One-Class SVM (Support Vector Machine) (Liu et
al., 2008; Hariri et al., 2019).

The Local Outlier Factor (LOF) (Breunig et al., 2000) is one of the most
popular density-based algorithms. It works by measuring the local density of
each data point and identifying anomalous points with significantly lower
densities compared to their neighbors. This approach is mostly used in
scenarios where the traditional distance-based approach may not perform well,
such as non-uniformly distributed data points. MiLOF (Salehi et al., 2016), an
incremental local outlier detection algorithm, expands LOF for data streams.
To address the memory issue and the limitation of detecting long sequences of
outliers, DILOF (Na et al., 2018) improved upon the LOF (Breunig et al., 2000)
and MiLOF (Salehi et al., 2016) algorithms by adopting a novel density-based
sampling algorithm to summarize past data and a new strategy for detecting
outlier sequences. Recently, Goodge et al. (Goodge et al., 2022) introduced
LUNAR, a hybrid approach that combines deep graph neural networks (GNN) and
LOF to learn information from the nearest neighbors of each node in a
trainable manner for anomaly detection. However, these techniques are most
effective when dealing with data of lower dimensions, as they are susceptible
to the curse of dimensionality when applied to higher-dimensional data.

####  5.1.2. Distance-based

Distance-based anomaly detection techniques in dynamic graphs propose certain
time-evolving measures of dynamic network structures and leverage the change
rates of those measures to detect anomalies. These methods focus on tracking
how network properties evolve over time and identifying deviations indicative
of unusual network behavior.

StreamSpot (Manzoor et al., 2016) is a clustering-based AD approach that
utilizes a novel similarity function for heterogeneous graphs in real-time
from a continuous stream of typed edges. This framework is tailored to process
temporal graphs with categorically designated nodes and edges while
simultaneously upholding the efficacy of graph sketches and clustering
configurations. StreamSpot employs a shingling-based similarity function to
create graph sketches that capture structural information, enabling memory-
efficient comparisons. In addition, StreamSpot further encompasses strategies
for the progressive upkeep of these sketches and clustering arrangements,
adapting to the dynamic nature of incoming edge data. Empirical validation of
StreamSpot is conducted via quantitative assessments on synthesized datasets
encompassing both normal and abnormal activities. StreamSpot obtains over a
$90\%$ average precision on approximately $25M$ system log streaming edges,
while the overall performance decreases as memory is constrained (i.e.,
detection is delayed). However, the running time and recovery decays are slow
for high-volume streams, making the approach less scalable.

Eswaran Dhivya et al. (Eswaran and Faloutsos, 2018) proposed SedanSpot, a
randomized algorithm for anomaly detection in edge streams. It uses a holistic
random walk-based edge anomaly scoring function to compare an incoming edge
with the whole (sampled) graph, emphasizing the importance of far-away
neighbors. SedanSpot detects edges that connect sparsely connected parts of a
graph, and it identifies edge anomalies based on edge occurrence, preferential
attachment, and mutual neighbors. As an improvement to SedanSpot, Eswaran et
al. (Eswaran et al., 2018) proposed SpotLight, a randomized sketching-based
method for detecting sudden changes in dynamic graphs and detecting the
appearance and disappearance of dense subgraphs or bi-cliques using sketching.
SpotLight guarantees that an anomalous graph is mapped ‘far’ away from
‘normal’ instances in the sketch space with a high probability for an
appropriate choice of parameters. This is done by creating a K-dimensional
sketch that comprises K subgraphs, thereby enabling the detection of sudden
changes within the dynamic graph.

Compared to SedanSpot (Eswaran and Faloutsos, 2018), which relies on a random
walk algorithm, SpotLight (Eswaran et al., 2018) uses a randomized sketch
algorithm, making it more scalable, fast, and reliable for the identification
of the sudden appearance of anomalies in densely directed subgraphs.
Experimenting on $1207$ graph snapshots and $288$ ground truth anomalies
($28\%$ of total), SpotLight gave precisions of $(0.79,0.64,0.57)$ at cut-off
rank $(200,300,400)$ respectively and an overall AUC of $0.7$. This is an
$8\%$ improvement on the state-of-the-art in 2018. SedanSpot, on the other
hand, gave an AUC score of $0.63$ when processing $2.54$ million edges in 4
minutes, and SedanSpot’s input stream is processed linearly, resulting in high
computational challenges. AnomRank (Yoon et al., 2019) introduced two-pronged
approaches for capturing both structural and edge weight anomalous changes.
However, AnomRank needs to compute a global PageRank, which does not scale for
edge stream processing.

Li et al.(Li et al., 2021) developed DYNWATCH, a distance (or similarity)
based approach for real-time anomaly detection using sensor data from the
electric power grid. The DYNWATCH algorithm is domain-specific and topology-
aware, allowing it to adapt to rapid changes in historical graph data.
DYNWATCH (Li et al., 2021) constructs a graph from the active devices of the
grid, using active grid buses as vertices and active grid devices as nodes. It
calculates the graph distance using the Line Outage Distribution Factors
(LODF) sensitivity measure and performs temporal weighting based on the
graph’s distance and weights for anomaly detection. In essence, the algorithm
works by defining graph distances based on domain knowledge and estimating a
reliable distribution of measurements at time $t$ from the most relevant
previous data. Other recent distance-based methods include SnapSketch (Paudel
and Eberle, 2020), a sketching approach that uses a simplified hashing of the
discriminative shingles generated from a biased-random walk. DynAnom (Guo et
al., 2022) tracks anomalies at both the node and graph levels in large,
dynamically weighted graphs, and SOM-based (Lamichhane and Eberle, 2022)
clusters visualize the normal and abnormal patterns in graph streams using
self-organized maps (SOM).

###  5.2. Matrix Factorization and Tensor Decomposition Approach

Matrix factorization is a mathematical technique that decomposes high-
dimensional matrices into lower-dimensional forms. It is applied to model
evolving relationships in dynamic graphs, revealing patterns and anomalies
over time by factorizing the adjacency matrix. Tensor decomposition, on the
other hand, extends matrix factorization to multi-dimensional arrays or
tensors. This technique finds latent factors and temporal patterns in dynamic
graph data. It is then possible to detect anomalies by decomposing the
multidimensional tensors that show how nodes interact over time.

Wang et al. (Wang et al., 2017) proposed an Edge-Monitoring technique based on
the Markov Chain Monte Carlo (MCMC) sampling theory. Wang et al. modeled the
dynamic network evolution as a first-order Markov process. They make the
assumption that an unknown foundational model exists that dictates how the
generation process works. Additionally, both the current generative model and
the previously observed snapshot have an impact on each snapshot of the graph.
Their approach is regarded as one of the best for change point detection.
However, the major limitation of this approach is that the Edge-Monitoring
(Wang et al., 2017) relies on consistent node orderings across all time steps.
In addition, edge monitoring assumes a constant number of nodes for each
snapshot. This assumption can be easily violated in the case of large social
networks, which frequently witness the addition of user accounts.

To address the limitation in (Wang et al., 2017), Huang et al. (Huang et al.,
2020) introduced LAD (Laplacian Anomaly Detection) which computes the singular
value decomposition (SVD) of the graph Laplacian to obtain a low-dimensional
graph representation. LAD takes snapshots of the graph structure at different
time steps and then applies the spectrum of the Laplacian matrix to make
embeddings with low dimensions. The core idea of LAD(Huang et al., 2020) is to
detect high-level graph changes from low-dimensional embeddings (called
signature vectors). The normal pattern of the graph is extracted from a stream
of signature vectors based on both short-term and long-term dependencies,
thereby comparing the deviation of the current signature vector from normal
behavior. The method addresses two primary challenges in the identification of
change points in dynamic graphs: the evaluation of graph snapshots across time
and the representation of temporal dependencies. By using the single values of
the Laplacian matrix and adding two context windows, LAD makes it possible to
compare the current graph to both short-term and long-term historical
patterns.

In contrast to Edge-Monitoring (Wang et al., 2017), LAD (Huang et al., 2020)
exhibits the ability to manage a fluctuating number of nodes over time in the
dynamic graph or network. LAD takes this into account by explicitly modeling
both short-term and long-term behaviors within the dynamic graph, effectively
aggregating the information from both temporal perspectives. Past studies have
also focused on detecting anomalous dense subtensors in tensor data, such as
social media and TCP dumps. The works of Faloutsos et al. (Shin et al., 2017)
have made significant contributions to the application of the tensor
decomposition approach to dynamic graphs. They proposed Fast Dense-Block (Shin
et al., 2016) and DenseAlert (Shin et al., 2017)—an incremental and constantly
updating algorithm designed for identifying sudden subtensors that emerge
within a short time frame.

Unfortunately, the laplacian matrix approaches are computationally expensive,
require manual extraction of the dynamic graph properties, and are also
susceptible to noise. Xie et al. (Xie et al., 2023) recently published MICPD,
a multi-view feature interpretable change point detection method based on a
vector autoregressive (VAR) model to turn high-dimensional graph data into a
low-dimensional representation. MICPD finds change points by following the
evolution of multiple objects and how they interact across all time steps.
Huang et al (Huang et al., 2023a) recently proposed MitliLAD (Huang et al.,
2020) as a simple and scalable extension of the LAD algorithm to multi-view
graphs that finds change points in multi-view dynamic graphs.

Table 4. A Comparison of Anomaly Detection (AD) Methods in Dynamic Graphs: A
Review of 53 Recent Papers (2016-2023)

Methods Paper Year Summary and Focus of Paper Learning Task Dataset Metrics
Traditional Machine Learning Methods Tree-based RRCF (Guha et al., 2016) 2016
A Robust Random Cut Forest-based AD algorithm in streams Node NYC, Synthetic
ACC, Prec,AUC Extended-IF (Hariri et al., 2019) 2021 Extends Isolation
Forest(IF) (Liu et al., 2008) where the split is based on hyperplanes with
random slopes instead single variable threshold Node Single-Blob, Sinusoid
AUC-ROC/PRC Density-based MiLOF (Salehi et al., 2016) 2016 An incremental LOF
detection algorithm for data streams Node UCI, IBRL, Synthetic ROC-AUC DILOF
(Na et al., 2018) 2018 Improve on LOF and MiLOF using a new density sampling
algorithm to summarize the data. Node UCI, KDDCup99 AUC LUNAR (Goodge et al.,
2022) 2021 A hybrid combination of deep learning and LOF Node HRSS, MI-F,
Shuttle AUC EvoKG (Park et al., 2022a) 2022 Models the event time by
estimating its conditional density Edge ICEWS18, Wiki, Yago MRR, Hits$@$n
Distance-based StreamSpot (Manzoor et al., 2016) 2016 Anomaly detection in
streaming heterogeneous graphs Node, Edge Youtube, Email ROC-AUC SpotLight
(Eswaran et al., 2018) 2018 Detects sudden (dis)appearance of densely directed
subgraph. Edge, Subgraph DARPA, ENRON, NYC Prec., Rec., AUC SedanSpot (Eswaran
and Faloutsos, 2018) 2018 Detects edges that connect sparsely-connected parts
of a graph. Edge DARPA, DBLP, ENRON Prec., Rec., AUC AnomRank (Yoon et al.,
2019) 2019 Detecting anomalies in dynamic graphs with a two-pronged approach.
Node, Edge DARPA, ENRON, Syn. ACC, Prec., SnapSketch (Paudel and Eberle, 2020)
2020 Shingling technique and baised random walk to sketch the graph Graph
DARPA, IOT-data Prec, Rec. DYNWATCH (Li et al., 2021) 2022 Anomaly detection
using sensors placed on a dynamic grid Edge, Graph Grid data (private) ROC-
AUC, F-1 DynAnom (Guo et al., 2022) 2022 Detect anomalies in large,
dynamically weighted graphs Node, Edge, Graph DARPA, EuCore, ENRON Precision
SOM-based (Lamichhane and Eberle, 2022) 2022 A self-organized map (SOM)-based
clustering and visualization approach on streaming graphs Node, Graph AST2012,
UNSW, ISCX t-SNE Maps Matrix-TF Matrix/Tensor Decomposition EdgeMonitor (Wang
et al., 2017) 2017 It models dynamic graph as a first order Markov process
Edge Synthetic, Senate Rec., Prec. DenseAlert (Shin et al., 2017) 2017
Detecting dense subtensor in tensor stream Sub-graph Rating (Yelp, Android),
KoWiki, Youtube, DARPA Density, Rec. Laplacian-AD (Huang et al., 2020) 2020
Laplacian spectrum for change point detection. Node, Subgraph Synthetic UCI,
Senate Hits$@n$ MICPD (Xie et al., 2023) 2023 Interpretable change point
detection method Node, Graph Synthetic, World Trade T2 chart MultiLAD (Huang
et al., 2023a) 2023 Generalization of LAD (Huang et al., 2020) to multi-view
graphs Node, Subgraph UCI, Senate, Bill-voting Hits$@n$ Probabilistic methods
CM-Sketch (Ranshous et al., 2016) 2016 Sketch-based outlier detection in edge
streams. Edge IMDB, DBLP AUC EdgeCentric (Shah et al., 2016) 2016 Uses Minimum
Description Length to rank node anomalies based on patterns of edge-attribute
behavior in an unsupervised way. Edge Flipkart, Software Marketplace (SWM)
Precision PENminer (Belth et al., 2020) 2020 Explores the persistence of
activity snippets, i.e., the length and regularity of edge-update sequences’
reoccurrences. Edge EuEmail, NYC, DARPA, Boston-Columbus Bike, Reddit,
Stackoverflow AUC MIDAS (Bhatia et al., 2022) 2020 Detects microcluster
anomalies in edge streams and uses count-min sketches (CMS) to count edge
occurrences. Edge TwitterSec-WorldCup DARPA, CTU13, UNSW15 ROC-AUC F-FADE
(Chang et al., 2021) 2021 Frequency-factorization to detect edge streams
anomalies Edge RTM-Synthetic, DARPA, DBLP BARRA, ENRON AUC MSTREAM (Bhatia et
al., 2021) 2021 Detects group anomalies in multi-aspect data Subgraph KDD99,
UNSW15, CICIDS ROC-AUC AnoEdge (Bhatia et al., 2023) 2023 Detects edge and
graphs anomalies by extending the CMS structure in MIDAS (Bhatia et al., 2022)
to a Higher-Order Sketch Edge, graph DARPA, ISCX-IDS12, CIC-IDS18, CIC-
DDoS2019 ROC-AUC Deep Learning Methods AutoEncoder DynGEM (Goyal et al., 2018)
2018 It utilizes deep auto-encoders to incrementally generate embedding of a
dynamic graph at each snapshot Edge HEP-TH, AS, ENRON Avg. MAP Dyngraph2vec
(Goyal et al., 2020) 2020 Uses multiple non-linear layers to learn structural
patterns. Edge HEP-TH, AS-dataset Avg. MAP H-VGRAE (Yang et al., 2020b) 2020
uses a hierarchical variational graph recurrent autoencoder Node, Edge UCI,
HEP-TH, GitHub AUC DGAAD (Gao et al., 2022) 2022 A deep graph autoencoder to
learn dynamic node embedding Node EuEmail AUC, ACC, Rec. Graph Embedding
Node2Vec (Grover and Leskovec, 2016) 2016 Uses BFS and DFS in the generation
of random walks for learning continuous feature representation. Node, Edge
Facebook, PPI, arXiv AUC NetWalk (Yu et al., 2018) 2018 Learns network
representations for node and edges, and detects deviations based on a dynamic
clustering algorithm. Node, Edge UCI, Digg, DBLP AUC GraphSAGE (Hamilton et
al., 2017) 2018 Inductive representation learning on large graphs Node
Citation, Reddit, PPI Micro-avg. F1 AER-AD (Fang et al., 2023) 2023 Inductive
anomaly detection in dynamic graphs Edge Mooc Reddit, Amazon, Enron, Wiki F1,
AUC GraphEmbed (Wang et al., 2023) 2023 Graph-level embedding that utilized a
modified random walk with temporal backtracking Graph Reddit, Enron, Facebook,
Slashdot Precision TEST (Cedre et al., 2023) 2023 Temporal Egonet-subgraph
transitions embedding method Node, Subgraph Enron, UCI, EuEmail Prec, Rec, F1
Deep Graph Learning AddGraph (Zheng et al., 2019) 2019 Detects edge anomaly
with extented GCN, Attention, and GRU Edge UCI, Digg AUC GENI (Park et al.,
2019) 2019 GNN-based approach for estimating node importance in KGs Node
fb15k, music10k, IMBD NDCG HOLS (Eswaran et al., 2020) 2020 Uses higher-order
structures for graph semi-supervised learning Node, Subgraph EuEmail,
PolBlogs,Cora ACC StrGNN (Cai et al., 2021) 2021 Leverage structural GNN to
detect anomalous edges Edge UCI, Digg Email-DNC, Bitcoin-Alpha/OTC AUC CGC
(Park et al., 2022b) 2022 Contrastive learning for deep graph clustering in
time-evolving networks Node, Subgraph, Graph ACM,DBLP,Citeseer, MAG-CS, NYC,
Yahoo ACC, NMI, F1, ARI ROLAND (You et al., 2022) 2022 Extends static GNNs to
capture dynamic graphs. Node, Edge Reddit, AS-733, BSI-ZK, UCI, Bitcoin MRR
PaGE-Link (Zhang et al., 2023b) 2023 GNN explanation for heterogeneous link
prediction Edge AugCitation ROC-AUC MADG (Yuan et al., 2023) 2023 Motif
detection with augmented GCN and self-attention Subgraph UCI,Email-DNC,
Bitcoin-Alpha/OTC Prec, Rec.,AUC SAD (Tian et al., 2023) 2023 A semi-
supervised AD on dynamic grapp, it uses statistical distribution of unlabeled
samples as the reference for loss calculation. Node Wiki, Reddit, Alipay AUC
Graph Attention $\&$ Transformer GAT (Velickovic et al., 2017) 2018 An
attention-based architecture to perform node classification Node Cora, Pubmed,
PPI ACC. F1 HAN (Wang et al., 2019) 2019 A heterogeneous GNN based on the
hierarchical attention Node DBLP, ACM, IMDB ACC, NMI GTN (Yun et al., 2019)
2019 Graph transformer networks, to learn a new graph structure Node DBLP,
ACM, IMDB ACC. DySAT (Sankar et al., 2018) 2019 Dynamic graph learning with
self-attention Network Graph Enron, UCI, Yelp AUC DyHAN (Yang et al., 2020a)
2020 Dynamic Heterogeneous graph embedding with Attentions mechanism Node,
Edge EComm, Twitter, Alibaba ACC,AUC HO-GAT (Huang et al., 2021) 2021 A
hybrid-order graph attention method for detecting node and subgraph anomaly in
a dynamically attributed graph. Node, Subgraph Scholat, AMiner, WebKB Prec,
Recall TADDY (Liu et al., 2021) 2021 Transformer-based AD model for Dynamic
graphs Node, Edge UCI, Alpha, OTC,Digg, EmailDNC, AS-Topology AUC Graphormer
(Ying et al., [n. d.]) 2021 Uses transformer (Vaswani et al., 2017) model for
graph representation learning Node, Edge OGB dataset MAE, AUC *ACC: Accuracy,
NMI: Normalized Mutual Information, ARI: Adjusted Rand Index, ROC-AUC: Area
Under the Receiver Operating Characteristic Curve *ROC-AUC: Area Under the
Receiver, Prec.: Precision, Rec.: Recall, F-1: F-1 Score MRR: Mean Reciprocal
Rank, MAE Mean Absolute Error, Syn.: Synthetic *NDCG: Normalized discounted
cumulative gain, MAP : Mean Average Precision

###  5.3. Probabilistic Method

A probabilistic approach for anomaly detection relies on the application of
probabilistic models to model neighborhood relationships and patterns in
dynamic graphs. Anomalies are determined based on a significant deviation from
the model, considering a given threshold. This approach allows for the
computation of p-values (or false positive rates) for their detection(Chang et
al., 2021). However, this may require a complex optimization process to
traverse a large graph dataset. Recent probabilistic methods include PENminer
(Belth et al., 2020), F-FADE (Chang et al., 2021), MIDAS (Bhatia et al.,
2022), AnoEDGE (Bhatia et al., 2023), and several others.

Ranshous et al. (Ranshous et al., 2016) introduced CM-Sketch, one of the
earliest approaches for outlier detection in edge streams. CM-Sketch first
considers both the global and local structural properties of the graph. It
then utilizes the Count-Min sketch data structure to approximate these
properties and provides probabilistic error bounds on their edge outlier
scoring functions.

In 2020, Belth et al. (Belth et al., 2020) introduced PENminer, an anomaly
detection approach for edge streams. PENminer focuses on exploring the
persistence of activity snippets within evolving networks, which are
essentially short sequences of recurring edge updates. Notably, PENminer is
designed for both offline and streaming algorithms. The offline version
leverages the measure to analyze time-stamped sequences of edges from
historical data, while the online version, called sPENminer, calculates the
measure incrementally for real-time analysis of edge streams. However, it is
worth noting that PENminer is not equipped to detect subgraph and graph-level
anomalies.

Chang et al. (Chang et al., 2021) introduced F-FADE, a frequency factorization
approach for AD in dynamic edge streams, which aims to detect anomalous edge
streams by factorizing the frequency of the patterns. F-FADE (Chang et al.,
2021) discovers patterns by estimating the maximum likelihood rule of observed
instances for each incoming interaction. It can effectively detect anomalies
but requires a considerable amount of time and is computationally expensive.

Bhatia et al. (Bhatia et al., 2022) proposed a MIDAS probabilistic approach
for detecting microcluster anomalies within edge streams. The algorithm
employs count-min sketches (CMS) to compute the occurrence frequency of edges
at each timestamp and subsequently utilizes the chi-squared test to assess the
extent of deviation from typical edges, generating anomaly scores. Higher
scores indicate the presence of anomalous patterns. Furthermore, the MIDAS
algorithm maintains a stable level of memory utilization and a steady temporal
complexity per edge. This method provides theoretical limitations on the
chance of false positives, a characteristic that is not present in other
probabilistic methods for anomaly detection in streaming. MIDAS (Bhatia et
al., 2022) also presents two distinct variants: Midas-R, which incorporates
temporal and spatial relations, and Midas-F, which enhances precision by
selectively filtering out anomalous edges. The MIDAS algorithm is one of the
more recent dynamic edge stream anomaly detectors, and it requires constant
memory and has a constant time complexity, which makes it scalable.

MIDAS (2020) vs. F-FADE: In a comparison between MIDAS and F-FADE, it is
evident that MIDAS demonstrates greater scalability and computational
efficiency when contrasted with F-FADE. However, MIDAS does have a notable
limitation as it fails to track community structures, thus making it
challenging to distinguish between various patterns. This particular
limitation has been addressed in recent methods MSTREAM (Bhatia et al., 2021)
and AnoEDGE (Bhatia et al., 2023) by Bhatia et al., both of which are
advancements on the MIDAS-R (Bhatia et al., 2022) algorithm, by expanding the
CMS to retain past dependencies and also implementing a higher-order sketch
data structure to retain dense subgraph structures.

Experimental results on three real-world dynamic graph datasets — DARPA
(Lippmann et al., 2000) (network IP-IP traffics), CTU-13 (botnet traffic
data), and UNSW-NB15 (a hybrid of real normal activities and synthetic
attacks) — indicate that MIDAS-R (Bhatia et al., 2022) provides an ROC-AUC
scores of (0.9514, 0.9703, 0.8517) respectively, while F-FADE (Chang et al.,
2021) shows scores of (0.8451, 0.8028, 0.6858) on the respective datasets.
Whereas, SEDANSPOT (Eswaran and Faloutsos, 2018) gives scores of (0.6442,
0.6397, 0.7575), and PENminer (Belth et al., 2020) provides scores of (0.8267,
0.6041, 0.7028). Compared to state-of-the-art methods, the MIDAS-R process
evolves faster in constant time and memory, providing up to a $62\%$ higher
ROC-AUC than state-of-the-art approaches.

MSTREAM (Bhatia et al., 2021) is a real-time streaming framework for detecting
group anomalies in multi-aspect data. The goal is to detect anomalies,
considering the similarity in categorical and real-valued attributes. MSTREAM
utilizes the locality-sensitive hash functions (Charikar, 2002) to hash an
incoming similar edge tuple into a fixed similar bucket, and then a temporal
scoring function is applied to identify anomalous activity. The major
difference between MSTREAM (Bhatia et al., 2021) and MIDAS (Bhatia et al.,
2022) is that MIDAS is designed to detect anomalous edges, which are two-
dimensional records consisting of source and destination node indexes.
Therefore, it cannot be applied in the high-dimensional context of multi-
aspect data. On the other hand, MSTREAM extends MIDAS by assigning an
anomalous score to each record and detecting anomalous records in a streaming
manner.

Bhatia et al. (Bhatia et al., 2023) introduced four sketch-based algorithms
for detecting edge and graph anomalies in constant time and memory: AnoEdge-G
and AnoEdge-L for edges, and AnoGraph and AnoGraph-K for graphs. These sketch-
based algorithms build on MIDAS (Bhatia et al., 2022) by expanding the count-
min sketch (CMS) data structure to a higher-order sketch. The higher-order
sketch data structure has the property of preserving dense subgraph structures
in dense submatrix form, which simplifies the task of identifying a dense
subgraph in a large graph to locating a dense submatrix in a fixed-size
matrix. To the best of our knowledge, AnoEDGE and AnoGRAPH (Bhatia et al.,
2023) are the current state-of-the-art streaming edge and graph anomaly
detection methods.

###  5.4. Deep Learning Methods

Deep learning, a subset of machine learning consisting of multiple
interconnected neural networks, has been applied to address anomaly detection
tasks. Notable techniques include autoencoders (Gong et al., 2019; Zong et
al., 2018; Zhou and Paffenroth, 2017), generative adversarial networks (GANs),
and RNNs (Su et al., 2019). However, conventional deep learning frameworks
face limitations in handling streaming data characterized by intricate
topological structures. Some of these challenges are discussed in Subsection
LABEL:1.1_deep_learning_challenges.

Deep learning-based graph learning techniques leverage classical deep learning
models for graph representation learning. These models fall into two broad
categories: those directly adapted from other domains and those re-designed to
suit the specific requirements of graph data embedding. We have grouped deep
learning-based dynamic graph methods into four categories: auto-encoders,
graph embedding, deep graph neural networks (GNNs), and graph transformer
models. For more information, refer to Table 4.

####  5.4.1. AutoEncoders

Autoencoders are a class of neural network architectures commonly used for
anomaly detection in dynamic graphs. They have the ability to learn and
reconstruct input data, and deviations from this reconstruction can indicate
anomalies. In the context of dynamic graphs, autoencoders demonstrate
adaptability to rapid changes in data distributions and are effective at
capturing relevant information from nodes and edges. In many cases,
variational autoencoders (VAEs) are utilized due to their probabilistic
modeling approach for dynamic graphs. Additionally, autoencoders offer
adaptive training and feature learning, making them well-suited for monitoring
evolving graph structures.

Notable techniques that employ autoencoders include DynGEM (Goyal et al.,
2018), DynGraph2Vec (Goyal et al., 2020), H-VGRAE (Yang et al., 2020b), and
DGAAD (Gao et al., 2022). H-VGRAE (Yang et al., 2020b) constructs a
hierarchical model by combining a variational graph autoencoder with a
recurrent neural network. DGAAD (Gao et al., 2022) introduces a deep graph
autoencoder model designed to acquire dynamic node embedding vectors for each
node within the network. Initially, DGAAD employs a time-sensitive random walk
algorithm to extract node sequences from the dynamic graph. Subsequently, it
utilizes an auto-encoding approach to generate high-dimensional representation
vectors for the nodes. Finally, the anomaly detection process is carried out
by evaluating the network embeddings in terms of their proximity to the
cluster center and their respective anomaly scores.

Experimental results: experimenting with real-world dynamic graph data,
autoencoders have yielded comparable results. For instance, DynGEM (Goyal et
al., 2018) achieved a noteworthy average MAP (mean average precision)
evaluation score of 1.279 for link prediction on the ENRON dataset,
outperforming all graph factorization baselines. Similarly, DGAAD (Gao et al.,
2022) demonstrated an AUC of 0.7304 (for a $1\%$ anomaly) and 0.7197 AUC (for
a $10\%$ anomaly injected) in the node prediction task on the ENRON dataset
(Shetty and Adibi, 2004). When compared to the Node2Vec (Grover and Leskovec,
2016) baseline methods, this represents a $10\%$ improvement on average and a
remarkable $21\%$ improvement compared to Spectral Clustering with the
Laplacian matrix for node embedding (Gao et al., 2022). H-VGRAE (Yang et al.,
2020b) also gave a comparable result of an AUC score of $0.8366$ on the UCI
message dataset, and a $0.7820$ AUC score on the Github dataset, which is
slightly better than AddGraph (Zheng et al., 2019) with an AUC of $0.8083$ and
$0.7257$ and NetWalk (Yu et al., 2018) with $0.7758$ and $0.6567$ for the
respective datasets.

Limitations: Despite the competitive performance of Autoencoders and Deep
Learning methods for anomaly detection in dynamic graphs, it is important to
acknowledge the challenges they face. Autoencoders, often known as black-box
models, suffer from a limitation in interpretability. Furthermore, they are
computationally expensive to train on large dynamic graphs. These models also
encounter difficulties in adapting to varying graph structures. Additionally,
when applied to large-scale streaming graphs, both Autoencoders and Deep Graph
Learning models may encounter scalability issues.

Therefore, it is recommended to explore alternative approaches, specifically
probabilistic, density-based, and distance-based methods, in dynamic graph
learning and representations. These techniques can offer valuable
interpretability insights, explainability, speed, and scalability that may
address the limitations associated with Autoencoders and Deep Learning models
in detecting anomalous patterns in dynamic graphs.

####  5.4.2. Graph Embedding

Graph embedding methods for anomaly detection involve applying graph embedding
techniques to detect anomalies or outliers in graph-structured data. These
methods aim to represent the graph’s nodes and edges as vectors in a low-
dimensional space, making it easier to identify nodes that deviate from the
expected patterns or exhibit unusual behaviors within the graph. We cover the
concept of graph embedding in depth in Section 3.

Several graph representation techniques, such as DeepWalk (Perozzi et al.,
2014), Node2Vec (Grover and Leskovec, 2016), LINE (Tang et al., 2015), and
NetWalk (Yu et al., 2018) have demonstrated their capability in generating
node representations and have been used as a baseline model for recent graph
learning methods. DeepWalk (Perozzi et al., 2014) is a technique for graph
embedding that relies on random walks. It creates random walks of a specified
length originating from a target node and employs a skip-gram-like approach to
acquire embeddings for unattributed graphs. LINE (Tang et al., 2015) aims to
maintain the similarity between nodes in the first order and the proximity
between nodes in the second order. Node2Vec (Grover and Leskovec, 2016), on
the other hand, incorporates both breadth-first traversal (BFS) and depth-
first traversal (DFS) in the generation of random walks. Similar to DeepWalk,
it also utilizes the skip-gram algorithm to learn node embeddings. The major
difference between DeepWalk (Perozzi et al., 2014) and Node2Vec (Grover and
Leskovec, 2016) is that DeepWalk relies on random walks and is suitable for
homogeneous graphs, whereas Node2Vec offers more flexibility by allowing both
breadth-first and depth-first random walks, making it adaptable to
heterogeneous graphs.

In contrast to DeepWalk and Node2Vec, the Netwalk (Yu et al., 2018) algorithm
proposed by Yu et al. in 2018 focuses on capturing evolving network dynamics
and scoring edge abnormalities in dynamic graphs, making it distinct from both
DeepWalk and Node2Vec. In detail, the NetWalk (Yu et al., 2018) approach uses
a random walk-based encoder for generating node embeddings, incorporating
clique embeddings, and utilizing a graph autoencoder for the embedding
learning process. It further captures the evolving nature of the network
through dynamic reservoir updates. Finally, it utilizes a dynamic clustering-
based anomaly detection method to assess the abnormality of individual edges.

The most recent graph embedding technique is AGR-AD (Fang et al., 2023) by
Fang et al., a method for detecting anomalies within dynamic bipartite graphs
in an inductive setting. Their approach tends to capture the characteristics
of an edge without using identity information. See Table 4 for more details
and comparison with other frameworks.

####  5.4.3. Deep Graph Learning Based Techniques

Zheng et al. (Zheng et al., 2019) proposed AddGraph, a framework that combines
Gated Recurrent Unites (GRUs) with attention mechanisms (Luong et al., 2015),
and temporal graph convolutional networks (GCNs) to detect anomalies in
dynamic graph data. AddGraph considers both node-level and edge-level
information in the graph to capture temporal dependencies. The attention
mechanism is utilized to highlight important nodes and edges during anomaly
detection. AddGraph (Zheng et al., 2019) captures the structural information
from the dynamic graph in each time stamp and the relationships between nodes.
It has two layers, the GCN layer and the GRU layer. Similar to Equation 2, at
every time step, the GCN utilizes the hidden state representation
$h_{u}^{(t-1)}$ at $t-1$ to generate the current node embeddings.
Subsequently, the GRU-layer employs these node embeddings and hidden states
attentions to learn the current hidden state $h^{(t)}$, as explained in
Section 3.2. Once the hidden state $h_{u}^{(t)}$ for all nodes is obtained,
the AddGraph algorithm assigns an anomaly score to each edge in the dynamic
graph, considering the associated nodes.

Park et al. proposed CGC (Park et al., 2022b), a novel deep graph clustering
approach that leverages a contrastive learning framework. CGC (Park et al.,
2022b) is designed to learn both node embeddings and cluster assignments in an
end-to-end manner. It differs from other deep clustering methods, such as
autoencoders, because it utilizes a multi-level scheme to carefully choose
positive and negative samples. This ensures that the samples accurately
reflect the hierarchical community structures and network homophily in the
graph.

In 2020, Eswaran et al., the authors of SpotLight (Eswaran et al., 2018) and
SedanSpot (Eswaran and Faloutsos, 2018) propose HOLS (Eswaran et al., 2020)
(higher-order label spreading) a graph semi-supervised learning (SSL) approach
that focuses on leveraging higher-order network structures. Traditional SSL
methods rely on the homophily of vertices in graph networks, where nearby
vertices are likely to share the same label. However, these methods often
overlook the varying strengths of connections between vertices and the
importance of higher-order structures in determining labels.

Cai et al. (Cai et al., 2021) introduced StrGNN, a GNN-based model for
detecting anomalous edges. StrGNN leverages the graph convolution (GCN)
operation and sorting layer to extract the h-hop enclosing subgraph of edges
at each snapshot and proposes a node labeling function to identify the role of
each node in the subgraph. Subsequently, stacked GCN and GRU layers are used
to capture the graph’s spatial and temporal dependencies. Finally, the model
is trained in two stages: pre-training the SGNN using a graph reconstruction
task and fine-tuning the entire STGNN for anomaly detection.

You et al. (You et al., 2022) proposed ROLAND, an extension of the static GNN
architecture to dynamic graphs. The primary focus is on snapshot-based
representations for dynamic graphs, in which nodes and edges arrive in
batches. Given the static node embedding state
$H_{t}=\\{H_{t}^{(1)},\dots,H_{t}^{(L)}\\}$, ROLAND views $H_{t}$ as the
hierarchical node state at time $t$, where each $H^{(l)}$ captures multi-hop
node neighbor information. The ROLAND update module dynamically and
hierarchically updates node embeddings over time.

Zhang et al.(Zhang et al., 2023b) proposed PaGELink, a path-based GNN
explanation for heterogeneous link prediction tasks that generates
explanations with connection interpretability. PaGE-Link works on
heterogeneous graphs and leverages edge-type information to generate better
explanations by reducing the search space by magnitude from subgraph-finding
to path-finding and scales linearly in the number of edges.

Recently, Yuan et al. (Yuan et al., 2023) introduced MADG, a motif-level AD
method for detecting unique subgraph patterns in dynamic graphs without
explicitly labeling anomaly data. MADG (Yuan et al., 2023) first uses the
motif-augmented stacked GCN to capture the topological relationships between
nodes and motif instances and figure out how they are represented in each
snapshot. Then, the generated representations of graph snapshots are input
into a temporal self-attention layer to capture the temporal evolution
patterns. Also, SAD (Tian et al., 2023), a recent method based on the semi-
supervised AD technique for dynamic graphs, utilizes the statistical
distribution of unlabeled samples as the reference for loss calculation.

Figure 4. A timeline illustrating the chronological progression of Anomaly
Detection (AD) methods in dynamic graphs from 2016 to 2023, as outlined in
Table 4. The timeline reflects the publication years, including months, and
denotes when each model was initially publicized. Note that the timeline may
differ from the citation year if a paper was pre-published.

####  5.4.4. Graph Transformer

The Graph Transformer approach is a method for learning graph representations,
which are commonly used in tasks like node classification, link prediction,
and graph classification. The success of the transformer models (Luong et al.,
2015; Yang et al., 2019; Vaswani et al., 2017) in natural language processing
(NLP) serve as inspiration for this adaptation to the graph domain. Graph
transformer models are effective for capturing both local and global
structural information within graphs, making them a valuable tool in graph-
based machine learning tasks. Recent research continues to explore and develop
new technique-based techniques. Recent transformer-based graph learning
techniques include GAT (Velickovic et al., 2017), GTN (Yun et al., 2019),
TADDY (Liu et al., 2021), and Graphomer (Ying et al., [n. d.]).

GAT (Velickovic et al., 2017) is a GNN-based model that uses the attention
mechanism (Luong et al., 2015) on homogeneous graphs. HAN (Wang et al., 2019)
is a heterogeneous GNN model based on hierarchical attention, including node-
level attention (to learn node importance) and semantic-level attention (to
learn the importance of different meta-paths). HAN learns graph representation
by transforming a heterogeneous graph into a homogeneous graph constructed by
meta-paths. GTN (Yun et al., 2019) employs a transformer-based model to learn
a new graph structure. This entails identifying valuable meta-paths and multi-
hop connections between unconnected nodes within the original graphs.

Unlike GAT (Velickovic et al., 2017) and HAN (Wang et al., 2019), where meta-
paths are manually defined and graph neural networks are applied to meta-path
graphs, GTN (Yun et al., 2019) learns meta-paths directly from the input graph
data and performs graph convolutions on these learned meta-path graphs. This
unique ability enables GTN to learn more useful meta-paths, leading to an
effective node representation.

The most recent transformer-based methods for dynamic graph learning are
Graphomer (Ying et al., [n. d.]) and TADDY (Liu et al., 2021). Ying et al.
(Ying et al., [n. d.]) introduced Graphomer, a graph representation framework
built upon the standard transformer model (Vaswani et al., 2017). Graphomer
incorporates various encoding techniques to learn graph information. First, it
utilizes centrality encoding to capture node importance by leveraging degree
centrality. Second, it applies spatial encoding to capture the structural
relationships between nodes (i.e., edge encoding). The Graphomer centrality
and spatial encoding are provided in Equations 12 and 13, respectively:

(12)
$h_{i}^{(0)}=x_{i}+z_{\textit{deg}^{-}(v_{i})}^{-}+z_{\textit{deg}^{+}(v_{i})}^{+},$

where, $z^{-},z^{+}\in\mathbb{R}^{d}$ represent the learnable embedding
vectors associated with the in-degree $\textit{deg}^{-}(v_{i})$ and the out-
degree $\textit{deg}^{+}(v_{i})$ of a directed graph, respectively.

For a spatial encoding technique, given any graph $G$, Graphomer (Ying et al.,
[n. d.]) proposes a function $\phi(v_{i},v_{j}):V\times
V\rightarrow\mathbb{R}$ to measure the spatial relation between $v_{i}$ and
$v_{j}$ if two nodes are connected, else the output of $\phi=-1$:

(13)
$A_{ij}=\frac{(h_{i}{W}_{Q})(h_{j}W_{K})}{\sqrt{d}}+b_{\phi(v_{i},v_{j})},$

where $A_{ij}$ is the $(i,j)$element of the Query-Key product matrix $A$ of
the attention mechanism. This matrix, formed through the query-key product, is
a foundational component of self-attention, enabling the model to selectively
focus on various segments of the input sequence. Additionally,
$b_{\phi(v_{i},v_{j})}$ is a learnable scalar indexed by $\phi(v_{i},v_{j})$
and shared across all layers.

TADDY (Liu et al., 2021), introduced by Liu et al., further expands the
transformer-based model to a dynamic graph scenario. TADDY aims to detect
anomalous edges within each timestamp while treating graph streams as a series
of discrete snapshots. TADDY (Liu et al., 2021) comprises four essential
components: edge-based substructure sampling, spatial-temporal node encoding,
a dynamic graph transformer, and the discriminative anomaly detector. This
framework is trained end-to-end, enabling it to directly learn and output
anomaly scores. The framework captures spatial-temporal contexts, integrates
node information, and extracts knowledge from edges to calculate anomaly
scores using a discriminative edge-scoring function.

Other self-attention-based methods for dynamic graph learning include DySAT
(Sankar et al., 2018), a dynamic self-attention network that computes node
representations by simultaneously utilizing self-attention layers in two
dimensions: structural neighborhood and temporal dynamics. DyHAN (Yang et al.,
2020a) is a dynamic heterogeneous graph embedding method that employs
hierarchical attention to learn node embeddings. Additionally, HO-GAT (Huang
et al., 2021), a hybrid-order graph attention method for detecting anomalous
node and motif (or subgraph) instances within dynamically attributed graphs.

###  5.5. Next-Generational Methods for Anomaly Detection in Dynamic Graphs

Despite the recent success of statistical learning methods, probabilistic-
based methods, matrix factorization, and deep learning-based methods, there
are new emerging approaches for graph representation learning that have been
explored in recent times. These emerging techniques include Quantum computing
and Quantum Neural Networks (QNNs) (Akbar and Saritha, 2020; Kukliansky et
al., 2024; Rosenhahn and Hirche, 2024), Federated learning for network traffic
anomaly detection (Pei et al., 2022), Reinforcement learning for anomaly
detection in IoT (Bikos and Kumar, 2021), and Graph Fourier Transforms (GFT)
and spectral graph filtering for community-based anomaly detection.
Specifically, we provide some quantum graph learning (QNNs) methods for AD in
dynamic graphs.

####  5.5.1. Quantum GNNs:

Quantum Graph Neural Networks (QGNNs) are types of neural networks that
process graph-structured data and leverage the power of Quantum Computing (QC)
to perform computations more efficiently than classical neural networks.

In 2023, Akbar et al. (Akbar and Saritha, 2020) proposed a Quantum Graph
Neural Networks (QGNNs) model for financial fraud detection. The authors first
constructed the graph representation for each transaction using PCA, and next,
they encoded the representations into quantum states utilizing angle-encoding
techniques. Furthermore, they utilized multi-layered Variational Quantum
Circuits (VGC) to calibrate each quantum 6-qubits. The output of the VQC is
subjected to average pooling, then fed through a linear layer, and finally to
the output layer. QGNNs gave an AUC score of 0.85, which outperformed
GraphSage with an AUC of 0.77 on a credit card fraud dataset with $284,807$
transactions. However, QGNNs challenges lie in the fact that it was not
experimented with on real-world data, and model time complexity and
scalability weren’t recorded.

Most recently, in 2024, Kukliansky et al. (Kukliansky et al., 2024) proposed a
Quantum Neural Networks (QNNs) approach for intrusion detection on noisy
quantum machines. Experimenting on the real-world dynamic graph datasets KD-
CUP99 and UNSW-NB15, their QNN approach gave an F1-score of $0.86$,
outperforming classical neural network architectures like CNN (with a 0.636
F1-score) and MERA (with a 0.585).

In 2024, Rosenhahn et al. (Rosenhahn and Hirche, 2024) proposed Quantum-based
Normalizing Flows for anomaly detection. By comparing the distribution of
quantum measurements, the authors computed a bijective mapping from the data
samples to a normal distribution and then detected anomalies. The authors
experimented with the Iris-Wine dataset and achieved an AUC score of 0.95
compared to classical Isolation Forest (Liu et al., 2008) with 0.92 and LOF
(Breunig et al., 2000) with 0.84. However, the authors did not experiment with
real-world graph datasets, and the model running time is not recorded.

Despite the recent advancement in quantum computing and the comparative
performance of QNN on graph anomaly detection, quantum-based algorithms are
extremely complex due to quantum hardware challenges. Quantum data encoding on
graph data requires advanced techniques; hence, this might not be a good
technique for scalable streaming graphs.

###  5.6. Timeline of Anomaly Detection Methods in Dynamic Graph

The timeline presented in Figure 4 provides a chronological overview of
anomaly detection (AD) methods in dynamic graphs spanning the years 2016 to
2023, as provided in Table 4. This timeline captures the advancement of AD
models, showcasing their initial date of publication along with corresponding
months. This will serve as a valuable visual representation, providing
insights into the research progress made in dynamic graph anomaly detection
techniques and highlighting the emergence of innovative methods over the
specified timeframe.

##  6\. Dataset and Evaluation Metrics

###  6.1. Dataset

Research studies on anomaly detection methods in dynamic graphs have mostly
used real-world network data to quantify their performance level. However, a
few others have also used synthetically generated data to simulate specific
tasks.

In Table 5, we present an overview of dynamic graph datasets used in the
current literature, along with links to the public repositories of those
datasets. The most commonly used datasets include:

####  6.1.1. UCI Message:

a directed and weighted network based on an online community of students at
the University of California, Irvine. Each node represents a user, and each
edge encodes a message interaction from one user to another, and the weight of
each edge represents the number of characters sent in the message.

####  6.1.2. Senate dataset:

is a social connection network between legislators during the 97rd-108th
Congress (Fowler, 2006). In this dataset, the 100th and 104th Congress
networks are recognized as the change points in many references. An edge is
formed between two congresspersons if they cosponsored the same bill. Each
bill corresponds to a snapshot and forms a clique of co-sponsors.

####  6.1.3. Canadian bill voting network:

Extracted from the Canadian Parliament bill voting network. The Canadian
Parliament consists of 338 Members of Parliament (MPs), each representing an
electoral district, who are elected for four years and can be re-elected [11].

####  6.1.4. Enron email data:

This data contains the email communication network between employees of the
former US company Enron that has been made public by the US Department of
Justice from January 2000 until April 2002 on a monthly level.

####  6.1.5. Ratings Data:

refers to 4-way tensors that include information about users, items,
timestamps, and the associated ratings. These include the Yelp (Challenge, [n.
d.]), Android, and YahooM datasets, as used in (Shin et al., 2017).

####  6.1.6. Wikipedia Edit History:

(Shin et al., 2016) include the KoWiki and EnWiki datasets. This data consists
of 3-way tensors that capture user interactions with Wikipedia articles. These
tensors include information about users, pages (articles), and timestamps.

####  6.1.7. Darpa:

(Lippmann et al., 2000) is a network traffic dataset simulating various
intrusion behaviors. It contains 4.5M IP-IP communications (directed edges)
taking place between 9,484 source IPs and 23,398 destination IPs (nodes) over
87.7K minutes.

####  6.1.8. NycTaxi dataset:

(Leskovec and Krevl, 2014) contains records of taxi ridership over a three-
month duration, from November 2015 to January 2016, sourced from the New York
City (NYC) Taxi Commission. See Table 5 for a comparison of commonly used
dynamic datasets in the literature.

Table 5. Summary of Commonly used Dynamic Graph Datasets in Literature

Dataset/Links Application Description UCI Messages Social Network Online
platform data of students at the University of California, Irvine. Bitcoin-
Alpha/OTC Rating Networks Rating networks collected from Bitcoin platforms.
Canadian Bill-Voting Voting Network Extracted form the Canadian Parliament
bill voting network. Yelp (Challenge, [n. d.]) Social Network The dataset is a
subset of Yelp’s businesses, reviews, and user data. koWiki, EnWiki (Shin et
al., 2016) Wikipedia Edit History Contain Wikipedia information such as
articles, edits, and revisions Youtube Favorite (Mislove et al., 2007) Social
Network Network data of YouTube users and their friendship connections. DARPA
(Lippmann et al., 2000) Network Intrusion Contains network traffic logs
simulating intrusion behaviors. KDDCUP99 Network Intrusion Based on the DARPA
dataset, and it simulates network traffic including both normal and malicious
activities. CICIDS 2018 (Bhatia et al., 2021) Network Intrusion Network data
generated at the Canadian Institute of Cybersecurity. UNSW-NB15 (Bhatia et
al., 2021) Network Intrusion Hybrid of real normal activities and synthetic
attack behaviors. It contains nine types of attacks. CTU-13 (Garcia et al.,
2014) Network Intrusion Botnet traffic dataset captured in the CTU University
in 2011 Android App rating Social Network A large crawl of product reviews
from Amazon users. DBLP Co-author Citation Network Graph dataset of authors
from the DBLP computer science bibliography. ENRON (Shetty and Adibi, 2004)
Communication Network Email communications between Enron energy company
employees. Email-DNC Communication Network Network of emails in the 2016 USA,
Democratic National Committee. Eu Email (Leskovec and Krevl, 2014)
Communication Network Timestamped edges of emails sent within a European
research institute BARRA Communication Network Collection of the email
networks of the Barracuda Networks customers. NycTaxi Transportation Network
Contains records of taxi ridership over a three-month Columbus Bike
Transportation Network A bike trips dataset in the bike-share systems Boston
Bike Transportation Network A bike trips dataset in the bike-share systems
Reddit (Leskovec and Krevl, 2014) Social Network A collection of Reddit users
post and timestamped references Stackoverflow (Leskovec and Krevl, 2014)
Social Network Interactions among users on the Stackoverflow website
TwitterWorldCup (Bhatia et al., 2022) Social Network Contains 1.7M tweets for
2014 World Cup 2014 (June 12-July 13). TwitterSecurity (Bhatia et al., 2022)
Social Network Tweet with Department of Homeland Security keywords on
terrorism. RTM (Akoglu et al., 2008) Social Network Synthetic weighted time-
evolving graph data on Kronecker products PolBlogs (Adamic and Glance, 2005)
Blog Network Contains network of hyperlinks to blogs discussing the U.S. 2004
election. Pokec (Eswaran et al., 2020) Friendship Network Dataset of online
friendship social network in Slovakia AugCitation (Zhang et al., 2023b)
Citation Network Constructed by augmenting the AMiner citation network Digg
Social Network Collected from a news website digg.com where each node
represents a user, and each edge represents a reply between two users. OGB
dataset (Hu et al., 2020) Graph Benchmark The Open Graph Benchmark (OGB) is a
collection of realistic, large-scale, and diverse benchmark datasets for
machine learning on graphs. AS-Topology Network Data Connection dataset
collected from autonomous systems of the Internet. IMDB Movie Review A movie
dataset containing three types of nodes (movies (M), actors (A), and directors
(D)) ACM Citation Network Contains dataset of papers published in KDD, SIGMOD,
SIGCOMM, MobiCOMM, and VLDB. PPI (Zitnik and Leskovec, 2017) Protein
Interaction A protein-protein interaction (PPI) dataset that consists of
graphs corresponding to different human tissues Alibaba dataset Social Network
Contains user behavior logs in the Alibaba.com e-commerce platform. WebKB
Social Network Contains hyperlinked dataset of 877 web pages of four
universities. HEP-TH(Yang et al., 2020b) Citation Network citations of the
papers in High Energy Physics Theory conference from 1993 to 2003 AS-dataset
(Goyal et al., 2020) Network data AS (Autonomous Systems) a communication
network of who-talks-to-whom from the BGP (Border Gateway Protocol) logs.

However, research on dynamic graphs is still relatively new and most cases of
dynamic tasks tend to model real-world scenarios. Thus, it is a challenge to
access real-world data, and this has hindered research and affects the
reproducibility of experiments. One approach is to fall back to the generation
of synthetic data. However, this may provide unrealistic scenarios with
topological and attribute value limitations for graph-level tasks (node, edge,
subgraph, graph).

###  6.2. Evaluation Metrics

Commonly used metrics for evaluating the performance of anomaly detection
techniques include accuracy, precision, recall, F1-score, AUC, Hit$@$n, MRR
(mean reciprocal rank), MAE (mean absolute error), NDCG (normalized discounted
cumulative gain), etc. In this section, we provide a detailed explanation of
each of these metrics. Additionally, in Table 6, we present the mathematical
definitions of these metrics.

####  6.2.1. AUC-ROC

(Area Under the Receiver Operating Characteristic Curve) is a critical metric
for binary classification model assessment. It quantifies the model’s ability
to distinguish between positive and negative classes at different
classification thresholds. The ROC curve, which underlies AUC-ROC, displays
the trade-off between true positive rate (TPR) and false positive rate (FPR)
as the threshold varies.

####  6.2.2. Hit$@$n (Hits at n)

is a metric that reports the number of identified significant anomalies out of
the top n most anomalous points.

####  6.2.3. Hotelling T2 chart

, often referred to as the Hotelling’s T-squared chart or $T^{\wedge}2$
control chart, is a statistical quality control tool used in monitoring and
detecting changes or shifts in multivariate data. It is an extension of the
univariate control charts, such as the Shewhart chart, to handle multiple
variables simultaneously.

####  6.2.4. NMI (Normalized Mutual Information):

NMI is a metric used to measure the similarity between two clusterings of
data. It quantifies the amount of information shared between two clusterings
while accounting for the different numbers of clusters. A higher NMI value