Graph neural networks (GNNs) have emerged as powerful tools for modeling dynamic graphs, yet their vulnerability to adversarial attacks remains underexplored. Existing attack methods on dynamic graphs lack explicit mechanisms to incorporate temporal importance into perturbation allocation. We propose TIDGA (Temporal Importance-aware Dynamic Graph Attack), a novel framework that incorporates temporal importance weighting to guide perturbation placement on discrete-time dynamic GNNs. TIDGA introduces two weighting mechanisms: (1) temporal position weight ( ), which prioritizes earlier snapshots based on the intuition that early perturbations have more time to propagate through subsequent snapshots, and (2) edge persistence factor ( ), which measures structural stability using Jaccard similarity. We evaluate TIDGA on three benchmark datasets, and the results demonstrate that TIDGA achieves statistically significant improvement over the comparative methods.
Graph-structured data has become ubiquitous across numerous domains, and Graph Neural Networks
(GNNs) have emerged as a powerful paradigm for learning from such data [
Despite their efectiveness, GNNs are vulnerable to adversarial perturbations [
Understanding this vulnerability is practically important: in safety-critical deployments such as fraud detection and social network monitoring, adversaries may manipulate historical interaction patterns to evade detection. Adversarial evaluation serves as a red-teaming tool for assessing model reliability before deployment, and studying efective perturbation strategies reveals which temporal patterns dynamic GNNs rely on, informing more robust architecture design.
Adversarial perturbations on dynamic graphs can be viewed as a form of graph transformation, where deliberate structural modifications to edge sets across temporal snapshots are designed to maximally degrade model prediction performance. By studying how such transformations propagate through sequential architectures, we gain insights into the sensitivity of dynamic GNNs to structural changes at diferent temporal positions.
We propose TIDGA (Temporal Importance-aware Dynamic Graph Attack), a framework that weights perturbations based on their temporal significance. Our contributions are as follows: • Temporal importance weighting mechanism that integrates two components: (1) temporal position weight, which prioritizes perturbations at earlier snapshots where they propagate through more subsequent computations, and (2) edge persistence factor, which considers edge stability across snapshots. • Empirical analysis across three datasets and two victim model architectures, identifying that temporal weighting improves attack efectiveness on dense graphs with parameter-evolving architectures.
The rest of this paper is organized as follows. Section 2 introduces the preliminary definitions. Section 3 surveys the related studies. Section 4 presents the proposed method. We evaluate the performance in Section 5, followed by the results and discussions in Section 6. Section 7 concludes this paper.
Definition 1 (Discrete-Time Dynamic Graph). A discrete-time dynamic graph is an ordered sequence of graph snapshots = {1, 2, . . . , }, where each snapshot = (, ) consists of a node set and adjacency matrix .
Let {′1, ′2, . . . , ′ } denote the perturbed snapshots.
Definition 2 (Adversarial Attack on Dynamic Graphs). Let ℳ be a victim dynamic GNN and its
embedding function that generates node embeddings of given 1:−1 . Let be the ground-truth
labels for a given task (for link prediction, these correspond to binary labels representing link existence
at timestep ). The attacker aims to introduce structural perturbations = ′ − at each timestep
< such that model inference at timestep for the target edges deteriorates. Following [
max ′1,′2,...,′ −1 subject to ℒ(^( (′1: −1 )), , ) ∑︁ ‖′ − ‖0 ≤ (1) where ^ is the predicted labels, ℒ is a task-specific loss (binary cross-entropy for link prediction), and is the perturbation budget.
Dynamic Graph Neural Networks. Several architectures combine graph convolution with temporal
modeling for discrete-time dynamic graphs. EvolveGCN [
Adversarial Attacks on Graphs. For static GNNs, NETTACK [
Practical Attack Scenarios. Adversarial attacks on dynamic GNNs are practically relevant in
settings where adversaries can manipulate interactions over time. In fraud detection, adversaries may
alter transaction patterns across time periods to evade GNN-based detectors [
In discrete-time dynamic graphs, GNN models process graph snapshots sequentially, updating node representations at each timestep based on both current graph structure and previous hidden states. This sequential processing creates an asymmetry: perturbations introduced at earlier snapshots influence more subsequent computations than those at later snapshots. We design a weighting mechanism that exploits this temporal asymmetry.
Temporal Position Weight. We define () to prioritize perturbations at earlier snapshots: () = ︂( − )︂ × exp(−) (2) where is the sequence length and controls the decay rate. The linear term ( − )/ captures propagation opportunity: a perturbation at timestep can influence ( − ) subsequent snapshots before reaching the prediction target. The exponential term exp(−) models propagation attenuation: as information flows through sequential layers, its influence diminishes due to normalization operations and non-linear activations. Together, these terms estimate the efective impact of perturbations based on their temporal position.
We note that this prioritization is motivated by the sequential processing of recurrent architectures: perturbations at earlier timesteps pass through more recurrent updates before reaching the prediction target at , creating greater opportunity for cumulative influence on learned representations.
Edge Persistence Factor. Beyond temporal position, we consider structural stability. Edges that persist across multiple snapshots are more deeply encoded in learned representations, as the model repeatedly observes and reinforces these patterns. We quantify persistence using Jaccard similarity between consecutive edge sets: () =
1 ∑︁ (, +), (, ) = | ∩ | =1 | ∪ | (3) where is the lookahead window. Higher () indicates that edges at snapshot tend to persist, suggesting perturbations at this snapshot target more stable, and thus more impactful, structural patterns.
Combined Weight. The temporal importance weight integrates both factors: (4) (5)
Normalization. We apply () as a learning rate multiplier during gradient-based perturbation optimization. To preserve overall optimization dynamics, we normalize by the mean: () = () × () ˜ () = () ¯ , where ¯ = 1 ∑︁ ( ) =1 This ensures the average multiplier equals 1: snapshots with above-average importance receive amplified updates (˜ () > 1), while below-average snapshots receive dampened updates (˜ () < 1). The total learning capacity is preserved while redistributing emphasis toward temporally significant snapshots.
TIDGA optimizes the perturbation matrix initialized to ones. At each iteration, gradients are weighted by temporal importance: ← + × ˜ () × ∇ ℒ (6) where is the learning rate. The normalized weight ˜ () functions as a per-snapshot learning rate multiplier, making the efective learning rate × ˜ () for each snapshot. For earlier snapshots where ˜ () > 1 , gradient updates are amplified, causing perturbation scores to increase more rapidly.
After each update, the perturbation matrix is projected onto the feasible set. When ∑︀ [
Datasets. We evaluate on three datasets with varying characteristics, following the preprocessing
protocol of Sharma et al. [
Victim Models. Two discrete-time dynamic GNN architectures serve as targets: EvolveGCN-O [
Training Protocol. Both victim models are trained on clean graph snapshots from timesteps 1 to
− 1 for link prediction at timestep , following the configuration of Sharma et al. [
Task and Evaluation Protocol. We target link prediction at the final timestep , where the model predicts edge existence based on learned node embeddings. Attack efectiveness is measured by relative drop:
Rel. Drop = AUCattacked − AUC clean × 100%
AUCclean (7) where larger negative values indicate more efective attacks.
Baselines. TIDGA is compared against four methods: (1) Random—uniform random perturbation
selection serving as lower bound; (2) Degree—targeting edges connected to high-degree nodes based
on structural importance heuristic; (3) TGA-Greedy [
Configuration. Attack budgets ∈ {5, 10, 20, 50} are tested with 50 optimization iterations using
Adam optimizer [
Computational Overhead. TIDGA adds negligible per-iteration overhead compared to TD-PGD, as temporal weighting involves only element-wise multiplication with precomputed weights; the one-time preprocessing for Jaccard similarities is ( × × ||).
Radoslaw-EvolveGCN-O. TIDGA achieves the best performance among all attack methods, including Random, Degree heuristic, TGA, and TD-PGD. PGD-based methods (TIDGA and TD-PGD) substantially outperform other approaches—at budget=50, TIDGA achieves −60.10% relative drop compared to TGA’s −19.29% and Random’s −9.62% . Among PGD-based methods, TIDGA outperforms TDPGD with margins of 1.17% (budget=5) to 6.10% (budget=50), with statistical significance confirmed (Wilcoxon signed-rank, -value = 3.05e-5). The improvement magnitude increases with budget size, suggesting temporal weighting becomes more efective when more perturbations are available for strategic allocation. This configuration combines favorable conditions: dense graph structure ensuring substantial gradient flow, short sequence (13 snapshots) where gradient vanishing remains manageable, and EvolveGCN-O’s parameter-evolving architecture.
Radoslaw-GCLSTM. TIDGA’s efectiveness diminishes on GC-LSTM architecture. While PGD-based methods still outperform other approaches (TIDGA: −15.79% vs TGA: −2.11% at budget=50), TIDGA shows marginally lower efectiveness than TD-PGD with diferences of 0.34–1.38%. GC-LSTM integrates graph convolution within LSTM gates operating on embeddings rather than evolving weights. Consequently, perturbations at early snapshots do not accumulate influence through the same propagation mechanism, reducing temporal weighting benefit.
UCI Dataset. On EvolveGCN-O, TIDGA and TD-PGD achieve comparable performance, both substantially outperforming other baselines (PGD-based: > 60% drop vs TGA: < 53%). Non-monotonic behavior occurs at budget=20, where both methods underperform compared to adjacent budgets, indicating convergence to local optima due to UCI’s intermediate density creating a complex loss landscape. On GC-LSTM, TIDGA shows reduced efectiveness compared to TD-PGD, consistent with the pattern observed on Radoslaw.
Reddit Dataset. On EvolveGCN-O, TIDGA underperforms TD-PGD by 0.61–1.78%, a diference confirmed as statistically significant (Wilcoxon signed-rank, < 0.001). On GC-LSTM, TIDGA shows substantially reduced efectiveness across all budgets, with the gap widening at higher budgets ( −3.23% vs −6.48% at budget=50). This represents the least favorable configuration for TIDGA.
boosting early timesteps where gradients indicate lower attack efectiveness. Since actual perturbation placement is determined by gradient magnitudes after weighting, TIDGA’s intervention becomes counterproductive when the optimization landscape favors late timesteps. On Radoslaw, gradients favor early timesteps, so temporal weighting successfully reinforces this direction.
Architectural Vulnerability Analysis. The consistent performance gap between EvolveGCN-O and GC-LSTM reveals fundamental architectural diferences. EvolveGCN-O evolves weight matrices through aLcScTuMmurelactuerirneflunecnec(eth(r)ou=ghLSthTeMw(eig−1ht ,evol(−1u)ti)o)n,ccrheaaitnin. gInaccoanstcraadstin,GgCefe-LctSTwMheorpeeeraartleys preecruturrrebnactieoonns node embeddings (ℎ = LSTM(GCN(, ), ℎ−1 )) with fixed parameters across timesteps, limiting temporal accumulation of perturbation efects and explaining why temporal weighting provides minimal benefit regardless of dataset.
We conduct ablation on Radoslaw with EvolveGCN-O, comparing TIDGA- (temporal position only) and TIDGA- (edge persistence only). At budget=50, TIDGA- achieves −60.56% versus −54.45% for TIDGA- , confirming that temporal position weight contributes more substantially. Figure 4 summarizes the results.
TIDGA improves attack efectiveness when two conditions are satisfied: (1) the victim model employs recurrent architecture that evolves model parameters across snapshots (EvolveGCN-O), and (2) gradient magnitudes remain distributed across multiple snapshots rather than concentrated at specific timesteps. When both conditions are met, TIDGA achieves statistically significant improvement over TD-PGD. When either condition is violated, TD-PGD maintains equal or superior performance. Across all configurations, both PGD-based methods substantially outperform heuristic baselines by 20–50 percentage points.
This work proposed TIDGA, a temporal importance-aware adversarial attack framework for discretetime dynamic graph neural networks. By incorporating temporal position weight () and edge persistence factor () as learning rate multipliers during gradient-based optimization, TIDGA guides perturbation allocation toward temporally strategic positions.
Experimental results demonstrate that TIDGA achieves the best performance among all attack methods on EvolveGCN-O with dense graphs (Radoslaw), outperforming TD-PGD by margins reaching 6.10% at higher budgets. TIDGA is efective when gradient magnitudes are balanced across snapshots, allowing temporal weighting to meaningfully redistribute optimization emphasis. However, TD-PGD outperforms TIDGA on GC-LSTM, where the architecture limits temporal propagation and gradient magnitudes concentrate at later snapshots, diminishing the efect of weighting at earlier timesteps. Ablation studies reveal that temporal position weight () contributes more significantly than edge persistence factor () , indicating that perturbation timing is more critical than structural stability for attack efectiveness. The key insight is that ˜ () operates as a learning rate multiplier rather than budget enforcement—efective only when gradients at early timesteps remain substantial enough to amplify.
These findings reveal that dynamic GNNs with recurrent weight propagation are particularly vulnerable to temporally-aware attacks under favorable conditions. Our evaluation is limited to small-tomedium graphs and link prediction; future work includes scaling to larger graphs, extending to tasks such as node classification, and exploring adaptive weighting strategies that learn temporal importance from gradient distributions.
This paper is based on results obtained from the project, "Research and Development Project of the Enhanced infrastructures for Post-5G Information and Communication Systems" (JPNP20017), commissioned by the New Energy and Industrial Technology Development Organization (NEDO), JST CREST Grant Number JPMJCR22M2, and JSPS KAKENHI Grant Number JP23K24949.
The authors have not employed any Generative AI tools.