STGCN_IJCAI_18论文阅读笔记

Spatio-Temporal Graph Convolutional Networks:A Deep Leaning Framework for Traffic Forecasting

摘要

及时准确的交通预测在城市交通控制和指导方面具有重要的作用。由于交通流的非线性和复杂性。传统的方法无法满足中长期预测任务的要求,而且通常忽略空间和时间的依赖关系,在本篇文章中,提出了时空图卷积网络(STGCN)。与传统方法使用正常的卷积和循环单元相比,我们在图上建立了问题,并使用全卷积的方式建立模型。使得参数较少,训练速度较快。实验证明STGCN可以有效的捕获复杂的时空关系。

介绍

准确实时的交通状况的预测对道路使用者,私营部门和政府非常重要。
广泛使用的交通服务,比如流量控制,路径规划和导航,都依赖高质量的交通状态的评估。
通常多尺度的交通预测是城市交通控制和指导的基础和前提。
在对交通的研究中,交通流量的基本变量,比如速度,流量,和密度作为交通状态的指标。
交通预测通常分为两个尺度:短期(5-30min),中长期(30min以上)
之前中长期的预测,可以大致分为两类:动态模型和数据驱动
动态模型是使用数学方法(比如差分方程)和物理知识使用计算仿真建立交通问题。为了达到稳定的状态,仿真不仅需要复杂的编程,也要大量的计算。其中不符实际的假设和简化建模也降低了预测精度。因此,随着交通数据采集与存储的快速发展技术方面,一大批研究人员正在将注意力转移到数据驱动的方法上。
经典的统计方法和机器学习方法是数据驱动的两个主要代表性方法。
现在深度学习的方法广泛应用在不同的交通任务上。在相关工作上取得了巨大的进展,比如深度置信网络DBN,堆叠自动编码器(SAE),但是在这些密集的网络中提取空间和时间特征是困难的。更何况,在严格的限制甚至没有空间属性的条件下,这些网络的表示能力,受到了严重的阻碍。
为了更好的利用空间特征,一些研究者使用CNN来捕获交通网络的邻接关系,同时,在时间轴上使用RNN。通过把LSTM和1D-CNN结合起来,Wu和Tan使用特征融合的结构CLTFP进行短期的交通预测。虽然采用的直接的方法,CLTFP是把空间和时间对齐的第一次尝试。之后Shi 提出了卷积的LSTM,在全连接LSTM(FC-LSTM)上使用嵌入卷积层的方法对LSTM进行扩展。然而,通常的卷积运算只能处理网络结构(如图像)而不是一般域,同时序列模型的RNN模型,需要迭代计算,会累积误差,同时训练难度大,计算量大。
为了解决上述的问题,我们引入了几个方法来有效的对交通流的时间动态和空间依赖进行建模。为了更好的利用空间信息,我们把交通网络看作一个普通的图,而不是独立的处理它,(比如,网格或者片段)。为了解决循环网络的继承关系,我们在时间轴上使用全卷积的结构。总之,我们提出了一个新的深度学习结构–时空图卷积网络进行交通预测。这个结构包含了几个时空卷积模块,它是由图卷积层和卷积序列学习层组成,对空间和时间依赖进行建模。据我们所知,这是第一次只用卷积结构从图结构的时间序列中提取空间和时间特征,实验表明,我们的框架,在多个预设的预测长度和结构尺度上优于现存的基线。

预备知识

道路图上的交通预测

交通预测是一个典型的时间序列的预测问题,比如 :在给定之前的M个时间步观测到的速度,预测接下来H个时间步的最有可能的速度。用公式表示为:
equation01
其中$v_t \in \mathbb{R}^n$ 是$n$条路段在$t$时间步的观测向量。每一个元素是一条路段的历史观测值。
在我们的工作中,我们在图上定义了交通网络,关注域结构化的交通时间序列。观察到的$v_t$不是独立的,而是在图中成对连接在一起的,因此,如Figure1所示,数据点$v_t$可以看作一个定义在具有权重 $W_{ij}$ 的无向图$G$(或有向图)上的图信号。在第$t$个时间步,在图$G_t =(V_t,\varepsilon,W)$中,$V_t$是顶点的有限集合。对应在交通网络中n个检测站。$\epsilon$是边的集合,表示站点之间的连接。$W \in \mathbb{R}^{n \times n}$ 表示$G_t$的含有权重的邻接矩阵

在图上卷积

规则的标准卷积显然不适合通常的图。现在一般有两种方式探究怎么把CNN推广到结构化的数据形式。一个是扩展卷积的空间定义,另一个使用傅里叶变换到谱域操作。第一种方法是把顶点重新排列为可以通过常规卷积处理的某种网格结构。第二种是引入谱框架,在谱域进行卷积。通常称为谱图卷积。通过把计算复杂度从$O(n^2)$降低到线性,使得图卷积更具有前景。
我们基于谱图卷积的概念,介绍在图卷积$*G$的概念。也即是信号$x \in \mathbb{R}^n$与核$\Theta$的乘积。
equation02

提出的模型

网络结构

在这个章节,我们详细的介绍时空图卷积网络(STGCN)的结构,如图2。STGCN包含了几个时空卷积块,每个块是具有“三明治”结构,两个门序列卷积层和一个空间图卷积层。
figure02

提取空间特征的图卷积网络

交通网络通常组织成图结构,把路网看作数学上的图是正常且合理的。然而,之前的研究忽视了交通网络的空间属性。网络的连接和全局性被忽视了,因为他们被分成了多个片段和网格。即使在网格上使用2-D卷积,也只能捕获到空间位置信息。在我们的模型中直接在图上做卷积提取模式和特征。由于直接计算核$\Theta$计算比较昂贵,可以使用两种方法解决这个问题

切比雪夫多项式近似

为了局部化过滤器核减少参数的数量,核$\Theta$可以限制为$\Lambda$的多项式,记作$\Theta(\Lambda)= \sum_{k=0}^{K-1}\theta_k\Lambda^k$,其中$\theta \in \mathbb{R}^K$ 是多项式系数的向量,K是图卷积的核大小,决定了从中心节点卷积的最大半径。通常,切比雪夫多项式$T_k(x)$用于将核近似为K-1阶的截断展开,$\Theta(\Lambda) \approx \sum_{k=0}^{K-1}\theta_kT_k(\widetilde{\Lambda})$,其中$\widetilde{\Lambda} = 2\Lambda /\lambda_{max} - I_n$($\lambda$ 表示L的最大特征值)。然后图卷积可以写作:
$$
\Theta_{*G}=\Theta(L)x \approx \sum_{k=0}^{K-1}\theta_kT_k(\widetilde{L})x (3)
$$
其中$T_k(\widetilde{L}) \in \mathbb{R}^{n \times n}$ 是尺度$\widetilde{L}=2L/\lambda_max - I_n$变化后计算的在k阶切比雪夫多项式,通过多项式递归地计算K-localized卷积,算式2的花费可以减少到$O(K|\epsilon|)$

1阶近似

分层线性公式可以定义为,使用图的拉普拉斯一阶近似叠加多个局部图卷积层,。因此,形成一个更深的结构可以恢复空间信息,而不会被多项式的参数所限制。因为在神经网络中的尺度变换和归一化,我们可以进一步假设$\lambda \approx 2$,这样公式3 可以简化为:
$$
\Theta_{*G} \approx \theta_0 x + \theta_1 (\frac{2}{\lambda_{max}} L - I_n ) x
\approx \theta_0 x - \theta_1 (D^{-\frac{1}{2}}WD^{-\frac{1}{2}})x
$$

其中$\theta_0,\theta_1$s是核共享的参数。为了约束参数核稳定数值性能,$\theta_0$和$\theta_1$使用一个$\theta$替换,使得$\theta = \theta_0= -\theta_1$ ,$W$和$D$ 再通过$\widetilde{W}=W+ I_n ,\widetilde{D}_{ii}=\sum_j\widetilde{D}{ij}$分别归一化,然后图的卷积可以表示为
$$
\Theta{*G} x = \theta(I_n + D^{-\frac{1}{2}} W D^{-\frac{1}{2}}) x
= \theta(\widetilde{D}^{-\frac{1}{2}} \widetilde{W} \widetilde{D}^{-\frac{1}{2}})x
$$
应用具有1阶近似的图卷积垂直层叠,达到了和K-localized水平卷积相似的效果。都利用了K-1阶的邻居信息。在这种情况下,K是在模型中连续滤波操作或者卷积层的数量。此外,分层的线性结构对于大型图来说是参数经济和高效的,因为近似的阶数被限制为1.

图卷积的推广

在$x \in \mathbb{R}^n$ 上的图卷积操作“$*G$”可以推广多维的张量,对于具有$C_i$通道的信号,$X \in \mathbb{R}^{n \times C_i}$,图卷积可以推广为:
$$
y_i = \sum_{i=1}^{C_i} \Theta{i,j}(L)x_i \in \mathbb{R}^n 1 \leq j \leq C_0
(6)
$$
切比雪夫系数$\Theta_{i,j} \in \mathbb{R}^K$的$C_i \times C_o$ 向量($C_i,C_o$ 是特征的输入和输出)。对于2维变量的卷积表示$\Theta_{\ast G}$为其中$\Theta \in \mathbb{R}^{K \times C_i \times C_0}$.特别地,交通预测的输入是由M帧路图作为输入,正如图1所示,每帧$v_t$可以看作一个矩阵,它的列i 是图$G_t$中第i个节点$v_t$d的$C_i$维的值。$X \in \mathbb{R}^{n \times C_i}$(在这个例子中$C_i=1$),对于M中的每个时间步,使用相同的核$\Theta$进行图卷积操作并行地施加在$X_t \in \mathbb{R}^{n \times C_i}$ 这样,图卷积可以进一步推广到3维变量中,表示为$\Theta_{\ast G} \chi $其中 $\chi \in \mathbb{R}^{M \times n \times C_i}$
figure01

提取时间特征的门CNNs

虽然基于RNN的模型,在时间序列分析中广泛应用。但是循环网络在交通预测中,具有耗时的迭代,复杂的门机制和对动态变化反应较慢。与此相比,CNN具有快速训练的优势,简单的结构和不依赖之前的步骤。所以在Gehring2017的启发下,我们在时间轴采用了卷积的结构获取交通流的时间动态表现。这个特定的设计使得通过层次表示的多层卷积结构可以并行和可控的训练过程。
正如图2显示那样,时间卷积层包含了一个具有宽度为$K_t$卷积核的1-D因果卷积,之后是一个门线性单元(GLU)作为一个非线性。在图G中节点,时间卷积利用输入元素的$K_t$个邻居(不用padding),这样可以每次把序列减少$K_t -1$.这样的话,每个节点时间卷积的输入看作一个长度为M,通道为$C_i$的序列,$Y \in \mathbb{R}^{M \times C_i}$. 卷积核 $\Gamma \in \mathbb{R}^{K_t \times C_i \times 2C_0}$,用来将输入Y映射为一个单独输出元素

我写的PPT,包含了内容