2023/07/26 by Yuni Lai, Marcin Waniek, Lai, Yuni +13 · 1 citation
Computer Science · Physics and Astronomy · #Anomaly Detection Techniques and Applications #Artificial Intelligence (cs.AI) #Complex Network Analysis Techniques #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Network Security and Intrusion Detection
paper · pdf · doi:10.48550/arxiv.2307.14387
openalex publication_date 2023/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Random Walks-based Anomaly Detection (RWAD) is commonly used to identify anomalous patterns in various applications. An intriguing characteristic of RWAD is that the input graph can either be pre-existing or constructed from raw features. Consequently, there are two potential attack surfaces against RWAD: graph-space attacks and feature-space attacks. In this paper, we explore this vulnerability by designing practical coupled-space attacks, investigating the interplay between graph-space and feature-space attacks. To this end, we conduct a thorough complexity analysis, proving that attacking RWAD is NP-hard. Then, we proceed to formulate the graph-space attack as a bi-level optimization problem and propose two strategies to solve it: alternative iteration (alterI-attack) or utilizing the closed-form solution of the random walk model (cf-attack). Finally, we utilize the results from the graph-space attacks as guidance to design more powerful feature-space attacks (i.e., graph-guided attacks). Comprehensive experiments demonstrate that our proposed attacks are effective in enabling the target nodes from RWAD with a limited attack budget. In addition, we conduct transfer attack experiments in a black-box setting, which show that our feature attack significantly decreases the anomaly scores of target nodes. Our study opens the door to studying the coupled-space attack against graph anomaly detection in which the graph space relies on the feature space.