Search papers, labs, and topics across Lattice.
This paper introduces SAGAD, a scalable graph anomaly detection framework that addresses homophily disparity by adaptively fusing low- and high-frequency information extracted using reparameterized Chebyshev filters. SAGAD mitigates node-level homophily disparity with an Anomaly Context-Aware Adaptive Fusion, conditioned on Rayleigh Quotient-guided anomalous subgraph structures, and class-level disparity with a Frequency Preference Guidance Loss. The framework supports mini-batch training, achieves linear complexity, and demonstrates superior accuracy and scalability on 10 benchmarks compared to existing GNN-based methods.
By adaptively fusing low- and high-frequency graph signals based on local anomaly context, SAGAD achieves state-of-the-art graph anomaly detection while scaling linearly to large graphs.
Graph anomaly detection (GAD) aims to identify nodes that deviate from normal patterns in structure or features. While recent GNN-based approaches have advanced this task, they struggle with two major challenges: 1) homophily disparity, where nodes exhibit varying homophily at both class and node levels; and 2) limited scalability, as many methods rely on costly whole-graph operations. To address them, we propose SAGAD, a Scalable and Adaptive framework for GAD. SAGAD precomputes multi-hop embeddings and applies reparameterized Chebyshev filters to extract low- and high-frequency information, enabling efficient training and capturing both homophilic and heterophilic patterns. To mitigate node-level homophily disparity, we introduce an Anomaly Context-Aware Adaptive Fusion, which adaptively fuses low- and high-pass embeddings using fusion coefficients conditioned on Rayleigh Quotient-guided anomalous subgraph structures for each node. To alleviate class-level disparity, we design a Frequency Preference Guidance Loss, which encourages anomalies to preserve more high-frequency information than normal nodes. SAGAD supports mini-batch training, achieves linear time and space complexity, and drastically reduces memory usage on large-scale graphs. Theoretically, SAGAD ensures asymptotic linear separability between normal and abnormal nodes under mild conditions. Extensive experiments on 10 benchmarks confirm SAGAD's superior accuracy and scalability over state-of-the-art methods.
