Reconstruction Enhanced Multi-View Contrastive Learning for Anomaly Detection on Attributed Networks

1 Introduction

Attributed networks are ubiquitous in many real-world scenarios, such as social networks and citation networks. Recently, anomaly detection on attributed networks is of great significance in many security-related applications, such as social spam detection [Jain et al., 2019], financial fraud detection [Wang et al., 2019] and network intrusion detection [Shone et al., 2018], and has attracted rising research interest. Though it has been extensively studied, detecting anomalies on attributed networks is still a challenging task [Ding et al., 2019]. One major challenge of this problem is that the abnormal patterns of nodes are related to not only their interactions with other nodes on the topological structure, but also their inconsistency in terms of node attributes [Ding et al., 2019; Peng et al., 2018].

∗Corresponding author

The early anomaly detection techniques, such as matrix factorization [Li et al., 2017] and OC-SVM [Erfani et al., 2016] have been widely used in many applications. A primary limitation of such methods is that they largely rely on feature engineering constructed by domain experts. Recently, deep learning techniques, especially Graph Neural Networks, have been widely used in various graph mining tasks (e.g. link prediction and node classification), and have achieved considerable performance gains. GNN-based techniques [Ding et al., 2021] have also been adopted to anomaly detection which aim to learn the anomaly-aware node representations. Due to the high cost of obtaining anomaly samples, anomaly detection is usually performed in an unsupervised manner. [Ding et al., 2019] proposed an unsupervised autoenconder-based method to detect the abnormal patterns effectively, which can capture the abnormal nodes according to the reconstruction errors. [Liu et al., 2021b] for the first time proposed a contrastive learning based framework for anomaly detection on graphs. Their model takes the local contextual information as supervision signals, and learns the representative features from the node-subgraph instance pairs. The final discriminative scores are used to detect abnormal nodes. [Jin et al., 2021] performed patch- and contextlevel contrastive learning via two GNN-based models to further improve the performance.

Although considerable research efforts have been devoted to this problem recently, we argue that the current approaches still have shortcomings due to the following reasons. First, local and global structural information are not well utilized and integrated. Existing SOTA approach [Liu et al., 2021b] typically constructed contrastive instance pair based on nodesubgraph to efficiently focus on the local information of a node for anomaly detection. They adopted one-layer GCN to extract the local structure information from the one-hop neighbors, while the global structure information beyond one-hop neighbors cannot be effectively captured and utilized. Previous studies show that higher-order neighboring information is also beneficial for graph mining tasks. [Ding et al., 2019] proposed to use the multi-layer GCN to capture the high-order interactions for anomaly detection on graphs, but the local and global structure information is modeled uniformly and coupled together, leading to information redundancy in feature representation learning. Meanwhile, GCN can be seen as a special form of low-pass filter, which has the effectiveness in smoothing signals [Bo et al., 2021]. Stacking multiple layers of GCN will more likely smooth out the abnormal signals. Therefore, a more effective and decoupled local-global structure information extraction and integration method is needed to provide high quality structure features. Second, how to effectively fuse the node attributes with network topological structures to further boost the detection performance is not well explored. Although GCN can handle both topological structure and attributes, the learned representations are not well suitable for anomaly detection under the unsupervised learning scenario [Liu et al., 2021b]. Anomalous nodes usually present inconsistency in terms of node attributes with their neighboring nodes, which provides us with additional self-supervised signals. How to fully utilize such signals and build an attribute reconstruction model based on the attribute consistency principle to further improve the anomaly detection performance is not well studied.

To alleviate the above drawbacks, we present a Subgraphbased multi-view self-supervised framework which contains a Contrastive-based module and a Reconstruction-based module (Sub-CR for convenience). Sub-CR can separate the local information from the global information instead of directly fusing them together, and alleviate the risk of smoothing out abnormal signals in GNN. Specifically, the original graph is first augmented by both graph diffusion and subgraph sampling to obtain local and global view subgraphs for each node. Then a two-view (intra- and inter-view) contrastive learning module is proposed. The intra-view contrastive learning aims to maximize the agreement between the target node and its subgraph-level representations of both views, here the agreement can be quantified as a discriminative score. The inter-view contrastive learning aims to make the discriminative score of the two views closer, which allows the model to encode both local and global information. In order to further utilize the self-supervised signals of the attribute consistency between the neighboring nodes, a masked autoencoder is also introduced to reconstruct the original attributes of the target node based on its neighboring nodes in both views. Finally, the two complementary modules are integrated for anomalous node detection. Our main contributions are summarized as follows:

• A novel self-supervised learning framework is proposed to address the problem of anomaly detection on attributed networks, which can effectively integrates contrastive learningbased and attribute reconstruction-based models.
• A multi-view learning model is proposed. Local and global information are modeled separately first and then integrated together, which can provide high quality features for detecting anomalous nodes.
• We conduct extensive experiments on five benchmark datasets for model evaluation. The results verify the effectiveness of our proposal and it outperforms existing state-ofthe-art methods.

2 RelatedWork

2.1 Anomaly Detection on Attributed Networks

The early work [Perozzi and Akoglu, 2016] proposed a quality measure called normality, which utilized structure and attributes together on attributed networks. [Li et al., 2017] proposed a learning framework to describe the residual of attributes and their consistency with network structure to detect anomalies in attributed networks. With the rapid development of deep neural networks, researchers also tried to adopt deep learning techniques to detect anomalies in attributed networks. [Ding et al., 2019] proposed to use GCN and autoencoder to measure the reconstruction error of nodes from the perspective of structure and attributes to identify anomalies, which can alleviate the network sparsity and data nonlinearity issues. [Yu et al., 2018] adopted a clustering-based method through the learned dynamic network representation to dynamically identify network anomalies based on clustering in an incremental manner. [Li et al., 2019] proposed SpecAE to detect global anomalies and community anomalies via a density estimation approach. [Liu et al., 2021b; Jin et al., 2021] proposed a contrastive self-supervised learning framework for graph anomaly detection, effectively capturing the relationship between nodes and their subgraphs to capture the anomalies.

2.2 Graph Contrastive Leaning

Recently, contrastive learning as an effective mean of selfsupervised learning [Liu et al., 2021a], has gained rising research interest, which aims to learn representations from supervised signals derived from the data itself. The core idea is that it considers two augmented views of the same data instance as positive sampler to be pulled closer, and all other instances are considered as the negative samplers to be pushed farther apart. Due to the great success of self-supervised learning on images [Chen et al., 2020], contrastive learning methods are also adopted to various graph learning tasks. [Velickovic et al., 2019] aimed to learn the node representations by maximizing the mutual information between the patch representation and the corresponding high-level graph summary. [Peng et al., 2020] directly maximized the mutual information between the input and output of the graph neural encoder according to the node features and topology to improve the DGI. [Zhu et al., 2020] proposed to generate two data views and then pull the representation of the same node in the two views closer, push the representation of all other nodes apart. [Zhu et al., 2021] proposed a contrastive framework for unsupervised graph representation learning with adaptive data augmentation.

3 ProblemFormulation

In this paper, for the convenience of presentation, the calligraphic fonts (e.g. G) represent sets, bold lowercase letters and bold uppercase letters represent vectors (e.g. x) and matrices (e.g. X), respectively. The terminology and problem definitions are given as follows. Let G = (V, E,X) denote an attributed network , where V ={v1, ..., vN} represents the set of nodes, N is the number of the nodes in the graph, E is the set of edges, X ∈ RN×F is the attribute matrix, where xi ∈ RF (i = 1, ...,N) is the attributes for the ith node, and A∈ RN×N is the adjacency matrix.

Problem Definition. Given an attributed network G = (V, E,X) whose adjacency matrix is A, we aim to learn an

(a) Graph diffusion & Subgraph sampling

(b) Contrastive learning & Attribute reconstruction

Figure 1: The framework of the proposed model.

anomaly score function score(·) to measure the degree of the abnormality for each node in G.

4 Methodology

As shown in Figure.1, the proposed Sub-CR contains a contrastive learning-based module and an attribute reconstruction-based module. We first construct two types of data augmentations: the subgraph sampling (left upper part in Figure.1) and the graph diffusion (left lower part in Figure.1), to get local and global view subgraphs for each node. For each view, both the subgraph and the target node are input into a GNN encoder to learn the embedding as shown in the middle part in Figure.1. Then we establish the intraand inter-view contrastive learning (right part in Figure.1) to encode local and global structure information. Meanwhile, we further introduce the masked autoencoder to identify the anomalous nodes through the attribute reconstruction errors in two views. Finally, the two complementary modules are integrated to give a final anomaly score.

4.1 Multi-ViewGraph Generation with Graph Diffusion and Subgraph Sampling

The effectiveness of the contrastive learning paradigm largely relies on the choice of the pretext task and the data augmentations [Liu et al., 2021a]. We adopt the node-subgraph matching pattern based pretext task which is proved useful for the anomaly detection on attributed networks [Liu et al., 2021b]. Meanwhile, the graph diffusion augmentation [Hassani and Khasahmadi, 2020] is introduced to get the global view of the structure, which allows each node to match with its localand global-view subgraphs respectively. Next, we introduce how to generate the two views of graph.

Graph Diffusion. We propose to use the graph diffusion as the first augmentation to obtain the global view graph. Graph diffusion can effectively capture the global structure information [Hassani and Khasahmadi, 2020; Klicpera et al., 2019].

This process is formulated as follows:

where θk is the weighting coefficient to control the proportion of local and global structure information and T ∈ RN×N denotes the generalized transition matrix to transfer the adjacency matrix. Note that θk ∈ [0, 1] and ∑∞k=0 θk = 1. In this paper, Personalized PageRank (PPR) [Page et al., 1999] is adopted to power the graph diffusion. Given the adjacency matrix A ∈ RN×N , the identity matrix I and its degree matrix D, the transition matrix and the weight can be formulated respectively as T = D-1/2AD-1/2 and θk = α(1 - α)k . Then the graph diffusion S can be reformulated as:

where α denotes the teleport probability in a random walk. The graph diffusion S is the global view of the initial graph.

Subgraph Sampling. We adopt random walk with restart (RWR) [Tong et al., 2006] to sample the local subgraph. In both views, a subgraph with the size P is sampled for each node. In particular, we sample nodes and their edges from the original view to form the local-view subgraph, and then select the exact nodes and edges from the other view to form the global-view subgraph. In each view, for node vi, its subgraph is regarded as its positive pair, and a subgraph corresponding to the other node is regarded as the negative pair.

4.2 Local &Global Graph Contrastive Learning

As mentioned before, the representation of a normal node is similar to that of the neighboring nodes in its subgraph while this does not hold for an abnormal node. Therefore, we define the intra-view contrastive learning in the local and the global views, which maximizes the agreement between the node and the corresponding subgraph-level representations. As shown in the right part of Figure.1, for node vi, the discriminative score of its positive pair should be close to 1, while the negative one should be close to 0. Meanwhile, the inter-view contrastive learning is defined between the two views. It aims to encourage the discriminative score that the same node between its subgraph in two views to be close.

Intra-View Contrastive Learning. This contrastiveness is defined in each view. Taking the local view in Figure.1 as an example, we obtain the corresponding positive and negative subgraphs Gi, ˜ Gi for the target node vi. Note that in order to make the obtained representation more discriminative, the attributes of the target node in the subgraph are masked. Then the subgraph are fed into a shared GCN encoder to learn a low-dimensional representation, which can be formulated as follows:

where ˆ Di ∈ RN×N is the degree matrix of A′i = Ai + IN, A′i is the subgraph adjacency matrix with self-loop, IN is the identity matrix and W0 ∈ RF×d is a learnable weight matrix. Since the target node is masked in the subgraph, we employ the weight matrix of GCN to map the features into the same embedding space. It can be formulated as:

where h0i = xi, φ is the activation function such as ReLU. So we obtain the representations Hi and ˜ Hi for the two-view subgraphs Gi, ˜ Gi, hi for the target node vi. In order to apply the node-subgraph matching pattern pretext task (the representation of node and its corresponding subgraph is more consistent), we take the average pooling function as the readout module to obtain the subgraph-level embedding vector ei:

where ni is the number of nodes in the subgraph Gi. So the discriminative scores for the positive pair can be defined as:

where Ws is a learnable matrix. Similarly, we can calculate ˜ si for the nagetive pair. Hence, the local view contrastive loss for the instance pair (vi, Gi, ˜ Gi) can be formulated as:

Besides, we can similarly calculate L2intra for the global view. Finally, by combining the two losses, we have the intra-view contrastive learning objective function defined below:

Inter-View Contrastive Learning. This contrastiveness is defined between the two views. Following the core idea in contrastive learning, we make the discriminative scores from node-subgraph pair of the two views closer. So the inter-view contrastive loss between the local- and global-view can be formulated as:

where s1, s2 are the vectors that consist of positive pair discriminative scores in the two views. By combining the intraand the inter-view contrastive learning, the overall loss function of the multi-view contrastive learning module is:

4.3 Attribute Reconstruction Based on Neighbors

The self-supervised learning method based on masked autoencoders (MAE) has been proved to be effective in many fields. For example, the BERT [Devlin et al., 2018]-based pre-training model has achieved remarkable results in many NLP tasks, and similar works are also proposed in CV [He et al., 2021]. The basic idea of these methods is to mask a part of a sentence or a picture and then input the unmasked part into the encoder and decoder for predicting the masked part.

Motivated by the masked autoencoder method, we propose to design an attribute reconstruction based on neighbors module to boost the performance. We adopt an asymmetric design. The encoder operates on the nodes in the subgraph that are not masked. The latent representations of these nodes are concatenated as the input of the lightweight decoder to reconstruct the masked node's raw attributes. Taking the local view as an example, for the subgraph Gi of node vi, we can get the representation of Gi through the GCN encoder. The reconstruction loss of the local view can be defined as:

where g(·) is the multilayer perceptron, Zi is the concatenation of neighboring nodes' representations in the subgraph. Similarly, we can calculate L2res for the global view. The overall loss function of this module can be formulated as:

4.4 Anomaly Score Inference

To jointly train the contrastive learning module and the attribute reconstruction module, we optimize the following objective function:

where γ is a controlling parameter which balances the importance of the two modules.

By minimizing the above objective function, we can compute the anomaly score of each node. Inspired by [Liu et al., 2021b], taking the node vi as an example, the anomaly score of the contrastive-based module can be calculated by:

where score1con (vi) = s1i -s1+ i , score2con (vi) = s2i -s2+ i , s1+ i (s2+ i ) and s1i (s2i ) are the local (global) view discriminantive scores of positive and negative pairs by Eq.(6). The anomaly score from the reconstruction-based module is:

where Z1i and Z2i are the concatenated neighboring node representations in local and global subgraphs for node vi, respectively. The two scores are first normalized, and then integrated by the following formula:

5 Experiments

5.1 Datasets

We evaluate the proposed model on five benchmark datasets that are widely used in anomaly detection on attributed networks [Liu et al., 2021b; Zheng et al., 2021]. These datasets include two social network datasets BlogCatalog and Flickr and three citation network datasets Cora, Citeseer, and Pubmed. Due to the shortage of ground truth anomalies, the anomalies are injected by the perturbation scheme [Ding et al., 2019]. The statistics of the datasets is shown in Table 1.

5.2 Experimental Settings

Baselines and evaluation metrics. In the experiments, we compare the proposed model with seven baselines. [Perozzi and Akoglu, 2016] evaluates the attribute correlation of node to detect anomalies. Specifically, it analyzes the abnormality of each node from the ego-network point of view. [Li et al., 2017] is a residual analysis-based method. It detects anomalies whose behaviors are singularly different from the majority [Peng et al., 2018] proposes a novel joint framework to conduct attribute selection and anomaly detection. [Ding et al., 2019] conducts the investigation on the problem of anomaly detection on attributed networks. [Velickovic et al., 2019] is an approach for learning node representations. A bilinear function is provied to score abnormality. [Liu et al., 2021b] is the first contrastive learning based method for graph anomaly detection. [Jin et al., 2021] is a recent method which performes patch- and context-level contrastive learning for anomaly detection on attributed networks. We use ROC and AUC to measure the performance.

Implementation Details. In Sub-CR, we set the node size P of subgraph to 4 for all datasets by considering both the efficiency and performance. Following [Liu et al., 2021b], we employ a one-layer GCN as the encoder, and the embedding dimension is set to 64. The model is optimized with the Adam optimizer during training. The bacth size is set to 300 for all datasets. The learning rate is set to 0.001 for Cora, Citeseer, Pubmed and Flickr, set to 0.003 for BlogCatalog. We train the model 400 epochs for BlogCatalog and Flickr, and 100

epochs for Cora, Citeseer and Pubmed. The parameter γ is set to 0.6 for BlogCatalog, Flickr, Cora and Citeseer and 0.4 for Pubmed. In the inference phase, we average the anomaly scores in Eq. (17) over 300 rounds to get the final anomaly score for each node.

5.3 Result and Analysis

Table 2 shows the comparison result of these methods in terms of AUC value. Due to space limitation, Figure.2 shows the ROC curves on Cora, BlogCatalog, Citeseer, and Flickr with two competitive baselines. As shown in the table, one can first see that our proposed model is superior to its counterparts on five benchmark datasets, which demonstrates the effectiveness of Sub-CR. To be specific, Sub-CR improves the performance by 3.38% and 1.61% over the best baseline ANEMONE on Flickr and Pubmed datasets, respectively. In details, the shallow methods including AMEN, Radar and ANOMALOUS perform worse than other models due to their less effectiveness in modeling the high-dimension node attributes and complex tological structures. The DOMINANT and DGI also do not show the competitive performance because they focus on modeling the whole graph structure instead of directly explore the abnormal patterns. DGI takes the node vs full-graph intstance pair contrastive, and DOMINANT aims to reconstruct the whole graph structure or attributes for each node, which do not decouple local and global information for anomaly detection. CoLA and ANEMONE achieve the suboptimal performance due to the consideration of sorrounding substructures. But they cannot fully catch the high-order structure information and ignore the selfsupervised signal of the original attribute reconstruction error. The superior performence of Sub-CR verifies the effectiveness of intergating the multi-view contrastive-based and reconstruction-based modules, which can decouple local and global information to better capture the attribution and the topological structure of nodes for anomaly detection.

5.4 Ablation Study

We next conduct an ablation study to verify the effectiveness of each component in Sub-CR. Sub-R and Sub-C denote the model without reconstruction-based and contrastivebased module, respectively. The variants Sub-weight and Sub-global are defined as that we remove the balance weight ( γ is set to 1) and the global view, respectively. The results are presented in Table 3. One can see that Sub-CR outperforms all the variants consistently on all the datasets, which demonstrates the components are all helpful to the studied task. Especially, Sub-CR outperforms Sub-C by 6.81%, 5.41%,

9.12%, 14,11%, 17.03% on five datasets, respectively, which demonstrates the contrastive-based module is crucially important to the model. The self-supervised signal of the matching pattern on the node-subgraph pair is more effective for capturing anomalies. As for the remaining three components, Sub-R performs worse than Sub-weight and Sub-global on BlogCatalog, Flickr, and CiteSeer datasets. On the Cora, the component of the global view is more important. Sub-weight has a more significant effect on Pubmed. The reason may be that the effect of different modules on different datasets varies due to the different data characteristics.

5.5 Parameter Study

We finally conduct the model sensitivity analysis on critical hyper-parameters in Sub-CR, which are the size P of subgraph, the embedding dimension in GCN and the balance factor γ. Figure.3 shows the effect of different γ values on the model performance. One can see that the most datasets can achieve the best result and not sensitive to the balance factor when γ ≥ 0.4. Figure.4 shows the AUC values under different subgraph sizes and embedding dimensions. One can observe that the best performance for Flickr and Citeseer is achieved at P = 2, and for BlogCatalog, Cora and PubMeb it is achieved at P = 4. When the size is too large, the subgraph will contain redundant information, which will hurt the performance. A suitable embedding dimension is d = 64 for most datasets as shown in the figure. A too small or large embedding dimension will both degrade the model performance.

6 Conclusion

In this paper, we propose a novel multi-view self-supervised learning framework for anomaly detection on attributed networks. The proposed contrastive learning-based module consists of two carefully designed contrastive views to better capture local and global structure information related to anomaly patterns. The attribute reconstruction module adopts the representation of those neighbors based on the subgraph to rebuild the raw attributes of the target node of the two views. Finally, the two complementary modules are integrated for more effective anomaly detection. Extensive experiments conducted over five benchmark datasets demonstrate the effectiveness of our proposed model.

Acknowledgements

This work was supported by NSFC under granted No. 62076124, partially financially supported by the National Science and Technology Major Project (J2019-IV-0018-0086), NSFC (No. 62172443), and the Fundamental Research Funds for the Central Universities (No. NZ2020014).