One Vertex Attack on Graph Neural Networks-based Spatiotemporal Forecasting
Authors: Fuqiang Liu
Luis Miranda Moreno
Lijun Sun
Venue:  (2021)
Keywords: adversarial attack
graph neural networks
spatiotemporal forecasting

Abstract: Spatiotemporal forecasting plays an essential role in intelligent transportation systems (ITS) and numerous applications, such as route planning, navigation, and automatic driving. Deep Spatiotemporal Graph Neural Networks, which capture both spatial and temporal patterns, have achieved great success in traffic forecasting applications. Though Deep Neural Networks (DNNs) have been proven to be vulnerable to carefully designed perturbations in multiple domains like objection classification and graph classification, these adversarial works cannot be directly applied to spatiotemporal GNNs because of their causality and spatiotemporal mechanism. There is still a lack of studies on the vulnerability and robustness of spatiotemporal GNNs. Particularly, if spatiotemporal GNNs are vulnerable in real-world traffic applications, a hacker can easily cause serious traffic congestion and even a city-scale breakdown. To fill this gap, we design One Vertex Attack to break deep spatiotemporal GNNs by attacking a single one vertex. To achieve this, we apply the genetic algorithm with a universal attack method as the evaluation function to locate the weakest vertex; then perturbations are generated by solving an optimization problem with the inverse estimation. Empirical studies prove that perturbations in one vertex can be diffused into most of the graph when spatiotemporal GNNs are under One Vertex Attack.

Under review as a conference paper at ICLR 2021
ONE VERTEX ATTACK ON GRAPH NEURAL NETWORKS-BASED SPATIOTEMPORAL FORECASTING
Anonymous authors
Paper under double-blind review
ABSTRACT
Spatiotemporal forecasting plays essential role in intelligent transportation sys- tems (ITS) and numerous applications, such as route planning, navigation, and automatic driving. Deep Spatiotemporal Graph Neural Networks, which capture both spatial and temporal patterns, have achieved great success in traffic forecast- ing applications. Though Deep Neural Networks (DNNs) have been proven be vulnerable to carefully designed perturbations in multiple domains like objection classification and graph classification, these adversarial works cannot directly applied to spatiotemporal GNNs because of their causality and spatiotemporal mechanism. There is still a lack of studies on the vulnerability and robustness of spatiotemporal GNNs. Particularly, if spatiotemporal GNNs are vulnerable in real-world traffic applications, a hacker can easily cause serious traffic congestion and even city-scale breakdown. To fill this gap, design One Vertex Attack to break deep spatiotemporal GNNs by attacking a single one vertex. To achieve this, apply the genetic algorithm with a universal attack method as the eval- uation function to locate the weakest vertex; then perturbations are generated by solving an optimization problem with the inverse estimation. Empirical studies prove that perturbations in one vertex can be diffused into most of the graph when spatiotemporal GNNs are under One Vertex Attack.
INTRODUCTION
Spatiotemporal traffic forecasting has been long-standing research topic and fundamental appli- cation in intelligent transportation systems (ITS). For instance, with better prediction future traffic states, navigation apps can help drivers avoid traffic congestion, and traffic signals can manage traffic flows to increase network capacity. Essentially, traffic forecasting can be modeled as a multivariate time series prediction problem for network of connected sensors based on the topology of road networks. Given the complex spatial and temporal patterns governed by traffic dynamics and road network structure (Roddick & Spiliopoulou 1999), recent studies have developed various Graph Neural Networks-based traffic forecasting models (Yu et al. 2018 Wu et al. 2019 Li et al. 2017
Guo et al. 2019).
These deep learning models have achieved superior performance compared with traditional mul- tivariate time series forecasting models such as vector autoregression (VAR). However, recent research has shown that deep learning fraaeworks are very vulnerable to carefully designed at- tacks (Kurakin et al. 2016b) Goodfellow al. 20144 Papernot al., 2016a| Tramer et al. 2017 Kurakin et al., (2) This raises critical concern about the application of spatiotemporal GNN- based models for real-world traffic forecasting, in which robustness and reliability are of ultimate importance.
For example, with vulnerable forecasting model, a hacker can manipulate the predicted traffic states. Feeding these manipulated values into the downstream application cause severe prob- lems such as traffic congestion and even city-scale breakdown. However, it remains unclear how vulnerable these GNN-based spatiotemporal forecasting models are. Particularly, previous adversar- ial works cannot be directly applied to fool GNN-based spatiotemporal forecasting models because of their causality and spatiotemporal mechanism, which is detailed in Section [
The goal of this paper is to understand and examine the vulnerability and robustness of GNN-based spatiotemporal forecasting models. In doing so, design One Vertex Attack (OVA) framework

---

Under review as a conference paper at ICLR 2021
to break these forecasting models by manipulating only vertex in the graph. We first propose universal attack method against spatiotemporal GNNs by applying the inverse estimation to avoid using future ground truth. Then, we utilize the genetic algorithm, whose evaluation function is composed of the proposed universal attack method, to locate the "weakest" vertex. Here the weakest vertex refers the vertex where attacking it will cause maximum damage the forecasting models. Finally, we generate perturbations by solving an optimization problem.
should be noted that poisoning all vertices even multiple vertices in real-world applications is im- possible, because the large scale of graph. For instance, the graph of traffic forecasting applications generally covers 1000 square kilometers, and it is unrealistic to organize Harker vehicles poison all vertices in such large scale road network. Hence, the proposed one-vertex attack is realistic solution to evaluate the robustness and vulnerability of spatiotemporal forecasting models deployed in real-world applications.
To prove the effectiveness of the proposed OVA method, we test it in two spatiotemporal traffic datasets with three different Spatiotemporal GNNs. The proposed method can cause least 15% accuracy drop, and there are about 10% vertices severely impacted with the boundary of speed variation limited to 15km/h.
The contribution of this paper can summarized as follows.
First, to the best of our knowledge, this is the first study on attacking Spatiotemporal GNNs by poisoning only one vertex.
Second, we proposed a novel OVA method that able to find the weakest vertex and generate optimal adversarial perturbations.
Third, we empirically study the effectiveness of the proposed method with multiple exper- iments on real-world datasets.
RELATED WORK
Adversarial Attacks against Time Series Analysis. Some previous works (Chen et al. 2019 Zhou al.) 2019; Alfeld al. 2016, Karim al. (019)) proposed adversarial attack methods against Autoregressive models or time series classification models. The above works only consider univariate time series. Different from these works, we focus on complex spatiotemporal domains. The input of spatiotemporal GNNs is the temporal dynamic graph rather than regular matrices or sequences. We take the spatial correlation into consideration while the above works didn't.
Adversarial A Attacks against Graph Neural Networks. Many studies (Dai et al. 2018 Zugner
& Gunnemann 2019 Chang et al. 2020 Tang et al. 2020) utilized Reinforcement Learning (RL), meta learning, genetic algorithm to fool GNNs in node, edge, and graph classification domains by tuning the graph topology. All these studies involve no temporal variation in their graphs, and they mainly focus on the spatial pattern. These cannot be applied to fool spatiotemporal forecasting models because of the lack of temporal correlation. Particularly, attacking spatiotemporal forecasing models deployed in real-world applications by graph topology-basee attack methods (Zugner & Gunnemann] 2019 [Chan et al. (2020) are unrealistic, because tuning the graph topology represents tuning the sensor network that collects spatiotemporal data continuously and any modification on sensors can be easily sensed by the sensor network manager.
Adversarial Attacks against Recurrent Neural Network. Recent studies (Rosenberg et al. 2019 Papernot et al. 2016b Hu & Tan 2017) demonstrated RNN classifiers were vulnerable to adversar- ial sequences. These adversarial works require the ground truth to compute adversarial sequences. Because of the forecasting applications' causality, the future ground truth is unavailable. Besides, these works focus on regular vectors or matrices, rather than irregular graphs. Hence these adver- sarial sequence generation models cannot be directly applied to attack spatiotemporal GNN-based forecasting models.
One Pixel Attack for Fooling Deep Neural Networks. Su et al. (2019) utilized Differential Evo- lution (DE) to generate the perturbation to poison one pixel in images, and then fool CNNs. Similar to one pixel attack, only poison one vertex in graphs. However, images regular-structured,
2

---

Under review as a conference paper at ICLR 2021
and Su et al. (2019) consider temporal variation. In addition, one pixel attack requires the ground truth to compute perturbations. In forecasting applications, the ground truth the future traffic state, and it is inaccessible. The above features prevents pixel attack from poisoning spatiotemporal forecasting models.
3 METHODOLOGY
3.1 SPATIOTEMPORAL SEQUENCE FORECASTING SPATIOTEMPORAL GNNS
Because of the impossibility of deploying sensors as regular grid in real-world applications, the form of spatiotemporal data is generally irregular. Consequently, to better mine the spatial informa- temporally varied graph rather than regular
tion, the spatiotemporal sequence is represented grid. The spatiotemporal sequence can be represented as G = {Ve, E, W). where & is the set of edges in the graph, W is the weighted adjacency matrix whose every element describe the spatial relationship between different variates, V/ = (V1,...... Pn,t) traffic speed and traffic volume) collected from sensors on timestamp t, and n is the number of sensors Shuman et al. 2013).
is the set condition values (e.g.
Multistep spatiotemporal sequence forecasting can be formulated Equation Previous conditions from timestamp N + to t are fed into forecasting model F that outputs predictions of future conditions from t + to M. In general, M s N. The above process customarily called settiencceto-sequenne (seq2seq) forecasting.
( F
where 9 denotes the prediction of the condition on timestamp i.
Most state-of-art spatiotemporal sequence forecasting models output a single future condition, which will be turn fed as input into the model to forecast the next condition. This process is named as the recursive multistep forecasting, which can be represented as Equation
gi+1 91 Gr Gi+2 1 9.-N42))
GitM
9 Gr-N+M
Most state-of-art forecasting models, F, are constructed based on spatiotemporal GNNs (Li et al, 2017 Wu et al. 2019 Yu al. 2018 Guo et 2019). Spatiotemporal GNNs are composed of both spatial layers and temporal layers. In general, gated linear unit (GLU) or Gated-CNN (Bai et al., 2018) works as the temporal layer capture the temporal patterns embedded the spatiotemporal sequence, and the Graph-CNN (Shuman et al. 2013: Bruna et al.) 2014) works as spatial layers to capture the spatial patterns.
In this paper, we focus adversarial studies towards recursive multistep spatiotemporal sequence forecasting. Our studies can be easily extended to seq2seq multistep forecasting.
3.2 UNIVERSAL ADVERSARIAL ATTACK AGAINST SPATIOTEMPORAN GNNS
In this section, we point out the form of adversarial attack against the spatiotemporal forecasting, and outline the gap between attacking spatiotemporal GNNs and attacking CNNs GNNs. Then we propose the inverse estimation to fill the gap. Finally, we design the universal adversarial attack against spatiotemporal GNNs.
3.2.1 ADVERSARIAL ATTACKS AGAINST SPATIOTEMPORAL FORECASTING
Adversarial attacking against recursive multistep forecasting can formed as Equation The goal mislead spatiotemporal GNNs to generate false forecasting by adding perturbations.

---

Under review as a conference paper at ICLR 2021
F(19 GI-N+1) + (pt, Pt N+-N++]) # 9 s.t. ||я: S & vi (l, N + +
(3)
where Pi denotes perturbations on timestamp || -lpp denotes b -n-m, and & denotes the pre-defined constant to constrain the perturbation scale. In real-workh traffic applications, control the hacker's driving behavior to balance the attack performance and detection avoidance.
Because of spatiotemporal sequence's causality, we cannot access the future condition that works as the ground truth of forecasting models. other words, Ge+1 in Equation 3 is not available on timestamp f. Previous adversarial studies against CNNs, RNNs, and GNNs (Dai et al. 2018] Papernot et al., 2016bb Kurakin et al. 2016b) Alfeld et al.) 2016) almost all involve the ground truth in the perturbation computation. In fooling spatiotemporal GNNs Equation 3 the ground truth, Ie+1. is still inevitable. As we mentioned above, the future condition is unavailable, and thus we cannot generate adversarial perturbations directly Equation
3.2.2 INVERSE ESTIMATION
We propose Inverse Estimation avoid using the future ground truth in fooling spatiotemporal GNNs. First, Equation is transformed to Equation 4 which represents our goal is to fool spa-
tiotemporal GNNs to generate opposite forecasting.
arg min
11a max(0, m
-E) (4)
where G.+1 denotes the opposite condition of Gi+1. denotes the penalty factor. The constrain in Equation 3 is replaced with a regularization term in Equation 4 to constrain the perturbation scale. The penalty factor is set 100 make sure the scale penalty term is much larger than the first term in Equation 4 so that the scale the computed perturbation is strictly forced. The above idea similar targeted attacks (Akhtar & Mian 2018). However, classical targeted attacks still utilize the ground truth in perturbation computations.
To use no future information, the opposite of future condition, G.+1, 1. estimated by computing the opposite of the most recent condition, which is represented Equation 5
G < J. (v., E, W]
(5)
where D/ {ū1,2, ...; (n.r) denotes a collection condition values opposite to these collected from sensors. Take the traffic condition for instance, when the condition is "congested/low speed", its opposite is "free/high speed", and vice versa. Ug the opposite of 0g,s, is computed as Equation 6
02 = max(V)) U/ < mid
(6)
min(m) (V), U/ 2 mid
where mid, mar(V), and min(V) represent the mean, maximum, and minimum value of the spa- tiotemporal dataset, respectively.
Table 1: Comparison on different estimation strategies.
PeMS
strategy
MAE
MAPE (%)
RMSE
PER(%)
MR
1.48
3.30
2.40
13.33
STGCN
1.39
3.06
2.37
10.55
ARIMA
1.92
3.64
3.02
12.17
IE
0.56
0.99
1.63
99.56
4

---

Under review as a conference paper at ICLR 2021
Inverse Estimation outperforms directly estimating the future ground truth. The error of the estima- tion on the opposite of ground truth is smaller than errors of any direct estimation. To validate the above assumption,
carry out a test on PeMS dataset. We compare the proposed inverse estimation with three types of ground truth estimation methods, namely estimating by the most recent traffic condition (MR), spatiotemporal graph convolution neural network (STGCN), and AutoRegressive Integrated Moving Average (ARIMA). The experiment result is shown as Table [ The proposed In- verse Estimation's performance, including mean absolute error (MAB), mean absolute percent error (MAPE), root mean square error (RMSE). and perfect estimation ratio (PER), is better than others'. should be noted 99.56% IE's estimations are exactly equal the opposite of ground truth.
3.2.3 UNIVERSAL ATTACKS AGAINST SPATIOTEMPORAL SEQUENCE FORECASTING
Adversarial perturbations generated by the subsection 3.2.2 vary with the input graph. Only if the perturbation keeps being updated, will be effective all the time. The universal attack denotes that the perturbation is consistent and independent from the input, which can be represented as Equation
arg min (I NC-N+13 + {pu)) - Ge+1 1l2 a max ph -))
Pu
where Pa denotes the universal perturbation.
The universal perturbation can be generated by solving equation 7 After the universal perturbation generated, there is no need to update when new data come. The proposed universal attack will be utilized to locate which vertex to attack for one vertex attack.
3.3 LOCATING WEAKEST VERTEX
In this subsection, we first mathematically define the "weakness" of vertex in a graph. The "weak- ness" of the jth vertex denotes the number of influenced vertices when the jth vertex is attacked by the proposed universal universal perturbation, which is shown as equation g
weak, = =1 F(IG..... G.NN+1 M, pw) (a0)--9+1/p
get1
(8)
where M2- Pe denotes that all elements except the one corresponding jth vertex are set to 0, and Ko[-} denotes element-wiss, filter to set elements whose absolute value is smaller than @ to 0. A greater "weakness" value represents more vertices will influenced the jth vertex is attacked. We will attack the vertex with the largest "weakness" value. In traffic forecasting applications, is set as 5 empirically.
A possible method to locate the weakest vertex is the complete traversal algorithm. However, this method is time consuming. To reduce the time cost, we utilize the genetic algorithm to locate the weakest vertex, which is shown as follows.
First, the initial candidate set is composed of s vertices with the most edges.
Second, the updated candidate set computed equation 9
0 (g 1) = e,1 (g) + p(v+2(g) vrs(g))
where U; denotes the position of the ith vertex, denotes the gth iteration, r1, r2, and r3 are random numbers with different values, and p the parameter be 0.5 empirically.
Third, compare the updated candidates' weakness with the previous candidates' then keep candidates with the largest weakness value.
Fourth, repeat the second and third step until the candidate set is consistent or g > 10. Select the weakest vertex to attack. It should be noted that the bound of g controls the trade- off of the proposed solution's 's effectiveness and efficiency. The larger bound represents the proposed solution is much closer the complete traversal algorithm.
5

---

Under review as a conference paper at ICLR 2021
3.4 ONE VERTEX ATTACKING AGAINST SPATIOTEMPORAN GNNS
After the weakest vertex is located, we generate one vertex perturbation based on equation I0 Poisoning the weakest vertex in graph with the carefully designed perturbation can fool the spa- tiotemporal GNN-based traffic forecasting system.
arg min My Mp--Pe---PNN441
+ My {prs... Pr- N++)+ - Gella a ..oneverree
(10)
Ronevertex
Σ
mar(0, (M, -))
imt-N+1
where J denotes the index of the weakest vertex, and M, Pos is the generated perturbation. It should be noted that | Pillo S
Different from adversarial attack methods proposed Equation 4 and Equation 7 the one vertex attack keeps poisoning one vertex in the graph, while others poison the entire graph. As for real- world traffic forecasting applications, poisoning the entire sensor network deployed in road networks is unrealistic, while one vertex attack is much more harmful.
In reality, the vertex denotes sensor like loop detector. The one vertex perturbation denotes vehicle's speed shift. If a hacking vehicle's speed varies following the perturbation computed as Equation I0 can fool the entire traffic forecasting system, not only at the vertex where the hacking vehicle is, but also at other vertices and even vertices far away from the attacked vertex.
4 EVALUATION AND RESULTS
The evaluation of the proposed method is based on two traffic datasets, namely PeMS and METR- LA(S). PeMS records 44-days traffic speed data which was collected from 200 stations Caltrans Performance Measurement System (PeMS), METR-LA(S) records four months of traffic speed on 100 stations on the highways of Los Angeles County. Our experiments are conducted under an NVIDIA DGX station with 4 NVIDIA Tesla V100 GPU cards.
We test three spatiotemporal GNNs including STGCN (Yu et al. 2018), DCRNN (Li et al. 2017). and Graph WaveNet (Wu al. 2019). Each dataset is split into 3 subsets: 70% for training, 10% validation, and 20% for testing. All setting parameters are as same as related papers (Yu et al. 2018 Li et al. 2017 Wu et al. 2019) except the number of input and output channels accordingly set as the number stations in the said dataset. In addition, we use the validation set to locate the attack position, and generate OVA perturbations in real-time for the test As for measurement, we introduce three metrics to measure the proposed method's effectiveness.
MAPE Increase (MAPEI) Mean Absolute Percentage Error (MAPE) is a measure of prediction accuracy and smaller MAPE represents better predictions. An increase in MAPE thus translates into a decrease in the prediction accuracy.
Normalized MAPE Increase (NMAPEI) denotes the ratio between MAPEI and the MAPE before attacking.
&%--mmpacte Vertices Counts the number of vertices with NMAPEI being greater than
k%.
4.1 TRADEOFF BETWEEN ATTACK PERFORMANCE AND DETECTION AVOIDANCE
In real-world traffic applications, the generated perturbations represent the hacking vehicle's 's speed shifts. The parameter& ç, which used to limit the driving behavior, in Equation I0 balances the attack performance and detection avoidance.
We first propose an experiment to test how the parameter influences the effectiveness of the pro- posed one vertex attack method. In this subsection, 15min traffic speed forecasting is undertaken by STGCN, DCRNN, and Graph Wavenet that work as the targeted models and the experiment is conducted on META-LA(S). These models attacked by the proposed OVA with different &.

---

Under review as a conference paper at ICLR 2021
Table 2 shows the number of impacted vertices with different When the v is equal to 20, over 10% vertices, whose NMAPEI are greater than 40%, are severely impacted, even with only one vertex attacked. With small VE. there are about 50% vertices influenced. Based on the results shown as T we can conclude that perturbations will be diffused from one vertex to most of the graph when apply spatiotemporal GNN-based forecasting models. The greater the perturbation is, the more vertices in the graph will be influenced.
Table 2: The relationship between V and the k%clmpacted Vertices
STGCN
DCRNN
Grave Wavenet
VE
10
15
20
5
10
15
20
5
10
15
20
k%
Impacted Vertices
43
71
69
90
51
75
82
88
42
70
82
91
10%-Imppaced Vertices
14
52
61
82
17
59
65
71
16
32
52
73
20%-Impacted Vertices
22
40
46
8
27
45
50
3
25
41
55
100%-Impacte Vertices
17
39
26
40
1
4
38
40%- Impacted Vertices
9
0
0
0
13
0
0
1
16
Setting & into an appropriate range important. An extremely large &, which represents abnormal driving behaviors in traffic domains, will be detected easily. By analyzing PeMS and META-LA(S),, speed variation within 15km/h occurs frequently, and consequently, we regard the accessible bound- ary of speed variation is 15km/h, namely VE 15.
4.2 EFFECTIVENESS AND EFFICIENCY OF LOCATING WEAKEST VERTEX
In this subsection, experiments PeMS carried to prove the effectiveness and efficiency of the proposed weakest vertex locating strategy. STGCN works as the model to attack. Three locating strategies, namely locating the vertex with the most edges (MOS), locating the vertex with the highest centrality (CEN), and locating the weakest vertex by the complete traversal algorithm (CT), work as baselines. After locating the weakest vertex by different strategies, perturbations computed as Equation I0 and then fed into STGCN. NMAPEI and 30%-IV are recorded in Table
Table 3: The effectiveness test the proposed weakest vertex locating strategy
NMAPEI
30%-IV
MOS
4.5%
CEN 3.2%
CT 15.2%
17
Proposed 15.2%
17
The proposed strategy's effectiveness is close to the complete traversal algorithm. In this experiment, locates the same weakest vertex the complete traversal algorithm does. Poisoning the vertex with the most edges the highest centrality cannot fool the forecasting model effectively. A possible reason is that these vertices' robustness is improved by their neighbors because of the STGCN's spatiotemporal mechanism.
In addition, the proposed strategy spends 1104 seconds to locate the vertex to attack, while the complete traversal algorithm spends 1795 seconds. The proposed strategy can reduce the time cost of locating the weakest vertex.
4.3 EFFECTIVENESS OF ONE VERTEX ATTACK
In this subsection, experiments on PeMS are designed to prove the effectiveness of the proposed method. 15min traffic speed forecasting is undertaken by three spatiotemporal GNN methods that work as models to attack. We compare the proposed OVA with four baselines that are detailed as follows.

---

Under review as a conference paper at ICLR 2021
RAN: Generate perturbations based Equation and randomly attack vertex; repeat the above step for times and compute the average MAPEI and NMAPEI.
RAN2: Generate Gaussian White Noise (GWN) with the same scale constrain as the pro- posed OVA method shown as Equation [0 and attack the weakest vertex following the proposed weakest vertex locating strategy.
MOS: Regard the vertex with the most edges in the graph the weakest vertex, and attack this vertex based on Equation I0
MFSM: Attack all vertices with modified Fast Gradient Sign Method (FGSM) (Szegedy et al. 2015). We replace the ground truth in the original FGSM with the proposed inverse estimation as Equation 5 which is shown as Equation 11
(11) where V computes the gradient of the cost function around the prediction of the fore- casting model parameterized by + w.r.t the input sequence (Gt, - J. sign denotes the sign function, G. denotes the inverse estimation of the ground truth, and control the scale of the perturbations.
(e Pt-N+13 = sign(V (9r,..,, N N+1 G.)
Table 4: Effectiveness evaluation based on PeMS
STGCN
DCRNN
Grave Wavener
NМАРEI
30%-IV
NMAPEI
30%-IV
NMAPEI
30%-IV
Proposed
15.2%
17
16.7%
22
15.5%
21
RAN
2.1%
1
2.7%
0
2.3%
0
RAN2
1.7%
0
2.3%
2.1%
0
MOS
4.5%
3
4.7%
5.7%
2
MFGSM-3
27.3%
24.4%
25.8%
MFGSM-2
15.4%
15.6%
16.2%
In these experiments, VE is set to 15 for methods that attack only one vertex. "MFGSM-c" used point out the perturbation constrain of MFGSM. Because attacks all vertices rather than one vertex, we set as and 2 respectively.
(a) Attack A
(b) A's input
(c) B's prediction
(d) C's prediction
Figure 1: Results of the proposed One Vertex Attack
Table shows the experiment results. Our proposed one vertex attack method outperforms attacking one vertex randomly (RAN) and attacking the vertex with the most edges (MOS), which represents that the proposed method on locating the weakest vertex works. Our method outperforms attacking the weakest vertex with GWN (RAN2), which represents the proposed method can generate the optimal perturbations for one vertex attack.
Fig la shows attack result on STGCN. Vertex A is attacked with the poisoned input Fig lb and predicted sequences in vertex and C are shown as Fig and ld Id respectively. B and are far away from A and there is attack on B and C. Fig shows example that the spatiotemporal GNN-based forecasting model mispredicts "congestion" as "uncongested" at about the 60th step.
For traffic forecasting in PeMS, the proposed method can cause 15% accuracy drop for all three Spatiotemporal GNN models, and about 10% vertices are seriously impacted (these vertices' NMAPEI greater than 30%) with VE equal to 15.
8

---

Under review as a conference paper at ICLR 2021
Attacking all vertices always better than attacking only vertex, but the proposed method's effectiveness is similar with attacking all vertices by MFSDM with approximately equal to 10% VE, which is concluded by comparing the proposed method with MFGSM-3 and MFGSM-2 in table 4 It should be noted that MFGSM attacks 200 vertices, while OVA only attacks one.
5 CONCLUSION
This paper proposed One Vertex Attack that can break spatiotemporal GNN-based forecasting mod- els by poisoning only vertex. The generated perturbation will be diffused to numerous vertices in the graph when Spatiotemporal GNNs are under attack.
Future works for the proposed study be summarized follows. First, we utilized a universal adversarial attack method to measure the "weakness" of vertices. We do not include temporal pat- possible
terns in our measurement. Consequently, involving temporal patterns in the evaluation modification. Second, we design genetic algorithm-basee method to find the "weakest" vertex in a graph attack. This might not be the optimal solution. Third, studies on the scalability one vertex attack is valuable.
Besides, as spatiotemporal applications require reliable algorithms, how to defend these adversarial attacks, and how to build more robust spatiotemporal LNN-based models are still valuable.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. arXiv preprint /00i.0/801.00500 2018.
Scott Alfeld, Xiaojin Zhu, and Paul Barford. Data poisoning attacks against autoregressive models. In AAAI, 2016.
Shaojie Bai, Zico Kolter, and Vladien Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.0/22 2018.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In ICLR, 2014.
Heng Chang, Yu Rong. Tingyang Xu, Wenbing Huang. Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box adversarial framework towards attacking graph embed- ding models. In AAAI, 2020.
Yize Chen, Yushi Tan, and Baosen Zhang. Exploiting vulnerabilities of load forecasting through adversarial attacks. In ACM ICFES, 2019.
Hanjun Dai, Hui Li, and Tian Tian. Adversarial attacks on graph structured data. In ICML, 2018.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In AAAI, 2019.
Weiwei Hu and Ying Tan. Black-box attacks against RNN based malware detection algorithms. 2017.
arXiv preprint
Fazle Karim, Somshubra Majumdar, and Houshang Darabi. Adversarial attacks on time series. arXiv preprint 1902: 2019.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint arXiv: 1..6111.000 1.01266, 2016a.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv: 00650320233,.... 2016b.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffussin convolutional recurrent neural net- work: Data-driven traffic forecasting. arXiv preprint arXiv: 2017.
Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Anan- thram Swami. Practical black-box attacks against deep learning systems using adversarial exam- ples. arXiv preprint arXiv: 1602.02697, 201
Nicolas Papernot, Patrick D. McDaniel, Ananthram Swami, and Richard E. Harang. Crafting adver- sarial input sequences for recurrent neural networks. arXiv preprint 160.v:1604.0800 2016b.
John Roddick and Myra Spiliopoulou. A bibliography of temporal, spatial and spatio-temporal data mining research. ACM SIGKDD Explorations Newsletter, 1999.
Ishai Rosenberg, Asaf Shabtai, Yuval Elovici, and Lior Rokach. Defense methods against adversarial examples for recurrent neural networks. arXiv preprint arXiv: 000:: 00000..0.9.,... 2019.
David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
Jiawei Su, Danilo Vasconcellos Vargas, and Sakurai Kouichi. One pixel attack for fooling deep
neural networks. In CVPR, 2019.
10

---

Under review as a conference paper at ICLR 2021
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, 2015.
Xianfeng Tang, Yandong Li, Yiwei Sun, Huaxiu Yao, Prasenjit Mitra, and Suhang Wang. Transfer- ring robustness for graph neural network against poisoning attacks. In ICWSDM, 2020.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint arXiv: 2017.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. In ISCAI, 2019.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In IJCAI, 2018.
Xingyu Zhou, Yi Li, Carlos A. Barreto, Peter Volgyesi, and Xenofon Koutsoukos. Load forecasting with adversarial attacks in power systems using deepforge. In ASHTSS, 2019.
Daniel Zugner and Stephan Gunnemann. Adversarial attacks graph neural network via meta learning. ICLR, 2019.


Reviews:
[{"review_id": "v5EWqdXEz-Y", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new one vertex adversarial attack to evaluate the robustness on deep spatialtemporal graph neural network. First, it formally defines the adversarial attack into optimization problem and uses a genetic algorithm to solve it. \n\nPros:\n1. To my best of knowledge,  none adversarial attack has been applied to spatialtemporal graph neural network. And the spatialtemporal graph neural network has its uniqueness in terms of unfixed input and graph property.\n2. The attack performance seems reasonable.\n\nCons:\n1. While it has proposed a new attack towards the spatialtemporal graph neural network, the novelty of the proposed method is not significant. It could just be treated as attack the node features on a normal graph neural network to predict the next node' label. \n2. The difficulty of unfixed or interactive input on spatialtemporal graph neural network is avoided instead of solving it. There are some papers like [1][2] that already attack the interactive input and address the problem instead of avoiding it. \n3. The universal attack claimed is not actually a universal attack. The universal attack is defined to use a common perturbation on features on every node instead of just one node. I suggest to take out the universal claims.\n4. While attacking the node attributes or features, it would be more interesting to utilize the graph topology as well, which is commonly discussed on the adversarial attacks related to graph neural networks.\n5. The constraint on the perturbation is actually a l2 constraint however it is a soft constraint. I am not sure whether the constraint is strictly forced. If not, how to measure the node feature's similarity after the perturbation?\n\n\n[1] Cheng, Minhao, Wei Wei, and Cho-Jui Hsieh. \"Evaluating and enhancing the robustness of dialogue systems: A case study on a negotiation agent.\" Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). 2019.\n\n[2] Gleave, Adam, et al. \"Adversarial policies: Attacking deep reinforcement learning.\" arXiv preprint arXiv:1905.10615 (2019).", "extra_scores": {}, "extra_text": {}}, {"review_id": "eTFEFlf_P2q", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a single vertex based white-box attack on spatiotemporal GNNs. They solve the optimization of the least perturbations with the inverse estimation. The results demonstrate that the perturbation on one vertex can mislead the performance of the GNNs. \n\nAdvantages: \nThe idea of designing a single one vertex based attack is novel; the experiments are exhaustive, and the results validate the effectiveness of the attack method. \n\nConcerns: \nI think the technical contribution of this paper is weak in that: \n1. One-pixel attack [1] is not new, I don’t see some novelties in designing the one vertex attack. The only interesting point is the expansion into the new scene of attacking GNNs.\n2. I'm wondering the efficiency of the one vertex attack. Is it really important to implement the one vertex attack? Besides, how's the attack success rate if the STGCN, DCRNN and Graph WaveNet are all aware of the attack method, i.e. the performance of attacks on defensed neural networks? For example, preprocessing is a routine method for defending against adversarial attacks. If the denfense side is aware of the attack, then how's the attack success rate when the attacked model is equipped with a simple filtering operation before the test sample are fed into the GNN?\n3. As far as I'm concerned, the adversarial attack and defense are the arms race, I'm not surprised the one vertex attack has a strong attack success rate since it is a white-box attacked and it computes the modification by solving an optimization problem. What really matters is why it is important to attack a GNN like network and what's the novelty, since we all know that deep neural network can be easily attacked by adversarial examples. I wish to see the real discoveries rather than just adapting an attack mechanism to a new classification task. \n\n[1] Su J, Vargas D V, Sakurai K. One pixel attack for fooling deep neural networks[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 828-841.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FLG2OlbzIH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of attacking graph neural networks for spatio-temporal prediction problems (e.g., traffic speed prediction). The input of the problem is a spatio-temporal sequence represented as graphs at time t-N+1 to t, where a graph neural network is trained to predict the graph sequence for time t+1 to t+M. The aim is to add perturbations to the input graph sequence, such that the predicted graph sequence varies from the ground truth as much as possible. \n\nThe novelty of the proposed attack model lies in that it does not require knowledge on the ground truth graph sequence. Instead, it uses an inverse estimation that uses the \"opposite\" of the graph at time t as the perturbation target. \n\nFor efficiency and practicality considerations, the vertex that has the maximum impact on the prediction output is computed using a heuristic algorithm, and perturbation is done on this vertex only. This makes the attack more realistic as only one vertex needs to be attacked rather than the full graph. \n\nPros:\n1. The problem studied is interesting. Spatio-temporal prediction problems have many applications, and many recent works on such problems do use graph neural networks to make predictions. \n\n2. Experimental results on real datasets show that the proposed algorithms are effective and efficient. \n\nCons:\n1. The proposed models and algorithms are shown to be effective. One concern is on the technical depth. The modelling of the problem and the algorithms are relatively straightforward. There is a lack of performance guarantees and theoretical guidance on the choice of parameter values. For example, how much worse in terms of the attack impact when the weakest vertex is found by the heuristic algorithm instead of by a full traversal? Why is g bounded by 10 in Equation 9? Are there guidance on choosing \\alpha in Equation 4 beyond \"empirically\"? What is the relationship between the number of vertices attacked and the impact of the attack? \n\nAdditional comments:\nHow exactly are the experiments in Table 1 set up? Are all algorithms/models in Table 1 given the same input and ground truth output for the error calculation? If not (which seems to be the case based on the current wording), the comparison might be unfair. \n\nWhat are the meanings of \"position\" of a vertex and '-' in Equation 9? What is the intuitive idea that the genetic algorithm suits the problem to find the weakest vertex?  \n\nWhat exactly does the right arrow in Equation 5 mean? Assigning \\Tilde{g}_t to \\Tilde{g}_{t+1}? \n\nThe related work section claims that \"these works (i.e., works on adversarial attacks against recurrent neural network) focus on regular vectors or matrices, rather than irregular graphs.\" It would be good to clarify the difference between \"regular matrices\" and \"irregular graphs\", since graphs are often represented by their adjacency (or vertex feature) matrices.  \n\nTypo: Check the double quotes throughout the paper. \n\n**Update after author response:** I appreciate the authors' efforts to address my comments. Part of the comments on the presentation of technical details have been addressed, such as the meaning of \"position\" of a vertex and \"-\" in Equation 9. However, the main concern in terms of the technical depth has not been addressed well. There is a lack of performance guarantees and theoretical guidance on the choice of parameter values. For example, how much worse in terms of the attack impact when the weakest vertex is found by the heuristic algorithm instead of by a full traversal? The results in Section 4.2 and Table 3 are empirical and not theoretical. As such, I could not change to a more positive rating. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-Fks0F6-Ja6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the attack of a spatiotemporal GNN and also proposing a method to find the weakest vertex for this attack. It investigates the strength of the suggested approach. The results are convincing.   It is well written with a few edits to make:\n- Page 2, ln 8: Spelling of spatiotemporal \n- Page 2, Section 2, par 2: These cannot... instead of These work cannot... \n- Page 3, par 2: equation 1 should be repositioned for flow. \n- Equation 6: \\min etc instead of min etc.\n- Page 4, last paragraph: refer to the section by number instead of saying 'above'\n- Page 5 and further: weakness and others have the speech commas facing incorrectly outwards. These could also just be removed rather. \n- Page 6, par above Table 2: Refers to the 'above results' which are actually below in Table 2 - use labels and ref. \n- There are many unpublished references included - these should possibly be reduced - many are probably now published? \n- Ref Dai 2018 has et al in it? \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes one vertex attack for GNN, applied to spatiotemporal forecasting. The paper can be improved w.r.t novelty, incorporating graph topology and rigorous analysis. 
Decision: Reject