Research map / Graph learning / Knowledge and temporal graphs
Practicable Black-Box Evasion Attacks on Link Prediction in Dynamic Graphs—a Graph Sequential Embedding Method
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GSE-METP, a black-box evasion attack on link prediction in dynamic graphs that combines a graph sequential embedding (static degree features plus two LSTMs) with DDPG and a multi-environment training pipeline sharing one replay buffer across instances.
Problem
Black-box evasion attacks on link prediction in dynamic graphs (LPDG) under practical limits on model queries (interactions) and edge perturbations; prior RL attack SAC needs millions of interactions and fails on large graphs.
Approach
Embeds each graph in the sequence with static multi-hop degree features, encodes the sequence with two LSTMs (actor and critic), and trains one DDPG agent across multiple instances from the same dataset and model with a shared replay buffer to cope with scarce interactions.
Key results
- On Haggle with DyGCN, GSE-METP and GSE reduce F1 from 0.9930 to 0.8118 and 0.8043 under 2% edge ratio and 3755 interactions, versus 0.8979 for random and 0.8149 for SAC.
- On AS with HTGN, GSE-METP lowers F1 from 0.8665 to 0.7649, versus 0.8377 for random and 0.8526 for SAC.
- On AS with ASTGCN, GSE-METP reaches F1 0.8020 from 0.8303 original, outperforming SAC (0.8264) and random (0.8276).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GSE-METP instead of the strongest baseline attack | DyGCN · AS | F1: 0.8899 -> 0.8573 | Helped |
| Use GSE-METP instead of the strongest baseline attack | ASTGCN · Facebook | F1: 0.9298 -> 0.9011 | Helped |
| Use GSE-METP instead of the strongest baseline attack | HTGN · Haggle | F1: 0.8083 -> 0.7417 | Helped |
| Add multi-environment training (METP) to GSE (ablation) | GSE attack · DyGCN, ASTGCN, and HTGN; Haggle, Facebook, and AS | F1: DyGCN Haggle: 0.8043 -> 0.8118; DyGCN Facebook: 0.9629 -> 0.9653; DyGCN AS: 0.8910 -> 0.8573 | Mixed |
| Add graph sequential embedding (GSE) instead of the SAC graph embedding (ablation) | METP attack · DyGCN, ASTGCN, and HTGN; Haggle, Facebook, and AS | F1: DyGCN AS: 0.8890 -> 0.8573; ASTGCN AS: 0.8263 -> 0.8020; HTGN AS: 0.8527 -> 0.7649 | Mixed |
Surprising findings
- SAC performs close to or worse than random attack under interaction and perturbation constraints, with its action variance collapsing during attack.
- Several SAC-based variants show F1 on HTGN Haggle (0.9603) barely below original (0.9753), indicating weak attack effect.
Limitations
- Attack evaluated only on three LPDG models and three datasets with simple random edge deletion for dynamic sequences.
- Random attack is a strong baseline in several settings; gains are inconsistent (e.g., GSE-METP worse than GSE on Haggle for DyGCN).
Experimental setup
Datasets: Haggle Facebook (SNAP social circles subgraph) AS-733
Benchmarks: Haggle Facebook AS-733
Metrics: F1 score
Baselines: Random attack SAC attack SAC-METP attack GSE attack
Builds on: DDPG SAC (black-box graph attack) LSTM
Closest papers by meaning
- Spear and Shield: Adversarial Attacks and Defense Methods for Model-Based Link Prediction on Continuous-Time Dynamic Graphs (AAAI 2024 · similarity 0.87)
- Let Graph Be the Go Board: Gradient-Free Node Injection Attack for Graph Neural Networks via Reinforcement Learning (AAAI 2023 · similarity 0.87)
- Highly Imperceptible Black-Box Graph Injection Attacks with Reinforcement Learning (AAAI 2025 · similarity 0.85)
- Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks (AAAI 2024 · similarity 0.84)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.84)
- TGB-Seq Benchmark: Challenging Temporal GNNs with Complex Sequential Dynamics (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.