Local Homophily-Aware Graph Neural Network with Adaptive Polynomial Filters for Scalable Graph Anomaly Detection

This paper presents the Local Homophily Graph Neural Network (LH-GNN), a novel framework for Graph Anomaly Detection (GAD). Anomalous activities in graphs often exhibit a complex interplay of homophily and heterophily, with our analysis revealing that anomalous nodes typically display a higher degree of heterophily compared to normal nodes. Existing GNN-based methods start to incorporate heterophily modeling but fail to address two critical challenges: (1) the efficiency challenge, as traditional spectral decomposition based methods are computationally expensive, and (2) the local homophily estimation challenge, where prior knowledge of node-wise homophily ratios is often unavailable. To address these challenges, LH-GNN introduces a lightweight polynomial graph filter that dynamically adjusts to node-specific homophily ratios, enabling efficient representation learning for both normal and anomalous nodes through adaptable heterophilic and homophilic bases. This design achieves linear time complexity, significantly improving computational efficiency. Additionally, we propose an iterative prototype learning strategy to estimate local homophily values without requiring additional labels. This strategy leverages class prototypes and uncertainty measures to assign reliable pseudo-labels, effectively capturing node-wise homophily. Together, these innovations enable LH-GNN to overcome the limitations of existing methods. Extensive experiments on four benchmark datasets demonstrate that LH-GNN outperforms state-of-the-art methods in both effectiveness and efficiency, achieving 4.4% improvements in detection accuracy and 11× computational speedup.