Abstract
Anomalies represent rare observations that vary significantly from others. Anomaly detection intended to discover these rare observations has the power to prevent detrimental events, such as financial fraud, network intrusion, and social spam. However, conventional anomaly detection methods cannot handle this problem well because of the complexity of graph data (e.g., irregular structures, relational dependencies, node/edge types/attributes/directions/multiplicities/weights, large scale, etc.) [1]. Thanks to the rise of deep learning in solving these limitations, graph anomaly detection with deep learning has obtained an increasing attention from many scientists recently. However, while deep learning can capture unseen patterns of multi-dimensional Euclidean data, there is a huge number of applications where data are represented in the form of graphs. Graphs have been used to represent the structural relational information, which raises the graph anomaly detection problem - identifying anomalous graph objects (i.e., vertex, edges, sub-graphs, and change detection). These graphs can be constructed as a static graph, or a dynamic graph based on the availability of timestamp. Recent years have observed a huge efforts on static graphs, among which Graph Convolutional Network (GCN) has appeared as a useful class of models. A challenge today is to detect anomalies with dynamic structures. In this chapter, we aim at providing methods used for detecting anomalies in static and dynamic graphs using graph analysis, graph embedding, and graph convolutional neural networks. For static graphs we categorize these methods according to plain and attribute static graphs. For dynamic graphs we categorize existing methods according to the type of anomalies that they can detect. Moreover, we focus on the challenges in this research area and discuss the strengths and weaknesses of various methods in each category. Finally, we provide open challenges for graph anomaly detection using graph convolutional neural networks on dynamic graphs.