Graph anomaly detection achieves high accuracy without training
Graph Anomaly Detection as Finite-Horizon Control: Training-Free Scoring via Empirical Bayes
Machine Learning
Summary
Detecting unusual nodes in networks like social or financial graphs usually needs complex training and tuning. The authors present a method called EB-GAD that finds anomalies by modeling normal node behavior mathematically and measuring deviation without any training. This approach uses graph structure and node features to score anomalies efficiently and stably. It performs very well on many large real-world datasets, often outperforming existing methods without needing labels or model training.
What this means in practice
- •For fraud analysts: Detect suspicious users or transactions in financial networks without needing labeled data or costly training.$Commercial implications: Enables fraud detection products that operate efficiently on large-scale networks with minimal configuration and no training data.
- •For social media engineers: Identify anomalous behavior or fake accounts in user interaction graphs using a stable, training-free detection method.
Authors
Fred Xu, Thomas Markovich, Florence Regol, Yizhou Sun
Abstract
Node-level graph anomaly detection (GAD) identifies nodes whose attributes and interactions deviate from dominant graph regularities. Existing GAD models encode normality and anomaly scoring indirectly through architectures, message passing, reconstruction or contrastive objectives, and tuned score families. This entangles graph trust (how strongly graph structure should define normality), graph-spectral weighting, and anomaly-score choice, yielding scores that are costly, opaque, and unstable across graph regimes. We propose EB-GAD (Empirical-Bayes GAD), a training-free framework that models normality as graph-aware generalized Ornstein-Uhlenbeck (GOU) relaxation toward a graph-filtered template. Empirical Bayes fits the graph precision from the residual-field likelihood; the GOU then turns scoring into a closed-form finite-horizon control energy, the minimum effort to steer a feature-neutral node to its observed endpoint along graph-spectral relaxation. Sweeping relaxation horizon and endpoint tolerance yields a bank of scores that share one fitted prior: equilibrium Mahalanobis scoring is one limit, while finite-horizon control-energy and scale-normalized ratio scores reveal anomalies that static equilibrium scoring can mask. A label-free selector chooses the score family from feature homophily, edge density, and feature dimension, then ranks candidates by fitted-null deviation and rank stability. On 11 benchmarks and without labels at any step, EB-GAD has the best or tied-best AUROC on 9: the four financial fraud networks (up to 3.7M nodes), the YelpChi and Amazon review graphs, Weibo, Reddit and Facebook, with margins of up to 21.7 points. It is second on BlogCatalog and ACM.