Decoupling Anomaly Discrimination and Representation Learning: Self-supervised Learning for Anomaly Detection on Attributed Graph

Recently, graph representation learning has achieved considerable success with GNNs. The core idea of GNNs is aggregating messages from neighbors to update node representations, which is based on the assortativity assumption. GNNs can be divided into two categories: spectral-based methods and spatial-based methods. The former category includes GCN [4], passing message by first-order approximation of Chebyshev filter. The latter category includes GAT [6] and GraphSAGE [16]. GAT utilizing the attention mechanism, assigns weight to each edge when aggregating messages. GraphSAGE proposes an inductive representation learning manner to cope with tasks on large-scale graphs.

Apart from the above fundamental GNN models, many advanced GNN models are also proposed to learn the graph representations better. To avoid the sparsity issue and filter the noise information, [17] proposes a framework preserving low-order proximities, mesoscopic community structure information and attribute information for network embedding. MTSN [18], a dynamic graph neural network, captures local high-order graph signals, learns attribute information based on motifs, and preserves timing information by temporal shifting. To alleviate the over-smoothing issue, NAIE [19] adopts an adaptive strategy to smooth attribute information and topology information, and develop an autoencoder to enhance the embedding capacity.

Self-supervised graph learning, a new learning paradigm that trains models without labels, has been widely used in computer vision [20] and natural language processing [21]. Self-supervised learning in graph can be categorized into: graph contrastive learning (e.g. SimGRACE [22]), graph generative learning (e.g. Graph Completion [23]) and graph predictive learning (e.g. CDRS [24]). Without augmentation, SimGRACE uses a formal encoder and a perturbation encoder to embed the graph, and then pulls close the same semantics while pushing away the different semantics between the two hidden spaces. Graph Completion removes features of the target node, and then reconstructs it from the unmasked neighboring nodes. CDRS makes a pseudo node classification task collaborated with the clustering task to improve representation learning.

Anomaly detection on attributed graph works for identifying patterns that notably diverge from the majority. Many methods have been proposed for anomaly detection, including the shallow methods and the deep methods. The shallow methods include [14], Radar [25], and ANOMALOUS [26]. AMEN measures the correlation of features between the target node and its ego-networks to detect anomalies. Radar analyzes the residuals of attribute information and its coherence with graph information to detect anomalies. ANOMALOUS integrates CUR decomposition and residual analysis to detect anomalies. The shallow methods are limited by their expressiveness ability in graph embedding. The deep methods can be further divided into two classes. The first class deep methods include DOMINANT [2] and DGIAD [15, 27]. DOMINANT reconstructs the adjacency matrix and the attribute matrix, then distinguish anomaly through reconstruction error. DGI contrasts node and graph for embedding. Deployed with a trained discriminator, DGI can be used for anomaly detection and we rename this method as DGIAD in this paper. The first class deep methods, node classification models equipped only with an anomaly discriminator, are not developed for anomaly detection and still don’t show satisfactory performance. The second class deep methods include HCM [28], CoLA [15], SL-GAD [29], ANEMONE [30],CONAD [31], Sub-cr [32] and GRADATE [33]. HCM trains GNNs with self-supervised learning and Bayesian learning to distinguish anomalies. CoLA, SL-GAD and ANEMONE contrast nodes and subgraphs to discriminate anomaly. CONAD augments graphs with prior knowledge for anomaly detection training. Sub-cr enhances anomaly detection by multi-view contrastive learning and graph reconstruction. GRADATE extends contrastive learning to node-node level and subgraph-subgraph level. The second class deep methods optimize model for anomaly detection, but neglect representation learning to overcome semantic mixture and imbalance issue.

The key to anomaly detection is finding the patterns significantly different from the majority. Therefore, discrimination pairs are crucial to this task. Graph objects can be categorized into edge, node, subgraphs, and graph. Any two of them, excluding edge, can be selected to constitute discrimination pairs. We sample discrimination pairs at node-subgraph level. The procedure is as follows:Target nodes and neighboring subgraphs are combined as discrimination pairs for anomaly discrimination. A positive pair includes a node and a subgraph sampled from it, while a negative pair includes a node and a subgraph sampled from other nodes. A toy sample of positive pair and negative pair is displayed in Fig. 4 for a better understanding.

For anomaly discrimination and contrastive representation learning, obtained target nodes and their neighboring subgraphs are mapped into low-dimensional embedding space by GNNs.

We apply a GCN encoder and a GCN autoencoder to embed the graph and reconstruct the attribute matrix, respectively.

Target node \(v_{i}\) is embedded as a graph with only one node. The GNN propagation formula can thus be simplified to MLP:And \({\textbf{e}}_i \in {\mathbb {R}}^d\) is used to denote the output of GCN encoder, which is the node level representation vector of \(v_i\).

On the \(K\)-nodes subgraph \({\mathcal {G}}_i\) sampled from node \(v_{i}\), the adjacency matrix is denoted by \({\textbf{A}}_{\{i\}}\in {\mathbb {R}}^{K \times K}\) and the attribute matrix is denoted by \({\textbf{X}}_{\{i\}}\in {\mathbb {R}}^{K \times d(0)}\). Then, the GNN operator is applied to:where \(\widetilde{{\textbf{A}}}_{\{i\}}={\textbf{A}}_{\{i\}}+{\textbf{I}}_K\), and \({\textbf{H}}_{\{i\}}^{(0)}={\textbf{X}}_{\{i\}}\).

The output of the GCN encoder is denoted by \({\textbf{Z}}^{i}\in {\mathbb {R}}^{K \times d}\), which is the context representation matrix of subgraph \({\mathcal {G}}_i\). And the output of the GCN autoencoder on \({\mathcal {G}}_i\) is denoted by \({\textbf{U}}_{\{i\}}\in {\mathbb {R}}^{K \times d(0)}\), which is the reconstructed attribute matrix of \({\mathcal {G}}_i\).

The readout module summarizes \({\textbf{Z}}^{i}\) into its subgraph-level representation \({\textbf{g}}_i\in {\mathbb {R}}^{ d}\). We take average pooling as the readout module. The subgraph-level representation can then be formulated as:where \(c_i\) is the index of \(v_i\) in neighboring subgraph \({\mathcal {G}}_i\).

In this subsection, We will describe how DSLAD discriminates anomaly. Context anomaly and reconstruction anomaly are two subtypes of anomaly discrimination. Here is more information on them in depth:

In the context anomaly module, the loss function in Eq. (7) mainly focuses on anomaly discrimination and pays less attention to representation learning. Moreover, all nodes are assumed to contribute equally. After message passing, semantic mixture and imbalance issue inevitably occur. To impede the normal nodes from dominating the representation learning, we implement the contrastive representation learning module and set the number of positive samples and negative samples equal.

For the target node \(v_i\), we choose the neighboring subgraph \({\mathcal {G}}_j\) (\(j \ne i\)) sampled from node \(v_j\) as the negative sample, in consistency with the context anomaly module. We propose two optional augmentation strategies to generate the positive sample. One augmentation strategy, denoted by \(local\_aug\), selects the neighboring subgraph \({\mathcal {G}}_i\) as the positive sample. Another augmentation strategy, denoted by \(global\_ aug\), embeds the entire graph without the mask and then takes the embedding of \(v_i\) as the positive sample. The \(local\_aug\) aggregates messages from a part of neighbors and removes the influence of attributes of the target node, while the \(global\_ aug\) aggregates messages from all neighbors within a specific hop and retains the influence of attributes of the target node. The key difference relies on the influence of attributes of the target node and neighbor selection. \({\textbf{e}}_i^{-}\) denotes representation vector of negative sample, and \({\textbf{e}}_i^{-} = {\textbf{g}}_j,j \ne i\). \({\textbf{e}}_i^{+}\) denotes representation vector of positive sample, andwhere \({\textbf{g}}_i\in {\mathbb {R}}^d\) is computed by Eq. (3) and f denotes GCN encoders in the context anomaly module. For a better understanding of the augmentation views, the procedure for generating positive and negative samples is displayed in Fig. 5.

Both the number of positive samples and negative samples are set to 1 for simplicity and fairness. We adopt infoNCE [37] as the loss function of contrastive representation learning:where \(\tau\) is a temperature parameter greater than 0.

In this subsection, we explain why and how we decouple anomaly discrimination and contrastive representation learning. When behaviors and label semantics are excessively inconsistent in anomaly detection tasks, [38] has shown that training graph representation learning and anomaly discrimination jointly may lead to performance degradation. Moreover, the problem of class imbalance can also be resolved significantly by decoupling representation learning and anomaly discrimination. At the beginning of training, discriminators are prone to predict arbitrarily, producing erroneous results while contrastive representation learning forms a balanced semantic space [39, 40]. During training, discriminators make increasingly accurate predictions while performance gained by contrastive representation learning decays [41, 42]. Gradually shifting to anomaly discrimination from contrastive learning enhances the effectiveness. Based on the above analysis, instead of jointly training by classification loss, we decouple anomaly discrimination and contrastive representation learning and give them dynamic weights. The workflow of our decoupled anomaly detection algorithm is shown in Fig. 6.

Let \(\beta\) denotes the ratio of current epoch to the number of training epochs, whose value indicates the training process. \(\pi (\beta )\) is the factor balancing the anomaly discrimination loss and the contrastive representation learning loss, where \(\pi (\cdot )\) is a mapping function. The final loss function can be written as:where \(\alpha\) and \(\lambda\) are the hyperparameters that control the role of different anomaly scores, and scale contrastive representation learning, respectively. And \(\pi (\beta )\) increases with \(\beta\).

We could calculate the final anomaly score for each node after training.

For node \(v_i\), context anomaly score \({\textbf{s}}_i^{con}\) and reconstruction anomaly score \({\textbf{s}}_i^{rec}\) can be inferenced as follows:where \({\textbf{s}}_i^{con(-)}\) and \({\textbf{s}}_i^{con(+)}\) are calculated by Eqs. (5) and (6) respectively. The score function can simultaneously consider the impact of both positive and negative pairs. For normal nodes, the similarity of positive pair matching is high, while the similarity of negative pair matching is low. For anomalous nodes, the similarity of positive and negative pair matching are both low.where the index of \(v_i\) in the neighboring subgraph \({\mathcal {G}}_i\) is \(c_i\), the reconstructed attribute vector of \(v_i\) in neighboring subgraph \({\mathcal {G}}_i\) is \({\textbf{U}}_{\{i\}}[c_i,:]\), and \(\textit{x}_i\) is the original attribute vector of node \(v_i\).

By MinMaxScalar, we transform the context anomaly score \({\textbf{S}}^{con}\) to [0,1] for standardization:where \({\textbf{s}}_{min}^{con}\) and \({\textbf{s}}_{max}^{con}\) are the min and the max of context anomaly scores, respectively. Similarly, reconstruction anomaly score \({\textbf{S}}^{rec}\) is also transformed to [0,1] by MinMaxScalar:where \({\textbf{s}}_{min}^{rec}\) and \({\textbf{s}}_{max}^{rec}\) are the min and the max of reconstruction anomaly scores, respectively.

Combining transformed context anomaly score and reconstruction anomaly score, we can get the final anomaly score \({\textbf{s}}_i\) of node \(v_i\):Neighboring subgraph is sampled stochasticly. To reduce the sampling variance, we take the averaging anomaly score over R times as the final anomaly score.

Six frequently used real-world datasets for anomaly identification, including four citation network datasets and two social network datasets, are applied to evaluate our model.

The following is a brief overview of the six datasets:Considering that there are no ground-truth anomaly labels in above six real-world datasets, injecting synthetic anomaly nodes into datasets to simulate real anomalies is used widely. We follow the perturbation processing in [2, 15] to inject anomalies with both attribute anomalies and structure anomalies into the six datasets. For the attribute anomaly injection, we select \(M_a\) nodes and replace their features with stochasticly selected remote nodes. For the structure anomaly injection, we pick up \(M_a\) nodes and divide them into \(M_c\) clusters averagely. Nodes within the same cluster are connected with each other. The statistics of these contaminated datasets are depicted in Table 2.

We choose some of the state-of-the-art methods as baselines to compare with our proposed DSLAD on the above six real-world datasets. These methods are divided into three categories:

(1) The shallow method: The shallow method detects anomalies without deep learning. We pick up the following three models for comparison:(2) The node-classification-targeted method: The node-classification-targeted methods simply expand the node classification model with an anomaly detection module to detect anomalies. We choose the following two models for comparison:(3) The anomaly-detection-targeted method: The anomaly-detection-targeted method is designed to detect anomalies directly, even without considering node classification. We select the following three models for comparison:

We utilize ROC-AUC, a widely used metric for anomaly detection, to quantify the performance of DSLAD and the baselines. The ROC curve is depicted by the true positive rate (y-variable) and the false positive rate (x-variable). AUC is the area enclosed by the ROC curve the x-axis. AUC always falls between 0 and 1. The better performance is indicated by the higher AUC.

We set neighboring subgraph size \(k\in Z^+\) in [2,10]. Layers of GNN encoders and GNN decoders are set as 3 on Flickr, and 1 on the other five datasets. The hidden dimension d is set as 64 while test rounds \(R=256\). The batch size is 300. We choose \(\pi (\beta ) = \beta\) and select \(\lambda\) from \(\{0.5,1,1.5,2,2.5,3\}\). Our proposed model is implemented in server with Ubuntu 20.04.1 LTS, Pytorch 1.10, dgl0.4.3post2, Intel(R) Xeon(R) Gold 6132 CPU @ 2.60GHz, and GeForce RTX 2080 Ti. We execute DSLAD over 8 times to measure the effectiveness statistically.

To verify the effectiveness of our model in anomaly detection task, we conducted comparison experiments for all baselines and DSLAD with AUC metric on six benchmark datasets and results are shown in Table 3. Based on the results, we can make the following observations:

The anomaly score measures the agreement among target nodes and positive (negative) samples. The semantic mixture can be revealed by the differences in the distribution of anomaly scores. To explore the semantic mixture between normal and abnormal nodes, we use the Wasserstein distance to describe the difference in the distribution of anomaly scores. The Wasserstein distance between the scores of normal and abnormal nodes on six datasets is demonstrated in Table 5. It can be observed that the result of Wasserstein distance meets with the result in Table 3. In terms of anomaly scores, there is a significant difference between normal nodes and abnormal nodes. The semantic mixture can be alleviated by our method.

In this subsection, we assess the effectiveness of the augmentation strategy to our method. As illustrated in Fig. 7a, our model is not sensitive to the augmentation strategy on Cora, and performs better with \(local\_aug\) than with \(global\_aug\) on the other datasets except for Flickr.

The main reason may be that Flickr has the most complex attribute information, which is more important than structure information. And on the other five datasets, structure information has a greater impact on the other five datasets than attribute information.

Based on the above observations, we choose \(global\_aug\) as augmentation strategy on Flickr, and \(local\_aug\) as augmentation strategy on the rest five datasets.

In this subsection, we investigate how different mapping functions \(\pi (\beta )\) would effect our model. Constant e.g. 0.5, linear growth e.g. \(\beta\), and activation function e.g. \(1-exp(-\beta ), sigmoid(\beta ),\)and \(tanh(\beta )\) are taken into consideration. As demonstrated in Fig. 7 (b), when setting \(\pi (\beta ) = \beta\), the best results are acquired, although our model is not sensitive to \(\pi (\beta )\) on Pubmed and Flickr. Linear \(\pi (\beta )\) also has the best generalization.

In this subsection, we conduct ablation studies for better understanding the effectiveness of each components in our method. Here, three variants are defined as:DSLAD w/o cl can be regarded as a variants with only anomaly detection. DSLAD w/o con can be regarded as a variants without context score. DSLAD w/o rec can be regarded as a variants without reconstruction score.

As shown in Table 6, DSLAD outperforms other variants, indicating that all components play an important role in our method and they could make mutual promotion. Removing contrastive representation learning and setting \(\pi (\beta ) = 1\) causes remarkable performance degradation. Obviously, decoupling anomaly detection and representation learning tremendously promotes anomaly discrimination by reducing class imbalance and lightening semantic mixture. Additionally, removing either context or reconstruction scores performance would result in performance degradation with the former being more noticeable.This demonstrates that context score and reconstruction score complement each other, while context scores are more effective for anomaly detection.

In order to verify that the semantic mixture and imbalance issue are resolved by decoupling anomaly detection and representation learning, we demonstrate the visualization of embeddings on Cora in Fig. 8. In Fig. 8a, CoLA can’t form sufficiently distinguishable clusters of the anomalous nodes. There are still quite a few anomalous nodes sporadically mixed with the normal nodes. The anomaly detection algorithms, which mainly optimize the model by anomaly discrimination, are often limited by insufficient expressiveness. In Fig. 8b, it can be observed that both the normal nodes and the anomalous nodes are denser and can be better discriminated by DSLAD than by CoLA. Decoupling anomaly detection and representation learning significantly solves the problems of semantic mixture and imbalance.

In this subsection, a series of experiments are conducted to study the effect of hyperparameters.