# Easy Begun is Half Done:
Spatial-Temporal Graph Modeling with ST-Curriculum Dropout

Hongjun Wang1,2§, Jiyuan Chen1,2§, Tong Pan1,2,3, Zipei Fan4 $\dagger$, Boyuan
Zhang1,2 Renhe Jiang4,5, Lingyu Zhang1,2, Yi Xie6, Zhongyi Wang6, and Xuan
Song1,2$\dagger$,

###### Abstract

Spatial-temporal (ST) graph modeling, such as traffic speed forecasting and
taxi demand prediction, is an important task in deep learning area. However,
for the nodes in graph, their ST patterns can vary greatly in difficulties for
modeling, owning to the heterogeneous nature of ST data. We argue that
unveiling the nodes to the model in a meaningful order, from easy to complex,
can provide performance improvements over traditional training procedure. The
idea has its root in Curriculum Learning (Bengio et al. 2009) which suggests
in the early stage of training models can be sensitive to noise and difficult
samples. In this paper, we propose ST-Curriculum Dropout, a novel and easy-to-
implement strategy for spatial-temporal graph modeling. Specifically, we
evaluate the learning difficulty of each node in high-level feature space and
drop those difficult ones out to ensure the model only needs to handle
fundamental ST relations at the beginning, before gradually moving to hard
ones. Our strategy can be applied to any canonical deep learning architecture
without extra trainable parameters, and extensive experiments on a wide range
of datasets are conducted to illustrate that, by controlling the difficulty
level of ST relations as the training progresses, the model is able to capture
better representation of the data and thus yields better generalization.

§§footnotetext: Equal contribution.$\dagger$$\dagger$footnotetext:
Corresponding to: Zipei Fan<EMAIL_ADDRESS>and Xuan Song
(songx@sustech.edu.cn).

## INTRODUCTION

Figure 1: Speed data visualization in METR-LA dataset.

With the advances in deep learning techniques such as Convolutional Neural
Network (CNN) and Graph Neural Networks (GNN), spatial-temporal graph modeling
has been receiving increasing attention. The basic assumption behind it is
that a node’s future state is conditioned on its historical state as well as
its spatial neighbors’ historical state (Wu et al. 2019). Thus, the modeling
target seeks to discover both the node-level spatial inter-dependent relations
and the node’s self-dependent temporal relations. The task has many real-world
applications like traffic speed forecasting (Yu, Yin, and Zhu 2017) and human
action recognition (Yan, Xiong, and Lin 2018).

While plenty of attention has been devoted to designing more sophisticated
model architectures so as to capture better ST relations, we are convinced
that it’s also valuable to take a step back and focus on an essential yet
easily-overlooked question: Can we simply use a more advanced training
strategy to improve model performances?  Almost all the existing work in ST
modeling tends to treat the nodes in the graph equally and feed them into the
neural network. However, chances are that the difficulty of modeling a node’s
ST pattern can vary greatly. Figure 1 (a), (b) and (c) show the regular speed
pattern of nodes in METR-LA dataset (Li et al. 2017), which demonstrate that
most of the nodes are only significantly affected by the morning and/or
evening peaks, when heavy traffic congestions might happen. These regular
temporal patterns are easy for models to learn. Nevertheless, Figure 1 (d)
shows an example of nodes whose speed patterns are highly disordered and
unpredictable, and their data representation can be very different from the
majority of nodes. This is an irregular one which is hard to model. For Figure
1 (e) and (f), as we mentioned before, ST graph modeling also relies on the
node-level spatial inter dependency. Figure 1 (e) shows the circumstance where
a node (red line) and its first-order spatial neighbors’ (blue lines) speed
patterns are very alike. This spatial relation without doubt can be easily
captured by the model, while Figure 1 (f) shows the opposite way where the
node (red line) doesn’t share the same trend as its neighbors (blue lines).
Although in Figure 1 (f) the temporal speed patterns of both the node and its
neighbors are easy to learn, their spatial relations can be confusing for the
model especially at early training stages. Extensive research has suggested
that presenting the training samples in a meaningful order, from easy to hard,
can benefit the training process and such strategy is referred to as
Curriculum Learning (Kumar, Packer, and Koller 2010; Xu et al. 2020; Wang et
al. 2021).

Curriculum Learning (CL) follows the intuitions of humans: learning should
start with the fundamental knowledge and then gradually build on that to
handle more complicated ones. The idea is first proposed by (Bengio et al.
2009) and we’ve witnessed its successful applications in many fields like
image classification (Srivastava et al. 2014), text classification (Ma et al.
2017) and object segmentation (Kumar et al. 2011). From the view of
optimization, curriculum learning excludes the impacts from difficult or even
noisy samples at the early stage of training when the model is vulnerable, and
is thus able to prevent the model from getting stuck in bad local minima,
making it converge faster and reach a better solution than the standard
approach. The success of curriculum learning, especially in highly non-convex
deep models, gives us the motivation to introduce it into the task of spatial-
temporal graph modeling, and to the best of our knowledge, such an idea still
remains unexplored.

In previous work, the smallest unit to be assigned a difficulty level is a
data sample (e.g., for image classification, a data sample should be a single
image), and the curriculum is built by progressively increasing the difficulty
threshold for input data. However, in the context of spatial-temporal graph
modeling, a data sample is a graph consisting of multiple spatially-connected
nodes with their temporal features. Therefore, it is hard to rank two data
samples’ difficulties when one’s nodes suffer from messy spatial relations,
and the others’ nodes suffer from terribly orderless temporal patterns. In a
word, as a graph, the data sample here lacks the necessary atomicity to be
analyzed as a whole. On the contrary, we find that the node in graph is atomic
and itself contains sufficient ST information (spatial neighborhood
relationships in spatial view and its own time series values in temporal
view). Therefore, unlike previous work, we innovatively set the smallest unit
as a node instead of the whole graph and define our curriculum as gradually
introducing the nodes with complex ST relations to the model.

The key challenge towards utilizing curriculum learning lies in determining
easy/hard nodes. In this paper, we propose to evaluate the difficulty of nodes
in high dimensional feature space. Specifically, we define easy nodes as those
whose data representations locate in high-density area of the feature space
and are consistent with their spatial neighbors on graph (we denote the
neighbors on graph as G-neighbors for simplicity). Conversely, difficult nodes
have their data representation either solitarily far away from the majority or
inconsistent with its $G$-neighbors. Then based on these difficulty scores, we
propose our ST-Curriculum Dropout as a novel training strategy specially for
spatial-temporal graph modeling. The idea is inspired by (Sinha, Garg, and
Larochelle 2020) which smooths the feature space with a continuously weakened
Gaussian kernel. We take a braver step by directly dropping out the nodes with
sophisticated ST relations at the early stage of training, such that the model
can only propagate and learn the most fundamental ST relations. We further
propose a smooth curriculum arrangement function to progressively introduce
harder nodes into the model, allowing at each training step, the model can
focus on “interesting” ST relations, that are near its border of capability,
neither too easy nor too hard, to expand the border gradually.

The main contributions in this paper are listed as follows:

  * $\bullet$

We explore and make novel adaptions of CL into spatial-temporal graph
modeling. To the best of our knowledge, this is the first time curriculum
learning is proven to be prospective in such a task.

  * $\bullet$

We propose a novel CL training strategy, which can also be formulated as an
external plug-in for canonical deep learning models, along with a smooth CL
arrangement function for ST graph modeling task.

  * $\bullet$

We obtained universal performance gain on a wide range of real-world datasets,
illustrating the effectiveness of our design.

## Preliminaries

Figure 2: The schematic of ST-Curriculum Dropout is shown above as a plug-in
to deep learning models. In high-level feature space, nodes with difficult ST-
relations will be dropped out at a certain ratio to “denoise” the data,
ensuring a smoother objective for the model to optimize at early training
stages. The ratio to retain difficult nodes will be progressively increased
during training until the overall utilization.

###### Definition 1

Graph. In this paper, a graph is represented as
$\mathcal{G}=(\mathcal{V},\mathcal{E},A)$, where $\mathcal{V}$ denotes the set
of nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ indicates the set
of edges, and $A$ is the adjacency matrix derived from graph $\mathcal{G}$. At
each time step $t$, the graph $\mathcal{G}$ has a dynamic feature matrix
$\mathbf{X}_{t}\in\mathbb{R}^{|\mathcal{V}|\times\mathcal{D}}$ and
$\mathcal{D}$ is the dimension of node features. ††The related work of this
paper is included in Appendix A.1

###### Definition 2

Spatial-Temporal Graph Modeling. Given a graph $\mathcal{G}$ and its N step
historical observation $\mathbf{X}_{t-N:t}$, the task of ST graph modeling is
to learn a neural network $f$ which is able to predict the future $S$ step
graph features $\overline{\mathbf{X}}_{t+1:t+S}$. We summarize the mapping
relation as:

$f:\left[\mathbf{X}_{(t-N):t},\mathcal{G}\right]\mapsto\overline{\mathbf{X}}_{(t+1):(t+S)}.$

## METHODOLOGY

In this section, we decompose our ST-Curriculum Dropout (abbreviated as STC-
Dropout) into two stages: Difficulty Evaluation and Curriculum Learning. In
the first stage, each node in graph will be assigned a score reflecting its
difficulty of ST relations. This is done by measuring both a node’s data
distribution density (temporal view) and its consistency with $G$-neighbors
(spatial view). In the second stage, based on these scores, nodes are exposed
to the model in an easy-to-difficult fashion, resulting in the final
curriculum that the model will be trained on. The schematic of our method is
shown in Figure 2 as a plug-in and the details will be elaborated next.

### Difficulty Evaluation

At the core of our idea is to develop a general difficulty evaluation
justified for all possible models in spatial-temporal graph modeling tasks,
even though in this paper only GNNs are conducted as an example. We analyze
the nodes’ high-level representations retrieved from previous layers in the
model. Here, one might question why we don’t directly analyze the original
data itself rather than its high-level representation. However, this is non-
trivial since models always encode the data through advanced non-linear
transformations, so what might seem reasonable to a human in the original data
might not be considered the same way by the model in its high-dimension
feature space. Therefore, we argue that the difficulty scores should be
derived from the high-level data representation inside the model so that we
can “eliminate” what the model itself thinks difficult or disturbing to its
training. This idea shares a consensus with Self-Paced-Learning (Kumar,
Packer, and Koller 2010), where the author claims the models should take
charge in deciding the difficulties of samples.

With the node’s high-level representation which infers the specific semantic
information perceived by the model, we can now evaluate the difficulties. For
the sake of clarity, let’s first remind the basic assumption of ST graph
modeling: a node’s future state is conditioned on its historical state as well
as its $G$-neighbors’ historical state. Intuitively, the easier nodes should
be consistent with $G$-neighbors (spatial view) and have their high-level data
representations in the high density area of the distribution (temporal view).
On the contrary, more difficult nodes should be the ones either have data
representation solitarily far away from the majority or are inconsistent with
its $G$-neighbors.

Formally, let $h^{(l)}\in\mathbb{R}^{|\mathcal{V}|\times d^{(l)}}$ indicate
the $d^{(l)}$-dimensional data representation of all nodes, which is generated
by the $(l-1)^{th}$ layer $f^{(l-1)}$ with $h^{(l-1)}$ as

$\displaystyle h^{(l)}=f^{(l-1)}(h^{(l-1)}).$ (1)

For node $v_{i}$ and its representation $h^{(l)}_{i}\in\mathbb{R}^{d^{(l)}}$,
we build a $d^{(l)}$-dimensional ball with radius $R$ centered at
$h^{(l)}_{i}$:

$\displaystyle\mathcal{B}\left(h^{(l)}_{i},R\right)=\left\\{h^{(l)}_{j}\mid
D(h^{(l)}_{j},~{}h^{(l)}_{i})\leq R\right\\},$ (2)

where $D$ is the distance function. We normalize the vectors here to eliminate
the effect of variances along different directions and apply Cosine Distance
to alleviate the curse of dimensionality in high-level feature space. Then, in
order to measure the node’s consistency with $G$-neighbors, we here further
introduce the concept of $k$ order neighbors.

###### Definition 3

$k$ order neighbors. If node $v_{j}$ is a $k$ order neighbor of node $v_{i}$
on graph $\mathcal{G}$, there exists a path $P_{v_{i}\rightarrow
v_{j}}:v_{i}\rightarrow v_{m}\rightarrow\cdots\rightarrow v_{j}$ which
satisfies $|P_{v_{i}\rightarrow v_{j}}|-1\leq k$.

Let $\Omega_{v_{i}}^{k}=\\{v_{j}\mid|P_{v_{i}\rightarrow v_{j}}|-1\leq k\\}$
denotes the set of nodes being the $k$ order neighbors of $v_{i}$, an
indicator function $\mathcal{I}$ can be further defined as

$\mathcal{I}_{v_{i}}(v_{j},\Omega_{v_{i}}^{k})=\left\\{\begin{aligned}
1,&\qquad v_{j}\in\mathcal{B}\left(h^{(l)}_{i},R\right)\wedge
v_{j}\in\Omega_{v_{i}}^{k}\\\ 0,&\qquad\text{otherwise}\end{aligned}\right.$

We can now count the portion of node $v_{i}$’s $k$ order neighbors which are
wrapped by the ball $\mathcal{B}\left(h^{(l)}_{i},R\right)$ as:

$\displaystyle\frac{1}{\mid\Omega_{v_{i}}^{k}\mid}\sum_{v_{j}\in\mathcal{V}}\mathcal{I}_{v_{i}}(v_{j},\Omega_{v_{i}}^{k}).$
(3)

Intuitively, the higher the fraction of node $v_{i}$’s $k$ order neighbors
captured by the ball, the more consistent $v_{i}$ should be with its
$G$-neighbors, which indicates an easier spatial relation for the model to
capture. However, for different nodes, their data distribution density (i.e.,
if a node’s high-level data representation are intensively surrounded by many
of others) can vary by orders of magnitudes, which the simple ratio in Formula
(3) can not properly capture. Take node $v_{i}$ as an example, if ball
$\mathcal{B}\left(h^{(l)}_{i},R\right)$ wraps massive nodes inside, which
means $h^{(l)}_{i}$ is located in the high density area of the feature space,
then $v_{i}$ is a normal node with easier temporal patterns and has many peers
similar to itself. If the nodes wrapped by the ball further account for a
large portion of $v_{i}$’s $k$ order neighbor, then the pattern of $v_{i}$
should be easy to learn in both spatial and temporal aspects. Conversely, if
$v_{i}$’s high-level representation $h_{i}^{l}$ stays solitarily away from
others (i.e., in low density area), then $v_{i}$ is an outlier in the dataset.
In this case, $v_{i}$ should be more difficult to learn in temporal aspect
regardless of its consistency with $G$-neighbors.

Therefore, in addition to Formula (3) which serves as a difficulty measurer in
spatial aspect, we further propose Formula (4) to measure the node’s
difficulty from temporal aspect as follows:

$\displaystyle\frac{|\mathcal{B}\left(h^{(l)}_{i},R\right)|}{|\mathcal{B}\left(h^{(l)}_{i},R\right)|+\epsilon_{R}},$
(4)

where
$\epsilon_{R}=\frac{1}{|\mathcal{V}|}\sum_{i=1}^{|\mathcal{V}|}|\mathcal{B}\left(h^{(l)}_{i},R\right)|$
acts as a penalty term for those “lonely” nodes. Specifically, the
functionality of Formula (4) mainly relies on three important properties: 1)
The value of Formula (4) increases monotonically as the node’s distribution
density becomes larger (i.e., $|\mathcal{B}\left(h^{(l)}_{i},R\right)|$ gets
larger). 2) The value of $\epsilon_{R}$ represents the average data
distribution density and serves as a penalizer. When
$|\mathcal{B}\left(h^{(l)}_{i},R\right)|\gg\epsilon_{R}$, we have
$\frac{|\mathcal{B}\left(h^{(l)}_{i},R\right)|}{|\mathcal{B}\left(h^{(l)}_{i},R\right)|+\epsilon_{R}}\approx
1$. Conversely, when $|\mathcal{B}\left(h^{(l)}_{i},R\right)|\ll\epsilon_{R}$,
we have
$\frac{|\mathcal{B}\left(h^{(l)}_{i},R\right)|}{|\mathcal{B}\left(h^{(l)}_{i},R\right)|+\epsilon_{R}}\approx
0$. The penalty strength of $\epsilon_{R}$ actually grows as the node’s data
distribution density decreases. 3) The range of Formula (4) is constrained to
$[0,1]$, which is consistent with the range of Formula (3). Therefore, by
integrating Formula (3) and Formula (4), we propose our difficulty evaluation
function $Diff(v_{i})$ as:

$\displaystyle
2-\underbrace{\frac{1}{\mid\Omega_{v_{i}}^{k}\mid}\sum_{v_{j}\in\mathcal{V}}\mathcal{I}_{v_{i}}(v_{j},\Omega_{v_{i}}^{k})}_{\text{Spatial
difficulty}}-\underbrace{\frac{|\mathcal{B}\left(h^{(l)}_{i},R\right)|}{|\mathcal{B}\left(h^{(l)}_{i},R\right)|+\epsilon_{R}}}_{\text{Temporal
difficulty}}.$ (5)

Moreover, to avoid excessive hyperparameters, we here heuristically define the
radius $R$ in Eq. (5) as
$R=\frac{1}{|\mathcal{V}|}\sum_{i=1}^{|\mathcal{V}|}\mathcal{Q}_{\rho}(\\{D(h^{(l)}_{i},~{}h_{j}^{(l)}):j\in\\{1,\cdots,|\mathcal{V}|\\}\\})$,
where $\mathcal{Q}$ is a quantile function that return the $\rho\%$ quantile
values expanding from small to large.

### Curriculum Learning

In this section, we start from the formalization of curriculum learning
(Bengio et al. 2009). Let $\lambda\in[0,1]$ denotes the training time such
that the training begins at $\lambda=0$ and finishes at $\lambda=1$. Suppose
$Q_{\lambda}(x)$ is the training distribution at time $\lambda$, where the
training sample $x$ is drawn. The concept of curriculum learning requires that
the training samples from $Q_{\lambda}$ should be easier than the samples from
$Q_{\lambda+\delta}$, $\delta>0$. Mathematically, curriculum learning holds
the assumption that

$\displaystyle Q_{\lambda}(x)\propto W_{\lambda}(x)P(x),$ (6)

where $P(x)$ denotes the target training distribution including both easy and
hard samples, and $0\leq W_{\lambda}(x)\leq 1$ is the difficult criterion for
every training time $\lambda$ and sample $x$. In the meanwhile, the choice of
$W_{\lambda}(x)$ should satisfy such property:

$\displaystyle H(Q_{\lambda}(x))<H(Q_{\lambda+\delta}(x)),$ (7)

where $H$ is the Shannon’s entropy. Eq. (7) expounds the fact that the
diversity and information in the training set should gradually increase with
respect to the training time $\lambda$, which is in accordance with our idea
to progressively exposing nodes with more complicated ST relations to the
model.

To control the change of difficulties of the training set during training (the
pace of curricula), we follow the theory in (Bengio et al. 2009) and
introduces our curriculum scheduler $\pi(t)$, which indicates the retain rate
of nodes at a certain training stage. Let $t\in\\{0,1,2,\dots\\}$ denotes the
training stages, measured by gradient updates, the scheduler should smoothly
level up the difficulty of training corresponding to $t$ by gradually
increasing the retain rate of nodes in a given layer. More straightforwardly,
we want the model to start from a small fraction of easy nodes
($\pi(0)=\bar{\alpha}$) and gradually increases the availability of nodes to
complicate the task until eventually recovering to normal training
($\lim_{t\rightarrow\infty}\pi(t)=1$). The scheduler function $\pi(t)$ can be
formulated as

$\displaystyle\pi(t)=1-(1-\bar{\alpha})\exp(-\beta t),\quad\beta>0$ (8)

With the previous derivations, we can now formally introduce our ST-Curriculum
Dropout strategy as, given a training stage $t$ and nodes’ high-level
representation $h^{l}$, we keep the top $\pi(t)\%$ easiest nodes and dropout
(set to zero) the others to control the level of difficulty of the task. The
procedure can be mathematically written as:

$\displaystyle S_{t}$
$\displaystyle=\mathcal{Q}_{\pi(t)}(\left\\{Diff(v_{j}):v_{j}\in\mathcal{V}\right\\})$
(9) $\displaystyle\mathcal{M}$
$\displaystyle=\mathbb{1}\left\\{Diff(v_{i})\leq S_{t}\mid
v_{i}\in\mathcal{V}\right\\}$ (10) $\displaystyle\widetilde{h}^{(l)}$
$\displaystyle=\mathcal{M}*h^{(l)}.$ (11)

Some might argue that the choice of $\beta$ in Eq. (8) can be annoying since
it requires cross-validation. However, as suggested in (Morerio et al. 2017),
this value can actually be heuristically decided. In order to reserve all the
nodes to recover normal training in later stages, we should have
$\pi(T)>1-\frac{1}{|\mathcal{V}|}$, where $T$ refers to the total number of
gradient updates. Surprisingly, we observe that
$\beta=\frac{10^{3}}{T\times|\mathcal{V}|}$ naturally implies
$|\pi(T)-1|<10^{-2}|\mathcal{V}|^{-1}\equiv\pi(T)>1-\frac{1}{100|\mathcal{V}|}$
and such principle can fit any situation in our framework.

So far, the nodes with difficulty level under the threshold of scheduler
function $\pi(t)$ will be sampled and treated equally in model training
stages. However, this could lead to a somewhat counterintuitive phenomenon:
those easy nodes (e.g., $Diff(v_{i})<0.1$) are likely to be repeatedly used in
model training, which deviates from the general learning principle of human.
For example, college students who study calculus no longer need to review the
simple addition and subtraction of numbers, but can still keep such capability
when learning harder courses. From the view of optimization, we prefer at each
iteration, the model can focus more on the difficult targets so as to better
extend its border of capacity, while the repeatedly used easy samples are paid
less attention. To this end, we introduce a simple and dynamic weighting
policy into our design, so that the model can further benefit from the
learning of curriculum. Formally, at training step $t$, we define the weight
of node $v_{i}$ as:

$\displaystyle w_{i}^{(t)}=$ $\displaystyle
1\quad\quad\quad\quad\text{if}\quad Diff(v_{i})\leq S_{t-1}$ (12a)
$\displaystyle w_{i}^{(t)}=$ $\displaystyle 1+\pi(t)\quad\text{if}\quad
S_{t-1}<Diff(v_{i})\leq S_{t}$ (12b) $\displaystyle w_{i}^{(t)}=$
$\displaystyle 0\quad\quad\quad\quad\text{if}\quad Diff(v_{i})>S_{t}.$ (12c)

We do not consider weights for those nodes which haven’t been included in
training (i.e., $Diff(v_{i})>S_{t}$) and set them as 0. And our scheduler
function $\pi(t)$ increases monotonically with its range in $[0,1]$.
Therefore, at each training step, the loss of newly included nodes will be
mildly emphasized with more weights, while others are applied normally with
$w_{i}^{(t)}=1$. There are three things worth noting about the weighting
design: 1) The weights of newly added nodes, which stand as the border of
model’s capacity at training step $t$, are positively correlated with the
value of $\pi(t)$, since intuitively we consider, as $\pi(t)$ becomes larger,
the newly added nodes can be treated as a harder capacity bound for the model
to breakthrough, and therefore requires larger weights. 2) When the curriculum
is over, all the nodes will be assigned the same weights (i.e., 1) to recover
normal training. 3) In addition to Eq. (11) which aims to prevent the unwanted
feature fusion between easy and difficult nodes (i.e., $Diff(v_{i})>S_{t}$) in
forward propagation, Eq. (12c) seeks to block such noise from model in
backward propagation. Finally, we combine the weighting
$w^{(t)}\in\mathbb{R}^{\mathcal{V}}$ with the objective function and formulate
them as follows:

$\displaystyle\mathcal{L}(\theta)=\left\|w^{(t)}\left(\mathbf{X}^{(t)}_{(n+1):(n+\beta)}-\overline{\mathbf{X}}^{(t)}_{(n+1):(n+\beta)}\right)\right\|_{2}^{2},$
(13)

where $\mathbf{X}^{(t)}_{(n+1):(n+\beta)}$ and
$\overline{\mathbf{X}}^{(t)}_{(n+1):(n+\beta)}$ indicate the ground truth and
model prediction at training step $t$, and $\theta$ is the set of model
parameters.

In our curriculum design, easier nodes are first fed to the model, helping it
learn the fundamental ST relations while prevent it from being disturbed by
the “noisy” data in early training stages, which is the most important time
for training DNNs (Jastrzebski et al. 2020). After that, more complex samples
are exposed to the model, allowing it to learn the higher-level abstraction in
ST relations. The newly added nodes, which serve as a manner of
regularization, both improve the generalization capability of the model and
allow the model to avoid over-fitting over the easy ST relations. As a result,
at each training stage, the difficulty of samples can stand at the border of
the model’s capacity, neither too easy nor too hard, so that the model can
expand its border gradually. This is very similar to the idea of Continuation
Methods (Allgower and Georg 1980), which suggests to first optimize a smoothed
objective and gradually consider less smoothing, with the intuition that a
smooth version of the problem can reveal the global picture.

## Experiment

In this section, we evaluate our proposed STC-Dropout on a wide range of
spatial-temporal datasets so as to demonstrate its general applicability:
METR-LA (Li et al. 2017), PEMSD7M (Yu, Yin, and Zhu 2017), Covid-19
(Panagopoulos, Nikolentzos, and Vazirgiannis 2021) and NYC-Crime (Xia et al.
2021). Since this is the first attempt to introduce CL into ST modeling task,
we validate the superiority of our strategy by comparing with the strong CL
strategies from other fields: 1) C-Dropout (curriculum dropout) (Morerio et
al. 2017) , 2) C-Smooth (curriculum by smoothing) (Sinha, Garg, and Larochelle
2020) and 3) Anti-CL (Shrivastava, Gupta, and Girshick 2016) on state-of-the-
art models : 1) STGCN (Yan, Xiong, and Lin 2018), 2) Graph WaveNet (Wu et al.
2019), 3) ASTGCN (Guo et al. 2019) and 4) Z-GCNETs  (Chen, Segovia, and Gel
2021). The four models we choose range from the classic ones to the latest
ones, and they are all designed for ST tasks. Please refer to the appendix
A.2-A.9 for more detailed descriptions of the datasets, baselines, experiment
setup and extra results.

Table 1: Performances of STC-Dropout on a wide range of spatial-temporal
datasets.

Model METR-LA (15/30/60 min) PeMSD7M (15/30/60 min) MAE MAPE(%) RMSE MAE
MAPE(%) RMSE ST-GCN 2.89/3.50/4.62 7.64/9.59/12.70 5.75/7.28/9.40
2.12/2.72/3.35 4.99/6.92/8.97 4.09/5.53/6.62 +STC-Dropout 2.67/3.28/4.37
7.37/9.22/12.22 5.54/6.83/9.06 2.03/2.61/3.27 4.83/6.85/8.64 3.85/5.30/6.38
GW-Net 2.70/3.05/3.53 6.88/8.38/10.05 5.17/6.24/7.37 2.08/2.66/3.23
4.91/6.69/8.48 3.94/5.31/6.35 +STC-Dropout 2.51/2.83/3.27 6.45/8.06/9.68
4.79/5.91/6.99 1.97/2.52/3.11 4.71/6.54/8.33 3.76/5.17/6.11 ASTGCN
4.87/5.45/6.54 9.24/10.14/11.62 9.25/10.62/12.50 2.19/2.77/3.52 5.42/7.31/9.18
4.15/5.37/6.54 +STC-Dropout 4.70/5.26/6.40 8.93/9.74/11.32 9.02/10.12/12.26
2.02/2.68/3.40 5.30/7.25/8.90 4.06/5.15/6.20 Z-GCNETs 2.62/2.99/3.32
6.79/8.45/9.97 5.09/6.04/7.15 1.91/2.35/2.98 4.86/6.52/8.18 3.78/5.18/6.17
+STC-Dropout 2.50/2.78/3.05 6.48/8.03/9.56 4.79/5.69/6.82 1.85/2.21/2.84
4.61/6.22/8.01 3.50/4.81/5.98 Model Covid-19 (3/5/7 days) Crime (3/5/7 days)
MAE MAPE(%) RMSE MAE MAPE(%) RMSE ST-GCN 3.51/3.68/3.88 2.29/2.36/2.53
6.22/6.57/7.18 2.15/3.22/3.86 1.40/2.10/2.52 3.21/5.04/6.10 +STC-Dropout
3.12/3.24/3.37 1.57/1.69/1.98 5.65/6.04/6.49 2.07/3.14/3.80 1.31/2.05/2.40
3.15/4.97/5.98 GW-Net 3.40/3.55/3.76 2.26/2.30/2.37 6.06/6.42/6.92
2.17/2.80/3.38 1.42/1.83/2.21 3.48/4.60/5.69 +STC-Dropout 2.89/3.18/3.26
1.49/1.65/1.81 5.56/5.81/6.24 2.11/2.77/3.33 1.36/1.72/2.07 3.42/4.55/5.61
ASTGCN 3.54/3.60/3.86 2.31/2.33/2.52 6.23/6.45/7.15 2.31/2.96/3.39
1.78/1.99/2.28 3.45/4.46/5.29 +STC-Dropout 2.94/3.17/3.24 1.60/1.77/2.02
5.53/5.75/6.32 2.24/2.91/3.32 1.65/1.91/2.17 3.35/4.37/5.21 Z-GCNETs
3.27/3.42/3.59 2.21/2.28/2.33 5.95/6.22/6.74 2.10/2.68/3.19 1.31/1.85/2.12
3.10/4.38/5.43 +STC-Dropout 2.82/3.07/3.12 1.43/1.65/1.86 5.54/5.69/6.18
2.06/2.61/3.12 1.22/1.78/2.04 3.08/4.29/5.30

Table 2: Different curriculum learning strategies.

Model CL Strategy MAE MAPE(%) RMSE METR-LA ST-GCN 2.89 7.64 5.75 +Anti-CL 3.04
7.73 5.91 +C-Dropout 2.75 7.52 5.69 +C-Smooth 2.77 7.60 5.72 +STC-Dropout 2.67
7.37 5.54 PeMSD7M GW-Net 2.08 4.91 3.94 +Anti-CL 2.16 5.07 4.11 +C-Dropout
2.03 4.91 3.92 +C-Smooth 2.01 4.82 3.86 +STC-Dropout 1.97 4.71 3.76 Covid-19
ASTGCN 3.54 2.31 6.23 +Anti-CL 3.55 2.30 6.23 +C-Dropout 3.23 1.83 6.06
+C-Smooth 3.27 1.78 5.92 +STC-Dropout 2.94 1.60 5.53 Crime Z-GCNETs 2.10 1.31
3.10 +Anti-CL 2.12 1.34 3.12 +C-Dropout 2.09 1.25 3.09 +C-Smooth 2.07 1.33
3.09 +STC-Dropout 2.06 1.22 3.08

### Experimental Results

We conduct extensive experiments on a wide range of ST datasets to demonstrate
the superiority of STC-Dropout, which are listed in Table 1. We can observe
that generally, SOTA models still have much room for improvement via the
utilization of STC-Dropout. We summarize the average improvements as follows:
MAE: 0.21 $\uparrow$, MAPE: 0.36 $\uparrow$, RMSE: 0.34 $\uparrow$ in METR-LA
, MAE: 0.47 $\uparrow$, MAPE: 0.63 $\uparrow$, RMSE: 0.61 $\uparrow$ in
Covid-19, MAE: 0.12 $\uparrow$, MAPE: 0.19 $\uparrow$, RMSE: 0.23 $\uparrow$
in PeMSD7M and MAE: 0.06 $\uparrow$, MAPE: 0.10 $\uparrow$, RMSE: 0.08
$\uparrow$ in Crime. Especially, according to recent traffic benchmarks (Li et
al. 2021; Jiang et al. 2021), our performance gains on METR-LA and PeMSD7M can
even match the performance improvements between two generations of models
(e.g., DCRNN and GW-Net), and we achieve this by just using a simple plug-in
to change the learning strategy (An intuitive reasoning in Appendix A.7).

Figure 3: Grid search of hyper-paramerters on ST-GCN.

We further horizontally compare STC-Dropout with several CL methods from other
fields and the results are reported in Table 2 (and Appendix A.8). It’s
observed that both C-Dropout and C-Smooth enhance the baseline models by a
certain margin, which again validates the idea of CL on ST modeling task.
However, Anti-CL fails to outperform baselines. Therefore, we here discuss
some reasons behind their performances and STC-Dropout’s overwhelming
improvements over others as follows:

  * $\bullet$

C-Dropout is a curriculum method proposed regarding the model itself, which
progressively reduces the model’s capacity in object classification tasks.
Completely adopting such an idea into spatial-temporal modeling might be hard
since the task is more complicated and requires a large network capacity to
model high-level ST relations, especially at later training stages. The
benefit of C-Dropout in experiment might come from the early stages of
training, which offers better parameter initialization (Morerio et al. 2017).

  * $\bullet$

C-Smooth is first proposed in CNN using Gaussian kernel filters to “blur” the
data and reduce noises. On the one hand, this might be too arbitrary without
consideration of the ST relations. On the other hand, although we modify it to
run on GNNs, this could arouse another problem called over-smoothing (Rong et
al. 2019). Conversely, STC-Dropout is specially developed for ST graph
modeling and considers the ST relation at the stage of difficulty evaluation.

  * $\bullet$

Anti-CL is another popular data selection strategy opposite to CL (i.e. hard
sample first). A well-accepted insight (Chang, Learned-Miller, and McCallum
2017) about whether to choose CL or Anti-CL points out that CL is more
preferable for noisy datasets to improve model robustness and Anti-CL is more
beneficial for cleaner datasets to accelerate convergence. In light of this,
we attribute the inferior performances of Anti-CL to the chaotic nature of ST
data.

### Ablation Study

Comparison with Heuristic Curriculum Strategy. To validate the effectiveness
of STC-Dropout, we compare it with multiple heuristic curriculum designs
(without ST correlation assumptions) to forecast future 15 min’s traffic speed
using ST-GCN. We perform the curriculum both in the high-level hidden space
(as STC-Dropout does) and directly at the input (corresponding to the
discussion in the first paragraph of Difficulty Evaluation). Two types of
heuristic curriculum schemes are used here: one defines the difficulty of
nodes via model predicting loss (Guo et al. 2018) and the other seeks the
complex samples through outlier detection (Zhang et al. 2019). For predicting
loss we apply a basic time series prediction models: LR (Linear Regression) as
the difficulty indicator, while for outlier detection, we use the popular
corresponding algorithms: LoF (Local Outlier Factor) (Breunig et al. 2000) and
IF (Isolation Forest) (Liu, Ting, and Zhou 2008). These above-mentioned
methods will rank the difficulty of nodes either in the hidden dimension or at
the input space, and then they follow the same schema of STC-Dropout to
dynamically dropout difficult nodes at early stages. We report the results in
Table 3, where we can discern that STC-Dropout, which we designed with ST
relation assumptions, yields the best outcome, and the curriculum performed in
hidden states is generally better than those in the input space.

Further, we consider several variants of STC-Dropout including the origin
Dropout without curriculum (Hinton et al. 2012), STC-Dropout-Mean: set the
dropout values to its neighbor’s mean instead of zeros, SC-Dropout: only
utilizes spatial difficulty measurer (Formula 3), and TC-Dropout: only uses
temporal difficulty measurer (Formula 4). The weighting design is also
included in the ablation. The comparison results are shown on Table 4.
Regarding the variants, there is no improvement over the standard STC-Dropout
on ST-GCN.

Table 3: Comparison with heuristic curriculum strategy

Level Models METR-LA MAE MAPE(%) RMSE Hidden ST-GCN 2.89 7.64 5.75 +C-LoF 2.73
7.48 5.66 +C-IF 2.78 7.58 5.71 +STC-Dropout 2.67 7.37 5.54 Input +C-LR 2.88
7.67 5.77 +C-LoF 2.76 7.53 5.70 +C-IF 2.84 7.63 5.74 +STC-Dropout 2.69 7.42
5.61

Table 4: Ablation Study

Models METR-LA MAE MAPE(%) RMSE ST-GCN 2.89 7.64 5.75 +Dropout 2.87 7.63 5.74
+STC-Dropout-Mean 2.79 7.60 5.71 +SC-Dropout 2.76 7.51 5.66 +TC-Dropout 2.73
7.49 5.68 +w/o. weight 2.70 7.44 5.58 +STC-Dropout 2.67 7.37 5.54

Hyper-parameter Analysis. Last but not least, we explore the hyper-parameters
sensitivity to $\rho$, which controls the radius of the $d^{(l)}$-dimensional
ball, and $\bar{\alpha}$, which specifies the initial retain rate of nodes.
The results of hyper-parameter search from
$\rho\times\bar{\alpha}\in[0.05,0.10,\cdots,0.95]\times[0.1,0.3,\cdots 0.9]$
on ST-GCN using both PeMSD7M and METR-LA datasets are depicted in Figure 3. As
we can see, the model performance is negatively related to the value of
$\bar{\alpha}$. Thus, it is recommended to set its value to be relatively
small to ensure only the easy samples can be retained in the early model
training. Concerning $\rho$, we encourage maintaining $\rho\in[0.25,0.4]$ for
desirable performances.

Figure 4: RMSE of ST-GCN with different noise magnitudes imposed on METR-
LA.(More in Appendix A.9)

When Does CL Take The Best Effect. We observe an interesting phenomenon in
Table 1: our method brings more improvements to METR-LA and Covid-19 than to
the others. This is somewhat reasonable since CL mainly works by excluding the
negative impacts of difficult samples to the model in the early training. So
its effect will decrease as the dataset becomes easy (e.g., for ST-GCN, METR-
LA is easier than Crime since it has lower prediction error). We further
validate our assumption via an experiment where we disturb the training data
as follows:

$\hat{z}=(1+\delta)z,\quad\delta\sim uniform(\bigtriangleup,\bigtriangleup).$

The noise magnitude is controlled by $\bigtriangleup$ and Figure 4 shows our
result. We can see that the as the noise magnitude becomes larger, our method
gradually brings more improvements. This also suggests that our method can
enhance robustness for models when training with noisy samples.

## CONCLUSION

This paper designs a novel curriculum strategy called ST-Curriculum Dropout,
especially for spatial-temporal graph modeling. By defining the complex score
of nodes based on their $G$-neighbor consistency (representing the difficulty
of spatial relations) and data distribution density (representing the
difficulty of temporal patterns), we gradually expose the complex nodes to the
network to form a curriculum. Experimental results show the effectiveness of
our design. One potential problem of our method could be the computation of
pairwise distance. Although the cost is acceptable, this can be further
alleviated by using Faiss111https://github.com/facebookresearch/faiss to
accelerate computing. In future work, we would like to extend the STC-Dropout
into further applications such as multi-variate time series.

## Acknowledgment

We are grateful to anonymous reviewers for their helpful comments. We
additionally would like to thank Lei Huang for his help. This work was
partially supported by the grants of National Key Research and Development
Program of China (No. 2018AAA0101100), National Key Research and Development
Project (2021YFB1714400) of China and Guangdong Provincial Key Laboratory
(2020B121201001), and Grant-in-Aid for Scientific Research B (22H03573) of
Japan Society for the Promotion of Science (JSPS).

## References

  * Allgower and Georg (1980) Allgower, E.; and Georg, K. 1980.  Simplicial and continuation methods for approximating fixed points and solutions to systems of equations.  _Siam review_ , 22(1): 28–85.
  * Bai et al. (2020) Bai, L.; Yao, L.; Li, C.; Wang, X.; and Wang, C. 2020.  Adaptive graph convolutional recurrent network for traffic forecasting.  _Advances in neural information processing systems_ , 33: 17804–17815.
  * Bengio et al. (2009) Bengio, Y.; Louradour, J.; Collobert, R.; and Weston, J. 2009.  Curriculum learning.  In _Proceedings of the 26th annual international conference on machine learning_ , 41–48.
  * Breunig et al. (2000) Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; and Sander, J. 2000.  LOF: identifying density-based local outliers.  In _Proceedings of the 2000 ACM SIGMOD international conference on Management of data_ , 93–104.
  * Chang, Learned-Miller, and McCallum (2017) Chang, H.-S.; Learned-Miller, E.; and McCallum, A. 2017.  Active bias: Training more accurate neural networks by emphasizing high variance samples.  _Advances in Neural Information Processing Systems_ , 30.
  * Chen, Segovia, and Gel (2021) Chen, Y.; Segovia, I.; and Gel, Y. R. 2021.  Z-GCNETs: time zigzags at graph convolutional networks for time series forecasting.  In _International Conference on Machine Learning_ , 1684–1694. PMLR.
  * Guo et al. (2018) Guo, S.; Huang, W.; Zhang, H.; Zhuang, C.; Dong, D.; Scott, M. R.; and Huang, D. 2018.  Curriculumnet: Weakly supervised learning from large-scale web images.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 135–150.
  * Guo et al. (2019) Guo, S.; Lin, Y.; Feng, N.; Song, C.; and Wan, H. 2019.  Attention based spatial-temporal graph convolutional networks for traffic flow forecasting.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 922–929.
  * Hinton et al. (2012) Hinton, G. E.; Srivastava, N.; Krizhevsky, A.; Sutskever, I.; and Salakhutdinov, R. R. 2012.  Improving neural networks by preventing co-adaptation of feature detectors.  _arXiv preprint arXiv:1207.0580_.
  * Jain et al. (2016) Jain, A.; Zamir, A. R.; Savarese, S.; and Saxena, A. 2016.  Structural-rnn: Deep learning on spatio-temporal graphs.  In _Proceedings of the ieee conference on computer vision and pattern recognition_ , 5308–5317.
  * Jastrzebski et al. (2020) Jastrzebski, S.; Szymczak, M.; Fort, S.; Arpit, D.; Tabor, J.; Cho, K.; and Geras, K. 2020.  The break-even point on optimization trajectories of deep neural networks.  _arXiv preprint arXiv:2002.09572_.
  * Jiang et al. (2014) Jiang, L.; Meng, D.; Mitamura, T.; and Hauptmann, A. G. 2014.  Easy samples first: Self-paced reranking for zero-example multimedia search.  In _Proceedings of the 22nd ACM international conference on Multimedia_ , 547–556.
  * Jiang et al. (2021) Jiang, R.; Yin, D.; Wang, Z.; Wang, Y.; Deng, J.; Liu, H.; Cai, Z.; Deng, J.; Song, X.; and Shibasaki, R. 2021.  DL-Traff: Survey and Benchmark of Deep Learning Models for Urban Traffic Prediction.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, 4515–4525.
  * Karras et al. (2017) Karras, T.; Aila, T.; Laine, S.; and Lehtinen, J. 2017.  Progressive growing of gans for improved quality, stability, and variation.  _arXiv preprint arXiv:1710.10196_.
  * Kumar, Packer, and Koller (2010) Kumar, M. P.; Packer, B.; and Koller, D. 2010.  Self-Paced Learning for Latent Variable Models.  In _NIPS_ , volume 1, 2.
  * Kumar et al. (2011) Kumar, M. P.; Turki, H.; Preston, D.; and Koller, D. 2011.  Learning specific-class segmentation from diverse data.  In _2011 International Conference on Computer Vision_ , 1800–1807. IEEE.
  * Li et al. (2021) Li, F.; Feng, J.; Yan, H.; Jin, G.; Yang, F.; Sun, F.; Jin, D.; and Li, Y. 2021\.  Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_.
  * Li et al. (2017) Li, Y.; Yu, R.; Shahabi, C.; and Liu, Y. 2017.  Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.  _arXiv preprint arXiv:1707.01926_.
  * Lin et al. (2021) Lin, H.; Gao, Z.; Xu, Y.; Wu, L.; Li, L.; and Li, S. Z. 2021.  Conditional local convolution for spatio-temporal meteorological forecasting.  _arXiv e-prints_ , arXiv–2101.
  * Liu, Ting, and Zhou (2008) Liu, F. T.; Ting, K. M.; and Zhou, Z.-H. 2008.  Isolation forest.  In _2008 eighth ieee international conference on data mining_ , 413–422. IEEE.
  * Ma et al. (2017) Ma, F.; Meng, D.; Xie, Q.; Li, Z.; and Dong, X. 2017.  Self-paced co-training.  In _International Conference on Machine Learning_ , 2275–2284. PMLR.
  * Morerio et al. (2017) Morerio, P.; Cavazza, J.; Volpi, R.; Vidal, R.; and Murino, V. 2017.  Curriculum dropout.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 3544–3552.
  * Panagopoulos, Nikolentzos, and Vazirgiannis (2021) Panagopoulos, G.; Nikolentzos, G.; and Vazirgiannis, M. 2021.  Transfer graph neural networks for pandemic forecasting.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 4838–4845.
  * Peng et al. (2020) Peng, W.; Hong, X.; Chen, H.; and Zhao, G. 2020.  Learning graph convolutional network for skeleton-based human action recognition by neural searching.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 2669–2676.
  * Rong et al. (2019) Rong, Y.; Huang, W.; Xu, T.; and Huang, J. 2019.  Dropedge: Towards deep graph convolutional networks on node classification.  _arXiv preprint arXiv:1907.10903_.
  * Seo et al. (2018) Seo, Y.; Defferrard, M.; Vandergheynst, P.; and Bresson, X. 2018.  Structured sequence modeling with graph convolutional recurrent networks.  In _International Conference on Neural Information Processing_ , 362–373. Springer.
  * Shrivastava, Gupta, and Girshick (2016) Shrivastava, A.; Gupta, A.; and Girshick, R. 2016.  Training region-based object detectors with online hard example mining.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 761–769.
  * Sinha, Garg, and Larochelle (2020) Sinha, S.; Garg, A.; and Larochelle, H. 2020.  Curriculum by smoothing.  _arXiv preprint arXiv:2003.01367_.
  * Spitkovsky, Alshawi, and Jurafsky (2009) Spitkovsky, V. I.; Alshawi, H.; and Jurafsky, D. 2009.  Baby Steps: How “Less is More” in unsupervised dependency parsing.
  * Srivastava et al. (2014) Srivastava, N.; Hinton, G.; Krizhevsky, A.; Sutskever, I.; and Salakhutdinov, R. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ , 15(1): 1929–1958.
  * Veličković et al. (2017) Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Lio, P.; and Bengio, Y. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_.
  * Wang, Chen, and Zhu (2021) Wang, X.; Chen, Y.; and Zhu, W. 2021.  A survey on curriculum learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.
  * Wang et al. (2021) Wang, Y.; Wang, W.; Liang, Y.; Cai, Y.; and Hooi, B. 2021.  CurGraph: Curriculum Learning for Graph Classification.  In _Proceedings of the Web Conference 2021_ , 1238–1248.
  * Wu et al. (2020) Wu, Z.; Pan, S.; Long, G.; Jiang, J.; Chang, X.; and Zhang, C. 2020.  Connecting the dots: Multivariate time series forecasting with graph neural networks.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 753–763.
  * Wu et al. (2019) Wu, Z.; Pan, S.; Long, G.; Jiang, J.; and Zhang, C. 2019.  Graph WaveNet for Deep Spatial-Temporal Graph Modeling.  In _The 28th International Joint Conference on Artificial Intelligence (IJCAI)_. International Joint Conferences on Artificial Intelligence Organization.
  * Xia et al. (2021) Xia, L.; Huang, C.; Xu, Y.; Dai, P.; Bo, L.; Zhang, X.; and Chen, T. 2021.  Spatial-Temporal Sequential Hypergraph Network for Crime Prediction with Dynamic Multiplex Relation Learning.  In _IJCAI_ , 1631–1637.
  * Xu et al. (2020) Xu, B.; Zhang, L.; Mao, Z.; Wang, Q.; Xie, H.; and Zhang, Y. 2020.  Curriculum learning for natural language understanding.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 6095–6104.
  * Yan, Xiong, and Lin (2018) Yan, S.; Xiong, Y.; and Lin, D. 2018.  Spatial temporal graph convolutional networks for skeleton-based action recognition.  In _Thirty-second AAAI conference on artificial intelligence_.
  * Yang, Tang, and Liu (2021) Yang, T.; Tang, X.; and Liu, R. 2021.  Dual temporal gated multi-graph convolution network for taxi demand prediction.  _Neural Computing and Applications_ , 1–16.
  * Yu, Yin, and Zhu (2017) Yu, B.; Yin, H.; and Zhu, Z. 2017.  Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting.  _arXiv preprint arXiv:1709.04875_.
  * Zhang et al. (2018) Zhang, J.; Shi, X.; Xie, J.; Ma, H.; King, I.; and Yeung, D.-Y. 2018.  Gaan: Gated attention networks for learning on large and spatiotemporal graphs.  _arXiv preprint arXiv:1803.07294_.
  * Zhang et al. (2019) Zhang, M.; Li, T.; Shi, H.; Li, Y.; Hui, P.; et al. 2019.  A decomposition approach for urban anomaly detection across spatiotemporal data.  In _IJCAI International Joint Conference on Artificial Intelligence_. International Joint Conferences on Artificial Intelligence.
  * Zheng et al. (2020) Zheng, C.; Fan, X.; Wang, C.; and Qi, J. 2020.  Gman: A graph multi-attention network for traffic prediction.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 1234–1241.
  * Zhu et al. (2020) Zhu, J.; Yan, Y.; Zhao, L.; Heimann, M.; Akoglu, L.; and Koutra, D. 2020.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _Advances in Neural Information Processing Systems_ , 33: 7793–7804.

##  Appendix A Appendix

### A.1 Related Work

Curriculum Learning. The basic idea of curriculum learning is to let the
models first learn from easy samples and work their way up to complex samples
and knowledge (Bengio et al. 2009). A well-written survey (Wang, Chen, and Zhu
2021) classifies the taxonomy of curriculum learning into data-level and
criteria-level. The data-level approach follows the natural definition of
curriculum learning through sampling (Jiang et al. 2014), weighting (Kumar,
Packer, and Koller 2010) and specific iterative (Spitkovsky, Alshawi, and
Jurafsky 2009) to select the most suitable examples for each training step.
The other bunch of study considers arranging the curriculum according to some
criteria which can be any design element in training a machine learning model.
A novel training strategy (Karras et al. 2017) has been designed to gradually
increase the model’s capacity by adding new neural units. Reference (Sinha,
Garg, and Larochelle 2020) combines the idea of adversarial training with
curriculum learning by using Gaussian kernel to smooth the noise in CNN
feature maps at early stages of training. Reference (Morerio et al. 2017)
introduces the dynamically stochastic dropout in curriculum learning by
moderately increasing the dropout rate during training to handle co-adaptions
in DNN.

Spatial-temporal Graph Modeling. The task of spatial-temporal graph modeling
intends to forecast the future single/multi-step signals according to the
historical observation and spatial graph information. Lots of applications
including taxi demand prediction (Yang, Tang, and Liu 2021), human action
recognition (Peng et al. 2020), traffic speed forecast (Wu et al. 2020) and
driver maneuver anticipation (Jain et al. 2016) can be categorized to this
case. The primary challenge of spatial-temporal graph modeling lies in
simultaneously capturing spatial and temporal dependencies from dynamic node-
level inputs and a fixed graph structure. Recent studies to solve this problem
mainly integrate the graph convolution networks (GCN) into existing models
(Yan, Xiong, and Lin 2018; Li et al. 2017; Seo et al. 2018; Yu, Yin, and Zhu
2017). In (Seo et al. 2018), the graph convolution has been utilized to filter
the node-level inputs and hidden state before passing them to a recurrent
unit. A diffusion graph convolution method is further devised (Li et al. 2017)
to better capture the spatial dependency. Reference (Yu, Yin, and Zhu 2017;
Yan, Xiong, and Lin 2018) combine GCN with standard 1D convolution layers
instead of recurrent units to overcome the drawbacks of RNN-based approaches
that tend to experience gradients explosion in long sequences scenario. The
attention mechanisms are also explored by using a convolution subnetwork to
control the importance of features from GCN (Zhang et al. 2018) or directly
employing graph attention (Guo et al. 2019). More recently, researchers
further propose a variety of work to address the common problem of location-
characterized (local) patterns (Bai et al. 2020; Lin et al. 2021). While all
the abovementioned efforts focus on building more complex models to enhance
their abilities to capture spatial-temporal dependencies, our contribution to
this task lies in a different direction. Instead of proposing yet another ST
model, we explore the possibility of simply using a novel CL training strategy
to let the model learn from more meaningful and discriminative features and
finally result in better overall performances. To the best of our knowledge,
we are the first work to explore such ideas.

### A.2 Datasets

The METR-LA dataset collects four months of traffic speed data using 207
sensors on the highways of Los Angeles. PEMSD7M collects two months statistics
of traffic speed using 228 sensors in Caltrans Performance Measurement System
(PeMS). These two datasets contain time-stamped characteristics of the average
speed and the sensors’ geographic locations, where they collect the speed
information.

The COVID-19 dataset used by (Panagopoulos, Nikolentzos, and Vazirgiannis
2021) is first released by Facebook in the scope of Data for Good
program222https://dataforgood.facebook.com/dfg/tools, which intends to provide
opportunities for researchers to investigate the dynamics of COVID-19, we here
focus on the data of an European country: France. In this dataset, each node
indicates a specific region of a country, and the weight of the edges
represents the corresponding volume of human flow from one region to another.
Since the existing ST models usually set edge weights to be static, we here
utilize the average human mobility between regions as their weights.

The Crime dataset is collected from New York City’s
OpenData333https://data.cityofnewyork.us/Public-Safety/NYC-crime/qb7u-rbmr
that includes crimes reported to the New York City Police Department (NYPD).
In this dataset, we divide the NYC into 256 disjoint spatial regions and
formulated them as a graph with each node indicating a $3km\times 3km$ spatial
grid.

The statistics of the datasets are reported in Table 1. We follow the data
pre-processing conducted in (Li et al. 2017) to use a Gaussian kernel as
follows:
$\hat{w}_{ij}=\exp\left(-\left(\frac{w_{ij}}{\sigma}\right)^{2}\right)$ to
smooth the weights of edges and build the adjacency matrix. The inputs are the
distances between and $\sigma$ is a normalizing factor. In terms of the graph
signals, we use the $z$-score normalization.

Table 1:  Dataset statistics. Tasks | METR-LA | PeMSD7M | Covid-19 | Crime
---|---|---|---|---
Start time | $10/1/2014$ | $5/1/2012$ | 2/20/2020 | 1/1/2014
End time | $12/31/2014$ | $6/30/2012$ | 20/6/2020 | 12/31/2015
Sample rate | 5 minutes | 1 minutes | 1 day | 1 day
Timesteps | 27403 | 12672 | 123 | 730
Sensors/Regions | 207 | 228 | 55 | 256
Training size | 16783 | 8870 | 94 | 510
Validation size | 2397 | 1267 | 12 | 73
Testing size | 4795 | 2549 | 24 | 146
Output length | 3, 6, 12 | 3, 6, 12 | 3, 5, 7 | 3, 5, 7

### A.3 Baselines Description and Setups

  * $\bullet$

Curriculum Dropout (Morerio et al. 2017): Curriculum Dropout gradually
increases the dropout rate to reduce the model capacity to form an easy-to-
hard curriculum for the model. We use the recommended hyper-parameters:
$\theta(0)=1$ and $\gamma=10/T$ in the curriculum dropout as the author
suggested.

  * $\bullet$

Curriculum by Smoothing (Sinha, Garg, and Larochelle 2020): The strategy
implements the curriculum with a Gaussian smoothing filter to reduce the
“noise” of data in early training stages on CNNs, and gradually anneals the
value of $\sigma$ in Gaussian filter to recover normal training. We extend
such settings to GCNs. The initial value of $\sigma^{(0)}$ is set to 1, and
gradually decreases every 10 epochs.

  * $\bullet$

Anti-CL (Shrivastava, Gupta, and Girshick 2016) : Anti-Curriculum is a
strategy opposite to Curriculum Learning. In our experiments, we simply
reverse the scheduler function to simulate Anti-CL.

  * $\bullet$

ST-GCN (Yan, Xiong, and Lin 2018): ST-GCN integrates the graph convolution and
1D convolution. It contains two ST-Conv blocks with (12, 16, 64) and (64, 16,
64) respectively.

  * $\bullet$

Graph WaveNet (Wu et al. 2019): GW-Net combines graph convolution with dilated
causual convolution. In Graph WaveNet, the number of layers and blocks are
defaulted as 4 and 2.

  * $\bullet$

ASTGCN (Guo et al. 2019): ASTGCN fuses the spatial-temporal attention
mechanism and the graph convolution together. Each graph convolution filter of
ASTGCN has 64 kernels.

  * $\bullet$

Z-GCNETs  (Chen, Segovia, and Gel 2021): Z-GCNETs uses the most salient time-
conditioned topological information of the data and formulates zigzag
persistence into a time-aware graph convolutional networks (GCNs). The model
structure of Z-GCNETs follows the original paper.

### A.4 Experimental Setups

All baselines in this paper are implemented based on the Pytorch framework
with eight GeForce GTX 2080Ti graphics cards and one Intel(R) Xeon(R) Silver
4216 CPU @ 2.10GHz. The datasets are divided into three parts in chronological
order for training, validation, and testing with the ratio of $7:1:2$. An Adam
optimizer with initialized learning rate $10^{-3}$ is applied to all models in
experiments and the batch size was set to 64 by default. The training
algorithm would either be early-stopped if the validation error converges
within 10 epochs or be stopped after 200 epochs. In order to verify the
performance of the STC-Dropout, the evaluation indicators selected in this
paper are Root Mean Squared Error (RMSE), Mean Absolute Error (MAE), and Mean
Absolute Percentage Error (MAPE). The random seed is predefined for the
consistency of the model’s initial parameters, based on which the
reproducibility and the reliability of the experimental results can be
guaranteed. Moreover, we present the prediction error of Covid-19 and Crime
datasets as the accumulated error for 3/5/7 days so as to better illustrate
the model performances.

Figure 1:  visualizing the curriculum scheduler function $\pi$ with different
settings.

### A.5 Curriculum Scheduler Function

We further visualize the curriculum scheduler function $\pi$ defined in Eq.
(8). We can observe from Figure 1 that the curve tends to be smoother with the
increase of $\beta$. Recall that $\beta$ is heuristically set as
$\frac{10^{3}}{T\times|\mathcal{V}|}$, so as to satisfy
$|\pi(T)-1|<10^{-2}|\mathcal{V}|^{-1}$. Take METR-LA for an example, assuming
$|\mathcal{V}|=207$, and $T=10000$, $\beta$ can be defined as
$\frac{1}{2070}$. At each training stage $t$, the scheduler function $\pi$
will give a ratio $\pi(t)\in(0,1)$ to retain the easiest $\pi(t)\%$ of nodes
for training.

### A.6 Evaluation Metric

RMSE (Root Mean Square Error), MAE (Mean Absolute Error), and MAPE (Mean
Absolute Percentage Error) are used in this paper to evaluate the performance
of baselines:

$\displaystyle\left\\{\begin{aligned}
RMSE&=\sqrt{\frac{1}{\mathcal{T}_{\text{test
}}}\sum_{t}^{\mathcal{T}_{\text{test
}}}\left\|\hat{\mathbf{X}}_{(t+1):(t+\beta)}-\mathbf{X}_{(t+1):(t+\beta)}\right\|^{2}}\\\
MAE&=\frac{1}{\mathcal{T}_{\text{test }}}\sum_{t}^{\mathcal{T}_{\text{test
}}}\left|\hat{\mathbf{X}}_{(t+1):(t+\beta)}-\mathbf{X}_{(t+1):(t+\beta)}\right|\\\
MAPE&=\frac{1}{\mathcal{T}_{\text{test }}}\sum_{t}^{\mathcal{T}_{\text{test
}}}\left|\frac{\hat{\mathbf{X}}_{(t+1):(t+\beta)}-\mathbf{X}_{(t+1):(t+\beta)}}{\mathbf{X}_{(t+1):(t+\beta)}+\varepsilon}\right|\end{aligned}\right.$

where $\mathcal{T}_{\text{test }}$ is the test datasets,
$\hat{\mathbf{X}}_{t}$ and $\mathbf{X}_{t}$ are the predicted and ground truth
tensor respectively, and $\varepsilon$ is a constant to prevent dividing by
zero.

### A.7 STC-Dropout’s Relation with Heterophily Graph

Essentially, the graph with corrupted spatial-temporal relations can be viewed
as a special form of heterophily graph, where the connected nodes belong to
different classes (under ST assumptions, the signals of connected nodes don’t
share similarity). In the literature of heterophily graphs, a large amount of
models are proposed to solve this problem, such as GAT (Veličković et al.
2017) which aims to use attention to study the nodes of the same class more
directly, and H2GCN (Zhu et al. 2020), which changes its aggregation function
to capture long-range correlations. Correspondingly, in ST mining work,
various work like ASTGCN (Guo et al. 2019) , GMAN (Zheng et al. 2020) and
AGCRN (Bai et al. 2020) are proposed. Fundamentally, these work all try to
design new learning paradigm for GCN models (e.g., the model does not
aggregate information from traditional neighbors but to use attention to
decide which node gives the most informative information). Our STC-Dropout can
also be viewed as a new learning paradigm for GCN models. In fact, if we
integrate STC-Dropout into some GCNs, we can actually propose a new model for
ST graph modeling. However, we consider it unnecessary because such design
will be less flexible and hard to extend. Therefore, we instead use a simple
plug-in to achieve the same target and it can be applied to any canonical ST
graph models.

Table 2: Different curriculum learning strategies. Model | CL Strategy | MAE | MAPE(%) | RMSE
---|---|---|---|---
METR-LA | GW-Net | 2.70 | 6.88 | 5.17
+Anti-CL | 2.89 | 7.02 | 5.31
+C-Dropout | 2.60 | 6.62 | 4.91
+C-Smooth | 2.64 | 6.72 | 4.99
| +STC-Dropout | 2.51 | 6.45 | 4.79
PeMSD7M | ASTGCN | 2.19 | 5.42 | 4.15
+Anti-CL | 2.26 | 5.64 | 4.26
+C-Dropout | 2.12 | 5.35 | 4.12
+C-Smooth | 2.10 | 5.31 | 4.10
| +STC-Dropout | 2.02 | 5.30 | 4.06
Covid-19 | Z-GCNETs | 3.27 | 2.21 | 5.95
+Anti-CL | 3.30 | 2.25 | 6.01
+C-Dropout | 2.69 | 1.88 | 5.62
+C-Smooth | 2.74 | 2.03 | 5.78
| +STC-Dropout | 2.28 | 1.43 | 5.54
Crime | ST-GCN | 2.15 | 1.40 | 3.21
+Anti-CL | 2.18 | 1.48 | 3.23
+C-Dropout | 2.13 | 1.38 | 3.20
+C-Smooth | 2.14 | 1.35 | 3.17
| +STC-Dropout | 2.07 | 1.31 | 3.15

### A.8 Comparison with Different Curriculum Learning Strategies.

Table 2 shows the extra results of different curriculum learning strategies.

### A.9 When Does CL Take The Best Effect.

Figure 2 shows the performance of Graph WaveNet in METR-LA with different
noise magnitudes.

Figure 2:  RMSE of Graph WaveNet with different noise magnitudes imposed on
the METR-LA.