Understanding and Simplifying Architecture Search in Spatio-Temporal Graph Neural Networks
Authors: Zhen Xu
quanming yao
Yong Li
Qiang Yang
Venue: Accepted by TMLR ()

Abstract: Compiling together spatial and temporal modules via a unified framework, Spatio-Temporal Graph Neural Networks (STGNNs) have been popularly used in the multivariate spatio-temporal forecasting task, e.g. traffic prediction. After the numerous propositions of manually designed architectures, researchers show interest in the Neural Architecture Search (NAS) of STGNNs. Existing methods suffer from two issues: (1) hyperparameters like learning rate, channel size cannot be integrated into the NAS framework, which makes the model evaluation less accurate, potentially misleading the architecture search (2) the current search space, which basically mimics Darts-like methods, is too large for the search algorithm to find a sufficiently good candidate. In this work, we deal with both issues at the same time. We first re-examine the importance  and transferability of the training hyperparameters to ensure a fair and fast comparison. Next, we set up a framework that disentangles architecture design into three disjoint angles according to how spatio-temporal representations flow and transform in architectures, which allows us to understand the behavior of architectures from a distributional perspective. This way, we can obtain good guidelines to reduce the STGNN search space and find state-of-the-art architectures by simple random search. As an illustrative example, we combine these principles with random search which already significantly outperforms both state-of-the-art hand-designed models and recently automatically searched ones.

Published in Transactions on Machine Learning Research (01/2023)
Understanding and Simplifying Architecture Search in Spatio-Tene Temporal Graph Neural Networks
Zhen Xu 4 Paradigm
mushen@@Apanddigm.cm
Quanming Yao"
qgoouu@tsingguua.cccccm wew.:ettsiinnuu.......rrrr
Department of Electronic Engineering Tsinghua University
Yong Li
Kyong077@tsinghuaa.d edu.cc
Department of Electronic Engineering Tsinghua University
Qiang Yang
rgang@Cscc.us..om ust.hk
Deportment of Computer Science and Engineering Hong Kong University of Science and Technology
Reviewed OpenReview: https: httpe://openreeveau openreview. net/ ptr/fo id= 4JEuSMPKSP
Abstract
Compiling together spatial and temporal modules via a unified framework, Spatio-Temppral Graph Neural Networks (STGNNs) have been popularly used in the multivariate spatio- temporal forecasting task, e-g- traffic prediction. After the numerous propositions of manually designed architectures, rescarchers show interest in the Neural Architecture Search (NAS) of STGNNs. Existing methods sulfer from two issues: (1) hyperparameters like learning rate, channel size cannot be integrated into the NAS framework, which makes the model evaluation less accurate, potentially misleading the architecture search (2) the current search space, which basically mimics Darts-like methods, is too large for the search algorithm to find a sufficiently good candidate. In this work, we deal with both issues at the same time. We first re-examine the importance and transferability of the training hyperparameters to ensure fair and fast comparison. Next, we set up framework that disentangles archilecture design into three disjoint angles according to how spatio-lemppoal representations flow and transform in architectures, which allows us to understand the behavior of architectures from a distributional perspective. This way, we can obtain good guidelines to reduce the STGNN search space and find state-of-the-art architectures by simple random search. As an illustrative example, we combine these principles with random search which already significantly outperforms both state-of-the-att hand-designed models and recently automatically searched ones.
1 Introduction
Multivariate forocasting is a crucial task commonly encountered in our daily life. In addition to classic time series forecasting, spatial correlation has been recently leveraged for more accurale prediction, titled Forecasting. typical and important example is traffic prediction which forecasts future traffic status (e.g., volume and speed) based on history data (usually the same as prediction targets), moving one step further towards smart transportation and intelligent city [Zhnng et al. 2011 Ran Boyee 2012
*Q. Yao is the correspondence author. "Qur code available htttps//ggtthbb com/ Com/AutaML-ta Rew.scchh/cacc//eeeTt

---

Published in Transactions on Machine Learning Research (01/2023)
Nagy & Simon
2018
Using learning models to better exploit spatio-temporal information is the key
challenge (Jiang et al. 2021
Li et al. 2021a
Early works use classic time series forecasting techniques like ARIMA Zare Moayedi & Masnadi-Shiraan 2008) and LSTM (Fu et al. 2016) but do not explicitly consider spatial relation. Motivated by the power of Graph Neural Networks (GNNs) Scarselli et al. 2009 Kipf & Welling, 2017) modeling relational data, two
representative works (Yu al. 2018 Li al., 2018)) firstly combine GNN and temporal modeling techniques and propose Spatio-Temmn SpapoolTemporal Graph Neural Networks (STGNN). STGNNs simultancously extract spatial correlation by GNN module and temporal correlation by, like Convolutional Neural Network (CNN) (LeCun ct al. 1989) or Gated Recurrent Unit (GRU) (Cho et al., 2014), and they have shown promising performance in traffic prediction. Subsequently, many variants are proposed to improve upon above pioneer works from various angles. Examples are STGCN (Yu et al., 2018). DCRNN (Li et al. 2018), MIGNN (Wu et al. 2020
AGCRN (Bai et al. 2020); and STEGCN (Li & Zhu 2021
As STGNNs go more complex, designing better archilectures by hand can go beyond human expertise because it remains difficult for researchers to understand which architecture configurations work better. More recently, Neural Architecture Search(NAS) methods have gained much attention due to their effectiveness in various rescarch directions (White et al., 2021 Eliasof et al. 2021 Liu et al. 2019). NAS researchers leverage the expertise in certain domains to propose efficient search space and strategy. Similarly, two STGNN NAS methods have been introduced as well AutoCTS (Wu et al. 2021 and AutoSTG (Pan et al. 2021), ,, which basically follow Darts-like differentiable search space (Liu et al. 2019) with a few customized operations to adapt on STGNN models. However, since there is lack of systematic architecture understanding in the STGNN community, the STGNN NAS methods still suffer from huge search space, hindering their efficiency and effectiveness. Moreover, all the STGNN NAS methods do not consider the impact of huperparameters, leading to probable evaluation bias.
Above works usually propose a novel architecture (manually or by search) and study this single model in an isolated way. Motivated by recent works that study a series related works in hindsight to produce general principles (Chu et al. 2021 Gorishniy et al.j 2021 Bello et al.] 2202 You et al., (2200) [Zhang et al., 2022), we aim at obtaining useful understandings to bring forth the next generation of STGNNs, which is an important missing piece in the community.
However, systematic understanding of STGNN architectures is not an easy task. First, the evaluation of architectures is expensive as hyperparameter tuning is required. Training hyperparameters in existing works are often tuned with a small grid inherited from prior studios. But different architectures may not prefer the same setting of hyperparameters and a small grid search cannot fully explore the hyperparameters space (You et al. 2020 Bello et al. 2021). Currently, there no existing methods that can evaluate and compare architectures a cheap and fair way. Second, the architecture space is huge and complicated. Classically, control variable methods, which analyze improvements with and without certain microscopic architecture designs, are popularly used (Bai et al.] 2020; Song et al. 2020). Reusing such methods here could lead to biased interpretations as they fail to explore different architectures from distributional perspective.
In this work, we take a step back and revisit the STGNNs. Inspired by the representative literature as illustrated in Figure [ we propose a disentangled framework composed of disjoint factors regarding the architecture designs. This framework includes design choices of temporal/spatial modules, spatio-temporal order and skip connection. Through the lens of this framework, we dig in depth the principles of different. architectural choices. We summarize and quantify empirically the influence of each part. Based on our understanding, we could casily find new STGNN models with simple method adapted from random scarch.
Our main contributions are as follows:
We propose a disentangled framework of of spatial/temporal modules, the spatio-temporal order and the skip connection.
Graph Neural Networks containing the designs
To allow fair and efficient evaluation of different model configurations, we study a much larger hyper- parameter setting and quantify the importance of each choice, which helps to reduce significantly the hyperparameter space.
2

---

Published in Transactions on Machine Learning Research (01/2023)
Input
Input
Input
Input
Spatial
Op1
Channels
S
ST-Block Block
Dilation
Kernels
Op2
OR
-lookk
Temporal
Channels
Op3
Graph Conv Embedding dim
S
ST Block
Node degres
Op4
Output
Output
Output
Output
(a)
(b)
(c)
(d)
Figure 1: Architecture plot of representative literatures. (a) STGCN (b) MTGNN (c) AutoCTS (d) Our framework. Red blocks represent spatial modulcs (S). Blue blocks represent temporal modules (T). For AutoCTS, each block composes four operations and each operation could be spatial or temporal module.
Through comprehensive experiments and distributional analysis, we conclude fundamental design principles of the skip connection choices and the spatio-temporal order, quantified by mathematically motivated measures. The design principles form naturally cherry regions, where architectures more likely to perform well.
Based on our in depth understanding of architectural principles and training hyperparameters, we propose simple method to obtaín new STGNN models more easily and effectively.
2 Problem Definition
A graph representing the topology network is denoted as G = (V. E, A, where V is the set of [ N nodes, E is the edge set and A is the adjacency matrix of shape RNN. We have then multivariate feature tensor of nodes X E RTxNxD representing the temporal graph signals. T is the total timestamps. D is the number of features per node at each timestamp. Denote also X, E IR NxD the features at one timestamp t and XOG(TT)) E RRT xxD the features of T' timestamps.
In spatio-temporal traffic prediction task, the goal is to predict Q future steps based on P past steps observations of traffic features (Li et all 2021a)). Due to the popularity and superior performance,
STGNNs as the prediction model. Following the mentioned literature (Wu et al. 2020 Chen et al. 2021b Wu et al. 2021), we consider P = Q = 12.
In order to understand the generalizable principles of STGNN architectures in a tractable way, we propose the following distributional bi-level formulation:
ming (awPs(a) [C( (a), a; Dval)l s.t. w w'(a) 10)--agg arg min L(w, or Dersin);
where is the model architecture, encoded in any format; is the trainable parameters depending og P is the architectural distribution parameterized by 0; L is the evaluation metric such as mean squared error; Dval, Durain are validation and training data. The usage of D in the outer optimization and Derai in the inner optimization is commonly adopted in the NAS community in order to seperate conceptually two levels of problem (Lu et al. 2019 Chen et al. 2021a). In our work, we follow this paradigm.
The distributional nature lies in the minimization of expected loss, similar (Chen et al. 2021a Xie et al., 2019). And since the raw architecture encoding is not compact and informative enough, turn this task into
3

---

Published in Transactions on Machine Learning Research (01/2023)
tractable one by proposing paramcterized measures 0 to map from raw architectures to their mcasures 0 and finally to the distributional predictive performances.
Generally speaking, the architecture a can capture certain prior knowledge on the traffic prediction task. For example, the order of how spatial/tempont representations are processed, how different levels of spatio- temporal representations could be fused. All these prior knowledge should be data-dependent and can largely influence the architecture choice.
Thus, understanding of architectures leads to better exploit the prior knowledge and subsequently obtain better prediction performance. As discussed in Section | existing works camnot be used since the architecture's space is large and complex and fair evaluation is expensive. In the sequel, we propose a disentangled framework and choose appropriate measures to evaluate architectures on observations generaled from the framework.
3 Disentangled Framework
To motivate such framework, take step back and revisit representative works' architectures in Figure [a)-(d). We remove unnccessary microscopic details and highlight their overall architectures. STGCN and AGCRN are simplified to compile 6 blocks of S-T-T-S-T and S-T-S-T-S-T). MTGNN compiles 6 blocks in another order (T-S-T-S-T-S) and in addition, adds skip connections. AutoCTS consists of multiple ST-Blocks, each which consists of 4 operations which could be spatial module, temporal module, identity module, etc. AutoCTS also has fixed skip connections inside the blocks and among the blocks.
modules in different orders (resp. T-
After visualizing above literatures, propose disentangled framework shown in Table and Figure [ We are thus interested in the correlation between the performance and these disjoint factors. Specifically, we consider
temporll order. Independent of module specific designs, STGNN models put together spa- halltempprall modules in a certain order to process spatial and temporal correlations. In our framework, for a pre-determined number of modules, say 6, each module could either be spatial module (S) or temporal one (T). Thus, is possible to have T-T-T-T-T-T, i.e. all six temporal modules or vice versa. Note that we do not include parallel connections here, e.g., STSGCN (Song et al. 2020) and GMAN (Zheng el. al., 2020), because such designs do not perform well, e.g. STEGNN in Table
Skip connection. Farliest works do not consider skip connection Yuu al. 2018 al. 2018). Later works let temporal modules skip to the end and skip internally every two blocks (Wu et al.) 2020). AutoCTS (Wu et al. 2021) connects each block to the end and inside the blocks, every later node connects to all previous nodes in determined way. We consider much larger skip connection space of over 2 million choices, ie., each layer could choose to connect to any number of previous layers.
Spatial module. For graph convolution, we consider several different GCNs that are common in Spatio- temporal GNN literature, namely Kipf GCN, Chebyshev GCN and Mixhop GCN, On graph structure, we adopt the setting of AGCRN but with additional kNN for spansity. To still make use of the provided graph structure, we include a mixture coefficient.
Temporal module. We only consider TCN here since it is easier to be trained than RNN. Specifically, we consider a typical dilated TCN on the time axis of features to extract temporal features. A set of convolution kernels are used and channels of different kernels are aggregated.
We can see that exemplar hand-designel architectures, e.g. STGCN, MTGNN and searched architectures, o.g., AutoCTS, AutoSTG are all included in the above framework. Moreover, it extends the scope of existing works' to many more possibilitics, especially by introducing the space of skip connections and spatio-temporal order.
4

---

Published in Transactions on Machine Learning Research (01/2023)
Table 1: Summarization of the proposed architecture framework
Type
Name
Detail
Spatio-temporal order
Arrangement of spatial/temporal modules in arbitrary order
Skip connection
Any jumping between two modules including input and output
Spatial module
Channels
16,32,64
Graph convolution
Kipf GCN, Cheb GCN, Mixhop GCN 10,20,40,60,8
Embedding dim
Node degree
5,10,20,40,60
Mixture coefficient
0,0,25,0.500.75,1
Temporal module
Channels
16,32,64
Dilation
1,2
kernel numbers
1,2,4,8
kernel candidates
2.3.1,566778.91101111111
4 Understanding STGNN Hyperparameters and Architectures
this section, we show how important principles can be observed based on the framework, which help
speedup the evaluation and subsequently design better STGNNs. We explain for cach factor its motivation,
the used methodology and the understanding obtained to answer sequentially the research questions. All
experiments in this section run on two datasets PeMSO4 and PeMS08 (Guo et al. 2019 Song al. 2020
which are introduced with more details in the Appendix B
4.1 Understanding training hyperparameters
Different STGNN models naturally need different training hyperparameters. To avoid biased evaluation of models by inheriting hyperparameter setting existing works, we instead consider hyperparameter space where bad hyperparameters choices can be removed such that once space, we obtain a distributionally fair evaluation.
model multiple times under this
We consider training hyperparameters (HP) that are common from STGNN literat as in Table 2 where the curriculum learning (Wu et al. 2020 Li et al. 2021a) is specified to STGNN here. The current training hyperparameters constitute space of over 10" choices and is not practical efficiently evaluato cach model configuration. We aim to independently study the impact by the ranking distribution to remove the hyperparameters that commonly bad for most architectures. The ranking distribution evaluates model with different hyperparameters to obtain relative rank and repeats to have distributional patterns. The details of ranking strategy, datasets and choices of hyperparameters are in Appendix and
Table 2: Common training hyperparameters for STGNNs.
Name
Original Scope
Reduced Scope
Learning rate
1e-5, 1c-4, 1e-3, 1e-2, le-1 8,16,32,64,128
1c-4, 1e-3
Batch size
8, 32, 128 Adam, AdamW
Optimizer
SGD, Rmsprop, Adam, AdamW, Adamax 0.1e:1,1e2211333,ee1..11 0,1.3,5,7.9 0,0.1.0.33005,077..... None,3,5,7
Weight decay
0, le-5
Gradient clip
1,
Dropout
0, 0.3
Curriculum learning
None, 3
The ranking strategy. To compare hyperparameter P of K choices (2.. PK), we randomly sample a configuration under our framework. configuration contains all necessary choices of hyperparamcters and architectures to identify a model. We then replace iteratively the hyperparameter of this configuration by all K choices and train the models one by one. Thus, for each batch of K runs, have K model results
5

---

Published in Transactions on Machine Learning Research (01/2023)
whose configurations differ from each other only in the hyperparameter P. We rank these results ascendingly (smaller error metric means better performance, thus ranks better). We run multiple batches of K runs and obtain the ranking distribution on each hyperparameter. For example in Figure a), we compare and rank the relative performance of five learning rate choices for a certain model configuration. After many configurations evaluated, we oblain that 1e-3 the best choice since it ranks first (most frequent) in all runs.
The ranking plot of each hyperparameter partially given in Figure and the full plots are in Appendix D The hyperparameters are grouped into three cases.
1. reduced options, c.g., learning rate and optimizer could be reduced to few options:
2. monotonically related, e.g., weight decay and dropout rate are (almost) showing monotonically better weight decay decreases;
3. obvious pollern, e.g., gradient clip does not show much difference long as it is activaled and same for batch size and curriculum learning.
The training hyperparameter space has been reduced by 500 times as in Table 2 with which we are able to largely increase the efficiency of model evaluation in a fair way.
Rank
Rank
4
Rank 4
1
1
1
1e-5
1e-4
1e-3
1e-2
1e-1
1e-5
1e-4
1e-3
1e-2
le-1
(a) Learning rate
(b) Weight decay
(c) Gradient clip
Figure 2: Rankings of three training hyperparameters. A lower rank means better performance. The more a choice ranks first, the better it is in terms of distribution.
4.2 Understanding architectures
With such a disentangled framework presented, we aim at the following research questions (RQ) to understand the influence of each factor:
RQI: What patterns in terms of spatio-temporal order do good models share? How to characterize spatio-temporal order patterns?
RQ2: What patterns in terms of skip connection do good models share? How to characterize skip connection patterns?
RQ3: How do different ppatial/temporal module designs influence the performance?
RQ4:
How transferable are above patterns in the architecture space?
However, these questions are not trivial to answer. We need to dedicatedly design systematic views over the huge architecture space such that correlations among different architectures and with the final prediction performance can be simultancously captured. In this way, principles that can indicate goodness of architectures can be generated. Ideally, we want to find cherry regions of architecture space since good architoctures should share important designs in common. An urchitecture in the cherry region has high probability to achieve good performance. A key challenge in finding such regions lies in the choice of quantitative measures.
4.2.1 Spatio- temporal order
The spatio-temporal order specifies the arrangement of both spatial/temporal modules to learn the representa- tion. Intuitively, the representation is influenced by how many spatial /tempora modules respectively

---

Published in Transactions on Machine Learning Research (01/2023)
Number of Inversion
8
T-14--84-
Number Inversion
8
Number of Inversion
6
4-
4
2
2
2
9--6-T-T-T
2
2
6
0
6
Number of T
Number
Number of
(a) Exemplar order.
(b) Order on PeMS04.
(c) Order on PeMS08.
Figure 3: Spatio-temporal order understanding on different datasets. For (b)(c), we normalize performances to show them in a colormap. The darker the circle, the better the performance.
and how these modules are interleaved to exchange the information. We propose two measures explained below to characterize spatio-temporal order of architecture:
Number of spatial or temporal modules. Without loss of generality, we observe temporal modules, noted as #T
Number of inversed order of module sequence. Let the number of inversed order of pair of modules (either S or T) be if S comes before T, i.e. ST, and 0 otherwise, Lee. TS, SS, TT. The number of inversed order of a module sequence defined as the sum of that of each pair modules.
The rationale of the above two measures is quantitatively justified in below Remark ! Specifically, they help identify a compact triangle region as in Figure 3 () where different combinatorial choices of S/T orders lie at the corners.
Remark 1. We claim that the number of inversed order along with the number of T modules (#T), can well caplure the interleaving of sequence of S-T modules, including the following 4 corner cases: (N is number of total modules)
Case 1: All S modules, #T is O and number of inversed order is 0, indicating no temporal feature is needed;
Case 2: All T modules, # is N and number of inversed order is 0, indicating no spatial fenture is needed;
Case 3: N. S modules followed by z the spatial information should strictly be processed before temporal information;
N T modules, #T is NN2 and number of inversed order is 0, indicating
N A indicating Case 4: N. T modules followed by NN. S modules, #T is N. and number of inversed order is the temporal information. should strictly be processed before spotial information.
We fix the framework factors except for the spatio-temporal order. As mentioned above, we relax the spatio-temporal order under 6 temporal and/or spatial modules, leading to space of 26 = 64 choices. We use the above mentioned measures to observe the order. Results are in Figure 3 We
see that for spatio-temporal order, all corner cases perform terribly. A clear region for 2 to 5 T blocks and for number of inversions between 3 and 8 exists and shows superior performance. This suggests that (1) we might have good performance for many temporal modules but too many spatial modules is not a good idea. This could be because of the oversmoothing phenomenon observed in GNN (Xu et al.) 2018) but further study is required; (2) a large number of inversion usually returns better performance which means that both modules are encouraged to interleave more frequently.
4.2.2 Skip connection
As the representation flows from the input to the output without a loop, we are motivated to formulate skip connections in STGNNs as a Directed Acyelic Graph (DAG) with a straight though flow path connecting sequentially each module (Figure [e). Afterwards, we need consider proper measures to observe the skip space as it is large. Intuitively, the performance of a certain skip pattern depends how many skip and
7

---

Published in Transactions on Machine Learning Research (01/2023)
where we skip. The former can be measured by number of paths from input module to output module and the latter can be measured by average shortest length for each pair of modules, both defined below. We propose another two measures explained below to characterize skip connection of an architecture:
Number of path, noted as (#Path). It is defined as the total number of trajectories from the predeter- mined imput node to the predetermined output node.
Average Shortest Length, noted as ASL. It is defined the average of shortest lengths from non-output nodes to the output node predetermined.
The rationale of the above two measures is quantitatively justified in below Remark 2 Specifically, they help identify a compact right triangle region in Figure 4(a) where different combinatorial choices of skip connections lie at the corners.
Remark 2. We claim that Average Shortest Length (ASL) and number of path(#Poth) in a Directed Acyelic Graph can well capture the spatio-temporal information flow, including the following 3 corner cases:
Case 1: ASL is low and #Path is low, i.e., limäted number of skips which mostly connects to the output node, where most literature folls in;
Case 2: ASL is low and #Path is high, i.e., lot of skip connections among which many skips to the oulpud node, polentially obfuscaling the propogated message;
Case 3: ASL is high and #Path is low, i.e,, almost no additional skips, which is the case of earliest STGCN model (Yu et al. 2018).
In Figure 4 we show the skip experiment on two datasets and on two spatio-temporal orders that have been used the literature. Details are given Appendix [ All these four experiments follow a similar pattern. First, all corner cases perform badly. In the center rectangle, we observe a clear region where the performance are much better, especially for AST. between 1.1 to 1.8 and #Path between 10 and 40. Notably, this region exists for different datasets and for different spatio-temporal orders, showing its universality in terms of principles. This observation can be exemplified by other works e.g. residual connection (He et al., 2016), JK-Net (Xu et al. 2018). message passing (Battaglia et al. 2018). Especially for GNN, we want to reinforce the remote message, e.g. the input node, in later nodes, thus ASL will be low. We also do not want to have too many messages that obfuscate the valuable message, thus #Path cannot be too high.
4.2.3 Spatial/temporal module design
Different choices of spatial/temporrs module influence the way the spatial/temporal representation are processed. In the literature, diverse modifications on TCN and GCN have been proposed. We use the same ranking distribution as in understanding training hyperparameters to study all the module choices. The ranking plots are partially shown in Figure and full plot is given in Appendix [ We remove a few bad options according the ranking, e.g., Cheb GCN, node degree 5, etc. Then, we also find we could largely reduce number of parameters by reducing channels temporarily due to high performance correlation, show in Appendix D
4.2.4 Summary of designing principles
With the empirical results in this section, after refining the training hyperparameter space, we find that good architectures share similar patterns. Firstly, Two cherry regions exist shown in Figure M(a) and Figure 4aa), answering RQ1 and RQ2. Concretely, we tend to consider architectures which have appropriate number of temporal modules, inversion number, averaged shortest length, and finally number of paths. The appropriate scope can be interpreted from the view of spatio-temporal information flow and message passing with jumping information. For module designs, we remove some bad choices as by ranking and discover that we could largely roduce number of parameters by reducing channel size due to high performance correlation, answering RQ3. All the experiments in this section are conducted on two datasets PeMS04 and PeMS08, showing the generability of the discoveries, thus answering RQ4
8

---

Published in Transactions on Machine Learning Research (01/2023)
Number of Paths
40
Number of Paths
40
30
30
20
20
50
Number Path
40
1.0
1.5
2.0
2.0 AvgSnortestLen
1.5
AvgSnartestLen
30
(b) PeMS04 + T-S-T-S-T-S
(c)
PeMS04 T-S-T-T-S-T
20
Cherry
50
10
Number of Paths
Number of Paths
40
40
1.0
1.5
2.0
AvgShortestLen
30
20
20
(a) Exemplar skip connections
1.0
1.5
2.0
1.0
1.5
2.0
AvgShortestLen
AvgShortestLen
(d) PeMSO8 T-S-T-S-T-S
(e) PeMSO8 T-S-T-T-S-T
Figure 4: Skip understanding different spatio-temporal orders and different datasets. For (b)(c)
normalize performances to show them in a colormap. The darker the circle, the better the performance.
Rank
Bank
Kipl
Cheb
Mixhoa
40
(a) and T Channel
(b) TCN dilation
(c)
GCN choice
(d) Node degree
Figure 5: Rankings several design choices. lower rank means better performance.
5 Searching Better STGNN Models in Simplified Way
5.1 A simplified but strong NAS baseline
Here, to give an example on how to leverage these understandings, we show simple but strong NAS baseline based on Random Search (RS) that is able to find better STGNN models efficiently, titled SimpleSTG as illustrated in Figure 6 We use random search with the cherry regions found by understanding results on typical datasets. Specifically, we evaluate a random sample if it lies in regions, otherwise reject and re-sample. Note that more complex search strategics leveraging our understanding surely exists and probably will be more efficient than our simple baseline, e.g. Evolutionary, Bayesian or even differentiable. But goal is to demonstrate how to utilize understanding and how effective it could be to design architectures with better understandings. We stick to this baseline for further comparison.
5.2 Overall performance comparison
In this part, we compare more thoroughly our models with related works. From Table 3 incoporating architecture priors, the proposed simple bascline could find novel STGNN models better than hand-designod and NAS-based methods. The other baselines are introduced follows. Vector Auto- nnto-Regression (VAR) is a baseline often for sanity check.

---

Published in Transactions on Machine Learning Research (01/2023)
New dataset
Eval
Space of ST order and skip
Sample
in Cherry Region?
Reduocd space of hyperparameters and ST design
Sample
Model
New dataset
New dataset
Understanding
Typical datasets
Figure Illustration of the pipeline in our simple random search baseline SimpleSTG.
ASTGCN (Guo et al.
2019 adopts attention mechanism for both spatial and temporal modeling, STS-
GCN (Song et al. 2020
proposes synchronous modules to leverage the heterogeneities in spatial-temporal data. 2020 stacks multiple localized GCN for extraction of correlations. STGODE (Fang el al. 2021 uses lensor-based ordinary differential equation. Z-GCNETs (Chen et. al. 2021b) is GRU-based and introduces a time zigzag persistence to integrate with GCN, Others have been discussed in Section 1.
STSGCN [Sog et al.
Note that there are many NAS methods for pure GNN such as (Li et al. 2021b Zhao et al,, 2021 These methods cannot be used directly in STGNN because of the difference in search space.
Table 3: Prediction performance comparison of different models. Bold number denotes the best and underscored number denotes the second best. Numbers in the parentheses indicate the standard deviation.
Model
PeMS03
PeMS04
PeMS07
PcMS08
MAE
RMSE
MAE
RMSE
MAE
RMSE
MAE
RMSE
VAR
23.65(0.00)
38.26(0.00)
23. 23,7000
36.66ro.00)
75.63(0.00)
115.2(0.00)
23.46((.00)
36.33(0.00)
STGCN
30. (7.49(0.46)
22. 22(004)))4)
35.55(0.75)
28.38(0.29)
38. 78(0.58)
27. 27.83(0.20) (8.02(0.14)
DCRNN
18, 18)0.1))
(0.25
24.70((0.22)
18(02()
25.30/0.52)
38.58(0.70)
27.83(0.05) 17.86(0.08)
ASTGCN
17.69(1.48)
29.66(1.68)
22.93(1.29)
35. (2.92()99))
28.05(2.30)
(2.57(3.31)
(8.61
16
STSGCN
17.48(0.15)
21.19(0.10) (0.26)
(3.65().20)
24.26(0.14)
(9.03
26.80(0.18) (7.13
AGCRN
16.58(0.10)
27. (4)
19.83(0.06)
32.26((.12)
(1.21
37.66(0.24)
(5.95(0.18)
25.22(0.22)
MTGNN
15.23(0.03)
26.12().20)
19. 19.25(0.03)
31 31.65(0.21)
21.28(0.11)
(1.31
(5.86(0.10)
21.93(0.11)
STGODE
20.84(0.00)
32.82(0.00)
(0.80
25.97
Z-GCNETs
19.90(0.00)
32.66(0.00)
16. (6.12
25.74(0.00)
STECNN
16.77(0.09)
28.34(0.46)
19. (3000))
31.88(0.14)
22.07(0.11)
35.80(0.18)
16. (0.09)
26.22 26.22(0.15)
AutoCTS
(4.47
24.54(0.33)
19. 13
30.44(0.24)
(0.93
33 69(0.9)))
(4.82(0.17)
23.64
SimpleSTG (ours) (4.45(0.10) (0.33
18.56(0.26)
30.71(0.41) 19.80 33.03
14.64 (3.77
The generalizability of the distilled principles is demonstrated in two ways. First, in Section 4 we show at the same time empirical results on two datasets and similar principles are observed. Second, Table note that we search only one model and evaluate this model on more datascts covering different regions of California (Appx Bi instead of searching the best. model per dataset as in other NAS methods. We show further the comparison datasot contains traffic information in Beijing, which is totally different from commonly used California datascts. The metric is MAE and RMSE on 15 mins, 30 mins and 60 mins prediction to comprehensively evaluate the effectiveness our our model. In almost all test cases, our baseline outperforms by large margin. We also provide evaluation on another non-traffic dataset and the configuration of searched model in Appx
new and different dataset NE-BJ released by (Li et al. 2021a). The NE-BJ
5.3 Search efficiency and effectiveness of space
We further demonstrate the effectiveness of our understanding on training hyperparameters and architectures in Figure 7 a-e) on two datasets. In the Figure 7(a), we evaluate the search efficiency in terms of GPU hours and compare NAS methods with hand designed results on dataset PeMS08. The orange line is our accelerated search in small channel and the green line the same architecture as in orange line but with large channel size. The motivation and correlation of performances with different channel sizes are illustrated in Appx D It can be found that our NAS method, though implemented with simple random search strategy, be very
10

---

Published in Transactions on Machine Learning Research (01/2023)
Table Performance comparison on NE-BJ. Bold number denotes the best and underscored number denotes the second best. Instead of avcarged 12 steps, we show results on 3/6/12 steps each for thoroughness.
Model
15 mins
mins
60 mins
MAE
RMSE
MAE
RMSE
MAE
RMSE
VAR
5.42
8.16
5.76
9.07
6.14
9.65
DCRNN
3.84
6.84
4.51
8.49
5.15
9.77
STGON
5.02
8.34
5.10
8.55
5.39
9.09
ASTGCN
4.43
7.34
5.31
8.86
6.29
10.31
AGCRN
6.81
4.55
8.32
5.06
9.54
GMAN
4.08
7.63
4.42
8.45
4.80
9.18
AutoCTS
3.91
6.70
4.69
8.21
5.64
9.80
SimpleSTG (ours)
3.71
6.69
4.33
8.21
4.85
9.34
28
RS space
26
STGNST
MAE PeMS04
MAE on PeM450
26
24
22
18.0
STOON
AutoCTS
STONN ismall
20
17.5
STONN llarge
PeMS08
17.0
DUSGEM
Redurad Sample distributions
Archi. Priors
50
100
Evallated samples (Search rounds)
16.5
STFGON
(b) Perf. dist. on PeMS04
(c) Space efficiency on PeMS04
16.0
15.5
26
26
15.0
MAt on PGMS08
MAE on PeMSO8
24
12
GPU Hours
22
(a) Search Efficiency.
20
20
RS all priors (NS-STOWW)
18
18
Sample distributions
Evallaated samples (Search rounds)
(d) Perf. dist. on PeMS08
(e) Space elficiency on PeMS08
Figure 7: Empirical results on the search efficiency and effectiveness of space.
efficient in terms of GPU hours. Note also that random search baseline is straightforward to adapt distributed systems without communication head while AutoCTS cannot easily achieve significant acceleration. In Figure (d),, we show the samples' performances in different spaces. With architecture priors and reduced hyperparameter space, the performance distribution is significantly better. In Figure (e), we show the random search efficiency considering different priors. Both plots show the effectiveness of our understanding and concluded principles.
6 Conclusion and discussion
In this work, we revisit Temeooll Graph Neural Networks in traffic prediction to study how to properly design models in a principled way. We propose framework that disentangles the choices into three groups: spatial/temp /temrrll module designs, spatio-temporal order and skip connection. We understand qualitatively and quantitatively the influence of each disjoint factor and conclude the principles behind the architecture
11

---

Published in Transactions on Machine Learning Research (01/2023)
design. To illustrate how these understandings could help find better STGNN models, propose simple strategy to efficiently and effectively search models that outperform all other works.
This work of course has limitations and could be further explored. Firstly, we limit our study scope to traffic prediction while STGNN is also used in other tasks and modalities, c.g. video action recognition, weather forecasting, etc. The STGNNs considered other communities are not. the same thus need further exploration. Besides STGNN, other neural networks might also benefit from similar cherry regions. On the other hand, consider TCN for temporal modeling in this work due to its efficiency and flexibility in architecture design. It is also interesting to consider RNN-based more unified understanding. Other future works include the introduction of differentiable search policy with the findings and the consideration of possible confounding factor or dependency of factors.
snteetioonbasett STGNN framework for
Acknowledgment
Q. Yao was in part supported by NSFC (No. 92270106) and CCF-Baidu Open Fund. This work also partially supported by the National Key Research and Development Program of China under Grant 2018AAA0101100 and Hong Kong RGC TRS
Broader Impact Statement
Our work does not contain potential harms to people, enviromment, society or any possible negative impacts listed on the TMLR Ethics Guidelines.
References
Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting. In Advances in Neural Information Processing Systems, 2020.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Gonzazz, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew M. Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, 2018.
Trwan Bello, William Fedus, Xianzhi Du, Ekin Dogus Cubuk, Aravind Srinivas, Tsung-Y Yi Lin, Jonathon Shlens, and Barret Zoph. Revisiting resnets: Improved training and scaling strategies. In Advances in Newral Information Processing Systems, 2021.
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. Drnas: Dirichlet. neural architecture search. In International Conference on Learning Representations 2021a.
Yuzhou Chen, Ignacio networks for time series forecasting. In International Conference on Machine Learning, 2021b.
and Yulia R. Gel. Z-genets: Time zigzags at graph convolutional
Kyunghyun Cho, Bart van Merrienboer, Damitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. In Eighth Workshop on Syntaz, Semantics and Structure in Statistical Translation, SSST@EMNLP. Association for Computational Linguistics, 2014.
Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen. Twins: Revisiting the design of spatial attention in vision transformers. In Advances in Neural Information Processing Systems, 2021.
Zhiyong Cui, Kristian Henrickson, Ruimin Ke, and Yinhai Wang. Traffic graph convolutional recurrent neural network: deep learning framework for network-ssale traffic learning and forecasting. IEEE Transactions Intelligent. Transportation Systems, 2020.
12

---

Published in Transactions on Machine Learning Research (01/2023)
Moshe Eliasof, Eldad Haber, and Eran Treister. PDE-GCN: novel architectures for graph neural networks motivated by partial differential equations. In Advances in Neural Information. Processing Systems, pp- 3836 3849, 2021.
Zheng Fang, Qingqing Long, Guojie Song, and Kunqing Xie. Spatial-temports graph ODE networks for traffic flow forecasting. In ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2021.
Rui Fu, Zuo Zhang, and Li Li. Using Istm and gru neural network methods for traffic flow prediction. In Youth Academic Annuul Conference of Chinese Associalion of Aulomation, 2016.
Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Revisiting deep learning models for tabular data. In Advances in Neural Information Processing Systems, 2021.
Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaïyu Wan. Attention based mnatial-tempore graph convolutional networks for traffic flow forecasting, In Association for the Advancement of Artificial Intelligence, 2019.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Computer Vision and Pallern Recognition, 2016.
Renhe Jiang, Du Yin, Zhaonan Wang, Yizhuo Wang, Jiewen Deng, Hangchen Liu, Zekun Cai, Jinliang Deng, Xuan Song, and Ryosuke Shibasaki. D1-trafT: Survey and benchmark of deep learning models for urban traffic prediction. In ACM International Conference on Information and Knowledge Management, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural compulation, 1989.
Fuxian Li, Jie Feng, Huan Yan, Guangyin Jin, Depeng Jin, and Yong Li. Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution. CoRR, 2021a.
Mengzhang Li and Zhanxing Zhu. Spatial-temporal fusion graph neural networks for traffic flow forecasting. In AAAT Conference on Artificial Intelligence, 2021.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network:
Data-driven traffic forecasting. In International Conference on Learning Representations, 2018.
Yanxi Li, Zean Wen, Yunhe Wang, and Chang Xu. One-shot graph neural architecture search with dynamic search space. In AAAI Conference on Artificial Intelligence, pp. 8510-8517, 2021b.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture scarch. In International Conference on Learning Representations, 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
Attila M. Nagy and Vilmos Simon. Survey on traffic prediction in smart cities. Peruasive and Mobile Computing, 2018.
Zheyi Pan, Songyu Ke, Xiaodu Yang, Yuxuan Liang, Yong Yu, Junbo Zhang, and Yu Zheng. AutoSTG: Neural architccture scarch for predictions of spatio-temporal graph. In The Web Conference, 2021.
Bin Ran and David Boyee Modeling dynamic transportation networks: an intelligent transportation system oriented approach. Springer Science & Business Media, 2012.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEFF Transactions on Neural Networks and Learning Systems, 2009.
13

---

Published in Transactions on Machine Learning Research (01/2023)
Chao Song, Youfang Lin, Shengnan Guo, and Huaiyu Wan. Spatial-temporal synchronous graph convolu- tional worksrks: A new framework for spatial-temporal network data forecasting. In Associalion for the Advancement of Artificial Intelligence, 2020.
Mingxing Tan and Quoc V. Te. Efficientnet: Rethinking model scaling for convolutional neural networks. Tn International Conference on Machine Learning, 2019.
Leye Wang, Di Chai, Xuanzhe Liu, Liyue Chen, and Kai Chen. Exploring the generalizability spatio- temporal traffic prodiction: Mota-modcling and an analytic framework. IEEE Transactions on Knowledge and Dala Engineering, 2021.
Colin White, Arber Zela, Robin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? In Advances in Neural Information Processing Systems, pp. 08454-28469, 2021.
Xinle Wu, Dalin Zhang, Chenjuan Guo, Chaoyang He, Bin Yang, and Christian S. Jemsen. Autocts: Automated correlated time series forecasting. International Conference on Very Large Data Bases, 2021.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chongqi Zhang. Connecting the dots: Multivariate time series forecasting with graph neural networks. In ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2020.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In International Conference on Learning Representations. OpenReview.net, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, 2018.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In Advances in Newral Information Processing Systems, 2020.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In International Joint Conference on Artificial Intelligence, 2018.
Haiyang Yu, Zhihai Wu, Shuqin Wang, Yumpeng Wang, and Xiaolei Ma. Spatiotemporal recurrent convolu- tional networks for traffic prediction in transportation networks. Sensors, 2017.
H. Zare Moayedi and M.A. Masnadi-Shirazi. Arima model for network traffic prediction and anomaly detection. In International Symposium on Information Technology, 2008
Junping Zhang, Yui-Yue Wang, Kunfeng Wang, Wei-Hua Lin, Xin Xu, and Cheng Chen. Data-driven intelligent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 2011.
Yongqi Zhang, Zhanke Zhou, Quanming Yao, and Yong Li. Efficient hyper- paprr-paraaete search for knowledge graph embedding. In Anaual Meeling of the Association for Computational Linguistics, pp. 2715-2735, 2022.
Huan Zhao, Quanming Yao, and Weiwei Tu. Search aggregate neighborhood for graph neural network. In IEFE International Conference on Data Engineering, pp. 552-563, 2021.
Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, and Jianzhong Qi. GMAN: A graph multi-attention network for traffic prediction. In AAAI Conference on Artificial Intelligence, 2020.
14

---

Published in Transactions on Machine Learning Research (01/2023)
A Related works
Our proposed framework differs from existing works as follows. DI-TTraf (Jiang et al. 2021) surveys the literature and proposes framework based the modeling method spatial axis and temporal axis (e.g., CNN, GRU, GNN, etc.). DGCRN (Li et al. 2021a) considers additional spatial topology construction and external features to classify different methods. STMeta (Wang ct al. 2021) proposes another analytical framework concerning consider macroscopic factors and training hyperparameters. The purpose of our framework is also different because we use our framework to understand the architecture space which potentially facilitates further architecture search. On the other hand, AutoCTS (Wu et al. (021) and AutoSTG (Pan et al., 2021) proposes their own framework of STGNN to search architectures, but they do not consider skip connection training hyperparameters. AutoCTS and AutoSTG do not try to understand the space.
information modeling. Our framework differs from then in that we also
Our methodologies of understanding have been inspired by many other works, including architecture understanding in Convolution Neural Networks, Graph Neural Networks and Neural Architecture Search (You et al. 2020), different communities' common discovery that training hyperparameters once well tuned can boost the model performance by a large margin and probably influence the models' evaluation (Tan Le 2019 You et al., 2020). Previous works on surveys, benchmarks, and NAS of traffic prediction should also be credited, discussed in the previous paragraph.
B Details on the datasets and problem setting
B.1 Dataset
To evaluate quantitatively the performance of different models, we experiment on four public real world datasets: PeMS03, PeMS04, PeMS07 and PeMS08 (Guo et al. 2019 Song et al., 2020 Bai et al., 2020 Fang et al. 2021 These datasets can be accessed GitHutt These datasets come from Caltrans Performance Mcasurement System (PeMS) and contain the mcasures of highway traffic flow in different regions. The raw temporal signal was recorded every 30 seconds and we aggregate both datasets into 5-mins regular traffic measures the same way as previous works. Detailed statistics are given in Table 5 Datasets are splitted in a 6,2,2 manner. A standard z-score normalization is applied which subtracts and divides data by mean and standard deviation of training split. We DO NOT include additional hand-craft features e.g. calendar, holiday time of the day. In all our experiments of Section 4, we both PeMS04 and PeMS08 for understanding general principles. In Section 5, show overall model performance comparisons all these four datasets.
Table 5: Dataset statistics
Dataset
Region
Timestamps
#Sensors
Time Period
PeMS03
Marysville
26208
358
01/09/2018
30/11/2018
PeMS04
Oakland
16992
307
01/01/2018 28/02/2016
PeMSO7
Los Angeles
28224
883
01/05/2017 31/08/2011
PeMSO8
San Bernardino
17856
170
01/07/2016 31 31/08/2016
B.2 Problem setting
In Section 2, we give formal problem definition on spalio-temporal traffic prediction. In practice, following
the literatue (Yu et al. 2017 Cui et al.) 2020 Bai et al.) 2020 Wu et al., 2020). we set P = Q = 12, ie.., predicting the next one hour based on past hour. Concretely, if we predict on dataset PeMS04 from Table 5 the input tensor is of shape: (307, 12, 1) and the output tensir is of shape: (307, 12, 1). the channels of traffic signal feature. Since we do not include additional calendar hand-designed features, this channel remains 1.
15

---

Published in Transactions on Machine Learning Research (01/2023)
5
Rank
Hank
Bank
2
1
1e.4
le:2
(a) Learning rate
(b) Optimizer
(c) Weight decay
(d) Dropout
Rank
2
166
32
64
128
None
(e) Batch size
(f) Gradient clip
(g) Curriculum learning
Figure 8: Rankings of different training hyperparameters. A lower rank means better performance. The more choice ranks first, the better it is in terms of distribution.
C Details on the disentangled framework
C.1 Curriculum learning
As pointed out by (Wu et al. 2020 Li et al. 2021a curriculum learning improves consistently the multi-step prediction. To use curriculum learning in traffic prediction, we first start with one step prediction with all training data (easiest task) and gradually increase the prediction horizon to deal with more difficult task. This curriculum learning strategy brings another hyperparameter: mumber of epochs to increase the task difficulty.
C.2 Calculation of skip connection choices
We have in total (--1(2=))) skip connection choices where is number of modules (including input module, spatio-temporal modules, and output module). The first module has (L 2) skip placeholders. The second module has (L- - 3) skip placeholders, and on. In the case of modules (6 spatio-temporal module plus input and output module), will have space of 26+3+4+342+1 = 2 2.09 millions choices.
D Details on the understanding results
D.1 More observations on training hyperparameters
Additional interesting observations could be made in Figure 2
For example, batch size 64 which most
literature uses is worst in our ranking The optimizer AdamW [Loshchilov & Hutter 2019) not considered by any literature in traffic prediction but showed best our rank. All these give evidences to certain biases in training hyperparameters. As a result, compare fairly different model architectures, we need take into account the training hyperparameters.
D.2 More on spatial/temporal module design
Different choices spatial/temporal module influence the way the spatial/temporal representation are processed. In the literature, diverse modifications on TCN and GCN have been proposed. With limited ablation study, is hard to conclude which part really contributes the performance gain, thus hinder our understanding spatio-temporal modeling.
16

---

Published in Transactions on Machine Learning Research (01/2023)
Renk
Rank
Kipf
Cheb
Mixhop
(a) and T Channel
(b) TCN dilation
(c) Kernel force
(d)
GCN choice
Bank
Rank
(e)
Embedding
(f) Node degree k
(g) Mixture coefficient
Figure 9: Rankings of different design choices. lower rank means better performance.
We use the same ranking distribution in understanding training hyperparameters to study all the module choices. Due to the huge impact on model parameters, we study in addition the channel correlation whose detailed plots are Appendix D
The full ranking plots are shown in Figure g Firstly, except for spatial/tempora channels, most designs from the literature are useful. We remove few bad options according the ranking, e.g., Cheb GCN, zero mixture coefficient, etc. Then, spatial/temporal channel influences lot the trainable parameters and shows consistent goodness in Figure 9 9a),, study further the performance correlation between channel 64 and channel 32. We find that channel 32 reaches correlation to 0.85 with channel 64 while having only half of the parameters. Thus, we use channel 32 for all the intermediate study for acceleration and change back to for final evaluation.
D.3 More on channel correlation
We have found Section 4 that channel rank is very significant, i.e., larger channel gives better performance. Actually, it is usually believed that larger channels can perform better but also bring trainable parameters (Tan & Le 2019). Thus, after ranking them, consider in addition to study the performance correlation between different channel choices to understand its impact and further opens the possibility to scale down models to accelerate the execution without messing up models' relative performance. We choose spatial module channel to the same as temporal module channel for simplicity.
First, the channel correlation can be visualized Figure 10 PeMS08), channel 32 achieves high performance correlation with channel 64 while the correlation between channel 16 and channel 64 not stable. On the other hand, channel 32 already reduces half of the trainable parameters compared to channel 64 and significantly lowers the training time cost. As result, will use channel 32 for the understanding study except for the final performance comparison where we use channel 64.
We show that on both datascts (PcMS04 and
D.4 More the chosen measures
Note that other measures exist but may not be the most appropriate in our study. In the example of skip connection, shortest length from input module output module reflects also where we skip. But we can only distinguish the case of shortest length and the other (because we have too many cases that coincidence on shortest length 2) which is not informative enough.
17

---

Published in Transactions on Machine Learning Research (01/2023)
64
1
0.85
0.75
64
1
0.81
0.57
32
0.85
0.89
32
0.81
0.62
16
0.75
0.89
16
0.57
0.62
64
32
16
64
32
16
(a) Spatio-temporal channel on PeMS04
(b) Spatio-temporal channel on PeMS08
Figure 10: Performance correlation with different channels.
D.5 More the skip connection experiments
To better understand the impact of skip patterns, we fix the other parts of the framework. In this part, we study the case of 6 spatial tential/emmpral modules thus N is 8. As by calculation in Appendix C we explore the skip space of 2 = 2907152 choices. For a certain dataset and certain fixed the other configuration, we randomly sample among these two million choices and record their performance with the above mentioned measures.
E
Details the searched model
E.1
Configuration of searched model
The found best model on PeMS08 uses the following configuration. Learning rate 1e-3; Batch size 128; Optimizer AdamW; Weight decay 0; Gradient clip 5; Dropout 0.3; Curriculum learning or 5; Temporal channels 64; Dilation 1; Kernet set 7,8; GCN channels 64; Graph convolution Mixhop GCN; Embedding dim 20; Node degree 40; Mixture coefficient 0.75.
E.2 Evaluation metric
Following the literatue Yu et al. 2017 Cui et al. 2020 Bai et al. 2020 Wu et al. 2020), we use past 12 steps to predict next 12 steps. Both metrise MAE and RMSE are cal calculated as the average over future 12 steps. Each step is 5min so we are predicting one hour ahead using past hour. In Sec 5, we also give results on 3/6/12 12 steps (15/30/60 mins) to compare more thoroughly.
E.3 More on the compared baselines
When running MTGNN, we notice that applies step-number-based curriculum learning, If apply directly other datasets of different size, it will not be able to train all 12 prediction steps and perform poorly. As result, we increase the epochs to 200 instead of 100 to have MTGNN trained on full 12 horizons. We leave other typerparameters as default. Our executed results are close to the reproduced ones from AutoCTS (Wu et al. 2021).
MTGNN.
AutoSTG. We find two works of AutoML applied STGNN modeling, AutoCTS and AutoSTG. We compare only with AutoCTR because AutoSTG requires additional meta information from geographic database construct their model which largely limits their applicability, as noted by AutoCTS (Wu et al. 2021
18

---

Published in Transactions on Machine Learning Research (01/2023)
E.4 Parameter comparison
During our study, also notice that the searched models are larger in terms of trainable parameters. In the literature, STGNN models are often smaller than 1 million(M) parameters while our searched model has parameters of 1.7M. To compare more fairly and understand better the models, we experiment further and show two things (1) more parameters do not always help (2) by compressing our searched model to same level of parameters with literature, we can still outperform them indicating our other choices of architecture indeed help. The results is summarized in Table
Table 6: Prediction performance comparison with models of different scale (Dataset PeMS08).
Model
# Param
RMSE MAE
AGCRN
0.8M
15.95
25.22
AGCRN (large)
1.8M
16.56
26.43
MTGNN
0.4M
15.86
24.72
MTGNN (large)
1.9M
16.02
25.30
Our searched model (ch=16)
0.4M
15.13
24.13
Our searched model (ch-32)
0.8M
15.04
24.03
Our searched model (ch=64)
1.7M
14.75
23.82
E.5
Evaluation on non-traffic dataset
To even further evaluate the generalization of our method, we use another non-traffic dataset "Flectricity" Wu al.
2021 and measure on 3/6/12 steps as well average over 12 steps.
Table 7: Performance comparison on Electricity.
Model
Average
3 steps
6 steps
12 steps
MAE
RMSE
MAE
RMSE
MAE
RMSE
MAE
RMSE
STGCN
423.1
3923.9
350.5
3706.5
414.3
3918.4
479.8
4111.2
DCRNN
400.5
3640.3
320.6
3356.5
380.8
3634.3
461.2
3919.6
AGCRN
297.1
2353.1
274.6
2066.6
304.3
2329.4
312.4
2475.4
MTGNN
261.0
2624.4
238.6
2331.3
267.9
2631.5
283.9
2867.7
AutoCTS
255.4
2101.6
230.9
1986.5
258.4
2115.9
277.1
2256.3
SimpleSTG (ours)
222.9
1926.9
214.8
1835.7
218.5
1843.7
238.0
2083.6
Improvement(%)
12.7
8.3
15.4
12.9
14.1
7.7
19


Reviews:
[{"review_id": "xsJBYwiHjK", "reviewer": "Reviewer_ZRsh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- In the design of their framework, the authors consider and analyze much prior knowledge special for STGNNs, such as the spatio-temporal order.\n\n- The efficiency of evaluation and fairness of comparison is crucial for NAS methods. Their integration of training hyperparameters into the search framework is necessary and meaningful.\n\nWeaknesses:\n\n- The authors introduce the concept of \"cherry region\", which seems interesting. However, it is rarely discussed in the paper (only mentioned twice). Although empirical evidence is provided in Figures 3 and 4, it would be better to also provide more in-depth insights into them. For example, why do those regions exist, does this phenomenon widely exist, and how can this phenomenon influence future studies?\n- There is only one NAS method (i.e., AutoCTS) in the performance comparison in Table 3, which makes the experiment relatively weak. It would be better to include and discuss more NAS methods for GNNs, such as [1, 2].\n\nReference:\n\n[1] Y. Gao, et al., \"Graph Neural Architecture Search\", In IJCAI, 2020.\n\n[2] Y. Li, et al., \"One-shot Graph Neural Architecture Search with Dynamic Search Space\", In AAAI, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a Neural Architecture Search (NAS) method to design Spatio-Temporal Graph Neural Networks (STGNNs). They mainly deal with two issues. Firstly, they propose a fair and fast comparison of diverse architectures by integrating the examination of training hyperparameters into their NAS framework. Secondly, they solve the problem of large-scale search space by disentangling it into three disjoint angles. Their method is compared to several hand designed architectures and a searched architecture.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address problems in \"Weaknesses\" as mentioned above.", "broader_impact_concerns": "No further concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YTDUCObtF6", "reviewer": "Reviewer_dhML", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The authors have addressed the issues raised by previous works and have taken training hyperparameters search into account for their NAS framework.\n- Additionally, they proposed four key modules for their NAS framework and conducted comprehensive studies for each one, which provides some insight to understand the\n behavior of architectures.\n- The authors utilized the above findings to minimize the hyperparameter search space and their experimental results demonstrate the superior performance compared to the most recent baseline approaches.\n\nWeaknesses:\n- At a high level, I am somewhat confused by the framework's design, particularly for Section 4. If we use a different dataset, do we need to repeat all experiments to find a reduced search space?\n- In Section 2, the problem formulation is not well-explained and seems confusing to me. For example, what is the definition/formulation for L? Why is $D_{train}$ in the inner problem of bi-level formulation and $D_{val}$ in the outer problem? \n- In Figure 2 and 5, the outer shape of each error bar is confusing to me. What does this irregular shape mean? Some explanations regarding the notations and interpretation need to be provided.\n- The conclusion regarding transferability lacks sufficient support. The authors used two highway traffic flow datasets for experiments to validate the transferability. Nevertheless, these datasets are too similar (although with different regions, timestamps, and sensors). \n- Table 3 lacks proper notation. The authors should mention or explain the bold and underscored numbers.  \n- Time comparison of different NAS approaches. AutoCTS seems to have a competitive performance; it would be interesting to compare the actual time cost for each approach to find the optimal network.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper highlights two issues in the current NAS literature for spatial-temporal (ST) problems: 1) Hyperparameters are not considered in the NAS framework. 2) The search space is too large. Instead, the authors proposed a disentangled Spatial-Temporal GNN framework that takes into account training hyperparameter search and introduced four additional search components: Spatial-Temporal module order, Skip connection, Spatial module, and Temporal module. Later, comprehensive studies and detailed analysis were conducted for each component. Lastly, they used these empirical findings to refine the hyperparameter search space and used random search on the reduced space to find the optimal network. Their results demonstrated that the proposed framework outperforms the existing baselines by hand-designed and automatically searched networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This is an interesting work, however, I would like the authors to address some of my concerns in the weakness, such as 1, 2, 4, 6. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bGuebzyPO7", "reviewer": "Reviewer_D4kp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nS1. This paper is well-written and easy to follow.\n\nS2. This manuscript conducts extensive experiments and concludes with some meaningful rules.\n\nS3. The new proposed algorithm achieves significant improvements beyond Non-NAS methods.\n\nWeaknesses:\nW1. The technical contribution of this article seems weak. From my experience in designing STGNNs, the reduced scope of hyperparameters is actually the best practice, and the same situation also occurs in the following topics. Therefore, it does not give me any extra information. This work is more like a technical report.\n\nW2. The results are not very convincing. It is common that the random seed affects neural networks a lot. Compared with a worse seed, a better seed may achieve over 20% improvements. For each set of hyperparameters, it would be good if the experiments can be repeated with several different random seeds. Moreover, statistical significance should be provided as well.\n\nW3. This article lacks an analysis of time consumption. \n\nW4. As far as I know, there are many studies modeling the spatio-temporal dependencies in a joint manner, instead of factorizing them. It would be good to add this joint ST module into the search space.\n\nMinor issues:\n\nW5. The paper claims that we do not include parallel connections here because such designs do not perform well. However, it doesn't provide any evidence here.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on improving STGNN with Neural Architecture Search (NAS). It first provides several guidelines for designing STGNNs and then presents a NAS-based algorithm based on the proposed rules.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to W2 and W3", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DajwkRyRbY", "reviewer": "Reviewer_J7Cd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- The paper conducts a comprehensive study to identify the optimal range for each factor in the search space. The resulting reduced search space becomes very effective that a simple random search produces strong results.\n- The study itself can be considered as a generic preprocessing step for NAS search space reduction, which by itself serves as a contribution to the community.\n- Empirically, the discovered architecture demonstrates mostly superior performance compared with the prior NAS method, taking into the fact that the author considers the transfer setting, which is more practical but puts the proposed method at a potential disadvantage.\n\nweakness:\n\n- Disentangling factors during search space pruning does improve efficiency. However, doing it also discards conditioning between factors, if I understand it correctly. For example, the optimal weight decay distribution depends on the learning rate.\n- I might've missed a point here about the computing ranking distributions for each factor. When studying one factor, how do you set the other factor? More concretely, take hyperparameters as an example; When plotting Figure 2.a, are other factors (e.g., skip connection) sampled at random?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies automated architecture design for Spatio-Temporal Graph Neural Networks.\nConcretely, the author identifies four factors of the search space design for this particular architecture, including hyperparameters, Spatio-temporal orders, skip connections, and spatial and temporal modules.\nThen the author studies the optimal range of these factors respectively, thereby reducing their choices and hence the search space size.\nThe resulting search space is efficient enough that a simple random search produces strong results.\nThe proposed method can be viewed as a search space pruning technique that is generically applicable to NAS.\nEmpirically, the discovered architecture outperforms prior searched architectures on 6 out of 8 scenarios, but the results are stronger than it seems as the author considers transfer setting, whereas prior work tailors one architecture for every dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- \"hyperparamters\" typo in 4.1 para 1\n- the distributional formulation of the NAS objective resembles DrNAS [1]. I encourage the author to mention it as well.\n\n[1] Chen et al. DrNAS: Dirichlet Neural Architecture Search. ICLR 2021.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduced neural architecture search for the design of  Spatio-Temporal Graph Neural Networks (STGNNs).  The authors highlighted the importance of hyperparameters in STGNNs and conducted comprehensive experiments for the evaluation. Another contribution is to address the large search space issue through a random search on the refined search space. All reviewers are happy with the authors' responses. But also some concerns were pointed out, e.g., the limited improvement over baseline AutoCTS. The authors noticed the literature on NAS for pure GNNs, but explained the difference between search spaces prevents a possible comparison. It is true that these existing NAS works are mostly about search strategies, while this paper focuses more on the search space. But it would be much more complete and convincing to include some relevant discussion or empirical study to suggest that a study on search space in this paper is really necessary and of significance, by comparing with those works on search strategies. 
Decision: Accept (poster)