NAAST-GNN: Neighborhood Adaptive Aggregation and Spectral Tuning for Graph Anomaly Detection

1 Introduction

With the rapid advancements in information technology, anomaly detection has become crucial in areas such as network security [Zhang et al., 2019], financial transactions [Lin et al., 2021], and social networks [Deng et al., 2023]. However, traditional anomaly detection methods struggle to keep pace with the growing complexity and scale of graphstructured data. Graphs, by effectively capturing intricate relationships between data points, have emerged as a powerful tool for anomaly detection. In particular, the rise of Graph Neural Networks (GNNs) has attracted significant attention, as they offer strong representation learning capabilities, making them ideal for addressing the difficulties of Graph Anomaly Detection (GAD).

∗Corresponding author

Recent studies [Gao et al., 2023a; Wang et al., 2023; Xu et al., 2024] emphasize the significance of heterophily in anomaly graphs. They observe that anomalous nodes in such graphs exhibit a high degree of heterophily, which makes GNNs based on the homophily assumption [McPherson et al., 2001] unsuitable for capturing this characteristic, resulting in suboptimal performance. However, some works [Ma et al., 2022; Luan et al., 2022; Chen et al., 2023a] argue that heterophily does not necessarily constrain the expressive power of GNNs and may not always be detrimental. Further studies [Luan et al., 2023; Gao et al., 2024; Wang et al., 2024] analyze heterophily through the lens of neighborhood distributions, which typically quantified as the probability distribution of neighbor categories, revealing a positive correlation between node distinguishability after graph convolution and the Euclidean distance between neighborhood distributions. In essence, the core challenge of heterophily stems from neighborhood distributions, which fundamentally hinder GNNs performance in GAD. This limitation arises from the message-passing mechanism of GNNs, where the semantic information learned for a node is inherently influenced by the category distribution of its neighbors.

Building on this foundation, we revisit GAD methodologies from the perspective of neighborhood distributions in both spatial and spectral domains. Spatial methods [Zhuo et al., 2024; Liu et al., 2021] focus on edge trimming or neighbor aggregation mechanisms, which essentially aim to enhance the distinguishability of neighborhood distrubutions between anomalous and normal nodes during the messagepassing process of GNNs, enabling the learning of distinguishable representations for different classes (normals and anomalies). Spectral methods [Xu et al., 2024; Tang et al., 2022], since nodes with similar neighborhood distrubutions but different classes exhibit different frequency components [Gao et al., 2024], employ polynomial filters to retain the high-frequency signals of anomalous nodes and the lowfrequency signals of normal nodes.

Although previous methods have made some progress, as shown in Figure 1, two key challenges remain: (1) Overlap of Inter-class Neighborhood Distrubutions: There is significant overlap in the neighborhood distrubutions between normal and anomalous nodes, making it difficult for GNNs to learn distinguishable representations for different classes. Existing methods [Liu et al., 2021; Dou et al., 2020] that determine message passing between nodes based on features can easily lead to errors being propagated to the results, causing suboptimal performance. (2) Dispersion of Intra-class Neighborhood Distrubutions: The intraclass neighborhood distribution exhibit significant dispersion in some cases. Fixed GNN aggregation strategies or filters struggle to adapt to such complex scenarios, causing learned representations within the same class to still demonstrate differences. Current approaches [Tang et al., 2022; Gao et al., 2024] fail not specifically address the diverse neighborhood distrubutions within the same class of nodes. Overall, the impact of these two challenges varies across different datasets. For instance, for YelpChi, it is primarily the former, whereas for T-Finance, it is mainly the latter.

To address the aforementioned challenges, we propose the GNN with Neighborhood Adaptive Aggregation and Spectral Tuning for graph anomaly detection (NAAST-GNN). The core idea is to dynamically adjust graph convolution propagation mechanisms based on node-specific predicted probabilities. Each layer consists of two key modules: The neighborhood adaptive aggregation module operates in the spatial domain, addressing the challenge of overlapping neighborhood distributions between anomalous and normal nodes. It constructs edge weights based on the predicted probabilities of nodes from the previous epoch, emphasizing a dynamic adjustment of edge weights. Specifically, this module assigns higher weights to homophilous edges and lower weights to heterophilous ones, ensuring that the aggregated neighborhood information remains distinct and discriminative, even when nodes from different classes share similar neighborhood distributions. The spectral tuning module operates in the spectral domain to address the dispersion in neighborhood distributions within the same class. By dynamically selecting and combining spectral filters based on the predicted neighborhood distribution, this module ensures adaptability to the diverse neighborhood characteristics within the same class. Finally, the learned spatial and spectral representations are integrated as inputs for the next layer.

The main contributions of this paper are summarized as:

• We identify two key challenges in GAD: the overlap of
• intra-class neighborhood distributions and the dispersion of inter-class neighborhood distributions.
• We propose the GNN with neighborhood adaptive aggregation and spectral tuning for graph anomaly detection (NAAST-GNN), which dynamically adjusts the graph convolution propagation mechaism based on predicted node probabilities.
• Extensive experiments on four public datasets demonstrate that our proposed method NAAST-GNN outperforms the state-of-the-art baselines.

2 Preliminaries

We present the notations and problem definition, and then delve into the concepts of homophily and heterophily, along with an analysis of neighborhood distributions.

2.1 Notations and ProblemDefinition

An anomaly graph is denoted as G = {V,X, E}, where V is the node set with size N = |V|, E is the edges set, and X ∈ RN×d denotes the node attributes matrix, with Xv ∈ Rd representing the attribute vector of node v.

The GAD is usually formalized as a binary node classification task (normal and anomalous), where normal nodes are labeled as 0 and anomalous nodes as 1. Given a graph G, the target of GAD is to train a classifier f(·) that can infer the labels of unlabeled nodes based on the known labels of some nodes. This process can be represented as:

2.2 Homophily/Heterophily and Neighborhood Distribution

The homophily coefficient Hv node is usually used to measure the degree of homophily of the node v, defined as:

where Nv denotes the set of neighbors of node v. Thus, the heterophily of the node v can be defined as 1 -Hv node .

Then, the Neighborhood Distribution (ND) of a node v, which represents the probability of its neighboring nodes u belonging to category c, can be calculated as:

Figure 1 shows the neighborhood distribution of each dataset when the neighboring nodes are normal, i.e., ND v0 . Since GAD involves only two types of nodes, the neighboring anomalous node case, i.e., ND v1 , equals 1-ND v0 , and its illustration is omitted here due to space constraints.

3 Methodology

We first provide an overview of the proposed NAAST-GNN, followed by a detailed description of its two key components: the neighborhood adaptive aggregation and spectral tuning module. Finally, we discuss the model optimization.

3.1 Overview

Figure 2 illustrates the detailed architecture of our proposed NAAST-GNN. The model operates iteratively, where the message-passing mechanism of the graph convolution relies on the node prediction probabilities from the previous epoch. Each convolutional layer consists of two core modules: the neighborhood adaptive aggregation and spectral tuning module. To address the issue of overlapping neighborhood distributions between anomalous and normal nodes, the neighborhood adaptive aggregation module constructs edge weights in the graph based on the predicted node probabilities. This ensures that nodes with similar neighborhood distributions but belonging to different classes aggregate distinct neighborhood information. Then, to tackle the challenge posed by significant intra-class variations in neighborhood distributions, the spectral tuning module dynamically combines different spectral information. This approach adapts to the diverse neighborhood characteristics of nodes, enabling the model to handle various neighborhood situations effectively. The two modules collaboratively address these challenges from spatial and spectral perspectives, respectively. Finally, the aggregated representations are transformed through a multilayer perceptron (MLP), generating updated representations that serve as input for the subsequent layer.

3.2 Neighborhood Adaptive AggregationModule

Most traditional GNNs are based on the homophily assumption [McPherson et al., 2001], which indiscriminately aggregates information from all neighbors. However, the neighborhood distributions of normal and anomalous nodes overlap significantly in GAD. This causes traditional GNNs to learn representations that fail to effectively distinguish between normal and anomalous nodes. To this end, we propose a neighborhood adaptive aggregation strategy that selectively aggregates information from relevant neighbors. Specifically, we utilize the classification probabilities ˆ y of the nodes at both ends of an edge from the previous epoch to compute the edge weights. This approach ensures that, for any given node, edges connecting neighbors of the same class are assigned larger weights, while edges connecting neighbors of different classes are assigned smaller weights. As a result, our method facilitates the learning of more distinguishable representations, even when the neighborhood distributions of different classes exhibit significant similarity.

First, for any central node v, we determine its category based on the comparison between its predicted probability ˆ yv in the previous epoch and the threshold ξ. If the probability is less than the adaptive adjustment parameter ξ, the instance is classified as normal; otherwise, it is considered an anomaly. Then, we adopt different strategies to construct edge weights based on their categories:

Empirically, anomalous nodes tend to exhibit ˆ y ≈ 1, while normal nodes usually have ˆ y ≈ 0. When a central node v is classified as anomalous (i.e., ˆ yv ≥ ξ), the edge weight is defined as wvu = ˆ yv ˆ yu, which assigns higher weights to edges connecting v with anomalous neighbors (where ˆ yu ≈ 1), and lower weights to edges connecting v with normal neighbors (where ˆ yu ≈ 0). Conversely, when v is classified as a normal node (i.e., ˆ yv < ξ), the weight is defined as wvu = (1 - ˆ yv)(1 - ˆ yu), thereby strengthening the connections with other normal neighbors and weakening those with anomalous ones. By constructing edge weights in this manner, even if the neighborhood distrubutions of anomalous and normal nodes overlap, the edge weights built for these two types of nodes are completely different, enabling the GNN to effectively handle different types of node scenarios.

Since ˆ y ∈ (0, 1), to prevent gradient vanishing and improve training robustness, we normalize the edge weights of the central node v using edge softmax:

Finally, based on the normalized edge weights αvu, the final spatial domain representation is obtained:

where hl-1 v represents the embedding of node v in layer l-1, with h0v = Xv, and W l-1 is a learnable parameter matrix.

3.3 Spectral TuningModule

Considering that even among nodes belonging to the same category, substantial differences in neighborhood distributions may exist. Previous approaches [Tang et al., 2022; Zhuo et al., 2024] often rely on predefined spectral convolution kernels or fixed aggregation strategies, which fail to adapt effectively to the unique neighborhood distributions of individual nodes. To this end, we propose a method to design convolution kernels in the spectral domain, tailored to the neighborhood distributions of the nodes.

According to [Gao et al., 2024; Wang et al., 2024], the distinguishability of node representations of different classes after applying GNNs is positively correlated with the Euclidean distance between their neighborhood distrubutions. Simultaneously, nodes of different classes with similar neighborhood distrubutions will retain different frequency components. Therefore, we can infer that for a given node, if there are more nodes of the same class in its neighborhood, more low-frequency information should be retained. Conversely, if there are more nodes of different classes in its neighborhood, more high-frequency information should be retained. Thus, the spectral tuning module will adjust the low- and high-frequency components in the spectral filters according to the node-level neighborhood distrubutions.

Specifically, we first determine the neighborhood distribution of each node v based on the predicted probability of the node in the previous epoch:

where the indicator function I(·) equals 1 if the condition inside the parentheses is true, and 0 otherwise. Here again, we utilize the relationship between the node probability ˆ yu and the adaptive adjustment parameter ξ to determine the neighborhood distrubution of nodes.

Then, based on the previous analysis, we adjust the spectral information of the filter according to the category of node v and its neighborhood distrubution. The final learned node representation in the spectral domain is:

where normalized Laplacian matrix L and its complement IL are employed here as high- and low-pass filters [Wang and Zhang, 2022], respectively. It is worth mentioning that other high- and low-pass filters can also be utilized in this context.

We analyze the case when the central node v is anomalous, i.e., when ˆ yv ⩾ ξ. The more neighbors of the same type it has, i.e., the higher the anomalous distribution of the neighborhood distrubution ND v1 is, according to the previous analysis, the more low-frequency information should be retained, making node v more similar to its neighbors. For the node v being normal, the situation is similar, but the retained spectral information is exactly the opposite. Through the spectral tuning module, we can ensure that nodes of the same class are well-tuned to their respective spectral information even when they have different neighborhood distrubutions.

Finally, the spatial representation hl-1 v,t from the neighborhood adaptive aggregation module and the spectral representation hl-1 v,f from the spectral tuning module are transformed as the input for the next layer:

where [·||·] denotes the concatenation operation, and MLP transforms the concatenated representations.

3.4 Model Optimization

We utilize the node representation hLv from the final layer of the model to perform classification, generating a predicted value ˆ yv, which represents the probability of node v being classified as anomalous:

where W and b represent a learnable parameter matrix and bias, respectively. Our model adopts an iterative optimization strategy, where ˆ yv serves as both the output of the current epoch and the input for the next epoch.

Then, to mitigate the class imbalance between normal and anomalous nodes, we minimize the weighted cross-entropy loss, defined as:

where γ is the ratio of the number of normals to anomalies.

During the model optimization process, the classification probabilities ˆ yv of the nodes are not available during the first epoch of training. For this purpose, we initialize the probabilities randomly for all nodes. In subsequent epochs, as the training loss decreases, the prediction probabilities are iteratively refined, becoming increasingly accurate with each epoch. The predictive objectives and the model's sophisticated design synergize effectively: higher prediction accuracy enhances the functionality of the neighborhood adaptive aggregation and spectral tuning modules, while improved capabilities in these modules, in turn, boost the model's overall prediction accuracy. This reciprocal relationship ultimately enhances the model's performance.

Finally, for the parameter ξ, we initialize it to 0.5 at the start of the first epoch. During model training, its value is dynamically adjusted to the threshold that maximizes the F1Macro score on the validation set [Tang et al., 2022].

4 Experiments

In this section, we perform experiments on four datasets and report results of our models and state-of-the-art baselines to show the effectiveness of NAAST-GNN.

4.1 Experimental Setup

Dataset. We conduct experiments on four datasets related to graph anomaly detection, the statistics of which are shown in Table 1. Among them, YelpChi [Rayana and Akoglu, 2015] and Amazon [McAuley and Leskovec, 2013] are two public spam review datasets for opinion fraud detection. YelpChi aims to identify reviews that unfairly promote or disparage specific products or businesses. Amazon focuses on detecting users who provide deceptive product reviews in the musical instruments category on the Amazon website and get paid for it. T-Finance and T-Social [Tang et al., 2022] aim to identify anomalous accounts in transaction networks and social networks, respectively. They share 10-dimensional features related to the number of days since registration, login activity, and interaction frequency. In T-Finance, edges represent transaction records between accounts. If a node is associated with categories such as fraud, money laundering, or online gambling, human experts label it as anomalous. In TSocial, nodes are connected if they have maintained a friendship for over three months.

Baselines. We evaluate NAAST-GNN against state-of-theart baselines, which are categorized into three groups. The first group comprises conventional GNNs, including GCN [Kipf and Welling, 2017], GraphSAGE [Hamilton et al., 2017], and GAT [Velickovic et al., 2018]. The second group focuses on spectral heterophilic methods, such as AMNet [Chai et al., 2022], LSGNN [Chen et al., 2023b], BWGNN [Tang et al., 2022], GHRN [Gao et al., 2023a], SEC-GFD [Xu et al., 2024], and BioGNN [Gao et al., 2024]. The third group encompasses spatial heterophilic methods, including CARE-GNN [Dou et al., 2020], PC-GNN [Liu et al., 2021], H2-FDetector [Shi et al., 2022], GDN [Gao et al., 2023b], GAGA [Wang et al., 2023], CONSISGAD [Chen et al., 2024], and PMP [Zhuo et al., 2024].

Metrics. Since GAD is a class-imbalanced classification task, we select two widely used evaluation metrics: F1-Macro and AUC. F1-Macro calculates the mean F1 score across all classes, ensuring equal significance to each class by balancing precision and recall. AUC quantifies a model's capacity to differentiate between positive and negative examples through the area under the ROC curve. Higher values for these two metrics indicate better performance.

Implementation Details. The training, validation, and test sets for all datasets are split in a 0.4/0.2/0.4 ratio, with experimental results reported as the average of five runs. For our proposed NAAST-GNN, the layer number is set to 2. The hidden layer dimension is set to 32 for YelpChi, Amazon, and T-Finance. Due to the large scale of the T-Social, its hidden layer dimension is set to 10. The choice of parameter ξ is discussed at the end of Section 3.4. We use the Adam optimizer and tune the hyperparameters using grid search, with the learning rate ranging from {5e-4, 1e-3, 5e-3, 1e-2} and the weight decay ranging from {1e-3, 1e-4, 1e-5}. For GCN, GAT, and GraphSAGE, we implement these models using DGL [Wang et al., 2019b]. For other baseline methods, we utiliz the source code provided by their respective authors. Due to the unavailability of the source code for SECGFD and BioGNN at the time of manuscript submission and our experimental settings are consistent with those outlined in their original publications, we present the results directly from the respective papers.

4.2 Experimental Results

We conduct a comprehensive comparison of our method against homophilous GNN models, state-of-the-art spectral and spatial heterophilous GNNs. The results are summarized in Table 2. Traditional GNNs based on the homophily assumption perform poorly on heterophilous anomaly graphs due to their inability to effectively model heterophilous structures. Recent spectral and spatial heterophilous GNNs introduce mechanisms to address heterophily, achieving some degree of performance improvement. However, they fail to fully consider the key factor of neighborhood distribution, which led to suboptimal performance.

Our proposed model consistently achieves superior performance in most cases. Specifically, NAAST-GNN outperforms the best baseline methods on YelpChi, T-Finance, and T-Social by 1.48%, 1.20%, and 4.26% in terms of Fl-macro, and by 1.19%, 0.74%, and 2.17% in terms of AUC, respectively. These results underscore the efficacy of our neighborhood adaptive aggregation and spectral tuning modules in addressing the challenges posed by inter-class neighborhood distribution overlap and intra-class neighborhood distribution dispersion. Notably, the performance of NAAST-GNN on the Amazon dataset is relatively less competitive, ranking as the second best. This may be attributed to the complex structural characteristics of Amazon, where excessive interaction complexity partially hampers the model's ability to distinguish neighborhood distributions effectively.

4.3 Ablation Study

To better verify the effectiveness of each module in NAASTGNN, we conduct ablation studies on the neighborhood adaptive aggregation (w/o NAA) and spectral tuning (w/o ST) modules. Additionally, for our proposed neighborhood adaptive aggregation, we replace it with GAT (w/ GAT), which dynamically aggregates neighborhood information through an attention mechanism based on node features. For the spectral tuning module, we design two variants, which replace it with situations that only retain high-frequency information (w/ HP) or low-frequency information (w/ LP), respectively.

As shown in Table 3, NAAST-GNN achieves the best performance in its complete state, indicating that each module contributes to its effectiveness. Compared to YelpChi and T-Social, we observe that for YelpChi, the removal of the NAA module has a more significant impact on performance than the removal of the ST module. In contrast, for T-Social, the removal of the ST module has a greater impact than that of the NAA module. This disparity can be attributed to the differing primary factors influencing their performance: for YelpChi, it is the overlap of inter-class neighborhood distrubutions, whereas for T-Social, it is the dispersion of intraclass neighborhood distrubutions. These findings further validate that the proposed modules are specifically designed to address these distinct challenges.

4.4 Analysis of Training Ratio

In real-world scenarios, we may not obtain enough labeled data. Therefore, we explore the impact of the training ratio on model performance. Table 4 shows the performance of NAAST-GNN on YelpChi and T-Social with training data ranging from 1% to 40%. According to [Tang et al., 2022], the validation and test set split ratio remains 1:2.

From the results in Table 4, it can be seen that as the training ratio increases, the model performance improves significantly for YelpChi. However, the improvement for T-Social is limited. We believe the possible reason is that in YelpChi, the neighborhood distrubutions of anomalous and normal nodes overlap too much, as shown in Figure 1(a), and the model requires more supervisory signals for training. The neighborhood distrubutions between classes in T-Social are quite different, as shown in Figure 1(d), making it relatively simpler. The main issue is the large intra-class neighborhood distrubution disparity, which our spectral tuning module can effectively address. Therefore, even with extremely limited training data (1%), NAAST-GNN still outperforms other graph anomaly detectors (using 40% training data in Table 2).

4.5 Visualization and Discussion

To intuitively illustrate the effectiveness of NAAST-GNN, we present a visualization of a portion of the convolution process of our model in Figure 3. As shown in the figure, the weights assigned to heterophilous connections are notably smaller compared to those of homophilous connections during the neighborhood adaptive aggregation. This mechanism enables the model to efficiently aggregate information from similar nodes, effectively mitigating the issue of excessive overlap in inter-class neighborhood distributions. Furthermore, our approach accurately captures the neighborhood distributions of nodes, facilitating the integration of low- and high-frequency information based on the node's specific neighborhood characteristics. This design addresses the challenge of substantial intra-class neighborhood distribution discrepancies. In summary, our method strategically leverages node prediction probabilities, ensuring that the graph convolution process and prediction objectives complement each other. This synergistic design results in significant performance improvements.

5 RelatedWork

This section introduces related work on GAD, as well as recent research on heterophily and neighborhood distribution.

5.1 Graph Anomaly Detection

Early works [Wang et al., 2019a; Liu et al., 2020] focus on leveraging multiple relationships to aggregate information. However, indiscriminate aggregation of all information cannot lead to the differentiation of anomalous nodes. Furthermore, CARE-GNN [Dou et al., 2020], PC-GNN [Liu et al., 2021], H2-FDetector [Shi et al., 2022], and GAGA [Wang et al., 2023] selectively aggregate neighbor information by designing unique GNN propagation mechanisms.

Additionally, some works address this task from the spectral domain, with the mainstream solution being the design of various spectral filters for denoising [Guo et al., 2024]. BWGNN [Tang et al., 2022] discovers that as the degree of anomaly increases, the spectral energy distribution shifts to the right. Building on BWGNN, GHRN [Gao et al., 2023a] trims heterophilous edges based on spectral energy components. SEC-GFD [Xu et al., 2024] extends BWGNN by incorporating missing high-frequency information. BioGNN [Gao et al., 2024] analyzes the relationship between heterophily and neighborhood distribution, suggesting that nodes with similar neighborhood distrubutions but different classes should retain different frequency components.

5.2 Heterophily and Neighborhood Distrubution

Recent studies on heterophilous graphs reveal that the poor performance of GNNs is not inherently due to heterophily but rather the indistinguishability of neighborhood distributions. Early studies [Ma et al., 2022; Luan et al., 2022; Chen et al., 2023a] found that heterophily is not always detrimental and that the distinguishability of nodes by GNNs is

(c) T-Social Normal id: 5396096 : 0.95 ND v ={0.74:0.26}

(d) T-Social Anomalous

Figure 3: Graph convolution visualization: Blue and red represent normal and anomalous nodes, respectively. The labels on the nodes are ˆ y, and the numbers on the edges indicate the edge weights αvu calculated by Equation (5). ND v indicates the neighborhood distrubution determined by ξ.

related to neighborhood distrubutions. [Mao et al., 2023] shows that GNNs often rely on majority-class structural distributions (homophily or heterophily), leading to poor performance for minority-class nodes in GAD. Moreover, [Luan et al., 2023] demonstrates that the superior performance of GNNs is related to whether the intra-class node distinguishability is less than the inter-class node distinguishability. Some studies [Gao et al., 2024; Wang et al., 2024] further proves that the distinguishability of nodes after the graph convolution operation is positively correlated with the Euclidean distance of neighborhood distrubutions. Additionally, [Huang et al., 2024] shows from a spectral perspective that high-frequency signals are more favorable on heterogeneous graphs, and the ideal graph signal bases are obligated to incorporate the heterophily of the graph.

6 Conclusion and FutureWork

In this paper, we highlight the critical role of neighborhood distribution in graph anomaly detection. To address the key challenges of inter-class neighborhood distribution overlap and intra-class neighborhood distribution dispersion, we propose NAAST-GNN. It integrates two modules: neighborhood ndaptive aggregation and spectral tuning, which dynamically adjust graph convolutions to align with node-specific neighborhood characteristics. Extensive experiments conduct on four public datasets validate the effectiveness of our approach, demonstrating superior performance compared to state-of-the-art methods. Future work will explore the broader interplay between heterophily and neighborhood distributions and extend the model to dynamic graph scenarios.

Acknowledgments

This work is supported by the National Natural Science Foundation of China No. 62402337, the Postdoctoral Fellowship Program of CPSF under Grant No. GZC20241207, and the China Postdoctoral Science Foundation under Grant No. 2024M752367.