Guarding Graph Neural Networks for Unsupervised Graph Anomaly Detection
Yuanchen Bei Sheng Zhou Jinke Shi Yao Ma Haishuai Wang Jiajun Bu









        





IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS
Shell et al.: A Sample Article Using IEEEtran.cls for IEEE Journals





Guarding Graph Neural Networks for 
Unsupervised Graph Anomaly Detection
    Yuanchen Bei,
        Sheng Zhou,
        Jinke Shi,
        Yao Ma,
        Haishuai Wang,
        and Jiajun Bu

    Yuanchen Bei, Jinke Shi, Haishuai Wang, and Jiajun Bu are with the College of Computer Science and Technology, Zhejiang University, Hangzhou, China. E-mail: yuanchenbei@zju.edu.cn; shijinke@zju.edu.cn; haishuai.wang@zju.edu.cn; bjj@zju.edu.cn.
    Sheng Zhou is with the School of Software Technology, Zhejiang University, Hangzhou, China. E-mail: zhousheng_zju@zju.edu.cn.
    Yao Ma is with the Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA. E-mail: majunyao@gmail.com.
    
    

    April 29, 2024
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




    Unsupervised graph anomaly detection aims at identifying rare patterns that deviate from the majority in a graph without the aid of labels, which is important for a variety of real-world applications.
Recent advances have utilized Graph Neural Networks (GNNs) to learn effective node representations by aggregating information from neighborhoods.
This is motivated by the hypothesis that nodes in the graph tend to exhibit consistent behaviors with their neighborhoods.
However, such consistency can be disrupted by graph anomalies in multiple ways.
Most existing methods directly employ GNNs to learn representations, disregarding the negative impact of graph anomalies on GNNs, resulting in sub-optimal node representations and anomaly detection performance. While a few recent approaches have redesigned GNNs for graph anomaly detection under semi-supervised label guidance, how to address the adverse effects of graph anomalies on GNNs in unsupervised scenarios and learn effective representations for anomaly detection are still under-explored.
To bridge this gap, in this paper, we propose a simple yet effective framework for Guarding Graph Neural Networks for Unsupervised Graph Anomaly Detection ().
Specifically, introduces two auxiliary networks along with correlation constraints to guard the GNNs from inconsistent information encoding. Furthermore, introduces an adaptive caching module to guard the GNNs from solely reconstructing the observed data that contains anomalies.
Extensive experiments demonstrate that our proposed can outperform seventeen state-of-the-art methods on both synthetic and real-world datasets. 





graph anomaly detection, graph neural networks, unsupervised anomaly detection, graph learning.




§ INTRODUCTION

Graph anomaly detection aims to identify rare patterns or behaviors that significantly deviate from the majority of a graph <cit.>.
It has attracted increasing attention from both academia and industry due to its practical applications, such as network intrusion detection <cit.>, social spammer detection <cit.>, and financial fraud detection <cit.>.
The scarcity of anomaly labels in real-world applications, coupled with the challenge of acquiring such labels, has led to a widespread study of unsupervised graph anomaly detection <cit.>.
Pioneer works on graph anomaly detection have separately mined the attributed anomalies and topological anomalies by feature engineering and graph structure encoding, respectively <cit.>.
Recent breakthroughs in Graph Neural Networks (GNNs) have empowered the unified modeling of attributes and topology, leading to significant advancements in graph anomaly detection  <cit.>.













The success of representative GNNs, as illustrated in Figure <ref>-(a), has heavily relied on aggregating information from neighborhoods sharing similar patterns, e.g. label homophily and feature consistency <cit.>. 

Although successful, in graphs with anomalies, we argue that this foundation can be easily undermined by various graph anomalies in multiple ways <cit.>.
Figure <ref>-(b-d) illustrates toy examples of the three main types of graph anomaly impacts on GNNs.
(i) As illustrated in Figure <ref>-(b), the attributed-induced anomalies where node features are corrupted, such as the account takeover in social networks, will directly result in aggregating incorrect information from neighborhoods.
(ii) As illustrated in Figure <ref>-(c), the topological-induced anomalies that connect to incorrect neighborhoods, such as the fraudsters in E-commerce systems, will result in aggregating information from inconsistent neighborhoods.
(iii) More seriously, as illustrated in Figure <ref>-(d), the mixed anomalies that simultaneous occurrence of multiple anomaly types is a more common situation and will have a significantly more detrimental impact on GNNs.

Existing unsupervised graph anomaly detection methods have primarily focused on designing effective unsupervised anomaly scoring functions within the representation space learned directly from GNNs while overlooking the negative impact of anomalies on the inherent GNNs themselves <cit.>. 
This is crucial for accurate anomaly detection, which is indispensable to discriminative node representations.
Under this limitation, the representation learning ability of GNNs is hampered to adequately capture the normal patterns in the graph, thereby leading to suboptimal representation learning and anomaly detection performance. Hence, it is crucial to alleviate the negative impact of anomalies and fully release the power of GNNs for anomaly detection.



Although important, addressing the negative impacts of graph anomalies on GNNs
in unsupervised scenarios is non-trivial.
An intuitive solution might involve the development of innovative GNNs that adapt to certain graph anomalies. This has attracted increasing attention and the few very recent works have achieved tremendous success in semi-supervised scenarios <cit.>. 
However, the lack of labels in unsupervised anomaly detection poses a significant challenge in guiding the redesign of GNNs, which is more commonly encountered in practice.
More importantly, while anomalies do exist on the graph and exert certain effects on GNNs, they account for only a small fraction of the total. The majority of patterns remain normal and can be effectively captured by GNNs. Therefore, a complete redesign or deprecation of GNNs could risk compromising the identification of the majority of normal patterns due to the influence of a minor proportion of anomalies, especially in unsupervised contexts.
Therefore, how to reduce the impact of anomalies on GNNs while enabling them to capture the majority of normal patterns effectively and aid in unsupervised anomaly detection?













To answer the above under-explored research question, in this paper, we propose a simple yet effective framework for Guarding Graph Neural Network for Unsupervised Graph Anomaly Detection (). 
Instead of directly encoding the observed graph with anomalies, first introduces two auxiliary encoders tailored with correlation constraints to guard the GNNs against encoding inconsistent information.

Subsequently, to optimize GNNs in an unsupervised manner and detect multiple types of unknown anomalies, proposes a comprehensive learning objective that includes both local attribute/topology reconstruction and global consistency alignment, which also serves as anomaly scoring. 
Finally, instead of directly reconstructing the observed graph with anomalies, integrates an adaptive caching module to guard the GNNs from misleading learning objectives.


Figure <ref> illustrates the comparison between the existing GNN-based unsupervised graph anomaly detection paradigm and the one under framework.
Extensive experiments on both synthetic and real-world graph anomaly detection datasets demonstrate that outperforms seventeen state-of-the-art unsupervised graph anomaly detection models.
The main contributions of this paper are summarized as follows:


    
  * We emphasize the negative impact of unknown anomalies on GNNs, which is crucial for graph anomaly detection under unsupervised settings while overlooked by most existing unsupervised works.
    
  * We propose , a simple yet effective framework to guard GNNs from encoding inconsistent information and directly reconstructing the abnormal graph in unsupervised graph anomaly detection.
    
    
    
  * We conduct extensive experiments on seven widely-used datasets including both synthetic and real-world scenarios. Experimental results show that the proposed outperforms seventeen state-of-the-art methods. 


In the following sections, we will first review the previous work related to our method in Section <ref>. Second, we will give some key preliminaries of our work in Section <ref>.
Then, the detailed description of the proposed will be introduced in Section <ref>.
To further verify the effectiveness of , we conduct various experiments in Section <ref>.
Finally, the conclusion of this paper is posed in Section <ref>.




§ RELATED WORKS



 §.§ Graph Neural Networks

Graph Neural Networks (GNNs) are a series of deep learning models specifically designed for processing graph-structured data <cit.>. The core design of GNNs is to learn node representations by aggregating and propagating information from neighborhoods to the central nodes. This information propagation (message passing) allows GNNs to capture complex topology dependencies and contextual information among nodes <cit.>.

Typically, in GNNs, each node has an initial feature representation, and through multiple layers of message aggregation and propagation operations, the node representations are gradually updated and refined <cit.>.
Representatively, GCN <cit.> adopts the graph convolution operator and stacks it into multiple layers for neighbor message passing. GAT <cit.> further introduces the attention mechanism to consider the different importance of neighbor nodes and dynamically assign different weights when aggregating neighbor features. GraphSAGE <cit.> extends and improves the graph convolution to handle large-scale graph data, with the key idea of generating node representations through sampling and aggregating neighbor nodes.


Due to the fact that real-world data can be widely modeled as graphs, GNNs have emerged as a significant branch within the field of neural network research <cit.>. They possess the ability to perform learning on graph-structured data, automatically extracting features and making predictions, providing an effective solution for tasks on graph data.
Based on these advantages, GNNs have achieved significant success in various application domains, such as social network analysis <cit.>, recommendation systems <cit.>, and bioinformatics <cit.>. 





 §.§ Unsupervised Graph Anomaly Detection

Graph anomaly detection technologies have been widely applied in real-world systems to ensure their robustness and security, such as financial transaction networks <cit.>, social network applications <cit.>, and E-commerce  systems <cit.>.
Due to the sparsity of anomalies and the high cost of acquiring anomalous labels, unsupervised anomaly detection has become an important research direction in recent years.

Existing graph anomaly detection methods under unsupervised manners can be largely divided into four main categories.
(i) Classical shallow models: SCAN <cit.> can be utilized for anomaly detection based on structural similarity. MLPAE <cit.> detects anomalies with nonlinear transformations.
(ii) Enhanced graph neural networks: GAAN <cit.> utilizes a generative adversarial framework to train the graph encoder with real graph and anomalous fake graph samples. ALARM <cit.> proposes a multi-view representation learning framework with multiple graph encoders and a well-designed aggregator. AAGNN <cit.> then enhances the graph neural network with an abnormality-aware aggregator. 
(iii) Deep graph autoencoder models: Dominant <cit.> first introduces a deep graph autoencoder model with a shared encoder to measure anomalies by reconstruction error.
SpecAE <cit.> utilizes a spectral graph autoencoder and Gaussian Mixture Model to perform the detection. 
AnomalyDAE <cit.> introduces asymmetrical cross-modality interactions between autoencoders. 
ComGA <cit.> further designs a community-aware tailored graph autoencoder to make the representation between normal and anomalous nodes more distinguishable. 
(iv) Graph contrastive learning methods: CoLA <cit.> exploits the local information and introduces a self-supervised graph contrastive learning method to detect anomalies.
Further, ANEMONE <cit.> utilizes the graph contrastive learning method in multi-scale.
SL-GAD <cit.> performs anomaly detection from both generative and multi-view contrastive perspectives.
Sub-CR <cit.> then proposes a self-supervised method based on multi-view contrastive learning with graph diffusion and attribute reconstruction.

However, the above GNN-based models directly apply the message passing without anomaly guarding, neglecting the inconsistent neighborhood of attribute and topology, thus the performance of GNNs is limited.



 §.§ Neighborhood Consistency in Graphs

The nature that neighboring nodes in real-world graphs tend to share consistent behaviors, such as labels or attributes <cit.>, has been the foundation of many GNNs.
As introduced in Section <ref>, pioneer representative works of GNNs<cit.> have utilized the neural message passing by aggregating information from neighbors, which is a straightforward way of applying the feature consistency.
Later works have proved that such message passing is equivalent to classic label propagation where the labels are propagated along with the connection between neighboring nodes <cit.>.
This can be viewed as utilizing the neighborhood consistency in labels, which is also widely called the homophily assumption in practice <cit.>.

However, the homophily assumption may not always hold in real-world graphs <cit.>.
To tackle this challenge, recent works have been made on the heterophily GNN for representation learning under graphs with low neighborhood consistency. 
Representatively,
MixHop <cit.> mixes powers of the adjacency matrix for graph convolution to ease the limitation.
H2GCN <cit.> designs a model with ego & neighbor separation, higher-order neighbors, and intermediate representations combination.
LINKX <cit.> separately embeds the adjacency and node features with simple MLP transformations rather than the aggregation based on neighborhood consistency.
GloGNN <cit.> performs aggregation from the whole set of nodes with both low-pass and high-pass filters.


Nevertheless, in unsupervised graph anomaly detection, these heterophily GNNs mentioned above are not directly appropriate, due to the unknown neighborhood inconsistency in attribute and topology under the unsupervised setting and the overlook of the anomaly-specific design.




§ PRELIMINARIES

In this section, we present some key notations and definitions related to our target unsupervised graph anomaly detection task. 
Note that we focus on node-level graph anomaly detection in this paper.
For the convenience of readers, we list the main symbols used in this paper in Table <ref>.






Notations. Let = (A, X) be a graph with the node set = {v_1, v_2, ..., v_n} and the edge set , where || = n. A∈ℝ^n × n denotes the graph adjacency matrix, for each element A_i,j∈A, A_i,j = 1 indicates that there is an edge between node v_i and node v_j, and otherwise A_i,j = 0. X∈ℝ^n × d denotes the node attribute matrix, the i-th row vector x_i = X[i,:] ∈ℝ^d indicates the attribute vector of v_i with d dimensional representation.
_i is the neighborhood set of a central node v_i in the graph .


    Graph Neural Networks: In form, for an L-layer GNN, the calculation process of each layer can be expressed as the aggregation and updating operators. In the aggregation phase, each central node aggregates the message from its neighbor nodes:
    
    m_i^(l+1) = Aggregator({h_j^(l)|j∈_i}),

    where the function Aggregator(·) is the message aggregation operator to aggregate information from nodes' neighborhoods, h_j^(l) is the representation of node v_j in the l-th GNN layer, and m_i^(l+1) is the aggregated message for node v_i in the (l+1)-th GNN layer. After obtaining the aggregated message, in the updating phase, each central node adopts the aggregated information to update and transform its own representations:
    
    h_i^(l+1) = Updater(h_i^(l), m_i^(l+1)),

    where the function Updater(·) is the node representation updating operator and h_i^(l+1) is the updated representation of node v_i.




    Graph Anomalies: Given an abnormal attributed graph = (A, X) containing n node instances, and k of them are graph anomalies (k ≪ n), whose attributes, connections or behaviors are different from most other normal nodes.
    On a graph with anomalies, each node v_i is associated with an anomaly label y_i∈Y, where Y denotes the anomaly label set and each element y_i∈{0,1} denotes whether node v_i is an anomaly. Note that the anomaly label set Y is invisible in the unsupervised setting.



    Unsupervised Graph Anomaly Detection: Given an abnormal attributed graph = (A, X) containing n node instances, and k of them are anomalies (k ≪ n), whose attributes, connections or behaviors are different from most other normal nodes.
    The target of unsupervised graph anomaly detection is to learn a model (·): ℝ^n × n×ℝ^n × d→ℝ^n in an unsupervised manner that outputs anomaly score vector S∈ℝ^n to measure the degree of abnormality of nodes. Specifically, the i-th element s_i in the score vector S indicates the abnormality of node v_i, where a larger score means a higher abnormality.







§ METHODOLOGY







In this section, we present the details of the Guarding Graph Neural Network for Unsupervised Graph Anomaly Detection (). The overall framework of is illustrated in Figure <ref>. 
Generally, framework follows a representative GNN-based anomaly detection scheme where the GNNs learn the representations, and the representations are optimized with unsupervised objectives and measured for anomaly detection.
Besides, introduces two novel guarding strategies to the paradigm, namely guarding against encoding inconsistent information and guarding against reconstructing abnormal graphs, so that the GNNs can produce effective representations and boost the anomaly detection ability. With carefully designed guarding strategies and equipped anomaly detection tasks, can outperform current GNN-based models.
In the rest of this section, we will introduce the details of these guarding strategies and how serves unsupervised graph anomaly detection.

















 





 §.§ Guarding GNNs against Encoding Inconsistent Information




Motivation. As discussed in previous works, GNNs are designed for capturing consistent information from neighborhoods <cit.>. However, in graphs with anomalies, the anomaly-induced inconsistent patterns in unsupervised graph anomaly detection have been largely overwhelmed and will negatively disrupt the GNN performance.


Therefore, first introduces two auxiliary encoders with correlation constraints to design an encoding guarding strategy for GNNs.

Specifically, the auxiliary encoders are expected to encode the inconsistent information from the attribute and topology perspectives, and the GNNs are guarded against encoding the inconsistent information under the correlation constraints among the representation learned by the three encoders.






  §.§.§ GNN Encoder
 
The GNN encoder is utilized for encoding the part of the information that satisfies the consistent homophily assumption, which is shared by both attribute and topology. 


To focus on the model architecture, we adopt a two-layer Graph Attention Network (GAT) <cit.> as the GNN encoder f_gnn(·) for simplicity. It is worth noting that any other GNNs can be directly applied here.
Given the input attributes x_i and x_j of node v_i and its neighbor v_j, a GAT layer learns the input attributes with the attention mechanism. The attention coefficient is computed as:

    e_i,j=att(x_i, x_j)=LeakyReLU(a^T·[W_encx_i||W_encx_j]),

where att(·) is a single-layer feedforward neural network, parameterized by weight vector a∈ℝ^2d' and W_enc∈ℝ^d' × d with the transformed dimension d', || denotes the concatenate operation. The attention coefficient α_i,j is normalized as:

    α_i,j=softmax(e_i,j)=exp(e_i,j)/∑_k ∈_iexp(e_i,k),

where _i denotes the neighbor set of node v_i. 
Then, the final output feature h_i∈ℝ^d' of node v_i can be obtained as:

    h_i=∑_j ∈_iα_i,jW_encx_j.

For convenience, we use H^(c)∈ℝ^n × d' denote the output representation of consistency encoder f_gnn(·).






  §.§.§ Auxiliary Encoders with Correlation Constraints

In our , the attribute-auxiliary encoder and the topology-auxiliary encoder are further utilized for encoding the part of information dependent on each information source (attribute and topology) as well as the potential specific type of anomalies under the attribute/topology inconsistent situation.




Existing methods directly utilize GNNs to model the attribute and topology simultaneously. However, in the part where the consistency is destroyed by anomalies, message passing in GNNs will introduce negative noise information, even helping the anomalies to camouflage when passing normal messages to them <cit.>. Therefore, we use two independent MLPs rather than GNN encoders to better model the inconsistent attribute/topology patterns and guard the GNN encoder learning.

Specifically, the two independent MLPs f_a(·) and f_t(·) are applied to encode the original attribute matrix X and the adjacency matrix A, respectively:

    H^(a) = f_a(X),  H^(t) = f_t(A),




where f_a(·), f_t(·) are two MLPs with learnable parameters W_a and W_t respectively, and H^(a), H^(t)∈ℝ^n × d' are the corresponding output matrices. 

To ensure better guarding of the GNN encoder against those inconsistent patterns, it is desired that the representations encoded from the GNN and the auxiliary encoders are more independent of each other. 
Therefore, we impose the correlation constraint on the embedding space of the encoded representation to ensure all aspects of information H^(a), H^(t), and H^(c) are well-disentangled encoding.


Specifically, the correlation constraint between each pair of encoded representation aspects is designed as the absolute correlation coefficient measurement. Minimizing the constraint ensures the two paired vectors to become more independent <cit.>. Take the constraint between H^(a) and H^(t) as an example, the formal expression is as follows:

    aCor(H^(a), H^(t)) = abs(Cov(H^(a), H^(t))/√(Var(H^(a)) · Var(H^(t)))),

where Cov(·) is the covariance between two matrices, and Var(·) is a matrix's own variance, and abs(·) is the absolute value function. aCor(H^(a), H^(c)) and aCor(H^(t), H^(c)) can be calculated in the same way.
The overall regularization _cc of all correlation constraints can be presented as:

    _cc =     aCor(H^(a), H^(c)) + aCor(H^(t), H^(c)) 
       + aCor(H^(a), H^(t)),

where the calculated _cc is utilized as a correlation regularization loss during the model training stage.





 §.§ Guarding GNNs against Reconstructing Abnormal Graph

Motivation. 
Graph anomalies have various types, including attribute anomalies, topology anomalies, and mixed anomalies. In unsupervised graph anomaly detection, we are unable to know either anomaly labels or anomaly types. Thus, aims to comprehensively detect different anomaly types in the following ways:


    
  * Local attribute reconstruction: the attribute reconstruction errors distinguishing sparse attribute anomalies from the predominant normal nodes. 
    
  * Local topology reconstruction: the topology reconstruction errors distinguishing sparse topology anomalies from the primary normal nodes. 
    
  * Global consistency alignment: the alignment distance between node representations encoded by the GNN and the global graph consistency vector can further be equipped for mixed anomalies distinguishing.
    

Among these objectives, the graph reconstruction scheme has been proven to be essential for both representation optimization and anomaly detection under the unsupervised setting <cit.>.
However, reconstruction targets are needed to make GNN-encoded representations to fit the observed graph data with anomalies. 
The unknown anomalies in the abnormal graph may provide a misleading objective for both tasks.
Thus, further introduces the adaptive caching to guard the GNNs against reconstructing abnormal graphs by cooperating with the auxiliary encoders that partake the inconsistent anomaly patterns.



  §.§.§ Adaptive Caching








From the consistent alignment perspective, since the consistent information encoded by the GNN encoder has already been guarded, it should be directly used for measuring the global consistency under a mixture of attribute and topology information. 

Yet from the attribute/topology reconstruction perspective, due to the graph to be reconstructed containing anomalies, it is necessary for further guarding the GNN-encoded representations against directly reconstructing and preserving the abnormal graph. 

Therefore, we design an Adaptive Caching (AC) module to concurrently leverage the GNN-encoded representations for normal part reconstruction and auxiliary-encoded representations for inconsistent part reconstruction, avoiding the force of GNNs to fit inconsistent anomaly patterns.
It automatically selects appropriate information for the reconstruction of normal and abnormal parts from GNN representation and auxiliary representation under unsupervised conditions, through learnable parameters.







The general AC module can be formulated as follows:

    imp = Tanh(τ(H^(1)||H^(2))),
    AC(H^(1),H^(2)) = imp_[:n]·H^(1) + imp_[n:]·H^(2),

where τ(·) is an MLP for information fusion, imp∈ℝ^2n is the weight vector of each dimension of the input features, H^(1) and H^(2) denote two information sources, such as H^(a), H^(t), and H^(c).

The AC module is utilized to generate two types of representations for attribute and topology reconstruction:






    Z_A = AC(H^(a),H^(c)),  Z_T = AC(H^(t),H^(c)),

where Z_A and Z_T are the cached attribute representation and cached topology representation.
Compared with vanilla GNN-based representation, the caching of GNN-encoded and attribute/topology-specific information automatically selects helpful information and better alleviates anomalies’ impact on the GNN-encoded representations.



  §.§.§ Anomaly Detection Tasks

Given the GNN encoded representation, cached attribute representation, and cached topology representation, we aim to make full use of them for anomaly scoring in an unsupervised setting.

Therefore, as the above definition of the three types of anomaly detection objections, the detection tasks can be unfolded as follows.









Local attribute reconstruction:
The reconstruction-based operator has been widely observed to be effective for unsupervised anomaly detection <cit.>.
Therefore, given the cached attribute representation Z_A, we utilize the node's attribute reconstruction ability for attribute anomaly mining, benefiting from the reconstruction target tending to fit the patterns of the predominant nodes while the patterns of anomalies are rare <cit.>.
We use a two-layer Graph Convolution Network (GCN) <cit.> as the attribute reconstruction function g_a(·) as follows:

    R^(l+1) = LeakyReLU(ÃR^(l)W_re^(l)),

where Ã=D̂^-1/2A^*D̂^-1/2∈ℝ^n × n is the normalized adjacency matrix, D̂∈ℝ^n × n is the degree matrix of A^*=A+I where I is the identity matrix. R^(l), W_re^(l) is the input features, trainable parameters in l-th layer, respectively. 



For the cached attribute representation Z_A, g_a(·) reconstructs the attribute matrix X̂∈ℝ^n × d with corresponding distance-based reconstruction loss _attr, which can be computed as:

    X̂=g_a(Z_A, A),
    _attr = ||X-X̂||_2^2,

where ||·||_2^2 is the Euclidean distance.

Local topology reconstruction:
Similar to the perspective of local attribute reconstruction, for the given cached topology representation Z_T, the topology reconstruction capability is also a factor for anomaly detection due to topology anomalies' rare and inconsistent local topological patterns.
The reconstruction function g_t(·) reconstructs the adjacency matrix from Z_T with the reconstruction loss _topo as follows:

    Â=g_t(Z_T)=Z_T·Z_T^',
    _topo = ||A-Â||_2^2,

where g_t(·) is designed as an inner product between Z_T and its self-transposition Z_T^' to make the reconstruction efficient.


Global consistency alignment:
Given the GNN encoded representation H^(c) to detect mixed anomalies, a naive way for evaluating both attribute and topology is to measure the distance between node embeddings and their corresponding subgraph.
However, the anomalies may occur as neighbors of normal nodes under the neighborhood inconsistency, aligning the node with a noisy subgraph may be suboptimal.
Thus, we turn to measure each node embedding with the graph summary vector for global consistency measurement to reduce the negative impact of neighborhood on the summary vectors.

Specifically, to conduct the alignment, we first read out the consistent GNN-encoded representations of nodes into a graph summary representation:

    E_g=Readout(H^(c)),

where Readout(·) can be a kind of pooling operation (such as min, max, mean, and weighted pooling <cit.>), here we use the mean pooling as default for simplicity, E_g is the readout representation of the graph.

Then we conduct the global consistency alignment task between each node's GNN-encoded representation z_c,i∈H^(c) and the graph summary vector E_g as follows:

    _cons=log(√(∑_i=1^n||z_c,i-E_g||_2^2)+e),

where z_c,i is the consistent representation of node v_i, e is a constant to limit the lower bound of the loss for better balance _cons's numerical relationship with other loss terms.




 §.§ Anomaly Scoring

With the three different anomaly detection tasks, we utilize the above three anomaly detection tasks for the final anomaly scoring.

The normal nodes in the graph are expected to show low discrepancies, while anomalies exhibit high discrepant values due to their inconsistency, irregularity, and diversity.
Therefore, here we compute the anomaly score s_i of each node v_i in multi-perspectives according to:

    s_i=   λ_1·||x_i-x̂_i||_2^2_Local Attribute Reconstruction + (1-λ_1)· ||a_i-â_i||_2^2_Local Topology Reconstruction
       +λ_2· log(√(||z_c,i-E_g||_2^2)+e)_Global Consistency Alignment,

where λ_1 is a hyperparameter to balance the attribute and topology reconstruction, and λ_2 also is a hyperparameter that measures the effect of the global consistency alignment.
Nodes with larger scores are more likely to be considered as anomalies, thus we can compute the ranking of anomalies according to the nodes' scores calculated as Eq.(<ref>).




 §.§ Joint Training Objective Function

To jointly train the different aspects of anomaly scoring loss with the correlation constraint for GNN guarding, the joint training objective function of :



    = λ_1·_attr + (1-λ_1)·_topo + λ_2·_cons + _cc,

where the hyperparameters λ_1 and λ_2 here are the same as mentioned in Eq.(<ref>).
In this way, is trained using the gradient descent algorithm on the designed joint training objective function.





Conclusively, the pseudocode of the overall procedure workflow of is described as the given Algorithm <ref>. In each training epoch, first encodes three aspects of representations by the guarded GNN encoder along with the auxiliary encoders. Further, we adopt the correlation constraint to minimize correlations between the three representations. Before conducting the anomaly detection tasks, the adaptive caching module is equipped for GNN representation guarding. Then, anomaly detection tasks are conducted for anomaly scoring and joint objective loss obtaining. A backpropagation is then executed with a gradient descent algorithm to optimize the parameters of . Finally, the anomaly scores are returned for each node to evaluate their abnormality.






 §.§ Complexity Analysis

In this subsection, we conduct the complexity analysis of . First, the time complexity of encoding is max((f_a(·), f_t(·), f_gnn(·))). The complexity of f_a(·) and f_t(·) is (|| d F), and the complexity of f_gnn(·) is ((|| + ||) dF), where F is the summation of all feature maps across different layers. Therefore, the complexity of the encoding guarding part is ((|| + ||)dF).
Then, the complexity of the AC(·) module is (|| dF), and the global consistency alignment can be processed simultaneously with (|| dF).
Finally, the time complexity of the reconstruction modules is max((g_a(·), g_t(·))), where (g_a(·)) is (|| dF) and (g_t(·)) is (||^2).
To sum up, the overall time complexity of is ((|| + ||)dF+max(|| dF, ||^2)).






§ EXPERIMENTS

In this section, we conduct comprehensive experiments to demonstrate the effectiveness of . Specifically, we aim to answer the following research questions:

    
  * RQ1: How does perform compared with state-of-the-art models?
    
  * RQ2: How much do the architecture and components of contribute?
    
    
  * RQ3: How well does disentangled encode the information in each encoder? And how does perform on different types of anomalies?
    
  * RQ4: How do key hyper-parameters impact 's anomaly detection performance?




 §.§ Experimental Settings



  §.§.§ Datasets

We adopt seven graph anomaly detection datasets on both synthetic and real-world scenarios that have been widely used in previous research <cit.>, including five synthetic datasets: Cora, Citeseer, Pubmed <cit.>, ACM, and Flickr <cit.>, and two real-world datasets: Weibo <cit.>, and Reddit <cit.>.
The statistics are shown in Table <ref>.
The details of the datasets are introduced as follows.

    
  * Cora [<https://linqs.soe.ucsc.edu/datac>] <cit.> is a classical citation network consisting of 2,708 scientific publications (contains 150 injected anomalies) along with 5,429 links between them. The text contents of each publication are treated as their attributes.
    
  * Citeseer <ref> <cit.> is also a citation network consisting of 3,327 scientific publications (contains 150 injected anomalies) with 4,732 links. The node attribute in this dataset is defined the same as the Cora dataset.
    
  * Pubmed<ref> <cit.> is another citation network consisting of 19,717 scientific publications (contains 600 injected anomalies) with 44,338 links. The node attributes in this dataset are also defined as the Cora dataset.
    
  * ACM[<http://www.arnetminer.org/open-academic-graph>] <cit.> is another attributed citation network from the academic field, of which each paper is regarded as a node and the links are the citation relations among papers. It consists of 16,484 nodes (containing 600 injected anomalies) with 71,980 links between them. The attributes of each paper are generated from the paper abstract. 
    
  * Flickr[<http://socialcomputing.asu.edu/pages/datasets>] <cit.> is a social network dataset acquired from the image hosting and sharing website Flickr. In this dataset, 7,575 nodes denote the users (contains 450 injected anomalies), 239,738 edges represent the following relationships between users, and node attributes of users are defined by their specified tags that reflect their interests on the website.
    
  * Weibo [<https://github.com/zhao-tong/Graph-Anomaly-Loss>] <cit.> is a user-posts-hashtag graph dataset from the Tencent-Weibo platform, which collects information from 8,405 platform users (contains 868 suspicious users) with 61,964 hashtags. The user-user graph provided by the author is used, which connects users who used the same hashtag.
    
  * Reddit [<http://files.pushshift.io/reddit>] <cit.> 
    is a user-subreddit graph extracted from a social media platform, Reddit, which consists of one month of user posts on subreddits. The 1,000 most active subreddits and the 10,000 most active users (containing 366 banned users) are extracted as subreddit nodes and user nodes, respectively. We convert it to a user-user graph with 20,744,044 connections based on the co-interacted subreddit for our experiments.



For the five synthetic datasets, we adopted synthetic anomalies to validate models <cit.>.
Following the widely used anomaly injection approach in previous advances <cit.>, we inject a combined set of both topological and attributed anomalies for each experimental synthetic dataset with the following manner.

    
  * Injection of topological anomalies. To obtain topological anomalies, the topological structure of networks is perturbed by generating small cliques composed of nodes that were originally not related. The insight is that in a small clique, a small group of nodes are significantly more interconnected with each other than the average, which can be considered a typical situation of topological anomalies in real-world graphs. Specifically, to create cliques, we begin by defining the clique size p and the number of cliques q. When generating a clique, we randomly select p nodes from the set of nodes  and connect them fully. This implies that all the selected p nodes are considered topological anomalies. To generate q cliques, we repeat this process q times. This results in a total of p × q topological anomalies. Following the previous works, the value of p is fixed as 15 and the value of q is set to 5, 5, 20, 20, 15 for Cora, Citeseer, Pubmed, ACM, and Flickr, respectively.
    
  * Injection of attributed anomalies. We inject attributed anomalies by disturbing the attribute of nodes. To generate an attributed anomaly, a node v_i is randomly selected as the target, and then another k nodes (v_1^c, ..., v_k^c) are sampled as a candidate set ^c. Next, we compute the Euclidean distance between the attribute vector 𝐱_c of each v^c∈^c and the attribute vector 𝐱_i of v_i. We then select the node v_j^c∈^c that has the largest Euclidean distance to v_i and change 𝐱_i to 𝐱_j^c. Following the previous works, the value of k is set to 50.















  §.§.§ Compared Baselines







We compare our proposed with seventeen representative state-of-the-art models, which can be categorized into five main categories.

Shallow detection methods:

    
  * SCAN <cit.> is a classic clustering method that can be applied for anomaly detection, which clusters vertices based on structural similarity to detect anomalies.
    
  * MLPAE <cit.> utilizes autoencoders onto both anomalous and benign data with shallow nonlinear dimensionality reduction on the node attribute.


Enhanced graph neural networks:

    
  * GAAN <cit.> is a generative adversarial framework with a graph encoder to obtain real graph nodes' representation and fake graph nodes' representation and a discriminator to recognize whether two connected nodes are from the real or fake graph.
    
  * ALARM <cit.> is a multi-view representation learning framework with multiple graph encoders and a well-designed aggregator between them.
    
  * AAGNN <cit.> is an abnormality-aware graph neural network, which utilizes subtractive aggregation to represent each node as the deviation from its neighbors. 


Graph autoencoder-based models:

    
  * GCNAE <cit.> is a classic variational graph autoencoder with the graph convolutional network as its backbone and utilizes the reconstruction loss for unsupervised anomaly detection.
    
  * Dominant <cit.> is a deep graph autoencoder-based method with a shared encoder. It detects the anomalies by computing the weighted sum of reconstruction error terms of each node. 
    
  * AnomalyDAE <cit.> is a dual graph autoencoder method based on the graph attention network, and the cross-modality interactions between network structure and node attribute are asymmetrically introduced on the node attribute reconstruction side.
    
  * ComGA <cit.> is a community-aware attributed graph anomaly detection framework with a designed tailored deep graph convolutional network.


Graph contrastive learning methods:

    
  * CoLA <cit.> is a graph contrastive learning method. It detects anomalies by evaluating the agreement between each node and its neighboring subgraph sampled by the random walk-based algorithm.
    
  * ANEMONE <cit.> is a multi-scale graph contrastive learning method, which captures the anomaly pattern by learning the agreements between node instances at the patch and context levels concurrently.
    
  * SL-GAD <cit.> is a state-of-the-art anomaly detection model with generative and multi-view contrastive perspectives, which captures the anomalies from both the attribute and the structure space.
    
  * Sub-CR <cit.> is a self-supervised learning method that employs the graph diffusion-based multi-view contrastive learning along with attribute reconstruction.


Heterophily graph neural networks:

    
  * MixHop <cit.> is a graph convolutional network with the mixed aggregation of multi-hop neighbors during a single message passing operation. We construct the unsupervised auto-encoder architecture for it and the rest heterophily models to fit the unsupervised graph anomaly detection scenario.
    
  * H2GCN <cit.> is a heterophily GNN by the separate encoding of ego & neighbor embeddings with higher-order neighbors and intermediate representations.
    
  * LINKX <cit.> is an MLP-based model for heterophily graph modeling, which separately embeds the adjacency and node features with simple MLP operations.
    
  * GloGNN <cit.> is a method that considers both the homophily and heterophily properties on the graph with the combination of both low-pass and high-pass filters over the whole node set.







  §.§.§ Evaluation Metrics and Hyper-parameter Settings

We evaluate the models with ROC-AUC (Area under the ROC Curve), the widely-adopted metric in previous works <cit.>, to evaluate the anomaly detection performance. A higher AUC value indicates better detection performance. Note that we run all the experiments five times with different random seeds and report the average results with standard deviation to prevent extreme cases.



  §.§.§ Hyper-parameter Settings
 In the experiments on different datasets, the embedding size is fixed to 64 and the embedding parameters are initialized with the Xavier method <cit.>. The loss function is optimized with Adam optimizer <cit.>. The learning rate of is searched from {5× 10^-2, 1 × 10^-2, 5 × 10^-3, 1 × 10^-3}, and the regularization term is searched from {1 × 10^-4, 5 × 10^-5, 1 × 10^-5}. 

For fair comparisons, all experiments are conducted on the CentOS system equipped with NVIDIA RTX-3090 GPUs.




 §.§ Anomaly Detection Performance (RQ1)

We first compare the main performance results between and the baseline models. The performance comparison results are reported in Table <ref>. 
Furthermore, we demonstrate the comparison of the ROC curves between with the top-5 performed baselines on each dataset in Figure <ref>.
From these results, we have the following observations:



    
  * can achieve significant performance improvements over state-of-the-art methods. Specifically, achieves the best performance on 4 out of 5 synthetic datasets and all real-world datasets among all baselines. The superior performance verifies the guarding schemes with correlation constraints and the adaptive caching under the local and global anomaly detection tasks is able to help improve the anomaly distinguishability over the abnormal graph.
    
  * Directly using the consistency GNNs or heterophily GNNs has sub-optimal detection performance. We can find from the results that the performance of enhanced consistency-based GNNs (the second category) and heterophily-based GNNs (the fifth category) both have a certain gap with . Thus, it further verifies that, under such a disrupted phenomenon induced by unknown anomalies, provides an effective way to guard the consistent homophily and utilize discrepant heterophily patterns.
    
  * There are differences in the performance of baseline between synthetic and real-world datasets. It can be found from the table that the graph contrastive learning-based methods are the best-performed baselines on synthetic datasets in general while enhanced graph neural networks and graph autoencoders achieve better results on real-world datasets. One possible reason is that the contrastive objective function of these models is related onefold, which is insufficient for directly applying to the irregular real-world datasets then enhanced graph neural networks and graph autoencoders.
    
  * Anomaly detection on real-world datasets is significantly harder than on synthetic datasets. The performance gap in real-world datasets between the models is large compared to synthetic datasets, especially the graph contrastive learning methods. This shows that the widely used anomaly injection scheme may lack diversity and be inadequate to simulate irregular patterns in the real world, <cit.> also has the same observation. Thus, we suggest that the model effectiveness examination should be conducted on both synthetic and real-world datasets for a more objective evaluation.






 §.§ Ablation Study (RQ2)

In this subsection, we aim to conduct the fine-grained ablation study to analyze the contribution of components and architecture of our .


  §.§.§ Component Study

To verify the effectiveness of the components, we conduct the ablation study on three variants: 
-w/o AR, -w/o TR, and -w/o CA, which removes the local attribute reconstruction, local topology reconstruction, and global consistency alignment, respectively.

From the results in Table <ref>, we can observe that notably outperforms all its three ablation variants in general.
Specifically, first, the removal of attribute and topology reconstruction has a greater impact, which shows that modeling of graph properties is important for anomaly discrimination.
Therefore, well-representing attributes and topology under anomaly discrepancy are significant for anomaly detection. Second, the effect of different modules varies from different datasets, which is related to the diversity of anomaly definitions. Thus, the comprehensive consideration of topology-specific, attribute-specific, and consistent patterns is beneficial to the model. 








  §.§.§ Architecture Study

To study the effectiveness of 's architecture, we further study the guarding architecture of with its two architecture variants:

-shared removes the auxiliary encoders and shares all input information with a single GNN, which ignores the guarding of anomalies for the GNN.
-separated replaces the three encoders with two parallel encoders without any information sharing, which is the simplest way without considering the consistent attribute-topology correlation that remained in the major normal nodes.



The results are shown in Figure <ref>. From the results, we have the following observations: First, compared to -shared variant, gains significant improvements which proves the necessity of auxiliary guarding under abnormal graphs. Second, the improvements over -separated demonstrate that simply separating attribute and topology information will miss the consistent patterns that remained in most normal nodes and lead to suboptimal performance. Therefore, the guarding architecture of is effective for unsupervised anomaly detection.



 §.§ Case Study (RQ3)

In this subsection, we aim to conduct case studies on with synthetic datasets to analyze the correlation-constrained GNN encoding guarding via embedding visualization and analyze the performance of on different types of anomalies.


  §.§.§ Embedding Visualization

We first conduct the distribution visualization of attribute-specific, topology-specific, and consistent GNN embeddings after the correlation constrained guarding from attribute encoder f_a(·), topology encoder f_t(·), and the GNN encoder f_gnn(·) by reducing their dimension to two with the T-SNE <cit.> method.

The visualization results are illustrated in Figure <ref>, which shows that the three aspects of representations are well distinguished from each other in the embedding space.


Therefore, it illustrates that the three aspects of representations have been well disentangled by to guard the GNN encoding.



  §.§.§ Performance on Different Anomaly Types

To further analyze different types of induced anomalies, we conduct the case study of compared with the overall top-3 performed baselines on two synthetic datasets. We report the detection performance on synthetic attributed anomalies, synthetic structure anomalies, and synthetic mixed (both attribute and structure perspectives) anomalies.

The split performance results are shown in Table <ref>. From the results, we find that the best baseline Sub-CR is obviously biased towards detecting only attribute anomalies, and the second-best performed model ANEMONE is biased towards detecting only topology anomalies.
Our can generally achieve good performance on all types of anomalies due to the explicit guarding of GNN representation learning, guarding of directly abnormal graph reconstruction, and comprehensive considering different kinds of anomaly characteristics.




































 §.§ Parameter Analysis (RQ4)

In this subsection, we aim to study the impact of different hyper-parameters on with two synthetic datasets and two real-world datasets, including the balanced parameters λ_1 and λ_2, the readout function in Eq.(<ref>), the learning rate, and the embedding dimension.


  §.§.§ Effectiveness of balanced parameters

We first investigate the effect of the different combinations of key balanced parameters λ_1 (balances the effect between topology and attribute reconstruction) and λ_2 (tunes the impact of consistency alignment) on . 
The parameter study results are shown in Figure <ref> on Cora, Citeseer, Weibo, and Reddit datasets. 
From the results, we can observe that the performance of varies with respect to balanced parameters λ_1 and λ_2. More specifically, first, changes in parameter λ_1 may bring more volatility than parameter λ_2. This is explainable since the consistency is related to both attribute and topology, which is more robust and stable <cit.>. Furthermore, with a fixed λ_2 value, a relatively large value of λ_1 can make perform better, which means that the impact of the attribute reconstruction needs more attention and consideration.







  §.§.§ Effectiveness of readout function

We further discuss the readout function selection of consistency alignment in Eq.(<ref>), which includes mean, min, max, and attention (scoring by an MLP) pooling as in Table <ref>. From the results, we can find that the simple non-parameter operation with mean pooling can achieve relatively good performance.
The possible reason is that due to the unbalanced number of normal and anomalies, simple mean pooling can reflect the global consistency from the representations of the majority of normal nodes.



  §.§.§ Effectiveness of learning rate

Then, the study of the effectiveness of the learning rate can be found in Figure <ref>. From the results, we can find that the performance of on synthetic datasets is less sensitive to changes in learning rate. As long as the learning rate is not set as a too large value, the model performance is similar under relatively small learning rates. For real-world datasets, the appropriate learning rate range will be smaller than that of synthetic datasets, but a learning rate value of around 0.005 can generally achieve relatively good anomaly detection performance.



  §.§.§ Effectiveness of embedding dimension

Furthermore, we have also analyzed the impact of different embedding dimensions on , as illustrated in Figure <ref>. It can be seen from the study results that, except for the Cora dataset, which can achieve optimal performance on a smaller 16-dimensional space, the other three datasets can achieve optimal performance on a 64-dimensional representation space in general, which is no need for us to continue to increase the representation dimension to achieve better performance.





§ CONCLUSION


In this paper, we study the problem of negative anomaly impact on GNNs in unsupervised graph anomaly detection, which is largely neglected by previous works. To address this issue, we propose , a simple but effective framework to guard GNNs against anomaly impacts in unsupervised graph anomaly detection. Specifically, introduces two guarding strategies with comprehensive anomaly detection perspectives. Firstly, guards the GNN encoder against encoding inconsistent information to enhance the node representation quality for anomaly distinguishing.
Then, we comprehensively include both local reconstruction and global alignment as the objectives for better detecting multiple anomalies. During this process, to guard the GNN-encoded representations against directly reconstructing the abnormal graph, further equips the representations with adaptive caching. 
Finally, anomalies are recognized by collaboratively adopting the three carefully designed objective functions.
Extensive experiments demonstrate that outperforms the state-of-the-art baselines.























 
 



IEEEtran




