# Reinforcement Learning-based Black-Box Evasion Attacks to Link Prediction in Dynamic Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Sep 2020.

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

- [Task and Model Agnostic Adversarial Attack on Graph Neural Networks](https://mlsanity.com/paper/2112.13267/) (2021)
- [Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence](https://mlsanity.com/paper/2304.04343/) (2023)
- [Dyn-Backdoor: Backdoor Attack on Dynamic Link Prediction](https://mlsanity.com/paper/2110.03875/) (2021)
- [On the Validity of Traditional Vulnerability Scoring Systems for Adversarial Attacks against LLMs](https://mlsanity.com/paper/2412.20087/) (2024)
- [Momentum Gradient-based Untargeted Attack on Hypergraph Neural Networks](https://mlsanity.com/paper/2310.15656/) (2023)
- [Dynamic Homophily with Imperfect Recall: Modeling Resilience in Adversarial Networks](https://mlsanity.com/paper/2512.12332/) (2025)

## Abstract (arXiv)

Link prediction in dynamic graphs (LPDG) is an important research problem that has diverse applications such as online recommendations, studies on disease contagion, organizational studies, etc. Various LPDG methods based on graph embedding and graph neural networks have been recently proposed and achieved state-of-the-art performance. In this paper, we study the vulnerability of LPDG methods and propose the first practical black-box evasion attack. Specifically, given a trained LPDG model, our attack aims to perturb the graph structure, without knowing to model parameters, model architecture, etc., such that the LPDG model makes as many wrong predicted links as possible. We design our attack based on a stochastic policy-based RL algorithm. Moreover, we evaluate our attack on three real-world graph datasets from different application domains. Experimental results show that our attack is both effective and efficient.