# Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 27 references that are in the map.
- First posted on arXiv 17 Dec 2024.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Backdoor Attacks to Graph Neural Networks](https://mlsanity.com/paper/2006.11165/) (2020)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [GraphFL: A Federated Learning Framework for Semi-Supervised Node Classification on Graphs](https://mlsanity.com/paper/2012.04187/) (2020)
- [Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [Adversarial Attack on Large Scale Graph](https://mlsanity.com/paper/2009.03488/) (2020)
- [Attacking Graph Convolutional Networks via Rewiring](https://mlsanity.com/paper/1906.03750/) (2019)
- [A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning](https://mlsanity.com/paper/1910.14147/) (2019)
- [Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networks](https://mlsanity.com/paper/2002.08012/) (2020)
- [Distributed Backdoor Attacks on Federated Graph Learning and Certified Defenses](https://mlsanity.com/paper/2407.08935/) (2024)
- [Efficient, Direct, and Restricted Black-Box Graph Evasion Attacks to Any-Layer Graph Neural Networks via Influence Function](https://mlsanity.com/paper/2009.00203/) (2020)

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

- [Unlocking Multi-Modal Potentials for Link Prediction on Dynamic Text-Attributed Graphs](https://mlsanity.com/paper/2502.19651/) (2025)
- [Backdoor Attacks on Discrete Graph Diffusion Models](https://mlsanity.com/paper/2503.06340/) (2025)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)

## Abstract (arXiv)

Link prediction in dynamic graphs (LPDG) has been widely applied to real-world applications such as website recommendation, traffic flow prediction, organizational studies, etc. These models are usually kept local and secure, with only the interactive interface restrictively available to the public. Thus, the problem of the black-box evasion attack on the LPDG model, where model interactions and data perturbations are restricted, seems to be essential and meaningful in practice. In this paper, we propose the first practicable black-box evasion attack method that achieves effective attacks against the target LPDG model, within a limited amount of interactions and perturbations. To perform effective attacks under limited perturbations, we develop a graph sequential embedding model to find the desired state embedding of the dynamic graph sequences, under a deep reinforcement learning framework. To overcome the scarcity of interactions, we design a multi-environment training pipeline and train our agent for multiple instances, by sharing an aggregate interaction buffer. Finally, we evaluate our attack against three advanced LPDG models on three real-world graph datasets of different scales and compare its performance with related methods under the interaction and perturbation constraints. Experimental results show that our attack is both effective and practicable.