Bibliographic Details
| Title: |
Coupled-Space Attacks against Random-Walk-based Anomaly Detection |
| Authors: |
Lai, Yuni, Waniek, Marcin, Li, Liying, Wu, Jingwen, Zhu, Yulin, Michalak, Tomasz P., Rahwan, Talal, Zhou, Kai |
| Publication Year: |
2023 |
| Collection: |
Computer Science |
| Subject Terms: |
Computer Science - Cryptography and Security, Computer Science - Artificial Intelligence |
| More Details: |
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.
Comment: 13 pages |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2307.14387 |
| Accession Number: |
edsarx.2307.14387 |
| Database: |
arXiv |
