This survey article presents a comprehensive and conceptual overview of anomaly detection (AD) using dynamic graphs. We focus on existing graph-based AD techniques and their applications to dynamic networks. The contributions of this survey article include the following: (i) a comparative study of existing surveys on AD; (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 AD in dynamic graphs.

The ability to detect fraudulent activities such as denial-of-service attacks (DoS), social media impersonations, or fake recommendations in e-commerce networks is a difficult task. One approach to aiding with detection of these types of anomalous activities is through representing the data as a graph. However, the scalability of graph-based approaches is problematic. In general, given a stream of graph edges, where each edge indicates a communication/link in a certain time, the objective is to detect anomalous edges that represent actions such as DoS attacks, port scans, etc., and do so in an online manner while consuming constant time and memory. In this paper, we propose Term Frequency-Inverse Graph Frequency (TF-IGF) as an online anomaly detection approach, which assigns anomaly scores to edge streams. TF-IGF offers the following contributions: (1) streaming; processes one edge at a time, (2) online; detects suddenly appearing anomalous edges in near real-time, (3) accurate; has better accuracy than the state-of-the-art approaches, and (4) efficient; consumes constant time and memory to process edges. We evaluate this approach on both synthetic and real-world data sets.

Discovering patterns and anomalies in a variety of voluminous data represented as a graph is challenging. Current research has demonstrated success discovering graph patterns using a sampling of the data, but there has been little work when it comes to discovering anomalies that are based upon understanding what is normative. In this work we present two approaches to reducing graph data: subgraph filtering and graph filtering. The idea behind the proposed algorithms is the removal of a "murky middle", where data that may not be normative or anomalous, is removed from the discovery process. We empirically validate the proposed approach on real-world, pseudo-real-world, and synthetic data, as well as compare against a similar approach.

The emergence of mining complex networks like social media, sensor networks, and the world-wide-web has attracted considerable research interest. In a streaming scenario, the concept to be learned can change over time. However, while there has been some research done for detecting concept drift in traditional data streams, little work has been done on addressing concept drift in data represented as a graph . We propose a novel unsupervised concept-drift detection method on graph streams called Discriminative Subgraph-based Drift Detector (DSDD). The methodology starts by discovering discriminative subgraphs for each graph in the stream. We then compute the entropy of the window based on the distribution of discriminative subgraphs with respect to the graphs and then use the direct density-ratio estimation approach for detecting concept drift in the series of entropy values obtained by moving one step forward in the sliding window. The effectiveness of the proposed method is demonstrated through experiments using artificial and real-world datasets and its performance is evaluated by comparing against related baseline methods. Similarly, the usefulness of the proposed concept drift detection approach is studied by incorporating it in a popular graph stream classification algorithm and studying the impact of drift detection in classification accuracy.

The use of the Internet of Things (IoT) devices has surged in recent years. However, due to the lack of substantial security, IoT devices are vulnerable to cyber-attacks like Denial-of-Service (DoS) attacks. Most of the current security solutions are either computationally expensive or unscalable as they require known attack signatures or full packet inspection. In this paper, we introduce a novel Graph-based Outlier Detection in Internet of Things (GODIT) approach that (i) represents smart home IoT traffic as a real-time graph stream, (ii) efficiently processes graph data, and (iii) detects DoS attack in real-time. The experimental results on real-world data collected from IoT-equipped smart home show that GODIT is more effective than the traditional machine learning approaches, and is able to outperform current graph-stream anomaly detection approaches.

Illegal insider trading of stocks is based on releasing non-public information (e.g., new product launch, quarterly financial report, acquisition or merger plan) before the information is made public. Detecting illegal insider trading is difficult due to the complex, nonlinear, and non-stationary nature of the stock market. In this work, we present an approach that detects and predicts illegal insider trading proactively from large heterogeneous sources of structured and unstructured data using a deep-learning based approach combined with discrete signal processing on the time series data. In addition, we use a tree-based approach that visualizes events and actions to aid analysts in their understanding of large amounts of unstructured data. Using existing data, we have discovered that our approach has a good success rate in detecting illegal insider trading patterns.

Due to potentially complex relationships among heterogeneous data sets, recent research efforts have involved the representation of this type of complex data as a graph. For instance, in the case of computer network traffic, a graph representation of the traffic might consist of nodes representing computers and edges representing communications between the corresponding computers. However, computer network traffic is typically voluminous, or acquired in real-time as a stream of information. In previous work on static graphs, we have used a compression-based measure to find normative patterns, and then analyzed the close matches to the normative patterns to indicate potential anomalies. However, while our approach has demonstrated its effectiveness in a variety of domains, the issue of scalability has limited this approach when dealing with domains containing millions of nodes and edges. To address this issue, we propose a novel approach called Pattern Learning and Anomaly Detection on Streams, or PLADS, that is not only scalable to real-world data that is streaming, but also maintains reasonable levels of effectiveness in detecting anomalies. In this paper we present a partitioning and windowing approach that partitions the graph as it streams in over time and maintains a set of normative patterns and anomalies. We then empirically evaluate our approach using publicly available network data as well as a dataset that represents e-commerce traffic.

Protecting and securing sensitive information are critical challenges for businesses. Deliberate and intended actions such as malicious exploitation, theft or destruction of data, are not only harmful and difficult to detect, but frequently these threats are propagated by an insider. Unfortunately, current efforts to identify unauthorized access to information such as what is found in document control and management systems are limited in scope and capabilities. This paper presents an approach to detecting anomalies in business transactions and processes using a graph representation. In our graph-based anomaly detection (GBAD) approach, anomalous instances of structural patterns are discovered in data that represent entities, relationships and actions. A definition of graph-based anomalies and a brief description of the GBAD algorithms are presented, followed by empirical results using a discrete-event simulation of real-world business transactions and processes.