  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.

Cryptography and Security;Artificial Intelligence