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 dual-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 dual-space attack
against graph anomaly detection in which the graph space relies on the feature
space.

基于随机游走的异常检测（RWAD）常用于在各种应用中识别异常模式。本文通过设计实用的双空间攻击，研究了图空间和特征空间攻击之间的相互作用，并提出了解决图空间攻击的两种策略：交替迭代攻击（alterI-attack）和利用随机游走模型的闭合解（cf-attack）。通过在有限的攻击预算下，全面实验表明我们的攻击方法有效地使目标节点成为 RWAD 的一部分，并进行了黑盒情况下的传递攻击实验，结果显示我们的特征攻击显著降低目标节点的异常分数。我们的研究为研究图异常检测中的双空间攻击打开了大门，其中图空间依赖于特征空间。