Address Anomalies at Critical Crossroads for Graph Anomaly Detection

Graph anomaly detection (GAD) on attributed networks aims to capture abnormal nodes whose attributes or structures differ significantly from most nodes. The existing GAD models amplify the representation differences between normal and abnormal nodes to identify anomalies via carefully designed feature extraction modules. However, these models ignore the bottlenecks encountered by abnormal nodes in message passing. In particular, when the anomalies occurs at critical crossroads, the information of multiple nodes is compressed into a fixed-length representation, and the resulting over-squashing weakens the abnormal information. To address this, we propose an unsupervised <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>ST</u></b>ructural optimization model guided by s<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>IM</u></b>ilarity reconstruction (STIM). Specifically, we define redundant edges that cause over-squashing, design the Neighbor-Structure Optimization module to filter redundant edges through the edge-dropping strategy based on critical crossroads, and optimize the graph structure to alleviate over-squashing. In addition, to alleviate the over-smoothing caused by the high inter-class node similarity of the data itself and the edge-dropping strategy, we design the Neighbor-Similarity Reconstruction module based on similarity calculation, which guides the model to expand inter-class variation. Extensive experiments on benchmark datasets show that STIM can effectively optimize message passing and improve anomaly detection performance. The source code is available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/Junyi-Yan/STIM</uri>.