GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction

Abstract

Graph Anomaly Detection (GAD) is a technique used to identify abnormal nodes within graphs, finding applications in network security, fraud detection, social media spam detection, and various other domains. A common method for GAD is Graph Auto-Encoders (GAEs), which encode graph data into node representations and identify anomalies by assessing the reconstruction quality of the graphs based on these representations. However, existing GAE models are primarily optimized for direct link reconstruction, resulting in nodes connected in the graph being clustered in the latent space. As a result, they excel at detecting cluster-type structural anomalies but struggle with more complex structural anomalies that do not conform to clusters. To address this limitation, we propose a novel solution called GAD-NR, a new variant of GAE that incorporates neighborhood reconstruction for graph anomaly detection. GAD-NR aims to reconstruct the entire neighborhood of a node, encompassing the local structure, self-attributes, and neighbor attributes, based on the corresponding node representation. By comparing the neighborhood reconstruction loss between anomalous nodes and normal nodes, GAD-NR can effectively detect any anomalies. Extensive experimentation conducted on six real-world datasets validates the effectiveness of GAD-NR, showcasing significant improvements (by up to 30% in AUC) over state-of-the-art competitors. The source code for GAD-NR is openly available. Importantly, the comparative analysis reveals that the existing methods perform well only in detecting one or two types of anomalies out of the three types studied. In contrast, GAD-NR excels at detecting all three types of anomalies across the datasets, demonstrating its comprehensive anomaly detection capabilities.

Accepted at the 17th ACM International Conference on Web Search and Data Mining (WSDM-2024)

References in corpus (19)

• DeepWalk: Online Learning of Social Representations
• Semi-Supervised Classification with Graph Convolutional Networks
• LINE: Large-scale Information Network Embedding
• Inductive Representation Learning on Large Graphs
• A Comprehensive Survey on Graph Anomaly Detection with Deep Learning
• Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning
• A Semi-supervised Graph Attentive Network for Financial Fraud Detection
• BotRGCN: Twitter Bot Detection with Relational Graph Convolutional Networks
• Bayesian anomaly detection methods for social networks
• Rethinking Graph Neural Networks for Anomaly Detection
• BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs
• Improving Generalizability of Graph Anomaly Detection Models via Data Augmentation
• Multi-scale Anomaly Detection on Attributed Networks
• Graph Auto-Encoder Via Neighborhood Wasserstein Reconstruction
• GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection
• SpecAE: Spectral AutoEncoder for Anomaly Detection in Attributed Networks
• AnomalyDAE: Dual autoencoder for anomaly detection on attributed networks
• Hop-Count Based Self-Supervised Anomaly Detection on Attributed Networks

Cited by in corpus (6)

• Reconciling Attribute and Structural Anomalies for Improved Graph Anomaly Detection
• Grad: Guided Relation Diffusion Generation for Graph Augmentation in Graph Fraud Detection
• A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions
• Graph Evidential Learning for Anomaly Detection
• UMGAD: Unsupervised Multiplex Graph Anomaly Detection
• Human-Centric Community Detection in Hybrid Metaverse Networks with Integrated AI Entities