Graph WaveNet - 学习笔记

1. 文章摘要

时空图建模是分析时间关系和空间关系的重要任务，过去的方法大多数都是从固定的图结构上提取空间依赖性，假设实体之间的基本关系是预先确定的。但是，显式的图结构不一定反应真实的以来关系，而且由于数据中连接不完整，可能缺少真正的关系。RNN和CNN又有各自的缺陷，无法捕捉长时间的序列，因此，该文章提出一种新的图神经网络架构Graph WaveNet用于时空图建模，通过开发一种新的自适应依赖关系矩阵，并通过节点嵌入的方式来进行学习。该模型可以捕捉数据中隐藏的空间以来关系，借助堆叠的膨胀1-D卷积，能够随着层数增加感受到宽广的感受野，从而处理非常长的序列。
该论文主要用于解决时空建模问题上图结构不确定性问题，通过自适应的可学习的邻接矩阵从数据中自动学习图结构，该论文是基于wavenet网络改进的。
论文主要思路：
时空图建模背后的一个基本假设是：一个节点的未来信息取决于它的历史信息以及它邻居节点的历史信息。但是这种模型存在两个主要的缺点：

显式的图结构不能充分的反应真实的依赖关系（空间）：
- 连接不需要两个节点之间的相互依赖关系
- 两个节点之间的相互依赖关系存在但连接缺失
时空图不能有效地学习时间依赖关系（时间）：
- 基于RNN的方法在捕获长序列时存在耗时的迭代传播和梯度爆炸/消失现象；
- 基于CNN的方法具有并行计算、稳定梯度和低内存需求等优点。然而，由于采用标准的一维卷积，其感受野大小随隐藏层数的增加而线性增长，因此需要使用许多层才能捕获很长的序列。

论文原文：https://arxiv.org/pdf/1906.00121.pdf

代码地址：github.com/nnzhan/Graph-WaveNet

2. 问题定义

交通预测问题，可以认为是给定一张图

图结构

其中V是节点，E是边，交通预测问题可以描述为：

式中：

分别表示X个特征在过去T个时刻的值（流量变化情况），这里N是节点数，D是数据维数，T是时间步，简单来说就是用过去的S步预测未来的T步。

3. 空间卷积

GCN时代：
GCN公式
其中要求邻接矩阵A已知，实际上很多情况下，A可能是变化的，或者存在未能被挖掘到的节点，对当前节点存在影响。文章不用传统的GCN，而是用了扩散的卷积层，形式如下：
扩散图卷积公式
式中：Pk代表是转移矩阵的k次乘方，K的次数是可以改变的，X是原来的特征，对于无向图，P=A/rowsum(A)，对于有向图，区分正反向，正向是Pf=A/rowsum（A），反向是Pb=At /rowsum(A_T)
从而扩散图卷积层可以写成式4的形式。

4. 自适应邻接矩阵

文章同时提出一种自适应邻接矩阵的概念，这种矩阵不需要任何先验知识，而且是可以从端到端的方式进行梯度下降训练。可以表示成：
自适应邻接矩阵定义
这里面，E1 E2是两个可学习的Embedding矩阵，案例来说应该就是原始输入X乘了一个Embedding矩阵之后得到的。这个公式的形式，和自注意力的计算公式不能说一模一样只能说完全一致

（自注意力的计算公式，Q Kt分别对应这里的E1 E2）区别在于文章这里加了个Relu （这是GAT的做法）只关注对当前节点正向的内容。
所以，在图已知的情况下，GWNet可以用式6的方式计算图卷积，如果是图未知的情况下，就用公式7计算
GVNet提出的图卷积计算公式
文章提到：值得注意的是，我们的图卷积属于基于空间的方法。尽管为了保持一致性，我们将图信号与节点特征矩阵互换使用，但我们在方程 7 中的图卷积确实被解释为聚合来自不同邻域顺序的转换特征信息。