文章标题：《Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting》
背景
因为本文是第一篇将图卷积用于提取空间和时间信息的文章，故之前文章使用的仿真模型（资源浪费大、且不合理的假设和简化使得效果很差）、统计方法（时间流具有高度不确定性，不可靠）、rnn一类的方法（只提取了时间信息没有提取空间信息）、cnn一类的方法（只处理了空间信息，没有结合时间信息）都不太兴，所以本文将图卷积试在交通预测流上。
前置知识：
问题定义如下，简单的说就是即通过前[t-m+1,t] 的交通流量状态来预测[t+1,t+H]的交通流量状态。但因为本文使用的是图卷积，所以是将每一个时刻的整个图的流量视为一个状态，用以预测后续的图的流量状态。
图的结构如下：由 G t = ( V t , E , W ) \mathcal{G}_{t}=\left(\mathcal{V}_{t}, \mathcal{E}, W\right) Gt?=(Vt?,E,W)来定义 V t \mathcal{V}_{t} Vt?表示节点，即各个传感器的位置， E \mathcal{E} E表示边,即各条边相连，W表示权重，即距离。
然后是现有的两种图卷积一种是拓展集合的空间定义，即将顶点重新排列成特定的网格形式以便可以进行卷积，第二种是利用图形傅里叶变换在谱域进行操作，又称为 spectral graph convolution谱图卷积。然后本文使用则引入了图卷积算子的概念，不过本质还是基于谱图卷积。
公式（1）如下： Θ ? G x = Θ ( L ) x = Θ ( U Λ U T ) x = U Θ ( Λ ) U T x \Theta *_{\mathcal{G}} x=\Theta(L) x=\Theta\left(U \Lambda U^{T}\right) x=U \Theta(\Lambda) U^{T} x Θ?G?x=Θ(L)x=Θ(UΛUT)x=UΘ(Λ)UTx,其中 Θ \Theta Θ是kernel， ? G *_{\mathcal{G}} ?G?代表图卷积算子，U则由拉普拉斯矩阵变化而来，即 L = I n ? D ? 1 2 W D ? 1 2 = U Λ U T ∈ R n × n L=I_{n}-D^{-\frac{1}{2}} W D^{-\frac{1}{2}}=U \Lambda U^{T} \in \mathbb{R}^{n \times n} L=In??D?21?WD?21?=UΛUT∈Rn×n,In是一个单位矩阵，D是对角矩阵，其中 D i i = ∑ j W i j D_{ii}=\sum_{j}W_{ij} Dii?=∑j?Wij?， Λ \Lambda Λ是L的特征值对角矩阵，经过上述公式即可将X进行滤波然后进行卷积。
模型
本文提出了spatio-temporal graph convolutional networks (STGCN)模型，模型图如下。这张图应当从左往右看，即右边为左边部分组件的解释。从最左边我们可以看到将输入经过两层ST-Conv blocks，再经过FC即可完成输出。而ST-Conv blocks由三层组成，分别是Temporal Gated-Conv–>Spatial Graph-Conv–>Temporal Gated-Conv组成（其实每层原理都一样，就是通道数变了），然后Temporal Gated-Conv由一个1-D Conv和GLU（门控线性单元）组成。
如何将原来的数据进行转化以进行图卷积？
这里提出，根据之前的谱图卷积，运算量达到 O ( n 2 ) O(n^2) O(n2)，计算代价比较昂贵，所以这里想了两种替代的方法。一种是Chebyshev Polynomials Approximation（切比雪夫多项式逼近）和1st-order Approximation （一阶矩阵估计）。
切比雪夫多项式逼近是将和函数限制为关于 Λ \Lambda Λ的多项式，即 Θ ( Λ ) = ∑ k = 0 K ? 1 θ k Λ k \Theta(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} \Lambda^{k} Θ(Λ)=∑k=0K?1?θk?Λk，其中 θ ∈ R K \theta \in \mathbb{R}^{K} θ∈RK是这个多项式的系数，K是图卷积的核大小，它决定了中心节点卷积的最大半径。而一般来说切比雪夫多项式 T k ( x ) T_{k}(x) Tk?(x)用于作为一个K-1阶的多项式的近似内核表示。即为 Θ ( Λ ) ≈ ∑ k = 0 K ? 1 θ k T k ( Λ ~ ) \Theta(\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\tilde{\Lambda}) Θ(Λ)≈∑k=0K?1?θk?Tk?(Λ~)，其中 Λ ~ = 2 Λ / λ max ? ? I n \tilde{\Lambda}=2 \Lambda / \lambda_{\max }-I_{n} Λ~=2Λ/λmax??In? 。
最终可表示为公式（2） Θ ? G x = Θ ( L ) x ≈ ∑ k = 0 K ? 1 θ k T k ( L ~ ) x \Theta *_{\mathcal{G}} x=\Theta(L) x \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\tilde{L}) x Θ?G?x=Θ(L)x≈∑k=0K?1?θk?Tk?(L~)x，其中 T k ( L ~ ) ∈ R n × n T_{k}(\tilde{L}) \in \mathbb{R}^{n \times n} Tk?(L~)∈Rn×n即为切比雪夫多项式在算子 L ~ = 2 L / λ max ? ? I n \tilde{L}=2 L / \lambda_{\max }-I_{n} L~=2L/λmax??In?的计算结果，这个操作可以将运算复杂度降低到 O ( K ∣ E ∣ ) O(K|\mathcal{E}|) O(K∣E∣).
而第二种方法认为分层线性公式（即前面提到的那个内核函数）可以由局部图卷积和拉普拉斯一阶近似叠加来定义。所以可以将上一段提到的公式（2）变为公式（3）：
Θ
?
G
x
≈
θ
0
x
+
θ
1
(
2
λ
max
?
L
?
I
n
)
x
≈
θ
0
x
?
θ
1
(
D
?
1
2
W
D
?
1
2
)
x
\begin{aligned} \Theta *_{\mathcal{G}} x & \approx \theta_{0} x+\theta_{1}\left(\frac{2}{\lambda_{\max }} L-I_{n}\right) x \\ & \approx \theta_{0} x-\theta_{1}\left(D^{-\frac{1}{2}} W D^{-\frac{1}{2}}\right) x \end{aligned}
Θ?G?x?≈θ0?x+θ1?(λmax?2?L?In?)x≈θ0?x?θ1?(D?21?WD?21?)x?
然后因为
θ
0
\theta_{0}
θ0?和
θ
1
\theta_{1}
θ1?是内核的两个共享参数，为了稳定性能，使
θ
0
=
?
θ
1
\theta_{0}=-\theta_{1}
θ0?=?θ1?，相应的D和W也进行变化，即可得到公式（4）：
Θ
?
G
x
=
θ
(
I
n
+
D
?
1
2
W
D
?
1
2
)
x
=
θ
(
D
~
?
1
2
W
~
D
~
?
1
2
)
x
\begin{aligned} \Theta *_{\mathcal{G}} x &=\theta\left(I_{n}+D^{-\frac{1}{2}} W D^{-\frac{1}{2}}\right) x \\ &=\theta\left(\tilde{D}^{-\frac{1}{2}} \tilde{W} \tilde{D}^{-\frac{1}{2}}\right) x \end{aligned}
Θ?G?x?=θ(In?+D?21?WD?21?)x=θ(D~?21?W~D~?21?)x?
这样做的效果使得逼近在水平方向K-区域的局部卷积效果了。
然后下部分就是这个图卷积算法的泛化，原来只是一个维度上可以拓展到多维度上。对于具有
C
i
C_{i}
Ci?通道的
X
∈
R
n
×
C
i
X \in \mathbb{R}^{n \times C_{i}}
X∈Rn×Ci?，公式可以变为
y
j
=
∑
i
=
1
C
i
Θ
i
,
j
(
L
)
x
i
∈
R
n
,
1
≤
j
≤
C
o
y_{j}=\sum_{i=1}^{C_{i}} \Theta_{i, j}(L) x_{i} \in \mathbb{R}^{n}, 1 \leq j \leq C_{o}
yj?=i=1∑Ci??Θi,j?(L)xi?∈Rn,1≤j≤Co?
其中
C
i
×
C
o
=
Θ
i
,
j
∈
R
K
C_{i} \times C_{o}= \Theta_{i, j} \in \mathbb{R}^{K}
Ci?×Co?=Θi,j?∈RK,Ci、Co是特征映射的输入输出大小。而二维图卷积表示为
Θ
?
G
X
\Theta *_{\mathcal{G}} X
Θ?G?X 其中
Θ
∈
R
K
×
C
i
×
C
o
\Theta \in \mathbb{R}^{K \times C_{i} \times C_{o}}
Θ∈RK×Ci?×Co?，而每个输入的Vt可以被看成一个矩阵，其中它第i列的数值是Ci维度的第i个节点的速度（这里Ci=1，就是第i个输入的时候（打个比分：因为是一步一步向后退的，假如由1-5时间片来推理第6个时间片，这时候1-5都是第一维，但是2-6推理第七个时间片，2-6就是第二维）），此时
X
∈
R
n
×
C
i
X \in \mathbb{R}^{n \times C_{i}}
X∈Rn×Ci?，然后又同时对M的每个时间步长进行相同卷积的操作，最终图卷积可以被扩充到三维，即
X
∈
R
M
×
n
×
C
i
\mathcal{X} \in \mathbb{R}^{M \times n \times C_{i}}
X∈RM×n×Ci?。
Gated CNN
这一块主要就是时间信息的提取，对之前的时间序列用1-D卷积来提取特征，然后GLU是为了作为非线性的手段，同时还有一个残差信息连接的步骤。
Spatio-temporal Convolutional Block**
这一块主要就是用于将之前提取的时间信息和空间信息进行融合，这个block的数量可以根据数据集的需要进行堆砌。然后很简单，就跟上面模型图设计的一样，就是类似于三明治的结构，两个空间信息提取块中间掺杂着一个时间信息提取块。作者认为通过对通道数的变化可以有效的实现尺度压缩和特征压缩。具体公式如下：
v
l
+
1
=
Γ
1
l
?
T
ReLU
?
(
Θ
l
?
G
(
Γ
0
l
?
T
v
l
)
)
v^{l+1}=\Gamma_{1}^{l} *_{\mathcal{T}} \operatorname{ReLU}\left(\Theta^{l} *_{\mathcal{G}}\left(\Gamma_{0}^{l} *_{\mathcal{T}} v^{l}\right)\right)
vl+1=Γ1l??T?ReLU(Θl?G?(Γ0l??T?vl))
然后使用的损失函数就是L2范式，这里就不贴公式了。
实验部分
用了BJER4和PeMSD7数据集进行实验。
结果如下：（反正效果都是SOTA啦，其中PeMSD7又分成了Medium和Large进行实验）
速度预测图
训练收敛图
感悟
第一篇运用图卷积的论文，果然牛！