时空序列

GaAN (UAI 2018)

GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs

arxiv:https://arxiv.org/abs/1803.07294

前言前言前言

这回介绍的时间线和前一篇差的不多，是发表在2018 UAI上的一篇论文。说是解决交通预测问题吧，但这篇文章其实大篇幅介绍的是门控注意力聚合机制（Gated Attention Aggregator），但在文章的最后也基于这个聚合机制提出了Graph GRU（GGRU）用来解决交通预测问题，就是这部分内容只是相当于把原先GNN+GRU中GNN部分的聚合函数做了个修改。所以我有点不知道该不该把这篇文章放到时空序列分析这个tag下了。

言归正传，照例从头开始介绍，在摘要部分，文章提到了该文主要解决的问题是在图卷积神经网络中，多头注意力机制中每个头的重要性都是一致的，而在实际情况中，每个头注意力得到的不同的特征子空间往往拥有不同的重要程度。为了解决这个问题，文章设计了一个卷积子网络来对重要性进行控制。（重要性的重要性，😀）

在Introduction部分，因为本文实际上是从图卷积神经网络的改进入手的，所以行文逻辑是从GNN走的，首先提出传统的利用图的方法是利用图的统计信息、人为提取（特征工程）等方法；之后进入Graph Convolution Network阶段，在图神经网络阶段，其实所有的操作都可以被抽象定义为一个聚合操作，通过叠加聚合操作来帮助节点学习局部和全局的信息，再构建一个端到端的系统进行学习。GNN可以分为频域和空域，频域GCN由于其消耗资源量大，计算慢的问题而无法适用于大规模图，所以GaAN基于的是空域的GraphSage。在之前的介绍中也可以看出，对于GNN而言，图聚合（Graph Aggregrate）是最重要的，也是整个图神经网络的基石(现有的图聚合方法主要有pooling和加权求和两种方法),一个优秀的聚合函数需要能根据邻居节点信息动态的调整权重，而注意力网络就能满足这样的需求。注意力网络有单头注意力网络和多头注意力网络两种，多头注意力网络是在单头的基础上叠加head，以帮助网络学习不同的特征子空间，但对于聚合函数而言，在聚合过程中让所有特征子空间具有相同的注意力得分显然不合理。因此，本文提出了GaAN，利用卷积自网络为重要性计算重要性。

GaAN的优势主要有以下几点：

1、可以通过这个门控机制控制head的数量（传统超参设定的multi-head在网络学习过程中head数固定，但GaAN可以通过Gate来减少head的数）

2、改动只加入了一个小的子网络，开销小，训练简单

3、在节点分类任务中使用了采样策略，减少了内存的消耗，提升了运行效率。

除了将GaAN应用于节点分类任务，文章的最后还提出了GGRU用来解决交通预测问题（终于😂）。

相关工作中介绍了注意力网络、大图上的图卷积网络以及图神经网络在时空预测上的应用。前两个不再介绍了，主要在我的认知里没有特别有意思的需要特别讲一下的东西，第三个介绍了GCRNN->DCRNN->GGRU。GCRNN是将LSTM中的全连接层替换为了ChebNet的操作（本来想着要不要再开个坑的，瞄了一眼发现挺简单的，就不再向前考古了）。DCRNN上回的文章刚介绍过，也不展开了。GGRU的不同点在于它给出了一个可以使用任意图聚合器的框架，而不是如同GCRNN、DCRNN这类的具体模型。

欸，一反常态，下面直接进模型，这里的问题定义我就不具体展开了，符号的定义之类的会在公式附近直接给，GO~

模型模型模型

模型主要介绍的就是Gated Attention Networks，因为这玩意核心还是个聚合操作，先给出Graph里聚合的数学表示：
yi=γΘ(xi,{zNi}) y_i = \gamma_{\Theta}(x_i,\{z_{\mathcal{N}_i}\})

这里的yiy_i和xix_i分别表示目标节点的输出和输入，γ\gamma表示聚合函数，Θ\Theta表示参数，zNiz_{\mathcal{N}_i}表示目标函数的邻居节点集合。本模型没有利用边的特征，但如果要引入也是比较方便的。

多头注意力聚合（Multi-Head Attention Aggragate）

OK，先来看一下基本的多头注意力聚合机制，这块挺简单的，我直接放公式了：
yi=FCθo(xi⊕∣∣Kk=1∑j∈Niwi,j(k)FCθv(k)h(zj))wi,j(k)=exp(ϕw(k)(xi,zj))∑l=1∣Ni∣exp(ϕw(k)(xi,zl))ϕw(k)(x,z)=<FCθxa(k)(x),FCθxa(k)(z)> \begin{aligned} y_i=&FC_{\theta_o}(x_i\oplus\underset{k=1}{\overset{K}{||}}\sum_{j\in\mathcal{N}_i}w_{i,j}^{(k)}FC^h_{\theta_v^{(k)}}(z_j))\\ w_{i,j}^{(k)}&=\frac{exp(\phi_w^{(k)(x_i,z_j))}}{\sum_{l=1}^{|\mathcal{N}_i|}exp(\phi_w^{(k)}(x_i,z_l))}\\ \phi_w^{(k)}&(x,z)=<FC_{\theta_{xa}^{(k)}}(x),FC_{\theta_{xa}^{(k)}}(z)> \end{aligned}

这里的FCFC表示全连接层，θ\theta表示对应的参数，hh表示激活函数，FCFC右上角有符号表示全连接层最外层有一个激活函数，wi,j(k)w_{i,j}^{(k)}表示第k个head中邻居节点jj对邻居节点ii的权重得分。这一块的内容其实和GAT中的注意力机制很像，唯一不同的点在于ϕW(k)\phi_W^{(k)}的计算方式中，下面给出GAT中注意力分数的计算公式:

wi,j=exp(LeakyReLU(aT[Whi∣∣Whj]))∑k∈Niexp(LeakyReLU(aT[Whi∣∣Whj])) w_{i,j} = \frac{exp(LeakyReLU(a^T[Wh_i||Wh_j]))}{\sum_{k\in\mathcal{N}_i}exp(LeakyReLU(a^T[Wh_i||Wh_j]))}

对应的ϕw(k)\phi_w^{(k)}就是aT[Whi∣∣Whj]a^T[Wh_i||Wh_j]。相较于GaAN的点积操作，GAT使用了一个全连接层。

门控注意力聚合

拍个图，图里是一个门控注意力聚合器的示例：

gaagaa

从基础的多头注意力公式里可以发现，模型对于不同head的结果其实就是直接做了一个concat操作，这相当于将不同特征子空间的重要性设成一致，但这显然不合理，所以论文设计了一个卷积层来计算重要性的重要性，为每个head的表征再计算了一个重要性得分gig_i，公式表示如下：
yi=FCθo(xi⊕∣∣Kk=1(gi(k)∑j∈Niwi,j(k)FCθv(k)h(zj)))gi=[gi(1),..,gi(k)]=ψg(xi,zNi) \begin{aligned} y_i=&FC_{\theta_o}(x_i\oplus\underset{k=1}{\overset{K}{||}}(g_i^{(k)}\sum_{j\in\mathcal{N}_i}w_{i,j}^{(k)}FC^h_{\theta_v^{(k)}}(z_j)))\\ g_i&=[g_i^{(1)},..,g_i^{(k)}] = \psi_g(x_i,z_{\mathcal{N}_i}) \end{aligned}

其中gi(k)g_i^{(k)}是第k个head对于节点ii的门控得分。而如何获得这个得分就有很多种方法了，为了控制参数量和速度，本文使用了一个卷积子网络，公式如下：
gi=FCθgσ(xi⊕maxj∈Ni({FCθm(zj)})⊕∑j∈Nizj∣Ni∣) g_i = FC_{\theta_g}^\sigma(x_i\oplus\underset{j\in\mathcal{N}_i}{max}(\{FC_{\theta_m}(z_j)\})\oplus\frac{\sum_{j\in \mathcal{N}_i}z_j}{|\mathcal{N}_i|}) 这里θθm\theta_{\theta_m}代表了全连接层中将特征维度映射到dmd_m的参数，θg\theta_g表示将concat完的向量映射到k维的参数。值得注意的是，这个计算中使用了最大池化和平均池化，获得的得分再[0,1][0,1]之间。

其他图聚合器

再拍个图，图里是不同图聚合器的示例：

aggregatoraggregator

为了方便对比文章中提出的聚合器和原始的聚合器，文章也介绍了常用的两种图聚合器。现有的聚合器可以分为Graph pooling aggregator和Graph pairwise sum aggregator两类。

Graph pooling aggregator可以说是最基本的一种聚合器，它不考虑周围节点与中心节点的关系，用公式可以表示为：
yi=ϕo(xi⊕poolj∈Ni(ϕv(zj))) y_i = \phi_o(x_i\oplus pool_{j\in\mathcal{N}_i}(\phi_v(z_j)))

Graph pairwise sum aggregator则和基于注意力的聚合器很相近了，但这种聚合会少一个softmax的过程，即得分仅仅与目标节点i及其邻居节点j相关。用公式可以表示为：
yi=ϕo(xi⊕∣∣Kk=1∑j∈Niwi,j(k)ϕv(k)(zj))wi,j(k)=ϕw(k)(xi,zj) \begin{aligned} y_i &= \phi_o(x_i\oplus\underset{k=1}{\overset{K}{||}}\sum_{j\in\mathcal{N}_i}w_{i,j}^{(k)}\phi_v^{(k)}(z_j))\\ w_{i,j}^{(k)}&=\phi_w^{(k)}(x_i,z_j) \end{aligned}

之后，文章根据这两个种类选了几个baseline，博客里我不太像介绍实验部分，就是想单纯记录一下思路，就不展开了。（后面还有一部分节点分类的实验设置和具体的实验数据我也略过了）

Graph GRU
再再拍个图：

GGRUGGRU

Graph GRU是针对交通速度预测提出的一个基于门控注意力聚合器的模型，和之前介绍的问题一样，这里也是希望能通过过去的J\mathcal{J}步X1,X2,...,XJX_1,X_2,...,X_J预测未来的K步X^J+1,...,hatXJ+K\hat{X}_{J+1},...,hat{X}_{J+K}，其核心也是改写了一下GRU，和DCRNN那边很像，直接给公式了哈：
Ut=σ(ΓΘxu(Xt,Xt;G)+ΓΘhu(Xt⊕Ht−1,Ht−1;G))Rt=σ(ΓΘxr(Xt,Xt;G)+ΓΘhr(Xt⊕Ht−1,Ht−1;G))Ht′=h(ΓΘxh(Xt,XT;G+Rt∘ΓΘhh(Xt⊕Ht−1,Ht−1;G)))Ht=(1−Ut)∘Ht′+Ut∘Ht−1 \begin{aligned} U_t &= \sigma(\Gamma_{\Theta_{xu}}(X_t,X_t;\mathcal{G})+\Gamma_{\Theta_{hu}}(X_t\oplus H_{t-1},H_{t-1};\mathcal{G}))\\ R_t &= \sigma(\Gamma_{\Theta_{xr}}(X_t,X_t;\mathcal{G})+\Gamma_{\Theta_{hr}}(X_t\oplus H_{t-1},H_{t-1};\mathcal{G}))\\ H^{'}_t&=h(\Gamma_{\Theta_{xh}}(X_t,X_T;\mathcal{G}+R_t\circ\Gamma_{\Theta_{hh}}(X_t\oplus H_{t-1},H_{t-1};\mathcal{G})))\\ H_t&=(1-U_t)\circ H^{'}_t +U_t\circ H_{t-1} \end{aligned}

这里面Xt∈R∣V∣×diX_t\in\mathbb{R}^{|\mathcal{V}|\times d_i}和Ht∈R∣V∣×doH_t\in\mathbb{R}^{|\mathcal{V}|\times d_o}分别表示模型的输入特征和在第t个时间步的隐藏状态，另外的参数都是GRU中的参数，UtU_t和RtR_t分别是更新门和重置门。

总结总结总结

总的来看哈，这篇文章介绍的是计算重要性的重要性，反而对时空序列这一块的创新没那么多。就是这个门控聚合函数可以作为一个组件加入到其他的网络中以作为一个小改进。