Unsupervised Deep Subgraph Anomaly Detection (Extended Abstract)

1 Introduction

Network data is a popular type of data that describes the properties of discrete objects and their pairwise relationship. Given a network, one of the major tasks in the field of network data mining is the detection of anomalous subgraphs. A subgraph can be defined as an anomaly when its connectivity structure or attributive properties can be described as an outlier in the graph. For example, the significant difference in subgraph topological structure is one type of anomaly subgraph. As shown in Figure 1(a), in a regular lattice material network, one might expect the inserted impurity as an outlier because the topological structure is different from other areas in the graph. Similarly, infectious disease researchers may have an interest in discovering a new unknown infectious disease at the early stage of a disease outbreak (e.g. COVID-19) from the health surveillance network. In normal cases, the count of cases for different disease symptoms should follow a statistical distribution such as the Poisson distribution. As shown in Figure 1(b), a group of connected nodes with significant abnormal symptom attributes may indicate a potential disease outbreak is taking place.

∗ Full version of this paper was originally published at the 2022 IEEE International Conference on Data Mining (ICDM) and received the Best Paper Award.

Existing graph anomaly detection algorithms [Akoglu et al., 2015] can be categorized into traditional shallow methods [Gupta et al., 2014; Chen et al., 2017; Miller et al., 2010; Sharpnack et al., 2013] and deep learning-based method [Ruff et al., 2018; Zhou and Paffenroth, 2017; Peng et al., 2018; Zhang and Zhao, 2021; Wang et al., 2022; Dou et al., 2020; Wang et al., 2021]. Previous shallow approaches to detecting anomaly subgraphs have mainly focused on manually defining anomaly quantification metrics for subgraphs and developing methods to extract anomalous patterns based on the designed measures. Although the ideas behind these shallow methods are simple and intuitive, the shallow mechanisms are suffered from the limited capability of capturing non-linear properties to discriminate complex anomalies from graphs with high-dimensional features and irregular topological structures. More importantly, these methods require prior knowledge to determine the measurement function for detecting anomalies, which are usually unavailable due to the unknown nature of anomaly subgraph patterns in many practical applications [Chandola et al., 2009; Ahmed et al., 2016]. On the other hand, deep learning-based methods, which have received growing attention in recent years [Ma et al., 2021], can extract expressive representations of objects, such as nodes or graphs, to effectively distinguish abnormal and normal objects. Previous works have shown impressive progress in many graph anomaly detection tasks [Ma et al., 2021].

Despite the success in generalizing deep learning techniques to graph anomaly detection problems, most previous works only focus on detecting node- or edge-level anomalies. The task of anomaly subgraph mining has been largely underexplored and has just started to attract attention. However, there is no trivial way to simply apply these methods to accomplish the task of detecting anomalous subgraphs due to several unique challenges: (1) Difficulty in obtaining sufficient training labels in an end-to-end manner without intensive supervision. Deep learning approaches heavily rely on the training objectives to optimize model parameters. For anomalous subgraph detection, this necessitates sufficient training labels and appropriate loss function such that models can effectively discriminate the anomalous patterns. Unfortunately, the training labels are hard to sufficiently obtain due to the exponential possible subgraphs in a given graph, and designing proper objectives for detecting anomalous subgraphs is challenging because there is usually no prior knowledge about the anomalies. (2) Difficulty in preserving both geodesic distance and topological similarity among nodes for representing subgraph anomaly. Existing end-to-end works that consider node- or edge-level cannot be directly used for subgraph-level anomaly detection. For example, within the scope of a given anomaly subgraph, individual nodes or edges might be normal. It only turns out to be anomalous when considered as a group compared to other areas. Merely aggregating node- or edge-level anomaly scores can not reflect the subgraph abnormality. But how to jointly consider intra-subgraph structure and the subgraph's position to the whole graph, is indispensable yet very challenging. (3) Difficulty in quantifying the degree of being abnormal under arbitrary and unknown anomaly types. It is extremely hard to quantify the degree of abnormality for arbitrary patterns of attribute and topological structure of subgraph when a ground truth anomaly type is unknown. Previous shallow methods typically utilize a handcrafted measure function, which is limited by its low expressive power and generalizability to unseen anomalies. Also, existing methods learn the scoring function from scratch, which is usually subject to the exponentially growing search space and can easily lead to overfitting issues.

2 ProblemFormulation

We consider an attributed network as G = (V, E), where V = {v1, v2, . . . , vN} is a set of nodes that N = |V| denotes the number of nodes in the graph and E ⊆ V × V is the set of edges. We also let X ∈ RN×p denotes the node attribute matrix and A ∈ RN×N represents the adjacency matrix. Specifically, the attribute of node vi can be expressed as a p dimensional vector xi ∈ Rp . Aij = 1 denotes there is an edge connecting nodes vi and vj ∈ G, otherwise Aij = 0. A subgraph h of the given G is represented as H = (VH, EH) where VH ⊆ V is a subset of nodes and EH is the corresponding set of edges. XH,AH are the corresponding node attribute and adjacency matrices. With the preliminary notion of the attributed network, we formalize the anomalous subgraph detection problem as follows:

Problem 1. Anomalous subgraph detection. Given a graph G, the task of anomalous subgraph detection is to search for a subgraph H ⊆ G that is most different from the majority of graph, where the degree of being abnormal is quantified by a score function f.

3 Methodology

3.1 Candidate Anomaly Subgraphs Extraction by Location-Aware Graph Autoencoder

In order to correctly reveal the potential contextual anomaly areas, we design a location-aware graph autoencoder to incorporate the locational information of nodes in the network when performing message aggregation. To be specific, we first sample a set of C random anchor nodes VC = {v1, v2, . . . , vC} in the given graph G. Then the shortest distance from each node to anchors, which is denoted as S ∈ RN×C , is calculated and treated as additional node labels. Thus the global location of each node can be inferred from the shortest distances to all anchor nodes (relabeled nodes attributes). The modified location-aware graphautoencoder can capture the dependence properties among nodes when they are located in a close area of the graph.

This module plays a critical role in correctly reconstructing the normal areas and uncovering anomalous areas.

Mathematically, given the input graph G, our proposed location-aware autoencoder first maps the adjacency matrix A, node attributes matrix X, and distances to anchors matrix S into the latent representation vectors z ∈ RN×D through location-aware encoder ϕ, where D is the dimension of latent representation and zi ∈ RD is the corresponding latent vector for the node vi. Formally, one convolutional operation of a location-aware encoder can be represented as:

where g(ℓ) , X(ℓ) and W (ℓ) is the graph convolution function, the latent embeddings of nodes, and a trainable weight matrix at layer ℓ, respectively. We take the attribute matrix X as the input of the first layer. Then, we reconstruct both node attributes matrix X′ and adjacency matrix A′ from extracted latent embeddings z by decoder φ.

The residual graph R can then be built upon the mismatch between the original graph G and the reconstructed graph φ(ϕ(G)). We first define the reconstruction error ri of one node vi as:

then the residual graph R is constructed as:

where ER is the corresponding set of edges to the set of nodes VR and τ is a threshold to filter out the nodes.

3.2 Quantifying Anomalous Scores of Subgraphs by Graph Supermodular Function

Given the extracted residual graph R from the original graph G by the reconstruction results of the location-aware graph autoencoder, the nodes VR in the residual graph can exhibit as a set of connected components {g|g ⊆ R} where each component g is an induced subgraph of the original graph G. Here a key question is how to evaluate the degree of abnormality of each extracted component in the residual graph. For example in Figure 3, in an online social network, it is more desirable to treat a subgraph of three connected potentially fraudulent users as more anomalous rather than three separate isolated users because they have abnormal neighbors. Therefore, when quantifying the anomaly of a given subgraph, its value needs to be no less than the sum of the anomalies of all its individual partitions. This indicates that the anomaly quantization function should be supermodular.

Given a graph G with a collection of N labeled nodes V = {v1, . . . , vN}, the set of all subgraphs can be represented as H = {H|H ⊆ G}. A graph scoring function f : H → R assigns a real value to any graph H ∈ H. Here suppose H is the subgraph that is induced by set of nodes VH. We also use H+{u} to denote the subgraph which is induced by the set of nodes VH ∪ {u} when {u} /∈ VH. We give the definition of a graph supermodular function as following:

Definition 1. For all Q, H ∈ H that VQ ⊆ VH ⊆ V\{u}, a graph function f(·) is said to be supermodular if and only if

A simplest example of supermodular function on graph can be given as f(G) = |V| + |E|, where |E| denotes the number of edges in graph G.

We then propose a novel deep graph supermodular neural network by extending the previous submodular deep learning model [Dolhansky and Bilmes, 2016]. Specifically, given an input graph G, one updating function of node vi by deep graph supermodular neural network at layer ℓ can be expressed as:

where σ(ℓ) is a non-negative non-decreasing convex function and w(ℓ) is a non-negative weight matrix. The whole deep graph supermodular neural network can be achieved by stacking L layers of updating operation in Equation 5 and a summation operation over all nodes.

3.3 Unsupervised andWeakly Supervised Learning Objectives of AS-GAE

To optimize the parameters involved in the previously mentioned components location-aware graph autoencoder and supermodular graph scoring function without intense supervision, we first present the objective function of the proposed framework under an unsupervised learning manner. After the training process, the anomalous scores can be given by the function f(g), ∀g ⊆ R. Subgraphs with higher anomaly scores are considered to have a higher probability of being anomalies. The loss function of AS-GAE under an unsupervised setting can be described as

where R is the residual graph and f(·) is the supermodular scoring function. β and γ are two hyperparameters, and ∥·∥ is commonly chosen to be the ℓ2-norm.

4 Experimental Results

Structural Anomaly Synthetic Datasets. We first apply several existing commonly used graph generator models to generate the background graph. In this paper, we investigate four classic graph generators as background graph: (1) Erd¨osR´enyi (ER); (2) Watts-Strogatz (WS); (3) Barab´asi-Albert (BA); and (4) complete graphs. Then a small subgraph with a different structural property is inserted into the background graph as the ground truth anomaly subgraph. We extend previous works [Gupta et al., 2014; Chen et al., 2017] to insert two types of anomaly subgraphs: chain and dense graphs.

Real-World Datasets. To further evaluate the performance of our proposed method and comparison methods in realworld scenarios, nine public real-world attributed network datasets, including four citation network datasets, three social network datasets, one communication dataset, and one materials dataset, are utilized as benchmark datasets in our experiments. We provide a brief description of these realworld datasets as follows:

Effectiveness Results. We compare our proposed method AS-GAE with benchmark methods on both synthetic datasets and real-world datasets in an unsupervised learning manner. The comparison of AUC scores for the structural anomaly synthetic dataset is provided in Table 1, by combinations of different background graphs and inserted anomalous subgraphs.

(1) The results demonstrate the strength of our proposed method by consistently achieving the best results in all eight structure anomaly synthetic tasks, and eight out of nine realworld datasets. Specifically, our results outperformed the benchmark models by over 31.7% for structure anomaly synthetic datasets, and 16.1% for real-world datasets.

(2) Our proposed method shows a stronger detection performance compared to other deep learning methods. A possible reason is that our method takes advantage of the dependence relationships information within the context of the graph to acquire a more competitive performance.

(3) As shown in Table 1, in the structure anomaly synthetic datasets experiments, our proposed method consistently achieves superior anomaly detection performance with respect to different combinations of background graphs and anomaly subgraphs, which proves the robustness of our proposed method. In comparison, the DEEPFD method and DEEPSVDD method have significantly different performances on different background graphs. For example, the DEEPFD method shows strong detection performance when having a random graph or scale-free graph as a background graph, while the DEEPSVDD method has competitive performance when the background graph is a complete graph or small-world graph.

(4) It is also worth noting that the deep learning-based benchmark methods (DEEPFD, DOMINANT, DEEPSVDD, and AS-GAE) show a more competitive performance than the non-deep learning-based benchmark methods (L1SUB and AMEN), by over 15.6% on average for structure anomaly synthetic datasets, and 12.9% on average for real-world datasets, which arguably indicates that non-deep learning methods have limited capability to effectively discriminate anomalies from graphs with complex structures.

5 Conclusion

This paper focuses on the crucial problem of detecting anomalous subgraphs from a given network under unsupervised learning settings. The proposed framework deep Anomalous Subgraph Autoencoder (AS-GAE) effectively addresses the unique challenges in anomaly subgraph detection by utilizing a location-aware graph autoencoder module to uncover the relative anomalous areas, and then a supermodular graph anomalies quantification module is applied to assign a reasonable anomaly score for the subgraphs in the built residual graph according to the reconstruction results of the autoencoder. Extensive experimental results on both synthetic and real-world datasets demonstrate the outstanding detection power of our framework.