# Coupled-Space Attacks against Random-Walk-based Anomaly Detection

arXiv: https://arxiv.org/abs/2307.14387 · HTML: https://mlsanity.com/paper/2307.14387/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 60 references that are in the map.
- First posted on arXiv 26 Jul 2023.

## Builds on (most cited first, 23 of 23)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Understanding disentangling in β-VAE](https://mlsanity.com/paper/1804.03599/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Videos as Space-Time Region Graphs](https://mlsanity.com/paper/1806.01810/) (2018)
- [ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions](https://mlsanity.com/paper/2201.00382/) (2022)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection](https://mlsanity.com/paper/2306.12251/) (2023)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction](https://mlsanity.com/paper/2306.01951/) (2023)
- [Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection](https://mlsanity.com/paper/2306.00006/) (2023)
- [Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagation](https://mlsanity.com/paper/2201.07986/) (2022)
- [Provable Self-Representation Based Outlier Detection in a Union of Subspaces](https://mlsanity.com/paper/1704.03925/) (2017)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [GuiltyWalker: Distance to illicit nodes in the Bitcoin network](https://mlsanity.com/paper/2102.05373/) (2021)
- [Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge](https://mlsanity.com/paper/2105.12419/) (2021)
- [BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detection](https://mlsanity.com/paper/2106.09989/) (2021)
- [Geometric graphs from data to aid classification tasks with graph convolutional networks](https://mlsanity.com/paper/2005.04081/) (2020)
- [Robust Collective Classification against Structural Attacks](https://mlsanity.com/paper/2007.13073/) (2020)
- [Faster Sparse Matrix Inversion and Rank Computation in Finite Fields](https://mlsanity.com/paper/2106.09830/) (2021)

## Built on by (most cited first, 2 of 2)

- [Random Walk Learning and the Pac-Man Attack](https://mlsanity.com/paper/2508.05663/) (2025)
- [Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks](https://mlsanity.com/paper/2601.07674/) (2026)

## Abstract (arXiv)

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.