Introduction

Typically, the graph anomaly detection (GAD) task is treated as a semi-supervised binary node classification problem (normal vs. anomalous). However, in an anomaly graph, the number of anomalies is significantly lower than normals. Generally, efforts to adapt GNNs to classimbalanced graphs can be broadly categorized into two types [1]: data-level and algorithm-level methods. Data-level methods typically attempt to balance class distribution by pre-processing the training samples using oversampling or undersampling techniques [2]. Algorithm-level methods consider misclassification costs to focus more on minority classes or to ignore majority classes, thereby mitigating the impact of class imbalance [3].

However, recent GAD methods struggle to adapt to this extreme class imbalance, leading to poor classification performance for anomalous nodes (minority class). Table 1 summarizes the distribution of the two classes of nodes in the YelpChi [4] and Amazon [5] datasets, as well as the test accuracy of a recent GNN for these two classes. It is evident that anomalies constitute only a small portion of the total nodes, and the prediction accuracy for anomalies is significantly lower than that for normals.

In this poster, we propose a method MG-GNN to solve this problem, which generates minority class samples for GNN in the hidden space, mitigating the negative impact of class imbalances. Specifically, we first use a GNN to map the node feature and structural information into hidden

Table 1

The distribution of the number of nodes in the YelpChi and Amazon datasets, and the test accuracy of BWGNN [6] space. Then, based on the hidden representations of the minority class, we generate a large number of minority nodes to achieve a relatively balanced class distribution before performing classification. The experiments show that our method can handle the class imbalance issues.

Methodology

Problem Definition

Given an anomaly graph 𝒢 containing both normal and anomalous nodes, the objective is to learn a classifier 𝑓 (•) based on the graph 𝒢 and a set of partially labeled nodes 𝑌 Train . The aims to predict the labels of the unlabeled nodes 𝑌 ˆTest, where 1 represents anomalies and 0 represents normal nodes. The task can be formalised as:

𝑓 (𝒢, 𝑌 𝑇 𝑟𝑎𝑖𝑛 ) → 𝑌 ˆ𝑇 𝑒𝑠𝑡(1)

Model Overview

Our model, MG-GNN, consists of three main components. First, a GNN encoder transforms the node feature and structural information into hidden space. Next, based on the representation of the minority class in the hidden space, a large number of nodes representing the minority class are generated, ensuring that the numbers of normal and anomalous classes are relatively balanced. Finally, a classifier is used to perform classification under these balanced conditions.

GNN Decoder

To encode the anomaly graph, we utilize BWGNN as the backbone network due to its lowand band-pass characteristics. It is noteworthy that we do not use GCN [7] as the encoder here because GCN is based on the homophily assumption and cannot adequately handle the heterophily of anomaly graphs. The decoder is defined as

𝐻 = BWGNN(𝐴, 𝑋)(2)

where 𝑋 ∈ R 𝑁 ×𝑑 represents the raw node features, 𝐴 is the adjacency matrix of the graph, and 𝐻 is the node representation in hidden space.

Synthetic Node Generator

After obtaining the node representations 𝐻, we use SMOTE [8] to generate synthetic anomalies. The basic idea is to interpolate between samples of the target minority class and their nearest neighbors in the hidden space. Specifically, let ℎ 𝑣 ∈ 𝐻 represent the representation of an anomalous 𝑣. First, the nearest node ℎ 𝑢 ∈ 𝐻 of node 𝑣 is found based on Euclidean distance:

𝑢 = argmin 𝑚 ‖ℎ 𝑚 − ℎ 𝑣 ‖, ℎ 𝑚 ∈ 𝐻(3)

where, unlike [9,10], we do not require node 𝑢 to necessarily be an anomaly class, as recent research [11] has shown that this strategy can better expand the decision space of anomalies. Then, we generate a new minority class node ℎ 𝑢 through linear interpolation:

ℎ 𝑘 = 𝛿ℎ 𝑣 + (1 − 𝛿)ℎ 𝑢(4)

where 𝛿 ∈ [0, 1] is sampled from the Beta distribution. The synthesized node 𝑘 is labeled as an anomalous node. Therefore, we can obtain a large number of synthesized anomalous nodes. Additionally, we can select more nearest neighbors to get more synthetic anomalous nodes.

Classifier

After synthesizing a large number of nodes, we stack the representations of the original nodes with the synthesized abnormal nodes to obtain a more balanced class, denoted as 𝐻 ′ . Finally, we use another MLP as a classifier for final prediction.

𝑌 ˆ= 𝑠𝑜𝑓 𝑡𝑚𝑎𝑥(𝑀 𝐿𝑃 (𝐻 ′ ))

Finally, the loss is calculated using cross-entropy. It is important to note that the loss is computed not only for the original nodes but also for the synthesized anomalous nodes. We employ three widely used class equalization metrics for fair comparisons, namely F1macro, AUC and GMean. The experimental results from Table 2 show that after generating a large number of anomaly class nodes using our method, the class imbalance is better handled and the overall performance is improved. Additionally, from Table 3 and Table 1 we observe a significant improvement in the accuracy of anomalies, while the accuracy of correct nodes remains largely unaffected. This demonstrates that our method effectively mitigates the impact of class imbalance.

Experiments

Conclusion

In this poster, we propose a method MG-GNN, which generates minority class samples for GNN in the hidden space. Experimental results demonstrate that our method can enhance the classification performance of anomalous nodes while having minimal impact on normal nodes.

In future work, we are interested in addressing the issue of class imbalance by leveraging the original distribution of the graph.