Temporal Dynamics Aware Adversarial Attacks On Discrete-Time Graph Models
Authors: Kartik Sharma
Rakshit Trivedi
Rohit Sridhar
Srijan Kumar
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Dynamic Graphs
Adversarial Attacks
Evolution-preserving

Abstract: Real-world graphs such as social networks, communication networks, and rating networks are constantly evolving over time. Many architectures have been developed to learn effective node representations using both graph structure and its dynamics. While the robustness of static graph models is well-studied, the vulnerability of the dynamic graph models to adversarial attacks is underexplored. In this work, we design a novel adversarial attack on discrete-time dynamic graph models where we desire to perturb the input graph sequence in a manner that preserves the temporal dynamics of the graph. To this end, we motivate a novel Temporal Dynamics-Aware Perturbation (TDAP) constraint, which ensures that perturbations introduced at each time step are restricted to only a small fraction of the number of changes in the graph since the previous time step. We present a theoretically-grounded Projected Gradient Descent approach for dynamic graphs to find the effective perturbations under the TDAP constraint. Experiments on two tasks — dynamic link prediction and node classification, show that our approach is up to 4x more effective than the baseline methods for attacking these models. We also consider the practical online setting where graph snapshots become available in real-time and extend our attack approach to use Online Gradient Descent for performing attacks under the TDAP constraint. In this more challenging setting, we demonstrate that our method achieves upto 5x superior performance when compared to representative baselines.

Under review as a conference paper at ICLR 2023
TEMPORAL DYNAMICS AWARE ADVERSARIAL ATTACKS ON DISCRETE- GRAPH MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Real-world graphs such as social networks, communication networks, and rating networks are constantly evolving over time. Many architectures have been de- veloped to learn effective node representations using both graph structure and its dynamics. While the robustness of static graph models well-studied, the vul- nerability of the dynamic graph models to adversarial attacks is underexplored. In this work, we design a novel adversarial attack on discrete-time dynamic graph models where preserves the temporal dynamics of the graph. To this end, we motivate a novel Temporal Dynamics-Awan Aware Perturbation (TDAP) constraint, which ensures that perturbations introduced at each time step are restricted to only a small fraction of the number of changes in the graph since the previous time step. We present iieoreticalllygroundde
desire to perturb the input graph sequence in manner that
Projected Gradient Descent approach for dynamic graphs find the effective perturbations under the TDAP constraint. Experiments on two tasks dynamic link prediction and node classification, show that our approach is up to 4x more effective than the baseline methods for attacking these models. We also consider the practical online setting where graph snapshots become available in real-time and extend our attack approach to use Online Gradient Descent for performing attacks under the TDAP constraint. In this more challenging setting, we demonstrate that our method achieves up to 5x superior performance when compared to representative baselines.
INTRODUCTION
Graph Neural Networks (GNNs) have been shown to be vuinerable to adversarial perturbations
(Jin et al. 2020 Bojchevski & Günneemann 2019 Dai et al. 2018 Wu et al. 2019 Zügner et al., 2018 Ma et al. 2020a). This has raised major concerns against their use important industrial applications such as friend/product recommendation (Ying et al. 2018 Sankar et al. 2021 Tang let al. 2020) and fraud detection (Zhao et al.) [021] Hooi et al. (017). However, these advancements in designing attack and defense mechanisms have predominantly focused on GNN models for static, non-evolving graphs In reality, the graph structure evolves with time new interactions happen and new connections are formed (Leskovec et al.) 2007 Kossinets & Watts 2006). GNN models that incorporate the temporal information are shown to outperform their static counterparts in modeling dynamic networks on tasks such as predicting link existence in the future (Kzemi et al, 2020
Pareja al. 2020; Sankar et al. 2020 Goyal et al. 2018 Chen al. 2018).
However, the vulnerability of dynamic graph models to adversarial perturbations is less studied.
The design of adversarial attacks for dynamic graphs is challenging for two reasons - (1) Attacks must simultaneously optimize both the edge(s) to perturb and when to perturb them, and more importantly, (2) Attacks must preserve the original graph evolution after perturbation order to be less detectable. Attacks that disturb original graph evolution are not desired since they can be detected as anomalies by defense mechanisms, c.g. graph anomaly detection methods (Akoglu et al.) 2015 Bunke et al.] 2007 Cai et al. 2021). Therefore, it is erucial to formulate adversarial attacks over snapshots such that they do not significantly alter the original change in the graph structure.
In this work, we introduce novel Temporal Dynamics-Aware Perturbation (TDAP) constraint to formulate vollution-preserviii attacks on discrete- timettt-tmeeeee dynamic graphs. This constraint asserts that the number of modifications added the current timestep should only be small fraction of

---

Under review as a conference paper at ICLR 2023
Method
Dynamie
White-box
Evasion
Targeted
TDAP
Online
PGD Xuu et al.
201
IG-JSMA (Xu et al.
2019b
Fan et al. Fan el al. 2020
Dyn- aan-Backoor [Chen
2021a
TGA (Chen et al. 20211
TD-PGD (proposed)
Table 1: Comparison of our attack with existing works on graph adversarial attacks. Note that an attack is TDAP if the perturbations made are aware the temporal dynamics.
the actual number of changes with respect the preceding timestep. We show theoretically that perturbations made under TDAP constraint preserves the rate of change both in the structural and the embedding spaces. To find effective attacks under this proposed constraint, we consider a targeted, white-box, and evasion setting. As noted in [ no prior works exist that can find attacks under our novel setting. Thus, we present a Gradient Descent (TD-PGD) approach. The locality of the constraint in time allows extend this approach to find attacks in a more practical online setting (Mladenovic et al. 2021) that has not been studied before for dynamic graphs. Here, perturbations found in real-time without any knowledge of the future snapshots. Our contributions can be summarized as follows:
prreticaall-groundde Temporal Dynamics-awe aware Projected
easily
1. We introduce novel Temporal Dynamics-Aware Perturbation (TDAP) constraint to make per- turbations in discrete-time dynamic graphs that preserves the evolution of the graphs.
We present a poooreiiclly-groundee PGD-based white-box attack to find effective attacks on dynamic graphs under the novel TDAP constraint in both offline and online settings.
We show that TD-PGD outperforms the baselines across different datasets and victim models on both dynamic link prediction and node classification tasks.
We test the attacks on dynamic graphs in a novel online setting and show that the online version of TD-PGD shows improved performance over existing baselines.
RELATED WORK
Representation Learning for Dynamic Graphs. GNNs have been combined with sequential mod-
eling architectures (Kazemi et al.) 2020) to model dynamic graphs. For instance, discrete-time
graphs have been modeled by using GNNs and RNNs together in pipeline (Narayan & Roe 2018
Manessi et al. 2020) or an embedded manner (Chen et al. 2008 Pareja et al. 2020 Attention- models have also been proposed to jointly encode the graph structure and its dynamics (Sankar al.)
2020 For continuous toe graphs, both RNN (Kumar et al.
2019 Trivedi et al., 2017;22199 Ma
Xu et al.] 2020) have been proposed such that embeddings are updated in real time upon an occurrence of new event.
al. 2020bb and attention-base based models (Rossi et al. 2020
Adversarial attacks on graphs. Static GNNs known be vulnerable to adversarial attacks in different settings (Jin et al. 2020). White-box attacks are studied assuming complete knowledge of the underlying model Wu et al. (2019): Xu et al. (201 9b). Limiting the model knowledge, gray-box ZZügner et al. 2018) and black-box attacks (Dai et al. 2018) have also been proposed. In com- parison, the literature Attack (TGA) (Chen et al., 2021b) is white-box evasion attack that greedily selects the perturba- tions across time under a budget constraint. In addition, attacks to poison training data (Chen al., 202 and black-box attacks using RI approaches (Fan et al. (020) have also been proposed.
adversarial attacks for dynamic graphs scarce. Time-aware Gradient
Imperceptible perturbations. The most common strategy formulate imperceptible attacks on graphs is to bound the total number of perturbations. In the case of dynamic graphs, perturbations must preserve the temporal flow to be imperceptible. Traditional anomaly detection algorithms flag an instance to be anomalous if distance between consecutive snapshots crosses threshold (Akoglu et al. 2015). In particular, Graph Edit Distance and Hamming distance between adjacency matrices have been used monitor communication networks (Shoubridge et al. 2002; Bunke et al.
2007]. Neural approaches have looked at the consecutive change in the embedding space to detect anomalies without feature extraction (Goyal et al. 2018 Cai al. 2021
2

---

Under review as a conference paper at ICLR 2023
3 METHODOLOGY
Problem Let 92. .r be the original graph snapshots and G..g2...,, , be the correspond- ing perturbed snapshots. Note that 9; = (A) where A, are the node features and the adjacency matrix for snapshot i, respectively. Also, let M be a victim dynamic graph model that we want to attack and let fM a function that generates the corresponding node embeddings of G, given -1:-1- Let Ptask be the actual labels for given task (for dynamic link prediction, these correspond to binary labels representing link existence in the future snapshot).
Then, the objective of the attacker is to introduce structural perturbations S, - at each timestep f such that the model inference at timestep T' for the target entities Egg deteriorates. More formally, the attacker solves the following optimization problem:
max A A A7-1 Lusk Frask (M Vrask Eig)
such that C(A holds
for some constraint function C on the perturbed adjacency matrices A; for each time Here, Vrask denotes the predicted labels for the given task and Lusk is a task-specific loss, for example, a binary cross entropy (CE) loss for link prediction.
The constraint function is designed to ensure imperceptibility of the adversarial perturbations. In the literature, budget constraint has been widely used to enforce imperceptibility in graphs (Dai) eet al. (018) and computer vision (Goodfellow et al.) 2014). However, this constraint only bounds the total amount of perturbations that be introduced by attacker. When the input is dynamic, as in the case of dynamic graphs, the perturbations should be constrained in the context of how the input evolves. However, since the budget constraint completely ignores the graph dynamics, could lead to drastic change in the evolution trend of the graph and thus, making the attacks easily detectable. For instance, with the budget constraint, all the perturbations can be made at a single time step, leading to an anomalous spike, which would be easily detected as a possible attack by graph anomaly detection methods for dynamic graphs (Akoglu et al. 2015 Shoubridge et al. 2002 Bunke et al. 2007). Thus, constraint is desired that can ensure that the introduced perturbations do not disrupt the evolving trend of the dynamic graphs.
3.1 TEMPORAL DYNAMICS- WYNAMICS-AWARE PERTURBATION (TDAP) CONSTRAINT
The simplest measure to study evolution is to consider the change in the input between consecutive time steps. Thus, for discrete-time input [x,], this corresponds to considering the discrete-time differential norm at time I, given by dx, = ||x -|l Then, we propose
Proposition 1 The number of perturbations introduced to input x at time step t must not be more than fraction times the differential i.e. TDAP(c):= - cdx, Vt.
For the case of dynamic graphs, when the graph structure evolves (for example, in social networks and transaction networks (Pareja et al. 2020 Sankar et al. 2020)), this constraint becomes ||,A; A,llı cdA,, Alternatively. dynamic graph may also involve temporally each node (Rozemberezki et al. 2021 ei al. 2017 Panagopoulos et al. 2021), in which case, this constraint becomes |2 -XII, <edx,
signal at
In this work, we focus on dynamic graph structures such that the constraint C (in Equation 1 for the perturbations is TDAP constraint. The optimization problem for the attacker, thus, becomes
max AGAA A4-1
Lrask (Fiask (
1.T -1r--1)),-- Vraskr Eig)
||A -4-1,,11 A,ll
such that (IE(1,T)
11A, -,,-1 S
||| -Ail $ E
where Ej are given parameters for this optimization. We use ||-|| to denote the 1 1-norm of the matrix flattened into vector, unless otherwise mentioned.
3

---

Under review as a conference paper at ICLR 2023
Implications. We show that TDAP constraint has the following implications the perturbations:
1. Perturbations under TDAP constraint preserves the average rate of structural change. Theorem Let dA ,L, LL, Then,
dA' S add B,
(3)
for some constants a, &, Rg0- Proof. By the definition of the perturbation matrix S., d ||A - -A, II + S
(A,1++S Then, using triangle inequality, we get dA; s
+ S Again
using triangle inequality, d d.A, s |IA ||A || Now, since ||S = ed,,, and
| is a constant, we get d S edA, + Ad + C, for some constant C.
d'A'
(Ed,A, I edd, ad.A + f. for some constants a, 2 0.
+C) 2E I, dA,+ C. Hence, we get that dA'
2. Perturbations under TDAP constraint preserves the rate of embedding change. Theorem Let d'z, = =12 2-1lh-- Then, for some constants y, 7,6 E I220
dZ' S ydz +
Proof. Note that = f(A,,
AA). We consider a stacked vector of flattened matrices
Yr [0.t] 9sr 9r-1- -1. 0....... 0), where qi is the flattened vector of A,, and
we append (f r) Os to make all vectors 9si of fixed dimension t. Then, by Cauchy's 's Mean Value Theorem in several variables, we have Z: Z I Vf (q 9s--1), which gives us - by Sehwary inequality. We note that ||g - 95t-1lh
IZ, -Z, =|
[[q -(::----1'" 91-1.- -2 91 I11 = -.,lq,----11 91-111 1| TdA. Thus, we have I|Z, - - CdA for some constant C 2 O. Using Theorem | we get dZ' S CdA' S AdA + B, for A = Ca, B = CB. By mean-value theorem, we also have d'z, 2 f- |لو 9 (o)()) C2d.A (0 is the angle between qg: and 951-1). Hence, dZ' S ydZZ + ô for some constants 5, 2 0.
We analyze the constants in these bounds in further detail in Appendix C
3.2 ATTACK METHODS UNDER TDAP CONSTRAINT
While the TDAP constraint allows us to limit the effect of the perturbations on the graph's 's evolution, it is not clear how one efficiently find perturbations that maximize loss function under this constraint. To this end, we present two algorithms to solve the optimization problem of Equation Z
Greedy. A greedy strategy can be adopted to find effective perturbations under our TDAP constraint. In this approach, perturbations are selected in a greedy manner based on their gradient values with respect to the downstream loss. However, this does not scale well as one needs to find gradient values corresponding to all the perturbations, which would be O(TVI), where V denotes the set of nodes. Thus, inspired by (Chen et al., 2021b), we find the perturbations in two steps - first, we find the top-gradient perturbation at each time step and then, select the one that reduces the prediction probability the most. In particular, we greedily select the perturbations with the lowest probability such that TD) is not violated for any time-step. We defer the full algorithm to Appendix A
Temporal Dynamics-aware Projected Gradient Descent (TD-PGD). Since the constrained opti- mization in Equation] 2 has general continuous objective, a greedy approach is only sub-optimal (even for a simpler convex objective) with no theoretical guarantees. A more standard approach to do optimization under convex constraint is to use projected gradient descent (PGD) (Boyd et al. 2004 [Bubeck et al.) (015)_ Since our problem is in discrete-space, we first relax it into continu- ous space, find the solution using PGD and then, randomly round it to obtain valid solution for the discrete problem. In particular, we relax the perturbation matrix S, into a continuous vector s, and show that closed-form projection operator exists for the TDAP(e) constraint. Algorithm demonstrates the steps involved in this approach (TD-PGD), following the result of Theorem 3
Theorem 3 Suppose S denotes the feasible perturbation space for the constraints |I
A! S é for all 1 < t < T and ||A, - A,ll S Eq. Then, one can project a vector a, onto S using the following projection operator:
Is(a,)) Ro.1jaa:-1)) H.) (ao1)(aa)
if 3 0: 1s Ro.j(aa 1icla;-Pi (1) (4)= = E
(5)
if 1 (P)Poa)(aa)) SE
4

---

Under review as a conference paper at ICLR 2023
Algorithm Temporal Dynamics-aware Projected Gradient Descent
Require: TDAP variables E, (from Thm. 3 Initial vector s Loss function L Actual labels
Plask Target entities Eig. Time steps 7, Learning rate T/: Iterations N, Rounding iterations N,
Ensure: Perturbation vector 5(1) preserves TDAP(E) at every time step
for to N do
Gradient descent: a s(i-1) + 1/; Liak 1 os; " Vth, Vlaskr Eig)
2:
3: Projection: For all E [1, --,,T-1]: s = =Is((a according to Equation
(N) 4: S, - ROUND (s, (e,) from Algorithm
= where E, = =d ccIA, - 1, and Po.1[(x)= = [0,1], 0fx and ifx> 1.
Proof. Please see Appendix B for the proof.
Following (Xu et al. 2019b), we use the bisection method (Boyd et al. 2004) to solve the equation 1 Po.ij(a, H1) = & in H4 for s E [min(a, - 1), max(a,))] This converges in the logarithmic rate, i.e. it takes Ollog2 (max((,,) min(a,- 1))/E) time for &-error tolerance.
3.3 ONLINE ADVERSARIAL ATTACKS
We also consider the online version of the problem in Equation 2 In this setting, the perturbations are added in real-time, i.e. they are both immediate and irrevocable. More formally, Equation 2 must now be solved considering online updates of the optimization variables, i.e., (1) A, is updated at time step without any knowledge 1 and (2) A, remains unchanged for future time steps. Note that TDAP constraint must still hold for A, all time steps
Online TD-PGD. Inspired from its theoretical guarantees online convex optimization (Zinkevich 2003),
Online Projected Gradient Descent for our problem. In this framework, we given a function fi for each step and the goal is to choose X₁ in an online manner such that the regret on the offline optimum x,. R(f,x) := Σ, (f((x,, fx(x)) is minimized. In our problem, as defined in Equation
2 we need to minimize a loss h(AA:TT1) ) at the final time step T. To use online gradient descent, we thus need to write as ((A,) for some fr- Let us assume that h cross-entropy loss and that the embeddings at each time are encoded in a sequential manner. Then,
h( M(AA --> Σ lo) = Σ y(d) Σ
log Mogp(d,,,,AA) A.-1)
dED Σ-
RED
Ald) A,.1)
dED
Thus, we can define fi(A,) = -de pld)oogdd, A.IA, A,-I), which is the prediction loss
for the data points at time step t. Algorithm [ can then be updated find attacks in real time,
(f) following Online Gradient Descent. In particular, for time we find perturbations s; by replacing the loss in line 2 with L(IG, @ s (1-1) - ((t)))(t).-)) Since the projection operator for TDAP (Equation 5) depends only on the current time step f, we can independently project for the current time, i.e.
line remains s; =s((aa)))
(i)
(8) For more details about the algorithm, refer Appendix D
EXPERIMENTAL SETUP
Datasets. We use 3 datasets for dynamic link prediction Rados law UCI and Reddi t Radoslaw and UCI are email communication networks, where two nodes (users) are connected they have an email communication time t. Reddit hyperlink network representing directed connections between subreddits if there is a hyperlink from one to the other at a given timestamp (Kumar al. 2018). For node classification task,
aualicly-available dataset, DBLP--5
hntp:///ooneet.c//erwwwkkk
5

---

Under review as a conference paper at ICLR 2023
XXu al. 2019a). This is co-author network with node attributes word2vec representations of the author's $ papers. There are node labels representing the different fields that the authors belong to. Please refer to Appendix for more details regarding the datasets.
Attack Methods We consider 4 different attack methods to find perturbations under TDAP con- straint. (1) TD-PGD is projected gradient descent with valid projection operator for the TDAP constraint, as specified in Algorithm I (2) (G)(c) greedily selects the perturbation with the high- est gradient value of the loss (we adapt TGA (Chen et al. 202 to our setting, as specified in Section 3.2) (3) DEGREE flips the edges (adds or deletes if already there) attached with the high- est degree nodes in the graph at each time step, while making at most edA, perturbations. (4) RANDOM randomly flips (add or delete) at most ed,,, edges at each time step t.
Victim Models. We test the performance of the above attack methods on 3 different discrete-time dynamic graph models. (1) GC-LSTM (Chen et al., 2018) embeds GCN into an LSTM to encode the sequence of graphs. (2) EVOLVEGCN (Pareja al. 2020) uses recurrent model (RNN- LSTM) to evolve the weights of GCN. We use the EVOLVEGCN- version for our experiments. (3) DYSAT (Sankar et al. 2020) utilizes joint structural and temporal self-attention to embed.
Metrics. We use the relative drop, as defined below, to evaluate the efficacy of the attack methods.
Rel. Drop (%) Perturbed performance Original performance x 100,
(6)
Original performance
where performance evaluated using ROC-AUC for dynamic link prediction and using Accuracy for node classification.
In order to evaluate the detectability of the attack methods, we propose a novel metric Embedding Variability (EV) to compare the consecutive embedding difference for the perturbed graph and that for the original graph. Consecutive embedding difference has been used to identify anomalies in the data (Goyal et al. 2018). Here, measure how the range of this difference changes due to the perturbation. In particular, we consider
ZZ,Z')) = 1- max, dZ, min, az, max, dz, min, dZ, This measures the relative variability of the consecutive change in the embedding space. For the attacks to be less detectable, this metric should be close to O. Note that we do not directly optimize for this metric in our constraint.
(7)
RESULTS
We compare the performance of different attack methods for the 3 victim models on link prediction and node classification tasks. We also test the attack performance on dynamic link prediction in the novel online setting. For all the experiments, we vary c from 0 to 1 and fix ε min,>1 ; cdA,-
5.1 DYNAMIC LINK PREDICTION
In this section, we show the attack performance on the task of dynamic link prediction (Sankar et al., 2020 Pareja et al. 2020). The task here to predict whether a link (u,v) will appear or not the Tuture timestep. The objective of the attacker, thus, is to introduce perturbations in the past time steps to make the model mispredict link's s existence in future. We test the victim models the final snapshot for set of target links. We consider 3 different sets of 100 positive and 1 100 negative random targets and show the mean relative ROC-AUC drop with error bars.
Figure T shows the performance of different attack methods on this task across different datasets and models. TD-PGD outperforms the other baselines all cases, except GC-LSTM model trained on Reddit. t. Moreover, TD-PGD is able to drop the AUC by up to 4 times the baselines and lead to 100% drop in the AUC, completely flipping the prediction. We also note that TD-PGD often has continuously decreasing slope and its performance saturates much later than the other baselines. The second best baseline is often TGA(c) but in many cases, it is only as good as random. One can also note that EVOLVEGCN shows a larger drop than the other 2 models across all datasets. This may pertain to the lower model complexity of EVOLVEGCN compared to others. We discuss these results in further detail in Appendix H

---

Under review as a conference paper at ICLR 2023
TD-PGD
TGA(e)
Degree
Random
0
Rel. Drop %
Rel. Drop %
Rel. Drop %
-20
-40
-30
-40
-80-
-60
0.02:0.00
10.00
0.06
0.02
-60
-100
0.02
0.30
0.50
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) Rados1 law, DYSAT
(h) Rados 1 law, EVOLVEGCN
(c) Radoslaa, GC-LSTM
-20
Rel, Drop %
Rel. Drop
-2
-40
Rel. Drop
-10
-4
-20
-6-
880
0.02-0.00
3.006
0.06
-30
0.06
-100
0.02.300
0.02
0.10
0.30
0.50
0.70
0.90
0.10
0.30
0.50
0,70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(d) UCI, DYSAT
(e) UC1, EVOLVEGCN
(f) UCI, GC-LSTM
Rei. Drop %
Rel. Drop %
Rel. Drop %
-10
-10
-40
-20
-60
00200.00
-80
10.06
10.08
0.02
0.30
0.50
0.90
0.02
0.10
0.50
0,70
0.90
0.02
0.10
0.30
0.70
0.90
Epsilon
Epsilon
Epsilon
(g) Reddit, DYSAT
(h) Reddit, EVOLVEGCN
Reddit, GC-LSTM
Figure 1: Attack performance dynamic link prediction task across datasets and models.
Detectability of the attack methods: Here, we use the EV metric, as defined in Section 4 to assess how detectable the attack methods are under our constraint. Table 2 compares the attack performance of the best method TD-PGD at 0.5 and the corresponding variability in the em- beddings, as given by Equation 7 One can note that smaller than 0.5 in all one case and that TD-PGD is able to cause up to 90% drop in performance while changing the evolution by only a factor of 0,22, on average. This shows that TDAP allows for undetectable yet effective attacks. Please refer to Appendix H for more analysis.
5.2 NODE CLASSIFICATION
In this section, compare the attack performance the task of semi-supervised node classification (Pareja et al., 2020). In this task, the objective to predict node labels of a set of nodes while knowing the labels of the other nodes that time step.

---

Under review as a conference paper at ICLR 2023
Dataset
Model
Rel. Drop
EV
DYSAT
47.03 (5.42)
0.04 (0.18)
Radosl aw
EVOLVEGCN GC-LSTM
91.61 (3.58)
0.45 (1.29)
52.63 (5.09)
0.18 (1.16)
DYSAT
4.02 (2.08)
0.14 (0.25)
UCI
EVOLVEGCN
96.21 (0.17)
0.22 (0.35)
GC-LSTM
16.12 (0.75)
0.35 (0.47)
DYSAT
23.24 (4.18)
0.14 (0.45)
Reddit
EVOLVEGCN
79.31 (3.13)
0.81 (6.37)
GC-LSTM
15.59 (1.28)
0.36 (0.59)
Table 2: Comparison of attack performance and detectability (refer Section for TD-PGD at 0.5. Mean values are noted with standard deviations in the parentheses.
TD-PGD
TGA(e)
Degree
Random
-1
-5
Rel. Drop %
Rel. Drop %
-20
-10
Rel. Drop
-40
-3
20
-5
10.00
-30
10.06
-80
0.02
0.10
0.30
0.50
0.70
0.90
0.2
0.10
0.30
0.50
0.70
0.02
010
0.30
0.50
0.7D
0.90
Epsilon
Epsilon
Epsilon
(a) D3LP-5, DYSAT
(b) DBLF-5, EVOLVEGCN
(c) DBLP-S, GC-LSTM
Figure 2: Attack performance on node classification task for top degree nodes across models.
Figure shows the effect of structural perturbations on node classification task by different attack strategies for the 3 models. Misclassifying the labels for influential top-degree targets can sig- nificantly impact model's usability in practice. Therefore, we consider the performance on 50 top-degree nodes for each class. Results show that TD-PGD outperforms the baselines all mod- els except DYSAT, in which all attacks perform almost equally. In particular, TD-PGD is able to cause 30% drop EVOLVEGCN while the baselines only lead to a drop of 5%. We show the performance on random targets in Appendix H and note that feature perturbations more effective in these cases when the structural information is sparse.
5.3 ONLINE ADVERSARIAL ATTACKS
In this section, we consider the online setting as described in Section 3.3 and compare the online version of TD-PGD with the RANDOM and DEGREE baselines on the dynamic link prediction task. Since the loss at the final step is not available at time step t, one cannot select the perturbations in greedy manner of the gradients. Therefore. do not have TGA(E) baseline for this setting.
Figure 3 shows the average performance of the three methods for dynamic link prediction task on datasets over random seeds. Please refer Appendix H for results on node classification. TD-PGD outperforms the other online baselines in most cases and is able to achieve competent performance to the offline version. In particular, shows up to times improvement over the existing baselines (for EVOLVEGCN on UCI), which is close to the offline TD-PGD as shown in Figure] However, TD-PGD does not perform well in Figures 3a and 3i Online TD-PGD perturbs the graph at time according to the loss at that time step rather than the final step. While it is guaranteed to give strong bounds for a convex objective, some models may learn a complex non-convex function in its input. We conjecture that the degradation may be due such functions being learned in these cases.
8

---

Under review as a conference paper at ICLR 2023
TD-PGD
Degree
Random
10
Rel. Drop %
Rel. Drop %
-2
Rel. Drop %
-20
40
-40
-10
-60
00.06.006
-80
10.06
12.00.0
-20
0.0211.00
0.10
0.02
0.30
0.50
0.90
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) Radoslaw, DYSAT
(b) Rados
EVOLVEGCN
(c) Radoslaw, GC-LSTM
0.0
-20
Rel. Drop %
-2.
Rel. Drop
Rel, Drop
-40
-5.0
-2
-60
-7.5
-10.0
-80
0.10 0.06
50.00
-1255
10230.00
-100
0.02
0:10:000
0.02
0.30
0.50
0.70
0.90
0.30
0.30
0.50
0.70
0.90
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(d) UCI, DYSAT
(e) UCI, EVOLVEGCN
(1 UCI, GC-LSTM
Rel. Drop %
Rel. Drop %
Rel. Drop %
-10
-10
-00
-20
-20
0.30 10
-80
0.02:...0
1.006
20.06
0.02
0.30
0.50
0.90
0.02
0.50
0.70
0.90
0.02
0:10
0.30
0.70
0.90
Epsilon
Epsilon
Epsilon
(g) Reddit, DYSAT
(h) Reddit, EVOLVEGCN
Reddit, GC-LSTM
Figure 3: Online Attack performance dynamic link prediction task across datasets and models.
CONCLUSION
Our work has shown that state-of-the-art dynamic graph models be effectively attacked while preserving the temporal dynamics. We introduce a novel Temporal Dynamics-Awar Perturbation (TDAP) constraint devise perturbations discrete-time dynamic graphs that preserves the graph evolution in both the structural and embedding spaces. Next, we present an effective PGD-based approach to find perturbations under this constraint and show improved attack performance than baselines in both offline and online settings. We hope that our work serves as first step towards opening exciting research avenues on studying attacks and defense mechanisms for both discrete and continuous-time dynamic graphs. Some limitations of our current exposition can be noted. First, the proposed method TD-PGD is not memory- and may not scale to larger graphs (more details in Appendix G). Second, randomly rounding the solution to discrete space may lead to suboptimal perturbations. Future work can study more effective and efficient methods to attack dynamic graphs under TDAP constraint in the restrictive black-box setting.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: survey. Data mining and knowledge discovery, 29(3):626 68888666688866668888 2015.
Alcksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning, pp. 695-704, PMLR, 2019.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):2313377 2015.
Horst Bunke, Peter Dickinson, Miro Kraetzl, and Walter D Wallis. A graph-theoretic approach to enterprise network dynamics, volume 24. Springer Science & Business Media, 2007.
Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li. and Haifeng Chen. Struc- tural temporal graph neural networks for anomaly detection in dynamic graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3747- 3756, 2021.
Jinyin Chen, Xueke Wang, and Xuanheng Xu. Ge-lstm: Graph convolution embedded Istm for dynamic link prediction. arXiv preprint 18/2. 2018.
Jinyin Chen, Haiyang Xiong, Haibin Zheng, Jian Zhang, Guodong Jiang, and Yi Liu. Dyn-backdoor: Backdoor attack on dynamic link prediction. arXiv preprint arXiv:2110.03877 2021a.
Jinyin Chen, Jian Zhang, Zhi Chen, Min Du, and Qi Xuan. Time-aware gradient attack on dynamic network link prediction. IEEE Transactions on Knowledge and Data Engineering, 2021b.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning, pp. 1115-1124. PMLR, 2018.
Houxiang Fan, Binghui Wang. Pan Zhou, Ang Li, Meng Pang, Zichuan Xu, Cai Fu, Hai Li, and Yi- Chen. Reinforcement learning- based black-box evasion attacks to link prediction in dynamic graphs. arXiv preprint wxXiv:200900/633 2020.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner,, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances Neural Information Processing Systems, 34, 2021.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.65777 2014.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dy- namic graphs. arXiv preprint urXiv:/803. /273, 2018.
Bryan Hooi, Kijung Shin, Hyun Ah Song. Alex Beutel, Neil Shah, and Christos Faloutsos. Graph- based fraud detection in the face of camouflage. ACM Transactions on Knowledge Discovery from Data (TKDD), 1 1(4):1-26, 2017.
Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adver- sarial attacks and defenses on graphs: A review, tool and empirical studies. arXiv preprint arXiv:2003.00653. 2020.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. J. Mach. Learn. Res., 21 (70):1-73, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 6480,6980, 2014.
10

---

Under review as a conference paper at ICLR 2023
Gueorgi Kossinets and Duncan J Watts. Empirical analysis of an evolving social network. science, 311(5757):88-9) 90,8889-000-000 2006.
Srijan Kumar, William L Hamilton, Jure Leskovee, and Dan Jurafsky, Community interaction and conflict on the web. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, pp. 933-943. International World Wide Web Conferences Steering Committee, 2018.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1269-1278, 2019.
Jure Leskovee, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2-es, 2007.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffussion convolutional recurrent neural net-
work: Data-driven traffic forecasting. arXiv preprint arXiv:1707.01926, 2017.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks graph neural networks. Advances in neural information processing systems, 33:4756-4766, 2020a.
Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. Attacking graph convolutional networks via rewiring. arXiv preprini arXiv: 1e06.09000000 1906003500 2019.
Yao Ma. Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 719-728, 2020b.
Yao Ma. Suhang Wang. Tyler Demr Lingfei Wu, and Jiliang Tang. Graph adversarial attack via rewiring. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1661-169,, 2021.
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. Pattern Recognition, 97:107000, 2020.
Andjela Mladenovie, Avishek Joey Bose, Hugo Berard, William L Hamilton, Simon Lacoste- Pascal Vincent, and Gauthier Gidel. Online adversarial attacks. arXiv preprint arXiv:2103.02014, 2021.
Apurva Narayan and Peter HO'N Roe. Learning graph dynamics using deep neural networks. IFAC- PapersOnLine, 51(():433-43 438, 2018.
George Panagopoulos, Giannis Nikolentzos, and Michalis Vazirgiannis. Transfer Graph Neural Networks for Pandemic Forecasting. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, 2021.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional net- works for dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5363-5370, 2020.
Stephen Ranshous, Shitian Shen, Danai Koutra, Steve Harenberg, Christos Faloutsos, and Nagiza Samatova. Anomaly detection in dynamic networks: a survey. Wiley Interdisciplinary Reviews: Computational Statisties, 7(3):223-244 2015.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637, 2020.
Benedek Rozemberczki, Paul Scherer, Oliver Kiss, Rik Sarkar, and Tamas Ferenci. Chickenpox cases in hungary: a benchmark dataset for spatiotemporal signal processing with graph neural networks. arXiv preprint arXiv: 00000000, 2021.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural rep- resentation learning on dynamic graphs via self attentttentonn networks. In Proceedings of the 13th International Conference Web Search and Data Mining, pp. 519-527, 2020.
11

---

Under review as a conference paper at ICLR 2023
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021. pp.
2021.
Peter Shoubridge, Miro Kraetzl, WAL Wallis, and Horst Bunke. Detection of abnormal change in time series of graphs. Journal of Interconnection Networks, 3(01n02):85-100) 2002.
Xianfeng Tang, Yozen Liu, Neil Shah, Xiaolin Shi, Prasenjit Mitra, and Suhang Wang. Knowing your fate: Friendship, action and temporal explanations for user engagement prediction social apps. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. pp. 2269 2269, 2020.
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. In international conference on machine learning, pp. 2e.34422-477 PMLR, 2017.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning rep- resentations over dynamic graphs. In International conference on learning representations, 2019.
Bin Wang, Teruaki Hayashi, and Yukio Ohsawa. Hierarchical graph convolutional network for data evaluation of dynamic graphs. In 2020 IEEE International Conference on Big Data (Big Data), pp. 4475 4481. IEEE, 2020.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adver- sarial examples for graph data: Deep insights into attack and defense. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 4816- 4823. International Joint Conferences on Artificial Intelligence Organization, 7 2019, doi: 10.24963/jcca..0119666 2019/699. URL http://dd..or//o0o2299/9////////
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive represen- tation learning on temporal graphs. arXiv preprint arXiv:2002.07962. 2020.
Dongkuan Xu, Wei Cheng, Dongsheng I Luo, Yameng Gu, Xiao Liu, Jingchao Ni, Bo Zong, Haifeng Chen, and Xiang Zhang. Adaptive neural network for node classification in dynamic networks. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 1402-1407. IEEE, 2019a.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint ar arXiv: 042144 2019b.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974- 983, 2018.
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 2672-2681, 2018
Tong Zhao, Bo Ni, Wenhao Yu, Zhichun Guo, Neil Shah, and Meng Jiang. Action sequence augmen- tation for early graph-based anomaly detection. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2668 2678, 2021.
Li Zheng, Zhenpeng Li, Jian Li, Zhao Li, and Jun Gao. Addgraph: Anomaly detection in dynamic graph using attention-base temporal gen. In IJCAI, pp. 4419-4425, 2019.
Dali Zhu, Yuchen Ma, and Yinlong Liu. A flexible attentive temporal graph networks for anomaly detection in dynamic networks. In 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 870-875. IEFF, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pp. 928-936, 2003.
12

---

Under review as a conference paper at ICLR 2023
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856, 2018.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
A GREEDY APPROACH
Algorithm 2 Greedy Algorithm (TGA(e))
Require:
TDAP variables (from Equation Initial perturbation vector s(0), Loss function task Probability function PM predicting link existence probability, actual labels yeask, Target entities Eig. Time steps T.
1: For all 9 91- Attack history H Φ
2: while True do
3: for to do
4:
S Φ
5:
for "lgg Eig do
6:
grads[v] (a 1V for V.
7:
Pick the first in the descending order of grads such that (Nig. v) S.
8:
(r..
9: probs.append((pvle $s,))
10: Pick s, in the descending order of probs such that |H, @s e..
11: if no I found then
12:
break
13:
G - G Sr.
H H, @s..
B PROOF OF THEOREM 3
Suppose S denotes the feasible perturbation space for the constraints || -
for all 1 < t T and ||-4; - A, s 1 Then, one can project a vector a, onto S using the following projection operator:
(s = Po.1j(a,-14 14)
if 00 1 Ro.j(a,, -4))
(8)
(P)))((a))
if 1o S &
where E, edA, = - fort 1, and Ro.1((x) = x if [0, 0 if x < 0, and if 1.
Then, for all [2, 12,T-1] 1]. since s, = -.-11, our constraint becomes ||s, S edA, S A Eg. which reduces to i 6t. For f= 1, we have - s Ej. which also becomes 1 s, e₁ Hence, have the constraint _ E for all
Proof. Let the perturbation vector be S2..
By definition, then, projection operator must be Is{(a) argmin - all?, where S (s [0, 1 1 Se Vr]. This reduces the following optimization problem:
Σ ||s, - a,l1? + (s.,)
Is(()) = arg min sES
(9)
[E[1.T]
such that Vr [1,T1, s, E
where [x) 0 if ( and otherwise.
This can be solved by the Lagrangian method. We note that the Lagrangian function of the above optimization problem is L(s, μ) Eie[1,T] (Hlls, - all (s, + 14
ac/as, 0 s; a; However, if st 0 st,i 1 for any i, then
Thus, the
minimizer to the above function is s Pio,j 14,), where Po,1((x) if x e [0,1], 1,, 0 if 0 and 1 if 1. In addition, the solution must satisfy the following KKT conditions Yt:
14

---

Under review as a conference paper at ICLR 2023
(1) -s)) = (2) p4 (3) S
If Mr > 0, then must have 1 Po.1j(a;- 14) Et. Otherwise if μ4 O, then 1 Po.1j(a,) s E,.
C INTERPRETING THE THEORETICAL BOUNDS ON EVOLUTION
In this section, we analyze the constants in the theoretical bound on the average structural change after perturbation under TDAP constraint, proved in Theorem I In particular, we show how Theorems [ and 2 shows that a local TDAP constraint preserves the average trend of structural and linear combination of the original trends. Thus. if the linear factors small enough, then, the average trend of evolution remains well-preserved. This ensures imperceptibilitty as perturbations that lead change in the trend of structural/emmeedding evolution detected by various anomaly detection algorithms (Cai et al. [222] Goyal et al. (2018). In particular,
embedding change
be easily
while the TDAP constraint allows to find bound on the perturbed trend in terms of the original trend, no existing constraints give us such a bound. This is because we constrain the number of perturbations introduced each time step be within a factor of the changes introduced in the original graph at that time step while existing constraints only impose global constraint on the perturbations over all time steps.
One can note that a 2e and 8 words, the average rate of structural change after perturbations within TDAP constraint remains within a factor of 2 times the permitted fraction for the TDAP constraint of the original average rate, plus 2 times the average no. of edges in the adjacency matrix. Since we consider a targeted case, the adjacency matrix includes only single column and the additive factor corresponds to times the average degree of the target vertex over all time steps. Since is parameter that is chosen by the attacker, a small enough e allows the attacker to preserve the evolution within a small enough multiplicative factor. The additive shift in the trend is equal twice the average degree of the target vertex, which can inform the choice of the target for the attacker according to his permitted limit.
-1 + L, In other
In comparison, simple budget constraint gives bound the average structural change in terms of the original change. This because, || s B, where is the budget. Thus, using similar calculations as Theorem I, we get d.A; < 7 + 7 Elll,, Therefore, perturbations introduced using a budget constraint exceed the average trend of structural change when B/T edA,
D ONLINE GRADIENT DESCENT
Problem 1 Given a convex set K. and every step i 1,2,...,T, we are presented with fü such that we have to choose a solution xli) K. every step way that minimizes the regret Ei(f(x - f((x")) without knowing the future functions fi+1.T-
Lemma Zinkevich 2003, Let G denote upperbound on [[Vi(x for any x E K. and any i, X yll2 be the diameter of K. The online gradient descent algorithm with
and let D maxx
f1 GVT gives regret per step of at most
D
2DG after T steps.
VT
Online Gradient Descent requires replacing Vf(x(0) with Vf(((()). Algorithm presents the corre- sponding online version for TD-PGD.
E DATA STATISTICS AND PRE-PROCESSING
Table 3 shows the statistics of the datasets used in this paper. DBLP-5 is the node classification dataset with 5 labels while the others are dynamic link prediction datasets with varying sizes. The datasets span over differing periods of time. We split each of them into finite number of timesteps to keep large enough number of time steps while maintaining a realistic period of splitting. Rados 1 law is split using 3-week period in 13 snapshots while the 13 snapshots in UCT denote
15

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Online Projected Gradient Descent for dynamic graphs
Require: Current time t, TDAP variable E,, Initial perturbation vector s ( Loss function task
Actual labels Plask- Target entities Fig- Learning rate Tii Iterations N, Rounding iterations Ny-
(i)
Ensure: Perturbation vector S preserves TDAP(E)
1: for fori- == to N do
2: Gradient descent: a, s: (i-1) (i)
+ tack es! 1 Vr [1,t]), Frask Egg)
Projection: st -I1((a,)) E,,,,) from Algorithm 4: S, ROUND (s) (N)
2-week period. The Reddit dataset is spanned over years, thus we use a 2-month split to obtain the 20 snapshots. We use the publicly available pre- reepproesssed data for DBLP-5 (Xu et al. 2019a).
For datasets with no node features, i.c., Radoslaw, UCI, and Reddit, we use uniformly random features with dimension 10. The pre-processed DBLP-5 has 100 node features for each node.
Nodes
# Edges
Time-steps
# Labels
Radoslaw
167
22K
13
UCI
1.9K
24K
13
Reddit
35K
715K
20
DBLP-5
6.6K
43K
10
5
Table 3: Description of the datasets.
F ADDITIONAL DETAILS ON EXPERIMENTAL SETUP
F.1 SETUP
We consider targeted setting with single targets, that selected using either random sampling or a degree-biased sampling. Each target is attacked one-by-one and the total performance of an attacker measured using either an ROC-AUC Accuracy the set of sampled targets.
F.2 HYPERPARAMETERS
For TD-PGD optimization, we used ADAM optimizer (Kingma & Ba 2014) with the initial learn- ing rate of 10. The initial perturbation vector (0) was initialized with all ones, thus, giving each perturbation an equal chance at start. The algorithm was run for iterations. We use Bi- nary Cross Entropy loss for training dynamic link prediction and Weighted Cross Entropy for node classification.
As we show in the Appendix H.6 TGA(e) algorithm does not scale well to higher and larger perturbation space. For this reason, we stop the greedy search the time taken exceeds 300 s, which is at least 3 times that of TD-PGD.
F.3
VICTIM MODEL TRAINING
Table shows the performance the test set of the victim models on different datasets. The performance is evaluated using ROC-AUC for the dynamic link prediction and using Accuracy for the node classification tasks. The test set for dynamic link prediction task denotes the edges and non-edges in the final snapshot, while for node classification, we use a 20% held-out set nodes as the test set for noting the performance and attacking.
16

---

Under review as a conference paper at ICLR 2023
Dataset
Model
Perf.
DYSAT
0.743
Rados law
EVOLVEGCN
0.742
GC-LSTM
0.813
DYSAT
0.952
UCI
EVOLVEGCN 0.873
GC-LSTM 0.968
DYSAT 0.947
Reddit
EVOLVEGCN 0,939
GC-LSTM 0.941
DYSAT 0.699
DBLP-5
EVOLVEGCN 0.687
GC-LSTM 0.695
Table 4: Performance (Perf.) on test set for different datasets and models. For Rados law, UCI, Reddit, we use ROC-AUC as the performance metric and for DBLP-5, Accuracy is used.
F.4 IMPLEMENTATION
We use the TorchGeometrie-Tene Seicooortrri--emmrraall implemennation of EVOLyEGCN and GC-LSTM to train these models. For DYSAT,
the pytorch implementation ! We adapt the official code of TGA to implement the greedy approach. For TD-PGD implementation, we adapt the DeepRobust implementation for dynamic graphs under TDAP constraint. Full code is provided in the attached supplementary for reference.
6
G COMPLEXITY ANALYSIS
TGA(e): It makes O(E E, dA,,) backward calls to the victim model for gradient calculation. Let the gradient calculation takes Tow for model M. Then, the total time for the greedy is given by O, (pw).
TD-PGD: makes O(N) backward calls to the victim model for gradient calculation. In addition, 1))/E] time per iteration and the random
the projection step takes log, minmmmin rounding takes O [s,)) O(T]V) time. Therefore, the total time taken by TD-PGD is given by O(NTh E,
] + TJV)).
Note that the bottleneck, here, is the term Thw and TD-PGD replaces the dependence on the no. of perturbations to a constant (which fixed to 50 in the experiments for all the datasets). Therefore, while TGA(E) finds it hard to scale to larger datasets, TD-PGD scale as long there is enough memory. is worthwhile to note here that TD-PGD would clearly need more memory storage as it needs to store the complete perturbation vector in the memory during optimization. A recent paper proposes an alternative method, called PR-BCD, which stores only optimizes for a fixed set of random perturbations (Geisler al. (021). Such an approach can be employed with our projection operator to scale to larger datasets at fixed memory usage. We leave testing the effectiveness of this approach on large dynamic graphs for the future.
https://gthuub.com/jann//ggg pytorch
17

---

Under review as a conference paper at ICLR 2023
H ADDITIONAL EXPERIMENTS
H.1 PGD PERFORMANCE ON DIFFERENT MODELS
compprees the TD-PGD attack performance over random targets of different victim models for dynamic link prediction. One can note that EVOLVEGCN the least robust among these models as TD-PGD causes the most drop in this model across datasets. On the other hand, GC-LSTM and DYSAT show similar drop with DYS AT being slightly more robust among them. One can explain this result using the architectural differences between these models DYSAT, being attention- based architecture, makes use of more parameters than other models. GC-LSTM embeds GCN into an LSTM and thus, uses the number of parameters than combination of GCN and LSTM. EVOLVEGCN uses a LSTM architecture to evolve the weights of a GCN, which is more efficient.
H.2 DYNAMIC LINK PREDICTION ON TOP-DEGREE TARGETS
Figure Searee5sshoose shows the attack performance dynamic link prediction with targets being 100 top-degree edges and non-edges each. These targets are picked in the decreasing order of the sum of the degrees of the end-nodes
the time-steps. One note that TD-PGD outperforms the existing baselines in most cases for these targets as well.
H.3 EMBEDDING VARIABILITY
In this section, we plot the raw values of embedding variability (EV) different models with in- creasing é. Figure showss the mean EV values with their standard deviations at different e, while Figure 7 shows the median values with the interpercentile range (10% and 90%). We note that mean and median values are close to zero for all the methods (only DEGREE reaches 1). DEGREE is embeddings. Huge
usually the most detectable the methods based on the variability caused variance in Figure 6 be attributed to the existence of outliers in the data the median and 90% quantile value usually low for all methods, except for DEGREF (as shown in Figure 77).
H.4 NODE CLASSIFICATION OVER RANDOM TARGETS
In this section, compare the attack performance the node classification task over randomly- selected target nodes from the test set. In addition to structural perturbations, we also do feature perturbations while following the TDAP constraint.
Structural perturbations Figure g compares the drop caused by different attack methods on the node classification task for different models over random targets. One can note that all attack models perform as good the other on EVOLVEGON and DYSAT, while TD-PGD outperforms others on
GCLSTM
EvolveGCN
DySAT
0
Rel. Drop %
Rel. Drop %
-20
Rel. Drop %
-20
400
-40
-40
-60
-60
-80
-100
10.0
-100
0.02
10.06
-80
1000
0.10
0.30
0.50
0.70
0.90
0.30
0.50
0.70
0.90
0.02
0110
0.30
0.50
0.70
0.90-
Epsilon
Epsilon
Epsilon
(a) Radoslaw
(b) UCI
(c) Reddit
Figure 4: PGD performance on dynamic link prediction task across datasets and models.
18

---

Under review as a conference paper at ICLR 2023
TD-PGD
TGA(e)
Degree
Random
0
Rel. Drop %
-10
Rel. Drop %
Rel. Drop %
-20
20
440
-40
-30
-60
-60
-40
-80
-100
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0,70
0.02
0.10
0.50
0,70
0.90
Epsilon
Epsilon
Epsilon
(a) Radoslav, DYSAT
(b) Rados EVOLVEGCN
(c) Radoslaa, GC-LSTM
2
-20
Rel. Drop %
Rel. Drop %
Rel. Drop
-10
-2
-60
-20
-80
-30
-6
-100
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
UCT, DYSAT
UCT, EVOLVEGON
(f) UCT, GC-LSTM
0
-20
Rel. Drop %
-20
Rel. Drop %
Rel. Drop
-20
-40
40
80
-80
-60
-100
0.02
0.10
0.30
0.50
0.70
0.90-
0.02
0.10
0.50
0.70
0.02
0.10
0.30
0.70
0.90-
Epsilon
Epsilon
Epsilon
(g) Reddit, t, DYSAT
(h) Reddit, EVoLVEGCN
(i) Reddi t, GC-LSTM
Figure 5: Attack performance on dynamic link prediction task across datasets and models for top-
degree targets.
19

---

Under review as a conference paper at ICLR 2023
TD-PGD
TGA(e)
Degree
Random
0.8
2.0
0.6
1.5
0.4
1.0
EV
EV
EV
0.0
0.
0.5
-0.4
-1.0
0.02
0.10
0.50
0,70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) Radoslav, DYSAT
(b) Radoslaw, EVOLVEGCN
(c) Radoslaw, GC-LSTM
1.5
1.5
1.5
1.0
1.0
1.0
EV
EV
0.5
0.5
0.0
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
UCT, DYSAT
UCT, EVOLVEGON
(f) UCT, GC-LSTM
2
EV
EV
EV
1
-20
-1
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.50
0.70
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(g) Reddit t, DYSAT
(h) Reddit, EVoLVEGCN
(i) Reddit, GC-LSTM
Figure 6: Comparison of embedding variability (EV) on link prediction task across datasets and
models, We show mean values for each method with standard deviation as error bars.
20

---

Under review as a conference paper at ICLR 2023
TD-PGD
TGA(e)
Degree
Random
0.3
1.5
0.2
1.0
EV
EV
EV
0.2
0.5
0.0
0.0
0.0
0.02
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0,70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) Radoslaw, DYSAT
(b) Radoslaw, EVOLVEGCN
(c) Radoslaw, GC-LSTM
1.5
2.0
1.5
1.5
1.0
EV
EV
1.0
0.5
0.5
0.0
0.0
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
UCT, DYSAT
UCT, EVOLVEGON
(f) UCT, GC-LSTM
5
4
3
EV
EV
2
2
1
0
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(g) Reddit t, DYSAT
(h) Reddit, EVoLVEGCN
(i) Reddit t, GC-LSTM
Figure 7: Comparison of embedding variability (EV) on link prediction task across datasets and
models, We show median values with the interpercentile range as error bars (1 (10% and 90%).
21

---

Under review as a conference paper at ICLR 2023
Dataset
Model
Rel. Drop %
EV
DYSAT
47.03 (5.42)
0.00 (0.00, 0.04)
Radoslaw
EVOLVEGCN
91.61 (3.58)
0.25 (0.03, 0.79)
GC-LSTM
52.63 (5.09)
0.07 (0.01,
DYSAT
4.02 (2.08)
0.06 (0.01, 0.39)
UCI
EVOLVEGCN
96.21 (0.17)
0.11 (0.01, 0.62)
GC-LSTM
16.12 (0.75)
0.20 (0.03, 0.85)
DYSAT
23.24 (4.18)
0.02 (0.00, 0.34)
Reddit
EVOLVEGCN
79.31 (3.13)
0.13 (0.02, 1.23)
GC-LSTM
15.59 (1.28)
0.13 (0.02, 0.84)
Table 5: Comparison of attack performance and detectability (refer Section 4 for TD-PGD at
0.5. Median values noted with 10% and 90% quantile values the parentheses.
TD-PGD
TGA(c)
Degree
Random
Rel. Drop %
1-
-1
-5
Rel. Drop
Rel. Drop
-10
-2
-15
0.06
1006
1.066
-2
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.31
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) DBLP, DYSAT
(b) DBLP, EVOLVEGCN
(c) DBLP, GC-LSTM
Figure Structural perturbation performance on node classification task over random targets.
GC-LSTM by factor of 2. No attack method is found to achieve significant drop, i.e., below 5%, in the accuracy of DYSAT and EVOLVEGCN on DBLP.
Feature perturbations Further analysis shows that feature perturbations are more effective in this task for random targets. Here, the task is to introduce continuous perturbations S.X X X; such that || - XzIl s edx, for all f. Equation] thus, becomes -X,
max X Xy C
Lrssk (rask (fu(X Praskr Fig)
(10)
1X SE
such that Vt (1,T):
|1, -
| -l
We adapt the Algorithm to this problem to find effective perturbations. particular, we replace sp to denote the feature perturbation vector at time t, i.e., the vector corresponding to X'-X, Finally, since the perturbations are supposed to be in continuous space, we remove the rounding step (line 4) and return the matrix form of (s,) S Thus, TD-PGD can be used to find effective attacks in the feature perturbation setting as well.
However, since TGA(c) and DEGREE takes decisions based the structure, omit these base- lines for this setting. We use RANDOM to introduce uniformly random perturbations the feature matrices of the random nodes.
Figure cammperommrrs the attack performance of the two feature perturbation methods on DBLP-5 over random targets. One note that TD-PGD is able achieve around 30% drop for all the models
22

---

Under review as a conference paper at ICLR 2023
TD-PGD
Random
-5
Rel. Drop %
Rel. Drop
-10
-10
Rel. Drop
-15
-20
-20
-30
10.00
-30
-30
0000
02.1000
0.10
0.30
0.50
0.70
0.90
0.30
0.50
0,70
0.90
0.02
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) DBLP, DYSAT
(b) DBLF, EVOLVEGCN
(c) DBLF, GC-LSTM
Figure 9: Feature perturbation performance on node classification task over random targets.
TD-PGD
Degree
Random
1.5
0.75
0.0
1.0
Rel. Drop %
0.50
Rel. Drop %
-2.
Rel. Drop
0.5
0.25
0.0
0.00
0.5
-0.25
10.00
-1.0
10.06
-0.50
10.00
-12.5
10006.
-5.0
0.10
0.02
0.10
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) DYSAT
(b) EVOLVEGCN
(c) GC-LSTM
Figure 10: Online adversarial attacks on random targets for DBLP.
while could not drop the performance below 5% these random targets using structural pertur- bations. This can be explained by the low degree of these targets (average 10 over 10 time steps) which allows for a small no. of perturbations per time step according to the TDAP constraint. Fur- thermore, the node features here correspond the word2vec attributes of the author papers while the labels represent the field of the author. Thus, there is strong connection between the attributes and the downstream labels, which makes feature perturbation more effective than structural co-author perturbations to flip predicted labels for the classification task.
H.5 ONLINE ADVERSARIAL ATTACKS
In this section, show the performance of the methods in the online setting for node classification on the DBLP dataset. Figures [0] and [I show performance over random and top-degree targets respectively. One can note that TD-PGD shows competitive performance over other baselines while obtaining 5x gain in the relative drop for GC-LSTM.
H.6 RUNNING TIME
Figure compares the running time per target for different attack methods on the largest dataset, Reddit. The times averaged over 200 targets from different seeds and emoor bars note the standard deviation. TGA(e) is the most expensive method in terms of time and scales almost linearly with (capped at 300 s). TD-PGD takes around half the time than TGA(e) and remains constant with increase E. This trend can be attributed to the difference in the complexity of the two methods, shown in Appendix G
23

---

Under review as a conference paper at ICLR 2023
TD-PGD
Degree
Random
Rel. Drop %
Rel. Drop %
-1
Rel. Drop %
-1
-20
-2
-2
-30
-40
192.0.00
20.06
-50
10.06
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
110
0.30
0.50
0.70
0:90
Epsilon
Epsilon
Epsilon
(a) DYSAT
(b) EVOLVEGCN
(c)
GC-LSTM
Figure 11: Online adversarial attacks on degree targets for DBLP.
TD-PGD
TGA(e)
Degree
Random
500
300
Time/target (s)
Time/target (s)
Time/target (s)
300
200
300
200
200
100
100
100
0
0.02
0.10
0.30
0,70
0.90
0.02
0.30
0.30
0.50
0,70
0.90
0.02
0.10
0.30
0.50
0,70
0.90
Epsilon
Epsilon
Epsilon
(a) Reddit, DYSAT
(b) Reddit, EVOLVEGCN
(c) Reddit, GC-LSTM
Figure 12: Running time of different attack methods on the largest dataset (Reddit)
Figure 13 compares the average running time of different methods at varying size of the dataset for a fixed (here = 0.5). As noted Table 3 Rados law is the most dense and Reddit the largest dataset in terms of edges. We find that TD-PGD scales at smaller rate than TGA(e) across different victim models.
1 TIME-AWARE PERTURBATION, DISCUSSION
targeted attack requires the derivative be with respect to targets only. Thus, I|A, A,-IIl in Equation considers adjacency matrices over the target nodes in the set Eig only. An untargeted attack, on the other hand, would take the differential norm over all the entities in the input (i.e., all the nodes in graph).
Clarifications:
J EXTENDED RELATED WORK
Adversarial attacks static graphs. Various attack environments, based on attacker's knowledge and intention, are studied in the literature to assess model performance under adversarial attacks on static graphs (Jin al. 2020). In the literature, adversarial attacks are studied in different settings based on (a) attacker's s knowledge of the underlying model (white-box v/s black-box), (b) their intention for the attack (targeted v/s untargeted), and (c) the timing of their attack (poisoning v/s evasion) (Jin et al.] 2020). Each such combination allows us to assess the model's performance in different attack environments.
24

---

Under review as a conference paper at ICLR 2023
250
500
250
Dyn-PGD
Dyn-PGD
Time/target (s)
200
Time/target (s)
400
Greedy
Time/target (s)
200
Greedy
Dyn-PGD
300
150
Greedy
200
100
100
50
50
DBLP
UCI Rado Reddit
DBLP
UCI
Rado Reddit
DBLP
UCI
Rado Reddit
Dataset
Dataset
Dataset
(a) DYSAT
(b) EVOLVEGCN
GC-LSTM
Figure 13: Running time of different attack methods at = 0.5. Here, Rado means Radoslaw.
We consider a white-box, targeted, evasion setting where the objective is to introduce targeted per- turbations to an already trained, fixed victim model assuming complete knowledge about its ar- chitecture and parameters. Optimization approaches for white-box evasion attacks in static graph literature include PGD (Xu et al. 2019b) and IG-JSMA (Wu et al. 2019). In the present work, we show how constraint. Secondly, IG-JSMA is proposed for the case of static graphs under a global budget con- straint. It is not clear how the importance scores calculated for each edge in the graph sequence would be chosen in a greedy manner to hold our local TDAP constraint.
PGD to generate effective perturbations
dynamic graphs under
novel TDAP
Adversarial attacks dynamic graphs. Adversarial attack dynamic graphs is underex- plored problem and no direct baselines exist that study attacks on dynamic graphs that can preserve temporal evolution (in particular, the proposed TDAP constraint). We only found three works that study adversarial attacks on dynamic graphs (Chen et al. 2021a b Fan et al., 2020). Out of these, only Chen et al. (202Tb) considers a white-box evasion (test-time) attack, which the same set- ting as ours. We adopt the greedy strategy proposed in Chen et al. (2021b) to our constraint to find feasible perturbations for our problem setting as the TGA(e) baseline. Other methods either consider black-box attacks (Fan et al.) (020) or train-time (backdoor) attacks (Chen et al.) 202 which cannot be directly applied here. This is because white-box attacks assume full knowledge of the victim model while black-box attacks find perturbations in model-agnostic manner, which would be suboptimal in a setting where model knowledge available. Secondly, backdoor attacks considers the objective of finding trigger sequence of subgraphs that is added to the train graphs such that the model trained on these perturbed train graphs misclassifies a target link. In contrast, we introduce edge-level perturbations directly to the end-points of the target link (instead of subgraphs) during test time which implies that the trained model parameters are not updated.
Imperceptible Attacks. In addition to bounding the total number of perturbations with budget, other strategies have been developed to make the attacks imperceptible for static graphs. These include rewiring the perturbed edges (Ma et al. 2019 202T). perturbing the low degree nodes (Ma et al. 2020a), and preserving the degree/feature distribution statistics (Zügner et al. 2018).
K
ADDITIONAL PROOFS
Theorem d 2 11 - 2c|dA
Proof. TDAP ensures that ||.4; - Aill S <clA,, - A1-1ll1- Now, we note that since ||-111 2 l1-2,, we also get ||A, -1ll2 S EILA, A,
Further note that ||x yll2 c implies ce, S x y ce, for all unit vectors e, (lle;1l 1). Thus,
|A,-- 144-AAj -,-- < eII -A, implies A, e - -A-illi,, S A, < A, A e1.
Substituting the above inequalities for A; and A₁ in ||A A 1/11l1+- we get ||,, A Ap 2
|LA, - A.-ille,,1 - -e|lA,-1 2 for some unit vectors e,,
Using reverse triangle inequality, ||A;- A; > ||IA, A,-lli elllI, A.-ille,,
25

---

Under review as a conference paper at ICLR 2023
||A,-1 A1-2ll1 e,, 2 ||IA, Ac-llh -(IA,, A.-illilee,,lll + 1IA,-1
where the last inequality is by triangle inequality. Summing both sides over all time steps, we get I,IA,; A 2 -, - A,-1I11 - +I|A,1 - A1,211i) 2
- -
- - +I1 - AA-2211) Replacing E,IlA, - A.-Il as d.A.
we get aA'' - 2e|dAA
Theorem | S C - AA,1ll
Proof. By Cauchy's MVT, Z; Z, S ff q, 9:- which gives us I|Z Z, S [| |1q - q.ll by
Cauchy-Schwarz inequality. Note thq 1 = =||A; Thus, ||Z,-Z,1| S [VV ||,1- CIIA; - A,ll s Ce|lA, - A,-Il by the definition of TDAP constraint.
Theorem 6 dZ' 2 xdZ
Proof. Note that Z, f(A, A 1-1, A1). We consider a stacked vector of flattened matrices
Vr E [0,f]: : 9sr = -97- 91-1,... 91, 0,0, 0), where qi is the flattened vector of A, and we append (t - T) Os to make all vectors 9s: of fixed dimension f. Then, by Cauchy's 's Mean Value Theorem in several variables, we have -, 2 V - --r-1) which gives us I|Z, -Z 9 by the definition 0 is the angle between 9st and 9s--1- We note || |V
that ||qsr - 9st-1 II(q: - 9--1. 922 91 Ih = E,llg, -g-llh = -TdA. Thus, we have -Z, CzdA for some constant C3 0. Using Theorem 4 get dZ' 2 C3d 2 C3l1 2c|dA. By mean-value theorem and Sauchy-Schwarz inequality, we also have dZ, S fIV l|q 1---1| = C4d.A Hence, dZ' 2 C3ll 2e 2 Clll- -eldZ- = x for some constant X 2 0.
L ANOMALY DETECTION WITH TDAP CONSTRAINT
Anomaly detection methods for dynamic graphs can be divided into two broad categories based on the available input Akoglu et al. (013): Ma et al. (202T): Ranshous al. (2015).
Supervised methods. Ground-truth labels for anomalous edges are known or estimated from the data. A model is trained to minimize a supervised loss to classify the labeled edges in the training set. For example, Cai et al. (202T); [hu al. (2020) use Cross Entropy loss while [Zheng et al. (2019): Wang et al. (2020) use margin loss on a parameterized anomalous score that is calculated for each edge using end-to-end trained node embeddings. Since these anomaly detection methods are trained on supervisory signals that may not be accessible to an attacker, evading these anomaly detectors is not the focus of our work.
Unsupervised methods. Here, anomalies are detected by studying certain properties of the dy- namic graph in the structural or embedding space. Victim graph representation models can employ such unsupervised strategies as defense mechanism against adversarial perturbations. Thus, an attacker must be able to defend against such methods to be effective in practice. The focus of our current work is thus to make the unsupervised methods fail to detect adversarial edges anomalies.
Traditional methods have studied, different graph distance metrics between consecutive snapshots such graph edit distance, hamming distance, and spectral distance, to detect anomalous snapshots Shoubridge et al.] (2002); Bunke et al. (2007). If the distance with the previous snapshot exceeds a threshold then the instance is deemed anomalous. These papers, however, have focused on effec- tively detecting graph anomalies instead of edge anomalies at any point in time. In our work, we consider a targeted attack setting, where perturbations (anomalies) are added only change the lo- cal behavior around the target and not the global graph dynamics. A graph-level anomaly detection would thus not be able to detect local perturbations. For this reason, we study these distance metrics for just the ego-network around the target node. Theorems [ and I show that the average rate of structural change remains preserved within certain factors that can be tuned to fool these detectors. Suppose one had chosen threshold B such that dA, 2 B is defined an anomaly. If initially the graph sequence not anomalous on average, i.e., d < B, then after perturbation, d'' 2 B would
26

---

Under review as a conference paper at ICLR 2023
happen if dA' 2 2eldA i... dA 3/(11-2el Thus, one choose value of such that this does not hold for given threshold and snapshot dynamics dA.
Embedding-based anomaly detection strategies have also been proposed that work in an unsuper- vised manner. Yu al. (2018) clusters the embeddings of sampled edge set at each timestep and flags an edge to be anomalous if its distance in the embedding space from each cluster exceeds a threshold. One can note that IDDA-constraines solutions would be effective against such detector as well since as noted in Theorem [ embeddings before and after perturbation change only by small factor of the actual change in the adjacency matrices relative to the previous timestep. Thus, the distance of edge embeddings from the cluster centers would change according to the structural evolution at that time. We further show this with empirical evidence as below.
Another embedding-based method uses the norm distance between embeddings in consecutive snap- shots to find anomalies when the distance exceeds a threshold Goyal et al. (2018). Theorems [ and 6 directly note that the embedding distance between consecutive snapshots would be preserved. We also show empirical evidence of this preservation via our metric Emhedding Variability. Note that Emhedding Variability measures the ratio of the range of the consecutive embedding distance before and after the perturbation. Thus, if the embedding variability is k, it means the range of d', after perturbation is 1 x (or 1- x) times the range of dz, before perturbation. to be D, then our perturbation would be anomalous if D 2 dz, 2 D/(1 + k). Thus, we can choose an e such that the obtained EV (i.e., x) does not satisfy the above inequality for given threshold D and embedding evolution dZz. In this work, we show how K varies with different e and can be as low as 0.04 even for an = 0.5.
the threshold was set
L.1 EMPIRICAL ANALYSIS
Netwalk. In this section, we test the efficacy of Netwalk anomalous scores to detect perturbations made under the TDAP constraint. We used the 3 victim representation models (as above) to ob- tain the embeddings and used the K-Means algorithm with k 5 for clustering each time step. Perturbations are selected from the TD-PGD algorithm and the edge embeddings are clustered in the original and perturbed embedding space for fixed set of held-out training edges. The anoma- lous score is then calculated as the average distance of the perturbed edges to the nearest cluster's centroid in the corresponding embedding space.
Figure shossw anomalous score of the Netwalk algorithm Yu et al. (2018) of the perturbed edges in different victim models for different datasets. One can note that the anomalous score the perturbed embedding space almost perfectly overlaps the anomalous score in the original embedding space. One exception Figure 14b) where the distance after perturbation increases significantly over the original space as e increases. We also conducted a 2-sample t-test between original and perturbed anomalous scores at each epsilon value for each model and dataset. The hypothesis of the two distributions being similar was accepted (i.e., p-value > 0.05) in all but five cases. These were EvolveGCN for Radoslaw at e = 0.3, 0.7, and DySAT for Radoslaw at E 0.9. Thus, perturbations under the TDAP constraint are not easily detectable by the Netwalk algorithm.
DynGem. DynGem detects anomalies based on the value dZ, at each time t. While Embedding Variability gives idea of how different the distribution of dZZ is before and after perturbation, the value can still be arbitrarily low. Thus, we conduct a 2-sample t-test between dZ and dZ' for each model-daatset pair different epsilons, to if the distributions are different. Table show p-values for each case and highlights the cases where the null hypothesis of the two distributions was not rejected (i.c., p-value 0.05). One can note that the I-test found a difference in dZ in only 40 out of 1 117 cases across 3 datasets, 3 victim models, and 13 epsilon values.
M RANDOMIZED ROUNDING FOR TD-PGD
We use randomized rounding for TD-PGD in order to efficiently obtain valid discrete perturbation solution from the continuous vector obtained by running N iterations of the PGD loop. Inspired by existing works on using PGD for graphs Xu et al. (2019)); Geisler et al. (021)) we do randomized rounding for fixed number of iterations and pick the solution that maximizes the loss while satis- fying the constraint. Furthermore, to ensure fast convergence, we adopt the top-k heuristic sampling strategy in the first iteration Geisler al. (021). Algorithm ddescribes the steps taken in TD-PGD
27

---

Under review as a conference paper at ICLR 2023
Original
Perturbed
Distance centroid
1.0
Distance to centroid
1.0
Distance to centroid
0.8
0.8
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.02
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.90
Epsilon
Epsilon
Epsilon
(a) Radoslav, DYSAT
(b) Radoslax. EVOLVEGCN
(c) Rados GC-LSTM
0.04
1.2
Distance centroid
0.5
Distance to centroid
Distance to centroid
0.4
0.8
0.3
0.02
0.2
0.4
0.1
0.0
0.00
0.0
0.02
0.30
0.50
0.70
0.90
0.02
0.10
0.30
0.50
0.70
0.02
0.10
0.30
0.50
0,70
0.90
Epsilon
Epsilon
Epsilon
(d) UCI, DYSAT
(e) UCI, EVOLVEGCN
(0 UCI, GC-LSTM
Figure 14: Distance of the embeddings to the nearest centroid for the perturbed edges at different
epsilons before and after perturbation.
Dataset
Model
Epsilon
p-value (dZ',
DYSAT
[0.02, 0.9]
0.8387
EVOLVEGCN
[0.02, 0.2)
2 0.2054
Rados law
EVOLVEGCN
[0.2,0.9]
s 0.0002"
GC-LSTM
[0.02,0.3)
0.1704
GC-LSTM
[0.3,0.9]
s 0.0432
DYSAT
10.02, 0.9]
0.9252
EVOLVEGCN
[0.02, 0.3)
2 0.0878
UCI
EVOLVEGCN
[0.3,0.9]
s 0.0197"
GC-LSTM
[0.02, 0.2)
0.2674
GC-LSTM
[0.2,0.9]
s 0.0378
DYSAT
[0.02, 0.9]
0.9636
EVOLVEGCN
[0.02, 0.3)
0.0735
Reddit
EVOLVEGCN
[0.3,
S 0.0271
GC-LSTM
[0.02, 0.6)
0.0554
GC-LSTM
[0.6, 0.9]
S 0.0270
Table 6: Significance values from 2-sample t-test between dZ' and dZ. Bold rows indicate that the difference is not significant and thus, DynGem-based anomalous scoring would be ineffective detect TDAP perturbations as made by our method TD-PGD.
to obtain valid discrete solution. Note that in the case of online TD-PGD, this algorithm runs for single time step instead of T 1
28

---

Under review as a conference paper at ICLR 2023
Algorithm 4 ROUND(,,,N,1e.))
Require: Perturbation vector s, Number of randomized iterations N,, TDAP variables ex.
1: S, < for all
2: Lbest <- -00
3: for != 1
do
4:
< Select the top [ perturbations based on the values of s..
5: = P. otherwise O.
6:
Lestt - (1ast S,; Vf), ytaskr Erg)
7:
for == to No,N,, do
8:
[ ~ Bernoulli(s,) for each [ S for all t then
9:
[[1] < (la @ S,[i]; Vi), Peaskr Fig)
11:
[[i] Chest then
12:
S, < S, bestt [[i]
13: return S, for all t.
N POTENTIAL NEGATIVE SOCIETAL IMPACTS
Our work presents the first comprehensive study on adversarial attacks on discrete-time dynamic graphs and shows that existing learning models in this domain are vulnerable to even those attacks that can preserve original evolution of graphs. Dynamic graphs can model large variety of so- cially critical data structures, ranging from social media, epidemiology. finance, biology, and road networks. Our work shows that state-of-the-arr deep learning prediction models vulnerable to perturbations under the TDAP constraint. This means that these models are not suitable for de- ployment in environments where adversarial attacks under TDAP constraint models are deployed in such a setting, adversarial attacks proposed in this work can be used by an adversary to hamper the predictions. However, must noted that none of the models used in this work are known to be deployed in the real-world. Secondly, TDAP constraint with large may not be realistic in many applications. Thus, our study has overall positive impact on the society as it allows practitioners to test the robustness of their models under a practical constraint before deploying vulnerable environments. Although our attacks can be adopted by adversaries for negative use, it is important to put it out in the community so that the model designers are made aware of these attacks that are specifically designed to evade detection.
realistic. If these
29


Reviews:
[{"review_id": "wG94m_zYJFY", "reviewer": "Reviewer_kVti", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel perturbation constraint (named TDAP) for adversarial attack on discrete-time dynamic graph. Importantly, TDAP can preserve the average rate of structure and embedding changes. As TDAP constraint has not been studied before for dynamic graph, authors propose a theoretically grounded approach named TD-PGD for easily extending TDAP to find attacks in a more practical online setting.\nExperiments are conducted on dynamic link prediction and node classification tasks to show the effectiveness of TD-PGD. \n", "summary_of_the_review": "The paper is well written in terms of grammar and writing style. Theoretical proofs are not mathematically rigorous and are inconsistent with the constraint targets. Necessary assumptions are not made clear.", "strength_and_weaknesses": "Strength:\n1. The paper is well written and easy to follow. \n2. Theoretical proofs are given.\n\nThe author proposed TD-PGD as an attack approach on dynamic graph models. I have the following questions that are mainly related to the proposed constraints.\n\n1. Limiting the impact of attack perturbations on the change rate of structures and embeddings sounds reasonable, but it would be conditional. Nowadays, spatial- and spectral-based anomaly detection techniques on graphs are developing rapidly. The attack constraint on dynamic graphs is fundamental to this task, thus the authors should give a rigorous proof about why and when anomaly detection algorithms fail in the face of the proposed constraints.\n2. The proof is not rigorous. First, although the bound is proven, there is no limit to the constants $\\alpha$ and $\\beta$, which might seriously affect the average change preservation. Second, the change of a matrix is directional, it is unreasonable to just consider the norm of average changes. To my knowledge, spectral anomaly detection methods can effectively capture the anomaly caused by the change directions.\n3. The proof is inconsistent with the target. It is not clear how the proven bound echoes the word ‘preserves’. A small enough $\\overline{dA’}$ instead limits the dynamics of dynamic graphs, which increases risk being detected. I think at least the following formula should be proved:  $\\vert \\overline{dA’}-\\overline{dA} \\vert \\leq \\phi$, where $\\phi$ is the bound to make the perturbed structure change rate preserved. ‘Implications’ are intuitively sound, but theoretical proof might be flawed.\n4. The authors are suggested to empirically demonstrate that anomaly detection is insensitive to the proposed attack method. If the attack itself is easily detected, the performance drop may be ineffective.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uF2Ma4p8Cr", "reviewer": "Reviewer_z1Xm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a new constraint on generating perturbations on discrete dynamic graphs and a white-box attack methods on dynamic graphs. Several experiments have been conducted to verify the effectiveness of the proposed method.", "summary_of_the_review": "My major concern is on the evaluation section:\n\n- It would be better if the authors can include more state-of-the-methods on dynamic graph modeling in the evaluation (e.g., ROLAND) in addition to the current methods (e.g., DySAT, etc.) and discuss whether the proposed attacking method apply to them or not\n- The relative drop figure can be misleading (e.g., Fig. 1) as the y-axis scales are not aligned. I suggest the authors to plot the absolute values instead\n- Some design choices need to be better justified: e.g., why only selecting top degree nodes to evaluate the classification tasks\n- I suggest the authors to conduct more analysis instead of just presenting the results: e.g., DySAT seems suffering less from the proposed attack methods. What is the potential reason for this robustness compared w/ other mechanisms? Any specific mechanisms can be further designed to attack this category of modeling algorithms?", "strength_and_weaknesses": "Strength:\n* The paper focuses on a new perspective of dynamic graph attack\n* The draft is organized well and easy to follow\n* The technical details are presented clearly\n\nWeakness:\n* The experiments results need more analysis and to be better presented; some experiment design needs to be better justified\n* The motivation of proposing the new constraint need to be highlighted", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mYznRflxcus", "reviewer": "Reviewer_gWpZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a novel adversarial attack strategy for discrete-time graph neural networks (GNNs). The objective is to perturb the sequence of graphs to decrease accuracy on prediction tasks such as dynamic link prediction and node classification. To preserve temporal dynamics of the graph to avoid detection, the authors propose the temporal dynamics-aware perturbation (TDAP) constraint. They then propose a projected gradient descent algorithm to identify effective perturbations that satisfy the TDAP constraint. They demonstrate strong empirical performance when attacking three different discrete-time GNNs.\n", "summary_of_the_review": "The authors present a novel and technically sound approach to attack dynamic GNNs. I have some technical concerns regarding empirical results that prevent me from more strongly recommending acceptance. I should note also that my expertise is in building models for dynamic networks and not attacking them, so my knowledge of research on adversarial learning is lower.\n", "strength_and_weaknesses": "Strengths:\n- Proposed TDAP constraint and projected gradient descent relaxation to find near-optimal attacks are principled and technically sound.\n- Proposed Temporal Dynamics-aware Projected Gradient Descent (TD-PGD) attack method is much more effective than greedy and other baseline attacks subject to the same TDAP constraint.\n- There does not appear to be much prior research on attacks for dynamic GNNs, so novelty is high.\n\nWeaknesses:\n- Some empirical results regarding the proposed Embedding Variability (EV) seem highly implausible, if not impossible.\n- Attack performance for online version of TD-PGD is inexplicably poor in several experiments. More investigation should be conducted as to why this is happening, beyond just a conjecture.\n\nQuestions:\n1. What is the meaning of the notation $\\mathbf{S}_t \\leq \\varepsilon_t$ in line 4 of Algorithms 1 and 3? On one side of the inequality, you have a matrix, and on the other side, you have a scalar. Is there supposed to be $\\ell_1$ norm around $\\mathbf{S}_t$?\n2. Also for line 4 in Algorithms 1 and 3, why randomized rounding using Bernoulli($\\mathbf{s}_t^{(N)}$) rather than just directly rounding? Can you guarantee that the discretized $\\mathbf{S}_t$ satisfies the TDAP constraint, and not just the continuous $\\mathbf{s}_t$?\n3. How is a standard deviation of 6.37 for the EV of EvolveGCN possible when the mean is 0.81, and EV must be greater than 0 according to Equation (7)? Similarly, I see error bars going into the negatives in Figure 6.\n\nTypos and minor issues:\n- Some minor inconsistencies in notation in Algorithm 1: I believe the vectors $\\mathbf{a^{(i)}}$ and $\\mathbf{s^{(i)}}$ should also have subscript $t$, and $s_t^{(N)}$ should actually be a vector $\\mathbf{s}_t^{(N)}$.\n- Abstract and Section 5.1: \"upto\" -> \"up to\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YaxIdMq7Dsz", "reviewer": "Reviewer_pnFA", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies adversarial attacks on time-evolving graphs. The paper introduces the Temporal Dynamics-Aware Perturbation (TDAP) constraint, which allows for small perturbations of graphs analogous with other adversarial settings, while still preserving the graph evolution. This constraint appears to be combinatorial, and the paper suggests greedy and projected gradient descent with rounding approaches. Numerical studies are shown to show the effect of the perturbations.\n", "summary_of_the_review": "* This seems to be an extension of adversarial perturbations to a setting where it is unclear the study is necessary.\n* Even if the problem were important, the theory seems weak and should be revised in its content and/or presentation.\n* Strangely, a new proposal for a defense mechanism is missing.\n\n", "strength_and_weaknesses": "Strengths\n\n\nWeaknesses\n\n* The paper and, in particular, the numerical studies do not provide much motivation as to why we need to study adversarial attacks in this setting.\n* The theory. Proposition 1 does not appear to be a true proposition but a condition. Are the Theorems really important? How good is the PGD approach at soolving the optimization problem in equation (2) in any specific setting?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QfRokj3yQa", "reviewer": "Reviewer_u4F7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper aims at modeling adversarial attacks which can perturb the input graph sequence on discrete-time dynamic graph models meanwhile preserving the temporal dynamics of the graph.Then they propose a constraint named Temporal Dynamics-Aware Perturbation (TDAP) to make imperceptible perturbations in discrete-time. Through the proof provided, the perturbations under TDAP constraint preserve changes from the structural and embedding perspectives.", "summary_of_the_review": "1. The meaning of proposed metric embedding variability (EV) is similar to the TDAP constraint. So the value of EV should be small intuitively under TDAP constraint. It is better to provide the explanation and comparison to other existed metrics. \n\n2. Table 2 only reports the EV metric for TD-PGD, I would like to see more attack methods in the results. And the proposed method seems cannot achieve the best results in appendix H.4, whiy.\n\n3. Some baselines should be considered, e.g., TGA (Chen et al., 2021b).\n", "strength_and_weaknesses": "\\+ It is a less studied problem that generates attacks on the time-evolving graphs.\n\n\\+ Theoretical proofs and extensive experiments are given. \n\n\\- The layout of this article is somewhat hard to follow.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject