{"id":"da0f55de-d928-491a-a52d-0f427524daba","arxiv_id":"2412.13134","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"GSE-METP uses an LSTM-based state embedding and multi-instance DDPG training to degrade link-prediction accuracy in dynamic graphs using far fewer queries than the prior SAC attack.","lead":"The paper proposes GSE-METP, a black-box attack on link prediction in dynamic graphs that combines graph sequential embeddings with shared multi-instance reinforcement learning to cut the number of model queries and edge perturbations. A generalist should read it because query-limited, small-budget attacks are the realistic threat for deployed link-prediction services.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's own perturbation budget is not enforced: Eq. (2) changes 2T edges per action, so Table 2's '2%' corresponds to ~40% of edge slots on Haggle; the practicability claim is unsupported until the episode is rebudgeted.","rationale":"The reader's conditional correctly identifies that the practicability claim depends on unrealistic oracle access to ground-truth future edges. I focus on a narrower internal problem that is even more directly tied to the abstract's 'limited perturbations': under the action definition in Eq. (2) and the budget in Eq. (4), each episode performs 2T edge modifications per action, so Table 2's δ values do not describe the actual amount of perturbation. This is not an added assumption; it follows from the paper's own equations. It is also actionable: rerunning with K' = floor(K/(2T)) would test whether the claimed advantage survives a truly limited perturbation budget. Because this can be fixed by redefinition or re-evaluation, I keep the reader's CONDITIONAL verdict rather than rejecting, but the condition should explicitly include honest perturbation accounting. The reader's ground-truth concern remains valid; in full, the practicability claim needs both an attacker without future-label reward and a real edge budget.","tokens_in":10241,"tokens_out":14949,"duration_ms":148433,"concrete_test":"Instrument one Haggle/DyGCN attack episode with K=751: log every (u,v,t) edge addition/deletion actually applied across the T=10 snapshots and compare the total (with multiplicity) to K. Then rerun Table 2 for all methods with episode length K' = floor(K/(2T)), so that actual edge flips are capped by K, and report F1. If GSE-METP's advantage over Random shrinks or vanishes under K', the 'practicable within limited perturbations' claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Equation (2) defines one RL action as adding an edge (u,v) and deleting an edge (u',v') in every snapshot simultaneously, i.e. A'_t = A_t([u][v]=1,[u'][v']=0) for all t in [1,T]. One action therefore changes 2T adjacency entries, not one. Equation (4), however, defines the perturbation limit as K = min(δ|Emax|, n), with |Emax| = |V|^2/2, and the text says the attacker may only perturb a few edges. In the default experiments K is used as the episode length, so an episode performs 2T·K edge modifications. For Haggle (T=10, |Emax|≈37,538, K=751) that is about 15,020 modified entries, roughly 40% of |Emax|, not the reported δ=2%; for Facebook (T=10, K=1,000) it is 20,000 modified entries, not 0.2% of |Emax|. The random baseline receives the same inflated budget, so relative comparisons are unaffected, but the absolute claim of 'within a limited amount of perturbations' is not supported. If the budget is redefined as actual edge flips, K must be divided by 2T, and it is unknown whether GSE-METP remains effective.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10540,"tokens_out":5641,"duration_ms":52814,"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":[{"comment":"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.","section":"Action (Eq. 2), Eq. (4), Table 2"},{"comment":"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?","section":"Environment and reward, Eq. (3)"},{"comment":"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).","section":"Experiments (paragraph beginning 'For each setting')"},{"comment":"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.","section":"Table 2 and Figure 6"}],"minor_comments":[{"comment":"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.","section":"Eq. (4)"},{"comment":"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.","section":"Eq. (8)"},{"comment":"There is a typo: 'Sigmod' should be 'Sigmoid'.","section":"Eq. (9)"},{"comment":"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.","section":"Experiments, Attack Settings"},{"comment":"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.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper's central idea is timely and the code availability is a plus. However, the practicability claim is undercut by the budget accounting, the unstated label-access assumption, and the lack of held-out evaluation. These are fixable with additional experiments and a revised threat model, so I do not recommend rejection, but the current version requires substantial revision before the claims can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's core offer is a black-box evasion attack on dynamic-graph link prediction that works with far fewer model queries than the previous SAC baseline, using a graph sequential embedding (GSE) and a multi-environment replay buffer (METP). That is a real step forward for the subfield, and the ablation study credibly separates the contribution of each component. The comparisons to SAC and random attacks on three standard datasets are informative, and the authors are honest about SAC's impractical interaction load.\n\nWhere it gets soft is in the accounting of the perturbation budget, and the stress-test note is right. Equation (2) applies one add and one delete to every snapshot simultaneously, so a single action flips 2T entries. But K in Eq. (4) is treated as the number of actions per episode. On Haggle that turns the reported 2% edge budget into roughly 15,000 modified entries out of about 37,500 possible — around 40%, not 2%. The random baseline gets the same inflated budget, so the relative comparisons still say something, but the absolute \"limited perturbations\" claim is not supported. If you redefine the budget as actual edge flips, you have to divide K by 2T, and we don't know whether GSE-METP still beats random.\n\nThere are two other weaknesses. The reward in Eq. (3) uses the ground-truth future graph ET+1, which an attacker typically does not have; the practicability story needs an explicit defense of that assumption. And the experiments appear to train and attack on the same ten instances, with no held-out split and no error bars, so the reported F1 numbers are optimized for those exact instances. Since the headline metric is also the RL training reward, the numbers are partly an optimization artifact.\n\nNone of this is fatal to the idea. The method is plausible, the writing is clear, and the code is promised. The paper deserves a serious referee who can push for a correct budget definition, a held-out evaluation, and a discussion of the ground-truth reward. I would want to see those fixes before relying on the practicability claim, but the core attack design is worth engaging with.","headline":"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.","tokens_in":11060,"tokens_out":2511,"would_cite":false,"duration_ms":26107,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["adversarial attacks","link prediction","dynamic graphs","black-box evasion attack","reinforcement learning","graph sequential embedding","multi-environment training","DDPG"],"falsifier":"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.","tokens_in":10040,"feed_emoji":"🕸️","tokens_out":7080,"duration_ms":55567,"temperature":0.7,"pith_summary":"The paper sets out to show that black-box evasion attacks on link prediction in dynamic graphs (LPDG) can be made practicable, meaning an attacker who can only query the target model a few thousand times and perturb a limited number of edges can still substantially lower the prediction F1. Prior reinforcement-learning attacks such as SAC require millions of queries and stall on large graphs. The authors propose GSE-METP, an attack agent built from a graph sequential embedding that turns a dynamic graph sequence into a compact state for a DDPG policy, plus a multi-environment training pipeline that shares experience across several attack instances. On DyGCN, ASTGCN, and HTGN over three real datasets, they report GSE-METP achieving the lowest F1 in most settings, with particularly large gains on the largest graph.","feed_headline":"Black-box attack cracks dynamic link prediction with few queries","feed_subtitle":"A graph-embedding agent needs only thousands of model calls, not millions, to lower F1 on three predictors.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the prior SAC black-box RL attack that GSE-METP compares against and whose large interaction cost motivates the practicability goal.","marker":"Fan et al. 2021"},{"why":"Introduces deterministic policy gradient, the theoretical basis for the DDPG actor-critic framework used to learn attack actions.","marker":"Silver et al. 2014"},{"why":"Supplies the deep deterministic policy gradient algorithm that carries the agent's policy and Q-network training.","marker":"Lillicrap et al. 2015"},{"why":"Provides the LSTM architecture used in GSE to encode the dynamic graph sequence into a compact state.","marker":"Hochreiter and Schmidhuber 1997"},{"why":"Motivates the random noise feature injected into the static degree embedding to strengthen its expressiveness.","marker":"Sato, Yamada, and Kashima 2021"},{"why":"Defines DyGCN, one of the three target LPDG models evaluated under the attack.","marker":"Manessi, Rozza, and Manzo 2020"},{"why":"Defines ASTGCN, one of the three target LPDG models evaluated under the attack.","marker":"Guo et al. 2019"},{"why":"Defines HTGN, one of the three target LPDG models evaluated under the attack.","marker":"Yang et al. 2022b"}],"fun_headline_variants":["First practicable black-box evasion attack on dynamic link prediction","RL agent with graph embeddings evades dynamic link prediction in black-box","Few-query attack on dynamic graph link prediction beats SAC","Dynamic link prediction vulnerable to practical black-box evasion attack","Graph sequential reinforcement learning enables practical black-box attack"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First practicable black-box evasion attack on dynamic link prediction","RL agent with graph embeddings evades dynamic link prediction in black-box","Few-query attack on dynamic graph link prediction beats SAC","Dynamic link prediction vulnerable to practical black-box evasion attack","Graph sequential reinforcement learning enables practical black-box attack"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000283,"raw_usage":{"total_tokens":1648,"prompt_tokens":897,"completion_tokens":751,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":672}},"tokens_in":513,"tokens_out":751,"duration_ms":7517,"temperature":1.0,"reasoning_tokens":672,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:22:57.444393+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the prior SAC black-box RL attack that GSE-METP compares against and whose large interaction cost motivates the practicability goal."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the LSTM architecture used in GSE to encode the dynamic graph sequence into a compact state."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates the random noise feature injected into the static degree embedding to strengthen its expressiveness."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines DyGCN, one of the three target LPDG models evaluated under the attack."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines ASTGCN, one of the three target LPDG models evaluated under the attack."}],"review_version":1}