Source-linked AI summary
Rethinking Graph Neural Networks for Anomaly Detection
Jianheng Tang, Jiajin Li, Ziqi Gao, Jia Li
TL;DR
Graph anomaly detection needs filters suited to anomalies because ordinary GNN aggregation can dilute their representations. The paper characterizes anomalies’ spectral right-shift and develops BWGNN with localized band-pass Beta wavelets, reporting superior performance across four datasets.
Problem
Vanilla GNNs can average anomalies with benign neighborhoods, while existing methods do not directly address spectral-filter selection for anomaly detection.
Method
BWGNN uses Beta graph wavelets to construct flexible, localized, band-pass filters in spectral and spatial domains.
Results
The analysis finds that anomalies cause spectral energy to concentrate less at low frequencies and more at high frequencies, and BWGNN shows superior performance and scalability on four datasets.
Takeaways & Limitations
Graph anomaly detection benefits from analyzing anomaly information in the spectral domain and using filters tailored to the resulting right-shift.
Takeaways & Limitations
Computing the spectral energy ratio requires graph-Laplacian eigendecomposition, which is time-consuming on large-scale graphs.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) are widely applied for graph anomaly detection. As one of the key components for GNN design is to select a tailored spectral filter, we take the first step towards analyzing anomalies via the lens of the graph spectrum. Our crucial observation is the existence of anomalies will lead to the `right-shift' phenomenon, that is, the spectral energy distribution concentrates less on low frequencies and more on high frequencies. This fact motivates us to propose the Beta Wavelet Graph Neural Network (BWGNN). Indeed, BWGNN has spectral and spatial localized band-pass filters to better handle the `right-shift' phenomenon in anomalies. We demonstrate the effectiveness of BWGNN on four large-scale anomaly detection datasets. Our code and data are released at https://github.com/squareRoot3/Rethinking-Anomaly-Detection
1. Introduction
Graph anomaly detection is important across applications, but vanilla GNN neighborhood aggregation can dilute anomalies. The paper analyzes anomalies spectrally, identifies a right-shift in spectral energy, and proposes BWGNN with localized band-pass filters, evaluating it on four datasets.
- Graph anomaly detection supports applications including cybersecurity, fraud detection, health monitoring, and device failure detection.
- Vanilla GNNs can average anomalous nodes with benign neighborhoods, reducing their distinguishability and harming anomaly-detection performance.
- Existing approaches use attention, selective resampling, or auxiliary losses, but analyze anomaly detection primarily in the graph spatial domain.
- The paper observes and rigorously analyzes a right-shift in spectral energy, where increasing anomaly degree transfers energy from low to high frequencies.
- BWGNN uses Beta graph wavelets to provide spectral and spatially localized band-pass filtering tailored to graph anomalies.
- Experiments on four datasets, including newly released T-Finance and T-Social benchmarks, show BWGNN outperforming widely used GNNs and state-of-the-art anomaly-detection methods.
2. Spectral Analysis of Graph Anomaly
The paper analyzes graph anomalies through spectral energy and identifies a right-shift from low to high frequencies as anomaly severity increases. It supports this finding theoretically and empirically, while introducing the high-frequency area to avoid costly eigen-decomposition on large graphs.
- Spectral phenomenon: Anomalies shift spectral energy toward high frequencies, concentrating less energy on low-frequency eigenvalues.This right-shift is the paper’s central theoretical and empirical finding.
- Theoretical results: Under a Gaussian anomaly model, the expected inverse low-frequency energy ratio increases monotonically with anomaly degree σ/|µ|.The anomaly degree is represented by the coefficient of variation σ/|µ|.
- Spectral metric: The high-frequency area Shigh increases with anomaly degree and measures spectral right-shift without requiring eigen-decomposition.Its change can therefore quantify anomaly effects on large-scale graphs more efficiently.
- Synthetic validation: Synthetic experiments show that increasing anomaly variance or fraction raises high-frequency energy and decreases the low-frequency energy ratio.The pattern appears on both Barabási–Albert and Minnesota road graphs.
- Real-world validation: In Amazon, removing anomalies shifts energy toward λ ∈[0,0.2) and away from λ ∈[0.8,1.2), unlike random node removal.The frequency band around λ = 1 is strongly connected with anomalies in this case.
- Real-world validation: Across the evaluated datasets, removing anomalies decreases Shigh, while random node removal has limited effects; decreases exceed 10% for worst-case features on T-Social and YelpChi.The comparison is summarized in Table 1 using mean and lowest relative changes.
3. Methodology
The methodology targets anomalies’ right-shifted spectral energy with Beta graph wavelets that provide localized, band-pass filtering in spectral and spatial domains. BWGNN applies these wavelet kernels in parallel and aggregates their outputs for anomaly prediction.
- Motivation: Existing GNN filters may become effectively low-pass because high-frequency anomalies are sparse while most spectral energy remains low-frequency.The paper motivates band-pass, spectral-localized filters to address this mismatch.
- Graph wavelet foundations: Hammond’s graph wavelets require band-pass spectral kernels across different scales, with admissibility imposing vanishing responses at zero and infinite frequency.Polynomial kernels can avoid Laplacian eigendecomposition for faster computation.
- Beta graph wavelets: The Beta distribution is introduced as a graph kernel and satisfies Hammond’s graph-wavelet requirements.The construction restricts p,q to positive integers so the kernel is polynomial and fast computation is possible.
- Filter construction: A group of C + 1 Beta wavelets combines one low-pass filter with band-pass filters at different scales.Increasing C improves spectral locality at the expense of spatial locality, and vice versa.
- Comparison and motivation: Compared with Heat wavelets and related wavelet GNNs, Beta wavelets provide diverse low-pass and band-pass spectral responses that can be positive or negative across channels.The diversified responses capture both node similarities and differences, making anomaly representations more distinguishable.
- Locality properties: Beta wavelets can concentrate on any specific frequency band, while their spatial support is localized within (p+q)-hops.The concentration result follows when p+q grows with p = cq; spatial locality follows from the polynomial order.
- BWGNN architecture: BWGNN uses different wavelet kernels in parallel, aggregates their filtering results, and feeds the representation to an MLP with Sigmoid output for abnormal probabilities.Training uses weighted cross-entropy, with the aggregation function implemented by summation or concatenation.
4. Experiments
Experiments evaluate BWGNN across four anomaly-detection datasets, training settings, baselines, and sensitivity conditions. BWGNN generally performs best, with results depending on graph heterogeneity, neighborhood order, and anomaly degree.
- Experimental Setup: Experiments use YelpChi, Amazon, T-Finance, and T-Social, evaluated with F1-macro and AUC against feature-only, general GNN, and anomaly-detection baselines.The datasets cover review, user, transaction, and social-network anomaly detection.
- Experimental Setup: BWGNN supports multirelational graphs either by treating edge types uniformly or by propagating separately per relation followed by maximum pooling.These variants are denoted BWGNN (homo) and BWGNN (hetero).
- Performance Comparison: BWGNN achieves the best performance on all datasets except Amazon (1%), where PC-GNN obtains the best AUC score.For multirelational graphs, BWGNN (Hetero) performs better on YelpChi, whereas BWGNN (Homo) performs better on Amazon.
- Performance Comparison: 13.9% and 10.6% absolute improvements in F1-Macro and AUC respectively are reported for BWGNN versus PC-GNN on YelpChi (40%).The paper also reports stronger improvement on T-Social and shorter training time than the compared state-of-the-art methods.
- Sensitivity Analysis: Higher order C improves T-Social performance, while T-Finance shows no significant differences for C ≥2.The paper attributes the T-Social trend possibly to its greater sparsity, which requires a larger neighborhood range.
- Sensitivity Analysis: 99% F1-macro is reached by BWGNN at σ = 4, and BWGNN consistently outperforms ChebyNet and CAREGNN as anomaly fraction α varies.All three models improve as σ increases because anomalies become more distinguishable.
5. Conclusion
The paper analyzes graph anomalies spectrally, identifies a right-shift in spectral energy, and develops BWGNN to capture anomaly information. Experiments on four datasets show the model’s reported superiority and scalability.
- Conclusion: Graph anomalies lead to a right-shift of spectral energy distributions, with energy moving from low-frequency toward high-frequency components.The observation is rigorously justified on a vanilla probabilistic model.
- Conclusion: BWGNN uses Beta graph wavelets to generate band-pass filters localized in both spectral and spatial domains.The architecture is designed to better capture anomaly information on graphs.
- Conclusion: Empirical results on four datasets show the superiority and scalability of BWGNN.
A. Proof of Proposition 2
The proof establishes that the expected inverse low-frequency energy ratio increases monotonically with anomaly degree σ under the Gaussian anomaly model.
- Proof: Gaussian rotational invariance yields one distinguished spectral coefficient and independent standard-normalized coefficients for the remaining frequencies.The all-ones eigenvector corresponds to λ1 = 0, while the other coefficients have zero mean.
- Proof: The remaining squared spectral coefficients form a chi-square variable independent of the distinguished coefficient.This independence supports reducing the analysis to a scalar integral involving the anomaly parameter.
- Proof: The expectation of the inverse low-frequency energy ratio E_x[1/η_k(x,L)] increases monotonically with anomaly degree σ.
- Proof: Log-concavity of the relevant Gaussian integral implies its maximum occurs at ρ = 0.The argument uses closure of log-concavity under products and integration, together with differentiability.
B. Proof of Equation (1)
The proof connects the graph-spectral energy expression to the Laplacian quadratic form, showing how spatial smoothness relates to spectral energy.
- Proof: The derivation links spectral energy distribution to spatial smoothness: closer values across connected nodes produce smaller x^T Lx.This relationship is used to interpret anomaly degree through graph signals.
- Proof: The Laplacian quadratic form is expressed as x^T Lx through spectral graph theory.
C. Baselines and Implementation Details
The evaluation compares feature-only models, general-purpose GNNs, and graph-anomaly-detection methods. Implementations use established libraries or author-provided code, with weighted training loss and threshold tuning to address class imbalance in generic baselines.
- Baseline Groups: Baselines comprise feature-only MLP and SVM models, general GNNs including GCN, ChebyNet, GAT, GIN, and GraphSAGE, and anomaly-detection methods GraphConsis, CAREGNN, and PC-GNN.The groups represent models without graph relations, general GNN node-classification models, and state-of-the-art graph anomaly-detection methods.
- Implementation: MLP uses PyTorch, SVM uses Scikit-learn, several GNNs use DGL, anomaly-detection baselines use author code, and BWGNN uses PyTorch and DGL.GWNN is implemented by the authors because its source code does not support the fast algorithm.
- Imbalance Handling: Generic feature-only and GNN baselines produce few positive predictions because they are not specifically designed for anomaly detection and suffer from class imbalance.This motivates using weighted cross-entropy during training for fair comparisons.
- Imbalance Handling: Validation selects the binary classification threshold at 0.05 intervals to maximize F1-macro.The threshold search is applied after training to improve comparability under imbalanced predictions.
D. Additional Experimental Results
Additional experiments report results on YelpChi and Amazon across two training ratios. The table summarizes 10-run performance using means and standard deviations.
- Evaluation Setting: Results are reported for the YelpChi and Amazon datasets.These datasets form the evaluation setting for the additional experimental results.
- Reporting: Table 4 reports the mean ± standard deviation over 10 runs.Repeated runs provide both average performance and variability for each compared method.
- Evaluation Setting: The experiments use 1% and 40% training ratios.The table compares performance under both limited and larger training-data settings.