Graph WaveNet for Deep Spatial-Temporal Graph Modeling

本文详细介绍了dilated casual convolution和TCN的相关知识以及论文Graph WaveNet for Deep Spatial-Temporal Graph Modeling的研究内容和成果

介绍

• 时空图建模旨在通过预定义的图节点间的关联，学习出其内部联系
• 考虑节点间的欧氏距离来预定义图的边的权重是不合理的
• 时空图建模的一个基本假设是一个节点的未来信息受制于其历史信息以及其邻接节点的历史信息，因此如何同时捕获时间和空间依赖成为关键问题
• 两个主要方向的时空图建模：
  • 结合GCN和RNN
  • 用CNN
• 以上方法面临两个主要的短板：
  • 认为图结构的数据组织形式反映了节点间的真实联系
  • 现有的时空图建模方式并不能有效学习到时间关联（算法效率）
• 本文中提出了一个基于CNN的方法名为Graph WaveNet，可以解决以上两个短板，并有以下三个主要贡献：
  • 提出了一个自适应邻接矩阵可以用来维护隐藏的空间依赖。能过够根据数据自动揭露隐藏 的图结构，不需要相关的知识
  • 提供了一个有效且高效的网络框架以同时捕获时空依赖，核心思想是将提出的图卷积和扩展因果卷积相结合（dilated and casual convolution）。每个图卷积层处理由扩展因果卷积提取出的不同粒度的信息

Convolution Network及其变种（反卷积、扩展卷积、因果卷积、图卷积）

方法论

先给出数学定义，再构建框架的模块——图卷积层（GCN）以及时间卷积层（TCN）共同工作以捕获时空关联。最后提出框架的结构。

问题定义

图被定义为，其中是节点的集合，是边的集合，从图中提取出的邻接矩阵。在每个时间戳，图有一个动态的特征矩阵，本文中特征矩阵和图信号可以互换。在给定了图以及其历史步的图信号之后，目标是学习一个可以预测未来步图信号的函数：

其中且

图卷积层

图卷积是提取节点特征的必要操作，在之前的研究中有用自环矩阵标准化的邻接自环矩阵，表示输入信号，表示输出，表示模型参数，图卷积被定义为：

也有提出用扩散卷积（diffusion convolution）的，将随机行走过程控制在有限的步：

其中，而在有向图中，考虑双向，该卷积可以写为：

其中，

本文的主要工作是提出一个自适应邻接矩阵，为了让模型呈现data-driven，随机初始化两个节点嵌入字典，学习出自适应矩阵：

该过程可以被看作是一个隐藏扩散过程的转移矩阵，通过组合预定义的空间关联和自学习的隐藏图之间的关联，可以提出以下图卷积层：

当图结构不可用时，倾向于采取自适应邻接矩阵捕获隐藏的空间关联：

时间卷积层

采用扩展因果卷积（dilated casual convoluition）作为时间卷积层（TCN）以捕获一个节点的时间变化趋势。该网络通过增加TCN层数可以提供指数级别的感受野，和基于RNN的方法对比，扩展因果卷积神经网络能够以一个非递归的方式处理长序列，以至于可以采用并行计算且减缓了梯度爆炸。计算过程中给特征边缘填充0，且卷积核以一个特定的步数跳动

给定一个一维序列和一个卷积核，时刻的扩展因果卷积可以描述为：

其中是扩展因子（dilation）用以控制跳动距离，通过堆叠卷积层，模型的感受野可以实现指数级增长，从而允许网络捕捉更长序列从而节省计算资源

随机在TCN中仿照RNN引入门控机制，一个简单的Gated TCN只包括一个输出门：

其中输入，，，以及都是模型参数，是哈达玛乘积，是输出层的激活函数（这里采用），是型函数用以决定信息去往下层的通过率

Graph WaveNet框架

Graph WaveNet的结构如下：

Sikp Connection相关介绍

Graph WaveNet由时空层和一个输出层堆叠而成，通过堆叠多层卷积层，网络可以处理不同时间标准的空间依赖，例如在底层GCN处理的是短程的时间信息，但是在顶层GCN处理的就是长程的时间信息。

训练过程中，卷积层的输入为，其中是节点数，是隐藏的维数，是序列长度，每层的图卷积输入为，选用作为训练时的损失函数：

不同于基于RNN方法的encoder-decoder结构，最终的输出为一个整体而不是分步输出，为了解决训练和测试时的不一致性，手动调整感受野，以至于最后一层卷积层的输出为一维即可。

实验

在METR-LA和PEMS-BAY两个数据集上验证了模型效果

基准

• ARIMA
• FC-LSTM
• WaveNet
• DCRNN
• GGRU
• STGCN

原文

---

• ← Previous Post
• Next Post →

---

---