Graph Anomaly Detection via Feature Selection with Local Topological Residuals

1 Introduction

Due to its wide application in several domains, including financial fraud detection and intrusion detection in cybersecurity [Pourhabibi et al., 2020; He et al., 2022; Dong et al., 2022; Huang et al., 2022; Yang et al., 2019], graph anomaly detection (GAD) has emerged as a highly prominent field within graph data mining. GAD aims to identify entities (e.g., nodes, edges or subgraphs) that deviate from normal patterns within a graph [Ma et al., 2021; Pang et al., 2021]. In this paper, our primary focus is on the detection of anomalous nodes. Recent works [Qiao and Pang, 2023; Chen et al., 2024; Pan et al., 2025] have been built on the concept of local inconsistency mining (LIM), which is grounded in the intuition that abnormal nodes tend to exhibit low similarity to their neighboring nodes. However, in the real-world anomaly dataset, normal nodes may also have a lower similarity to neighbor nodes [Qiao and Pang, 2023]. Under these circumstances, incorporating structural information to align the representations of benign nodes with those of their neighbors can effectively suppress their anomaly scores, thereby mitigating false positives. Consequently, it is imperative for LIM to leverage Graph Neural Networks (GNNs) to incorporate topological information to better distinguish these normal instances from true anomalies.

∗Corresponding author.

A key challenge lies the inherent conflict between the message passing of GNNs and the assumptions underlying LIM. As illustrated in Figure 1, the aggregation mechanism of GNNs tends to homogenize connected nodes [Chai et al., 2022; Li et al., 2019; Balcilar et al., 2021], thereby increasing the consistency between a node and its neighborhood. This process effectively obfuscates local anomalous signals, making it significantly more challenging to distinguish local irregularities from their surrounding context.

While a multilayer perceptron (MLP) [Ramchoun et al., 2016] could be employed to circumvent this conflict, such an approach disregards valuable anomalous signals embedded within the graph topology, ultimately resulting in limited applicability. Consequently, the wholesale abandonment of message passing is ill-advised, as it provides a vital mechanism for regularizing normal data. On the other hand, while attention mechanisms can be leveraged to mitigate message passing between anomalous nodes and their neighbors, such approaches are primarily effective only when anomalies exhibit pronounced dissimilarity to their local context. Since structural anomalies often manifest as cohesive clusters with similar attributes and synchronized behaviors, attention-based methods frequently fail to accurately detect these collective patterns.

Driven by these insights, we develop a new GAD framework aimed at harmonizing inherent conflict between neighborhood message passing and LIM mechanisms. In this paper, we propose local feature-topological residuals (LTR) to quantify the impact of aggregation operations on individual feature dimensions. Building upon this, we propose LTRGAD, a two-stage framework that performs local and global anomaly detection decoupled. In the local detection phase, LTRGAD leverages LTR to perform adaptive feature selection. Specifically, features minimally impacted by the aggregation operation are processed via a Graph Convolutional Network (GCN) [Kipf and Welling, 2016] to integrate structural context for structural anomaly detection, while the remaining features are fed into an MLP to detect primitive attribute anomaly. Through adaptive feature selection and specialized dual-path processing, LTRGAD effectively reconciles the inherent conflict between neighborhood message passing and LIM. Based on the resulting anomaly scores, we derive high-confidence normal and anomalous subsets. From the high-confidence normal set, we extract global normal contexts and normal prototype nodes to serve as references for the subsequent stage. During the global anomaly detection phase, LTRGAD employs a transformer-based architecture to facilitate long-range information propagation. LTRGAD implements a prototype-based querying mechanism, where each node retrieves information from its nearest prototypical node to construct a prototype query representation, which is subsequently integrated into a comprehensive global node representation. The representation space is optimized by maximizing the similarity between high-confidence normal nodes and the global normal context, while constraining their distance to prototypical nodes. Finally, anomaly scores are computed based on the nodes' deviation from the global context and their spatial distance to the prototypes. The final anomaly score is obtained by aggregating the scores from both stages.

The primary contributions of our paper are summarized as follows:

• We investigate the inherent challenges faced by current LIM-based GAD methods when handling GNN message passing. To address these, we introduce LTR as a metric to quantify the impact of neighborhood aggregation on individual feature dimensions. Subsequently, we design an adaptive feature selection mechanism guided by LTR to reconcile the conflict between the message passing of GNNs and the assumptions underlying LIM.
• From a global perspective, we introduce a novel prototypical querying mechanism integrated within a transformer-based framework. This mechanism re-
• trieves representations by querying the relationship between a node and its nearest prototype node. The spatial distance between the node and these prototype nodes is subsequently utilized as a anomaly metric.
• Extensive experimental results on seven benchmark datasets, including four datasets injected with synthetic anomalies and three datasets with organic anomalies, demonstrate that our method achieves state-of-the-art performance compared to a series of baselines. Furthermore, ablation experiments confirm the effectiveness of feature selection based on LTR.

2 RelatedWork

Traditional GAD methods [Breunig et al., 2000; Zhou et al., 2021; Perozzi and Akoglu, 2016; Li et al., 2017; Peng et al., 2018] often underperform due to their limited capacity to integrate graph features and topology. Conversely, GNNs have revolutionized the field with superior representational power. While some supervised models exist [Dou et al., 2020; Liu et al., 2021a; Gao et al., 2023; Zhang et al., 2021], research primarily focuses on Unsupervised Graph Anomaly Detection (UGAD), which can be categorized into autoencoderbased methods, graph contrastive learning (GCL) methods, and LIM-based methods.

Autoencoder-based Methods. DOMINANT [Ding et al., 2019a] established the graph autoencoders architecture, scoring anomalies via joint structural and attribute reconstruction error. Building on this, AnomalyDAE [Fan et al., 2020] integrates an attention mechanism within the structural encoder to capture complex topological features, while ComGA [Luo et al., 2022] integrates community aware mechanisms to mitigate intercommunity feature homogenization.

GCL-basedMethods. CoLA [Liu et al., 2021b] pioneered GCL for GAD by aligning node and local subgraph representations to derive similarity-based anomaly scores. Building on this, SL-GAD [Zheng et al., 2021] integrates attribute regression with multi-view contrastive learning, while Sub-CR [Zhang et al., 2022] combines multi-view contrastive learning and masked autoencoder reconstruction.

LIM-based Methods. While the motivations of some aforementioned methods are conceptually aligned with the LIM, more recent LIM-based GAD approaches specifically formulate anomaly scores based on the discrepancy between a node and its local neighborhood. TAM [Qiao and Pang, 2023] unveils the phenomenon of one-class homophily inherent in real-world anomaly datasets and formulates local node affinity as the primary metric for calculating anomaly scores. TAM addresses the conflict between message passing and LIM by pruning non-homophily edges. GADAM [Chen et al., 2024] employs only an MLP for local anomaly detection to avoid message passing, and subsequently adjusts the message-passing framework based on the anomaly detection results. Both TAM and GADAM adjust their messagepassing frameworks based on preliminary detection results. However, this dependency limits their performance across diverse datasets where initial predictions may be unreliable. In contrast, LTRGAD addresses the conflict between message passing and LIM through adaptive feature selection, offering superior generalizability and effectiveness.

3 Preliminary

AttributedGraph. An attributed graph is formally denoted as G = (V, E, X), where V = {v1, . . . , vn} represents the set of n nodes, E ⊆ V × V is the set of edges, and X ∈ Rn×d signifies the node attribute matrix. Specifically, the i-th row Xi ∈ Rd of X characterizes the feature vector associated with node vi. The topological structure of the graph is encoded by a binary adjacency matrix A ∈ {0, 1}n×n , where Ai,j = 1 if (vi, vj) ∈ E, and Ai,j = 0 otherwise.

Problem Statement. Given an attributed graph G = (V, E, X), the objective of GAD is to learn a scoring function f : V → R that assigns an anomaly score Si = f(vi) to each node vi ∈ V. This score quantifies the degree of deviation of node vi from the normative patterns exhibited by the majority of nodes in the network. Nodes that significantly diverge from the consensus structural or attribute distributions are assigned higher scores, thereby facilitating their identification via a descending rank-order analysis.

4 Methodology

As shown in Figure 2, the overall workflow of LTRGAD consists of two stages. (1) Local Anomaly Detection Stage: This stage performs adaptive feature selection based on the LTR metric. Features are selectively channeled into either the MLP encoder or the GCN encoder to execute dual tasks for local anomaly detection. The output includes sets of highconfident normal and anomalous nodes, along with a global normal context and normal prototype nodes. (2) The Global Stage: This stage employs a transformer to facilitate global feature interaction. Building upon the transformer architecture, we compute the relationship between each node and its most relevant normal prototypes to generate prototype-query embeddings. These embeddings are then integrated to produce global node representations. Finally, the anomaly score is derived by considering both the node's similarity to the global normal context and its spatial distance from the prototype nodes. Next, we provide a detailed exposition of each stage within our proposed framework.

4.1 Local Feature Topological Residual

While the neighbor information brought by GNN aggregation is beneficial, it fundamentally conflicts with the mining of local inconsistency. To address this, we propose the local feature-topological residuals (LTR) to quantify the impact of GNN aggregation on various feature dimensions, formulated as follows:

where Sim(·) denotes the cosine similarity function. ˜X = ( ˆA)kX represents the aggregated node feature matrix obtained by propagating information across k-hop neighborhoods, and ˜X(m) i corresponds to the aggregated feature vector of the i-th node under the m-th attribute view. And ˆA is the symmetrically re-normalized adjacency matrix, defined as ˆA= ˜D-1/2 ˜A˜D-1/2 , where ˜A=A+ I, and ˜D denotes the corresponding degree matrix. In the subsequent experiments, the value of k is fixed at 2.

A higher value of LTR(m) indicates that the m-th feature undergoes a more pronounced consistency transformation due to the aggregation operation, which proves detrimental to the efficacy of the anomaly detection task. Conversely, a lower LTR(m) suggests that the m-th feature exhibits lower sensitivity to aggregation, thereby allowing for the beneficial integration of topological information through the aggregation process.

4.2 LTR-Based Local Anomaly Detection

For each feature X(m) , we calculate its LTR according to Eq. (1), followed by a normalization step to account for variations across diverse datasets. We then employ a threshold-based filtering mechanism to partition the features into two disjoint subsets, denoted as Xlow and Xhigh. Specifically, features satisfying LTR < λ are assigned to Xlow and processed via a GCN to incorporate topological information. Conversely, the remaining features, denoted as Xhigh, are handled by an MLP to identify original attribute anomalies.

Attribute Anomaly Detection via Contrastive Learning

Normal nodes typically exhibit high attribute similarity with their neighbors, whereas anomalous nodes manifest lower levels of such affinity. Leveraging this disparity, we employ contrastive learning to quantify the similarity between a node and its local neighborhood, thereby facilitating the identification of attribute anomalous.

MLP as encoder. We employ an L-layer MLP to obtain the node embedding matrix, as formulated in Eq. (2). Utilizing the MLP as an encoder preserves the independence of node attribute representations, thereby circumventing the over-smoothing issue typically induced by message-passing mechanisms.

where H(0) MLP = Xhigh and σ(·) is an activation function. The node representations yielded by the terminal MLP layer serve as the finalized attribute embeddings Zattr = H(L) MLP .

Contrastive Learning. Motivated by the observation that normal nodes exhibit a high degree of similarity with their neighbors, we designate the first-order neighborhood Ni of node vi as its positive sample set. Correspondingly, the negative sample set is constructed from the first-order neighbors of a randomly sampled non-neighboring node vj (where vj is not connected to vi). Specifically, for a target node vi, we define its positive representation EPi and negative representation ENi as follows:

To quantify the similarity between the target node and its corresponding positive and negative instances, we employ the inner product as the similarity discriminator, which is equivalent to cosine similarity after L2 normalization:

To distinguish anomalous nodes from normal ones, we employ the Binary Cross-Entropy (BCE) loss to optimize. Specifically, the objective is to maximize the similarity scores of positive instance pairs while minimizing those of negative instance pairs, thereby pulling normal nodes closer to their local context and pushing anomalous nodes away.

Then, the similarity score of the positive instance pair, denoted as sPi , is utilized as the raw attribute anomaly score:

Structural Anomaly Detection via Link Prediction

Normal nodes tend to form robust and cohesive connections with their peers, reflecting a high degree of structural homophily. LTRGAD introduces the link reconstruction task as a self-supervised signal to compel the model to extract generalizable connectivity patterns directly from the graph topology. Intuitively, if the ground-truth edges of a node consistently receive low prediction confidence during the reconstruction process, it signifies that its structural relationships are poorly explained by the normal structural patterns captured by the encoder. Consequently, such a discrepancy indicates a high degree of structural anomalousness for the corresponding node.

GCN as encoder. LTRGAD integrates topological information via GCNs and employ a link reconstruction task to identify structural anomalies. Formally, the node representations at the l-th GCN layer can be generally expressed as:

where ϕ(·) denotes a non-linear activation function. H(l-1) GCN denotes the node embedding matrix from the preceding layer, with the initial input set as H(0) GCN = Xlow.

Link Prediction. The node representations yielded by the terminal GCN layer serve as the finalized structural embeddings Zstruct = H(L) GCN. To model interactions between node pairs, we utilize the Hadamard product [Horn, 1990] as the interaction operator and employ a MLP as the decoder. For any node pair (vi, vj), the link prediction logit ˆ yij is computed as:

where zi, zj ∈ Zstruct and ⊙ denotes the element-wise product. ˆ yij ∈ R serves as an unnormalized logit that quantifies the structural compatibility between the two nodes.

To provide supervision for the link reconstruction task, we construct the training sample set by designating all observed edges in the original graph as the positive set E+, while the negative set E- is formed by uniformly sampling non-adjacent node pairs at random. We optimize the link reconstruction task using the BCE loss:

where σ(·) denotes the Sigmoid function.

We define the structural anomaly score of a node based on the link reconstruction consistency within its true neighborhood. Specifically, for a node vi, the structural anomaly score is computed as:

Local Anomaly Detection

The final local node representation is obtained by concatenating the embeddings derived from the two respective branches:

where ∥ denotes the concatenation operator.

To jointly optimize the local anomaly detection module, the total training objective is defined as the sum of the attribute loss and the structural loss:

To aggregate the diagnostic information from dual perspectives, the final local anomaly score Slocal is formulated as a weighted fusion of the attribute and structural components:

where α ∈ [0, 1] is a balancing coefficient. Based on the fused scores, we rank all nodes and identify the top knor% of nodes with the lowest scores to constitute a high-confidence normal set Vn. To capture the representative characteristics of the normal class, a global normal context C is derived by averaging the local representations of nodes in Vn:

Symmetrically, we select kano% of nodes with the highest anomaly scores to form a high-confidence abnormal set Va. To further account for the multi community distribution of normal patterns, we perform K-means clustering [MacQueen, 1967] on Vn to extract K distinctive normal prototype nodes P = {p1, p2, . . . , pK}. These prototype nodes, together with the global context C and the two high-confidence sets, serve as refined supervised signals to guide the subsequent global anomaly detection stage.

4.3 Global Anomaly Detection

While effective in capturing neighborhood-level irregularities, the local detection module is inherently constrained by its finite receptive field, which may impede the identification of anomalies with global-scale deviations. To bridge this gap, we initiate a second stage of analysis that capitalizes on the high-confidence normal and abnormal priors distilled from the local phase. This stage enables the model to conduct a more comprehensive anomaly assessment from a holistic global perspective.

Global Contextual Feature Extraction. To capture longrange dependencies, we employ a transformer architecture that operates directly on the raw node features X. We deliberately bypass the local embeddings generated in the first stage and utilize raw attributes as input to circumvent the over-smoothing issue. By re-engaging with the raw feature space, the global branch can extract distinct structural and semantic signals that are independent of the local topological bias.

We project X into Query Q = XWQ, Key K = XWK, and Value V = XWV spaces via standard linear transformations. To ensure computational efficiency on large-scale graphs, we adopt a linear attention mechanism [Wu et al., 2022]. The global contextual representation is formulated as:

where ϕ(·) is a non-negative feature mapping function.

Normality Alignment via Prototype Querying. We utilize the normal prototype nodes P obtained from the local anomaly detection stage to explicitly anchor the representation of normal data. Normal prototype query representation is formulated as:

where Aproto denotes the cross-attention weights between nodes and prototype nodes. The final global node embedding is formulated as the additive fusion of the contextual information and the normal prototype query:

Inspired by the observation that anomalies tend to exhibit a greater divergence from the global normal context C than normal nodes [Chen et al., 2022], we quantify the degree of alignment by computing the similarity between node embeddings and the global center:

where gi = Dis(Zglobal i , C) = Zglobal i CT .

Furthermore, in accordance with the principle that normal nodes should align with their respective community-level normality [Francisquini et al., 2022], we quantify the structural anomaly by measuring the Euclidean distance between the fused node embedding and its prototype-based query:

The loss function of the global module is defined as:

The normality of a node is characterized by the extent to which its representation aligns with the global normal context C. Similarly, a node is considered more normal if its representation lies closer to the learned normal prototype queries in the latent space. Based on these principles, we define the final global anomaly score as:

Ultimately, the final anomaly score is derived by fusing S local and S global using β ∈ [0, 1] as a balancing factor to yield a comprehensive assessment:

5 Experiments

5.1 Experimental Settings

Datasets. To comprehensively evaluate the proposed model, we conduct experiments on seven benchmark datasets. (1) Four widely used benchmark datasets: Cora, Citeseer, Pubmed [Sen et al., 2008], and ACM [Tang et al., 2008]. Given the absence of inherent anomalies in these graphs, we adopt the synthetic injection protocol established in prior work [Song et al., 2007; Ding et al., 2019b; Ding et al., 2019a]. (2) Three real-world datasets that contain organic anomalies: Books [S´anchez et al., 2013], Disneyc [M¨uller et al., 2013], and Enron [S´anchez et al., 2013]. Detailed descriptions of the datasets and anomaly injection approach are summarized in the supplementary material.

Baseline. To evaluate the performance, we benchmark our approach against nine representative methods. DOMINANT [Ding et al., 2019a], AnomalyDAE [Fan et al., 2020] and ComGA [Luo et al., 2022] leverage autoencoder architectures to facilitate GAD. CoLA [Liu et al., 2021b], SL-GAD [Zheng et al., 2021], and Sub-CR [Zhang et al., 2022] represent GAD approaches grounded in graph contrastive learning. TAM [Qiao and Pang, 2023], GADAM [Chen et al., 2024] and HUGE [Pan et al., 2025] are GAD methods that employ local inconsistency mining. We provide more details for these methods in the supplementary material.

Evaluation metrics. We evaluate the proposed framework and baseline methods using ROC-AUC, a widely adopted metric for anomaly detection [Ma et al., 2021]. The ROC curve illustrates the trade-off between the true positive rate and false positive rate based on ground-truth labels. The AUC score represents the probability that an anomalous node is ranked higher than a normal one, with values closer to 1 indicating better performance.

Implementation details. We set the number of MLP layers in the local module to 1 and the GCN layer to 2. We set knor% = 50% and kano% = 5% for all datasets. It is noteworthy that LTRGAD exhibits strong robustness to the hyperparameters K and β. Consequently, we set K = 10 and β = 0.5 as the default values for our experiments. Both the local and global modules are trained for 100 epochs. Other implementation details are provided in the supplementary material.

5.2 Result and Analysis

As illustrated in Table 1, LTRGAD demonstrates a significant performance advantage over nine representative baselines in terms of ROC-AUC. LTRGAD achieves substantial improvements on challenging real-world anomaly datasets. Specifically, LTRGAD achieves absolute ROC-AUC improvements of 15.96, 11.92, and 9.56 percentage points on the Disney, Books, and Enron datasets, respectively. These results clearly demonstrate the superior capability of LTRGAD in effectively capturing and identifying real-world anomalies. LTRGAD demonstrates great compatibility across diverse graph domains, consistently achieving superior performance on datasets characterized by both injected and realworld anomaly patterns. This robustness distinguishes LTRGAD from existing paradigms that often struggle to maintain efficacy across varying anomaly distributions.

5.3 Ablation Study

To verify the contribution of each component within the LTRGAD framework, we conducted an ablation study by comparing the full model against four variants: (1) LTRGAD w/o Global, which removes the global detection stage; (2) LTRAGD w/o FS, which removes the feature selection module and feeds all features into the MLP encoder and GCN encoder simultaneously; (3) LTRGADMLP w/o FS, which removes the feature selection module and directly feeds all features to an MLP encoder; and (4) LTRGADGCN w/o FS, which similarly the removes feature selection module and uses a GCN encoder. The results in the Table 2 verify the importance of two key components of LTRGAD:

• Global Module. The complete LTRGAD consistently outperforms LTRGAD w/o Global across all datasets. This performance gap is particularly evident on the Books and Enron datasets, indicating that the longdistance dependencies and global context captured by the global module are beneficial for anomaly detection.
• Feature Selection Module. In the absence of feature selection, we observe a significant performance decline across all datasets, which validates the effectiveness of our feature selection module. Furthermore, we observed a difference in performance when using MLP encoders and GCN encoders independently within the local mod-

ule. Specifically, the LTRGADMLP w/o FS exhibits superior performance on datasets with injected anomalies, whereas LTRGADGCN w/o FS proves more effective on real-world anomaly datasets. This phenomenon indicates that injected anomalies are susceptible to the noise propagation inherent in GCNs, whereas real-world anomalies, characterized by strong attribute camouflage, necessitate the structural context provided by GCNs. Crucially, the full LTRGAD model consistently outperforms both variants across all benchmarks. This validates that our feature selection strategy provides LTRGAD with superior compatibility, making it equally effective for injected anomalies datasets and real world anomalies datasets.

5.4 Parameter Study

Thresholds λ and Balancing Factors α. As shown in figure 3, we investigate the impact of different thresholds λ and balancing factors α on the proposed LTRGAD framework across four datasets: Cora, Citeseer, Disney, and Enron. Specifically, for datasets featuring injected anomalies (Cora and Citeseer), the optimal ROC-AUC is typically achieved at lower values of λ and α. This suggests that the model benefits from a higher sensitivity to attribute-level deviations to capture artificial perturbations. Conversely, on real-world anomaly datasets (Disney and Enron) the model yields superior performance with larger λ and α. This phenomenon indicates that while naturally occurring anomalies may exhibit attribute distributions similar to normal instances, they often manifest more pronounced irregularities in their structural connectivity, necessitating a parameter configuration that prioritizes structural incongruity.

High-Confidence Anomaly Ratio kano%. To evaluate the impact of the two high-confidence sets on LTRGAD, we conducted a sensitivity analysis of model performance and pseudo-label accuracy across various kano% values. Notably, as normal nodes constitute the vast majority of the dataset, we omitted the reporting of knor%. As illustrated in Figure 4, the consistently high accuracy of the pseudo-labels validates the effectiveness of our local model. Furthermore, LTRGAD demonstrates strong robustness across different kano% settings. Consequently, in our practical implementation, we set knor% = 50% and kano% = 5% for all datasets.

6 Conclusion

In this paper, we investigate the inherent conflict between the message-passing mechanism of GNNs and the underlying assumptions of the LIM. To address this challenge, we propose a novel framework, LTRGAD, which employs adaptive feature selection guided by LTR to process features through dual paths, thereby effectively reconciling this conflict. Furthermore, LTRGAD incorporates a global module that leverages global normal context and normal prototypes to identify anomalies beyond the local perspective. Extensive experimental results demonstrate the superiority of LTRGAD, while ablation studies provide deeper insights into its inner workings. We hope our work provides insights for detecting anomalies in complex real-world scenarios.

Ethical Statement

There are no ethical issues.

Acknowledgments

This work was supported in part by the Natural Science Foundation of Tianjin under Grant 25JCZDJC01300, and in part by the National Natural Science Foundation of China under Grant U2468204.