图卷积神经网络GCN---在交通预测中考虑网络拓扑结构

1、文章信息

《Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting》。

2017年第二十七届IJCAI国际人工智能联合会议的一篇会议论文，作者是北京大学数学科学学院的一名博士生余冰,被引53次。（可能是由于非专业计算机，里面的很多计算机的东西介绍的比较模糊，且更偏重数学推导。）

2、摘要

在本文中，我们提出了一个新的深度学习框架，时空图卷积网络(STGCN)，解决交通领域的时间序列预测问题，我们没有使用常规的CNN和RNN单元，而是将问题用图表示出来，并建立具有完整卷积结构的模型，这使得模型训练速度更快，参数更少。实验表明，STGCN模型通过对多尺度交通网络的建模，有效地捕获了时空相关性。

3、简介

对于深度学习方法而言，常规CNN只能处理网格结构(如图像、视频)，而不处理一般网络结构，而RNN需要迭代训练，引入了逐级累积的误差，且基于RNN的网络(包括LSTM)难以训练，计算量大。为了克服这些问题，我们引入了几种策略来有效地对交通流的时间动态和空间依赖性进行建模。为了充分利用空间信息，我们没有单独处理交通网络，而是用一般的图来对其进行建模（例如网格或路段）。为了解决递归网络的固有不足，我们在时间轴上采用了全卷积结构。总之，我们提出了一种新的深度学习结构，时空图卷积网络，用于交通预测任务。该体系结构由多个时空卷积块组成，时空卷积块由图卷积层和卷积序列学习层组合而成（参考论文Convolutional neural networks on graphs with fast localized spectral filtering），对时空依赖关系进行建模。据我们所知，这是第一次使用图卷积神经网络结构进行交通预测。

4、基础介绍

在本文中，我们在一个图上定义了交通网络，重点研究了结构化交通时间序列。Vt在图中不是相互独立的，而是通过成对连接起来的。因此，数据点Vt可以看作是一个图信号（也就是文中所说的signal），它定义在一个权值为Wij的无向图(或有向图)G上，如图1所示。

在第t时刻，在图Gt = (Vt, E, W)中，Vt是一个有限的顶点集合，对应于交通网络中n个监测站的观测值;E是一组边，表示站点之间的连通性;当W表示Gt的加权邻接矩阵。

常规网格化的标准卷积显然不适用于一般图。目前，有两种基本方法正在探索如何将CNNs推广到结构化数据表。一种是扩展卷积的空间定义（参考论文Learning convolutional neural networks for graphs），另一种是利用图的傅里叶变换在光谱域中进行操作（参考论文Spectral networks and locally connected networks on graphs）。前一种方法将顶点重新排列成特定的网格形式，这些网格形式可以通过常规的卷积操作来处理。后者引入了频谱框架，将卷积应用于频谱域，通常称为频谱图卷积。后续的几项研究通过将计算复杂度从O(n2)降低到线性，使得图卷积更有前景（参考论文1：Convolutional neural networks on graphs with fast localized spectral filtering，参考论文2：Semi-supervised classification with graph convolutional networks）。

本文基于谱图卷积介绍了图卷积算子的概念

，代表图信号x与内核

的乘积。

5、模型框架

如图2所示，STGCN由多个时空卷积块组成，每个卷积块组成类似于“三明治”结构，其中包含两个门控顺序卷积层和一个空间图卷积层。每个模块的细节如下。（最右边的组成中间的，中间的组成左边的，这种表示方法也是有点奇怪）

5.1 Graph CNNs提取空间特征

交通网络一般以图形结构组织。用图来表示道路网络是自然和合理的。然而，以往的研究忽略了交通网络的空间属性，忽略了网络的连通性和全局性，因为它们被划分为多个段或网格。即使使用网格上的二维卷积，由于数据建模的折衷，它也只能粗略地捕获空间局部性。因此，在我们的模型中，将图卷积直接应用于图结构数据，在空间域中提取具有高度意义的模式和特征。式（2）中由于核函数要不断与图的傅里叶基相乘导致计算复杂度很高，本文采用两种近似策略来克服这一问题：切比雪夫多项式近似和1阶近似（推到过程其实可以不用看，直接用推倒结果即可）。近似之后图卷积操作即为：

其中

为邻接矩阵和单位矩阵的和，

为 的度对角矩阵，

为参数矩阵。

图卷积也可扩展到多维张量。

5.2 Gated CNN 门控提取时间特征

我们利用时间轴上的整个卷积结构来捕捉交通流的时间动态行为。这种特殊的设计允许通过多层卷积结构实现并行和可控的训练过程。

如图2(右)所示，时域卷积层包含一个一维卷积，其次是门控线性单元(GLU，这个东西文章里面介绍的模模糊糊，没看懂说的是啥)。此外，在叠加的时间卷积层之间还添加了一个残差连接。

5.3 时空卷积块

为了融合时空域的特征，构造了时空卷积块(ST-Conv块)联合处理图结构时间序列。块本身可以根据特定情况的规模和复杂性进行堆叠或扩展。

如图2 (mid)所示，中间的空间层是连接两个时间层的桥梁，通过时间卷积可以实现图卷积到时间卷积的快速时空传播。“三明治”结构还帮助网络充分应用bottleneck策略（即两头大中间小，两边是64个filter，中间是16个filter），通过图卷积层对通道C（也就是filter）进行下缩放和上缩放，实现尺度压缩和特征压缩。此外，每个层都进行了归一化，防止过拟合。在叠加两个ST-Conv块后，我们在最后附加了一个额外的时域卷积层和一个全连通层作为输出层。

模型特点总结：

STGCN是处理结构化时间序列的通用框架。它不仅能够解决交通网络建模和预测问题，而且可以应用于更一般的时空序列学习任务。

时空卷积块结合了图卷积和门控时间卷积，能够提取出最有用的空间特征，并连贯地捕捉到最基本的时间特征。

该模型完全由卷积结构组成，在输入端实现并行化，参数更少，训练速度更快。更重要的是，这种经济架构允许模型以更高的效率处理大规模网络。

6、实验部分

本文的实验也是用了两个数据集来验证（现在都流行两个数据集了么……），并与几个模型进行了对比，模型对比也并没有说清楚用了什么配置就直接给出了结果……