REVIEW 4 major objections 5 minor 34 references
Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method
T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper claims that a black-box attacker with only a few thousand model interactions and a small perturbation budget can reliably lower the F1 of link prediction in dynamic graphs, using a graph sequential embedding trained under a…
desk verdict Query-efficient attack on dynamic-graph link prediction with a genuinely useful RL design, but the perturbation budget is miscounted and the evaluation reuses the attack instances; real promise, not yet a convincing practicability claim. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is a deep reinforcement-learning attack with two novel components. Graph Sequential Embedding (GSE) computes a static degree feature per graph snapshot from powers of the average adjacency matrix plus random noise, then feeds the sequence of degree embeddings through two LSTMs (one for the actor, one for the critic) to produce a compact state for the DDPG agent. Multi-Environment Training (METP) treats multiple target instances as parallel environments and stores their interaction experience in one aggregate replay buffer, so the policy and Q networks train on collective experience. The action at each step adds one edge and deletes one edge in every snapshot of the sequence, and the reward is the drop in the target model's F1 score computed against the ground-truth next graph.
What would settle it
Run GSE-METP on held-out graph sequences not seen during the multi-environment training, or replace the ground-truth reward with the target model's own prediction scores; if the F1 reductions disappear, the claim of practicability is falsified.
Extended reading notes
Core claim
The central claim is that GSE-METP is the first practicable black-box evasion attack on LPDG: under a perturbation cap $K=\min(\delta|E_{\max}|,n)$ and an interaction cap $I$, the learned agent degrades the target model's F1 more than random attacks and more than SAC, which is impracticable because it requires millions of interactions. The authors argue that the two designs are responsible: the graph sequential embedding provides a low-dimensional state that changes responsively under edge additions and deletions, unlike the static degree-ranking state of SAC, and the multi-environment pipeline lets a single agent learn from several instances through a shared replay buffer, overcoming the low interaction budget per instance.
Load-bearing premise
The attack's reward is computed from the ground-truth next-snapshot graph, which a real attacker generally would not know; if the agent is trained and evaluated on the same instances without that oracle, the reported F1 drops may not occur.
Editorial extensions
If this is right
- If GSE-METP works as reported, an attacker with only $I=5K$ interactions can cut the F1 of DyGCN, ASTGCN, and HTGN on Haggle, Facebook, and AS substantially below what random perturbation achieves.
- The prior SAC attack is shown to be impracticable under the same constraints: it often performs no better than random, and its state representation barely changes during the attack, while GSE-METP's state varies and adapts.
- Both components earn their place: ablations show GSE alone and METP alone each improve convergence, and removing either reduces attack effectiveness.
- Because the reward is the immediate F1 drop and the edge actions commute in effect, the Q-function can be trained as a reward predictor rather than a long-horizon value function, which suits the limited interaction budget.
- The attacker's success improves as the allowed interaction count grows, and GSE-METP converges faster than its ablations.
Reading between the lines
- Editorial inference: the practicability claim depends on the attacker knowing the ground-truth next graph to compute rewards; if those labels are unavailable, a surrogate reward would be needed and the reported F1 drops may not transfer.
- Editorial inference: because the state embedding uses only degree statistics plus random features, it may transfer across different dynamic-graph predictors, potentially seeding other RL-based attacks or defensive evaluations.
- Editorial inference: the default budget $I=5K$ already multiplies the perturbation cap by five; testing at $I=K$ or $I=2K$ would reveal the minimum query budget for a meaningful attack.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes GSE-METP, a black-box evasion attack against link prediction in dynamic graphs (LPDG), combining a graph sequential embedding (GSE) module with a multi-environment training pipeline (METP) within a DDPG reinforcement-learning framework. The attack is claimed to be the first 'practicable' black-box evasion attack for LPDG, operating under limited model interactions and edge perturbations. Experiments on Haggle, Facebook, and AS datasets against DyGCN, ASTGCN, and HTGN report lower F1 scores than random and SAC-based baselines. The authors also provide an ablation study isolating the contributions of GSE and METP.
Significance. If the claims hold, the paper would make a useful contribution to adversarial machine learning for dynamic graphs: it introduces a concrete RL-based attack design with a novel state-embedding approach and a multi-instance training mechanism, and it provides code for reproducibility. The idea of sharing experience across attack instances to overcome interaction limits is interesting and potentially transferable. However, the support for the central 'practicable' claim is currently weakened by several evaluation gaps: the perturbation budget is not enforced as defined, the reward requires access to ground-truth future labels that a black-box attacker may not have, the evaluation appears to use no held-out instances, and no error bars are reported. These issues make the quantitative superiority claims less convincing than they appear at first sight.
major comments (4)
- [Action (Eq. 2), Eq. (4), Table 2] The perturbation budget is not enforced as defined. Equation (2) defines one action as adding one edge and deleting one edge in every snapshot simultaneously, i.e., 2T adjacency entries are modified per action. Equation (4) defines K as the perturbation limit, but the experiments use K as the episode length. Thus the total number of edge modifications is 2T·K, not K. For the default settings in Table 2, this means Haggle's reported δ=2% corresponds to approximately 15,020 changed entries, about 40% of |Emax|, and Facebook's δ=0.2% corresponds to 20,000 entries, about 4% of |Emax|. The absolute claim of 'within a limited amount of perturbations' is therefore not supported by the reported numbers. The authors should either redefine the budget as the actual number of edge flips (dividing the episode length by 2T) or clearly state that K counts actions rather than perturbed entries, and then re-evaluate whether the attack remains effective under the stricter interpretation.
- [Environment and reward, Eq. (3)] The reward in Eq. (3) is computed by comparing the target model's prediction with the ground-truth future graph E_{T+1}. In the black-box setting described in the Problem Definition, the attacker only has access to the model's prediction interface and does not necessarily have access to the true next-snapshot graph. The paper does not state that the attacker knows E_{T+1} or justify how the reward signal would be obtained in practice. Without such an assumption, the reported F1 drops are an optimized objective rather than an independent measure of a practicable attack. Please clarify the threat model: is the attacker assumed to know the future ground-truth edges, and if so, is this a realistic assumption for the intended applications?
- [Experiments (paragraph beginning 'For each setting')] The evaluation protocol appears to use the same 10 instances both for training the target model and for running the attack. The text says 'We use these instances to train the target model M, and apply the attack method C to perform a black-box attack' but does not describe any held-out split. If the target model is trained and evaluated on the same instances, the reported results may reflect overfitting to the training instances of the target model and do not demonstrate that the attack transfers to unseen dynamic graph sequences. Please evaluate on held-out instances (for example, train the target on a subset and attack on the remainder, or explicitly report performance on a separate test split).
- [Table 2 and Figure 6] No error bars, confidence intervals, or repeated-run statistics are reported. Several comparisons in Table 2 show very small differences (e.g., Haggle/DyGCN: GSE-METP 0.8118 vs. SAC-METP 0.8094, and Facebook/DyGCN: GSE-METP 0.9653 vs. SAC-METP 0.9651). Given the stochasticity inherent to RL training and random graph sampling, these differences may be within run-to-run noise. Please report means and standard deviations over multiple seeds, and state the number of runs used to produce the reported values.
minor comments (5)
- [Eq. (4)] The formula |Emax| = |V|^2/2 overcounts the maximum number of edges in an undirected graph without self-loops; the correct value is |V|(|V|-1)/2. This affects the numeric values of K and the reported perturbation ratios.
- [Eq. (8)] The LSTM equations are not fully defined: the variables i_t, f_t, g_t, o_t are used but their dimensions and the exact forms of L_i and L_h are unclear. Please rewrite with standard LSTM notation or a citation to a standard formulation.
- [Eq. (9)] There is a typo: 'Sigmod' should be 'Sigmoid'.
- [Experiments, Attack Settings] For the AS dataset, the binding constraint is n=1000 rather than δ=4.8e-5, which makes the reported δ misleading. Please clarify which constraint is active in each configuration and why those particular values were chosen.
- [General] The paper does not provide training hyperparameters (learning rate, batch size, replay buffer size, exploration schedule, number of random exploration steps). The code link is helpful, but the manuscript should include these details in an appendix or supplementary material for reproducibility.
Circularity Check
No significant circularity: the attack's effectiveness is measured against external baselines; reward and metric coincide as the RL objective, not as a derived prediction.
full rationale
The paper is an empirical black-box attack paper, not a formal derivation. Its central claims (GSE-METP is practicable and effective under interaction/perturbation constraints) are supported by direct comparisons against Random, SAC, SAC-METP and GSE baselines on three datasets and three LPDG models. The GSE embedding and METP training are presented as design choices, with METP's similarity assumption explicitly labeled a hypothesis; neither is derived from the attack result. The RL reward in Eq. (3) is the same F1-difference objective being optimized, so Table 2 reports the optimized objective; in an RL attack paper this is the standard evaluation of the learned policy, not a circular derivation. No load-bearing step reduces to a self-citation: citations to the authors' prior work (e.g., Wang et al. 2024) appear in related work but are not invoked to justify the attack's effectiveness or to forbid alternatives. The perturbation-budget undercount (Eq. (2) changes 2T edge entries per action, while Eq. (4) counts actions) is a validity concern about the 'limited perturbations' claim, but it is a factual/budgeting issue, not a circularity. Accordingly, no circular steps are flagged.
Assumptions & free parameters
free parameters (3)
- delta (edge ratio limit) =
0.02 (default)
- n (edge amount limit) =
1000 (default)
- I (interaction limit) =
5K (default)
assumptions (2)
- domain assumption Instances from the same dataset and the same target model share similarities that allow training experience to be transferred.
- domain assumption The attacker has access to the ground-truth future graph ET+1 to compute rewards.
Cite this review
Pith. "Pith review of Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method." pith.science (2026). https://pith.science/paper/LTJ3DYI2
@misc{pith2026241213134,
author = {Pith},
title = {Pith review of: Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method},
year = {2026},
howpublished = {\url{https://pith.science/paper/LTJ3DYI2}},
note = {Machine review of arXiv:2412.13134}
}
read the original abstract
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.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Dai, H.; Li, H.; Tian, T.; and more. 2018. Adversarial attack on graph structured data. In ICML
work page 2018
-
[2]
Fan, H.; Wang, B.; Zhou, P.; and et al. 2021. Reinforcement learning-based black-box evasion attacks to link prediction in dynamic graphs. In IEEE HPCC
work page 2021
-
[3]
Goyal, P.; Kamra, N.; He, X.; and Liu, Y . 2018. DynGEM: Deep Embedding Method for Dynamic Graphs. CoRR
work page 2018
-
[4]
Guo, S.; Lin, Y .; Feng, N.; Song, C.; and Wan, H. 2019. At- tention Based Spatial-Temporal Graph Convolutional Net- works for Traffic Flow Forecasting.AAAI, 33(01): 922–929
work page 2019
-
[5]
Haarnoja, T.; Zhou, A.; Abbeel, P.; and Levine, S. 2018. Soft actor-critic: Off-policy maximum entropy deep reinforce- ment learning with a stochastic actor. In ICML
work page 2018
-
[6]
Hochreiter, S.; and Schmidhuber, J. 1997. Long Short-Term Memory. Neural Computation, 9(8): 1735–1780
work page 1997
-
[7]
Kunegis, J. 2013. KONECT: The Koblenz Network Collec- tion. In WWW Companion
work page 2013
-
[8]
Leskovec, J.; and Sosiˇc, R. 2016. SNAP: A General-Purpose Network Analysis and Graph-Mining Library. ACM TIST
work page 2016
Show all 34 references
-
[9]
Li, J.; Xie, T.; Chen, L.; Xie, F.; He, X.; and Zheng, Z. 2021. Adversarial attack on large scale graph. IEEE TKDE
2021
-
[10]
Tassa, Y .; Silver, D.; and Wierstra, D. 2015. Continuous control with deep reinforcement learning. arXiv
2015
-
[11]
Liu, X.; Si, S.; Zhu, X.; Li, Y .; and Hsieh, C.-J. 2019. A unified framework for data poisoning attack to graph-based semi-supervised learning. In NeurIPS
2019
-
[12]
Ma, J.; Ding, S.; and Mei, Q. 2020. Towards More Prac- tical Adversarial Attacks on Graph Neural Networks. In NeurIPS
2020
-
[13]
Ma, Y .; Wang, S.; Derr, T.; Wu, L.; and Tang, J. 2019. At- tacking graph convolutional networks via rewiring. arXiv
2019
-
[14]
Manessi, F.; Rozza, A.; and Manzo, M. 2020. Dynamic graph convolutional networks. Pattern Recognition
2020
-
[15]
Mu, J.; Wang, B.; Li, Q.; Sun, K.; Xu, M.; and Liu, Z. 2021. A Hard Label Black-box Adversarial Attack to Graph Neu- ral Networks. In CCS
2021
-
[16]
Pareja, A.; Domeniconi, G.; Chen, J.; Ma, T.; Suzumura, T.; Kanezashi, H.; Kaler, T.; and Leiserson, C. E. 2019. EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. CoRR, abs/1902.10191
2019 arXiv
-
[17]
Sato, R.; Yamada, M.; and Kashima, H. 2021. Random fea- tures strengthen graph neural networks. In SIAM SDM
2021
-
[18]
Schulman, J.; Levine, S.; Abbeel, P.; Jordan, M.; and Moritz, P. 2015. Trust region policy optimization. In ICML
2015
-
[19]
Klimov, O. 2017. Proximal policy optimization algorithms. arXiv
2017
-
[20]
Riedmiller, M. 2014. Deterministic Policy Gradient Algo- rithms. In ICML
2014
-
[21]
Sun, Y .; Wang, S.; Tang, X.; Hsieh, T.-Y .; and Honavar, V . 2020. Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learn- ing Approach. In The Web Conference
2020
-
[22]
Takahashi, T. 2019. Indirect Adversarial Attacks via Poison- ing Neighbors for Graph Convolutional Networks. In BD
2019
-
[23]
Wang, B.; and Gong, N. 2019. Attacking Graph-based Clas- sification via Manipulating the Graph Structure. In CCS
2019
-
[24]
Wang, B.; Jia, J.; Cao, X.; and Gong, N. Z. 2021. Certi- fied robustness of graph neural networks against adversarial structural perturbation. In KDD
2021
-
[25]
Wang, B.; Li, A.; Pang, M.; Li, H.; and Chen, Y . 2022. Graphfl: A federated learning framework for semi- supervised node classification on graphs. In ICDM
2022
-
[26]
Wang, B.; Li, Y .; and Zhou, P. 2022. Bandits for Black-box Attacks to Graph Neural Networks with Structure Perturba- tion. In CVPR
2022
-
[27]
Li, H.; and Chen, Y . 2024. Efficient, direct, and restricted black-box graph evasion attacks to any-layer graph neural networks via influence function. In WSDM
2024
-
[28]
Wang, B.; Pang, M.; and Dong, Y . 2023. Turning strengths into weaknesses: A certified robustness inspired attack framework against graph neural networks. In CVPR
2023
-
[29]
Zhu, L. 2019. Adversarial examples on graph data: Deep insights into attack and defense. In IJCAI
2019
-
[30]
Xia, Z.; Yang, H.; Wang, B.; Jia, J.; et al. 2024. GN- NCert: Deterministic Certification of Graph Neural Net- works against Adversarial Perturbations. In ICLR
2024
-
[31]
Xu, K.; Chen, H.; Liu, S.; and more. 2019. Topology attack and defense for graph neural networks: An optimization per- spective. In IJCAI
2019
-
[32]
Yang, Y .; Li, Q.; Jia, J.; Hong, Y .; and Wang, B. 2024. Dis- tributed backdoor attacks on federated graph learning and certified defenses. In CCS
2024
-
[33]
Zhang, Z.; Jia, J.; Wang, B.; and Gong, N. 2021. Backdoor attacks to graph neural networks. SACMAT
2021
-
[34]
Zhou, L.; Yang, Y .; Ren, X.; Wu, F.; and Zhuang, Y . 2018. Dynamic Network Embedding by Modeling Triadic Closure Process. In AAAI. Z¨ugner, D.; and G ¨unnemann, S. 2019. Adversarial attacks on graph neural networks via meta learning. In ICLR
2018
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.