ASTGNN (Learning Dynamics and Heterogeneity of Spatial-Temporal Graph Data forTraffic Forecasting)

标签：Forecasting ASTGNN 卷积 Graph 节点序列空间注意力输入

引言

时空神经网络(STGNNs)被广泛应用于交通预测问题中，在STGNNs中每个节点代表一个交通监测站，边表示道路网络。

在动态预测中，物理量x(t)随时间的变化模型是一个黑盒模型，我们要做的事情就是对黑盒模型进行建模。线性自回归方法直接将动态变化规律看成线性的，这使得动态变化完全由参数所决定。这带来了两个问题：1.动态规律变成线性的了；2.这种动态变化规律不会随着时间的变化而变化，也就是说之前时刻的输入并不影响动态变化。RNN通过一个上下文向量来进行动态建模，并使用非线性激活函数进行递归更新。RNN虽然解决了线性化的问题，但是动态规律依然不会随着时间的变化而变化，因为模型的参数依然与之前时刻的输入无关。CNN也有同样的问题，因为卷积核相对于输入是不变的。

而在空间关系上，目前的方法是在道路网路图上执行图卷积，其结构是静态的。也就是说，这些方法认为空间相关性是恒定的，而这种看法在现实中是不成立。

同时，现存的方法很难做出准确的长期预测。RNN容易遇到梯度消失问题；由于卷积核的感受野有限，因此CNN很难捕获长距离的依赖性。即使是专门用于序列预测的TCN，仍然需要堆叠几个卷积层来连接序列中的任意两个位置，这削弱了其学习长期依赖关系的能力。

交通数据带有一定的周期性，显式地对周期性进行建模有利于预测。另外，空间的异质性也是流量预测中的重点。不同的位置具有不同的交通模式，空间的异质性与道路类型、速度限制和POI(兴趣点)等静态特征有关，但是在现实中我们不一定能捕获到这种特征。因此，如何在只有道路网络结构的情况下捕捉空间异质性仍然是一个亟待解决的问题。

为了解决上述问题，本文提出了一种基于自注意力机制的预测模型——ASTGNN(Attention baesd Spatial-Temporal Graph Neural Network)。ASTGNN中的参数依赖于输入，并且每个符号的表示能够直接感受到序列中其他符号的影响，这样的全局感受野能够使模型做出准确的长期预测。除此之外，本文还显示表示了周期性和空间异质性。

问题陈述

定义

交通网络

我们将交通网络定义为一个有向图或无向图G=(V,E)， $\left | V \right |=N$ 表示G的节点，对应于交通监测站； $\left | E \right |=M$ 表示G的边，对应于道路。

交通信号矩阵

交通网络G在时刻t的观测值由交通信号矩阵 $X_t=(x_{t,1},\ x_{t,2},...,\ x_{t,N} )^T \in \mathbb{R}^{N \times C}$ 给出，其中 $x_{t,v} \in \mathbb{R}^C$ 表示节点v在t时刻的特征向量，C表示特征的数量。

问题陈述

流量预测

给定过去 $T_h$ 个时刻的历史时空交通信号矩阵：

$\mathcal{X} =(X_{t-T_h+1},\ X_{t-T_h+2},...,\ X_t) \in \mathbb{R} ^{N\times C\times T_h}$

一个全局周期序列 $\mathcal{X}_g$ 和一个局部周期序列 $\mathcal{X}_l$ ，预测未来 $T_p$ 个时刻的交通信号矩阵序列：

$\mathcal{Y} =(X_{t+1},\ X_{t+2},...,\ X_{t+T_p}) \in \mathbb{R} ^{N\times C\times T_p}$

注意力机制

注意力机制的目的是将一个请求和一组键值对映射到一个输出，其中查询、键、值和输出都是向量。输出是值得加权和，并且每个权重由相应的键和请求共同决定，表示请求和每个键值对之间的关联性强度。

Scaled Dot-Product Attention

Scaled Dot-Product Attention的权重计算为请求和值之间的点积，因此它具有较好的空间和时间效率特性。它的定义如下：

$Attention(\mathbf{Q,K,V})=softmax(\frac{\mathbf{QK}^T}{\sqrt{d_{model}}})\mathbf{V} \ (1)$

其中， $\mathbf{Q},\ \mathbf{K},\mathbf{V}$ 和 $d_{model}$ 分别是请求、键、值和它们的维度。

注意力时空图神经网络(Attention Based Spatial-Temporal Graph Neural Networks, ASTGNN)

ASTGNN建立在一个通用的编码解码器结构上，编码器和解码器都由一堆相同的层堆叠而成。为了保证随着模型变深依然能够完成有效的训练，在blocks内部还使用了残差链接和层归一化。并且编码器中的每一层都有相同的维度 $d_{model}$ 。

记输入到第l个编码器层的输入为：

$\mathcal{X} ^{(l-1)}=(\mathcal{X}_{t-T_h+1}^{l-1}, \mathcal{X}_{t-T_h+2}^{l-1},...,\mathcal{X}_{t}^{l-1}) \in \mathbb{R}^{N\times d_{model} \times T_h}$

其中 $l \in \left \{ 1,2,...,L \right \}$ ，ASTGNN的工作流程如下：

通过具有空间嵌入层和时间嵌入层的线性投影将原始输入 $\mathcal{X} \in \mathbb{R} ^{N \times C \times T_h}$ 转换为一个维度更高的表示 $\mathcal{X}^{(0)} \in \mathbb{R} ^{N \times d_{model} \times T_h}$ 。
通过L层编码器将输入序列 $\mathcal{X}^{(0)} =(X_{t-T_h+1}^{(0)},X_{t-T_h+2}^{(0)},...,X_t^{(0)})$ 映射到一系列的中间表示 $\mathcal{X}^{(L)} =(X_{t-T_h+1}^{(L)},X_{t-T_h+2}^{(L)},...,X_t^{(L)})$ 。
通过调节编码器的输出 $\mathcal{X}^{(L)}$ ，解码器采用另一个L'层的解码器层来生成未来交通信号的输出序列 $\mathcal{Y}^{(L')} =(X_{t+1}^{(L')},X_{t+2}^{(L')},...,X_{t+T_p}^{(L')})$ 。为了生成每一步的 $\mathcal{Y}^{(L')} _i$ ( $i \in \left \{ 1,...,T_p \right \}$ )，解码器将 $\mathcal{X}^{(L)}$ 和所有之前生成的交通信号矩阵 $\mathcal{Y}^{(L')} _{1:i-1}$ 作为输入。
通过线性投影把 $\mathcal{Y}^{(L')}$ 映射到目标输出 $\mathcal{Y}$ 。

时空编码器

时空编码器由许多相同的层堆叠而成，每一层都包含两个基本模块：时间趋势感知多头自注意力块和空间动态GCN块。时间趋势感知多头自注意力块致力于对交通数据在时间维度上的动态性进行建模；空间动态GCN块试图去捕捉交通数据的空间相关的动态规律。

时间趋势感知多头自注意力

多头自注意力的基本操作是scaled dot-product attention((1)式， $\mathbf{Q}=\mathbf{K}=\mathbf{V}$ )。多头自注意力首先将请求、键和值线性投影到不同的表示子空间中，然后执行公式(1)；最后将输出融合并进一步投影，得到最终的输出。

$MHSelfAttention(\mathbf{Q,K,V})=\bigoplus (head_1,...,head_h)W^O \ (2)\\ head_j=Attention(\mathbf{Q}W^Q_j,\mathbf{K}W^K_j,\mathbf{V}W^V_j)\ (3)$

其中，h式注意里头的序号， $W^Q_j,W^K_j,W^V_j$ 式应用到 $\mathbf{Q,K,V}$ 上的投影矩阵， $W^O$ 式最后的输出映射矩阵。不管序列中的元素相距多远，多头自注意力都允许对元素的相关性进行建模，这使得模型有有效的全局感受野。它提供了一种灵活的方式来捕捉交通数据中复杂的动态相关性，从而实现准确的长期预测。

然而，多头自注意力最初是为了处理离散token，并没有考虑连续固有的局部趋势信息。因此，简单地将其应用于交通信号序列变换可能会导致不匹配问题。为了解决数值数据预测中传统多头自注意力的局部趋势不可知问题，本文设计了一种时间趋势感知的多头自注意力机制，该机制考虑了局部上下。时间趋势感知多头自注意力在节点之间共享，他是卷积自注意力的变体，替代了式(3)得投影操作。由于卷积运算通过将局部上下文作为输入来计算表示，这使得模型能够感知隐藏在交通数据序列中的局部变化趋势。

$TrSelfAttention(\mathbf{Q,K,V})=\bigoplus (Trhead_1,...,Trhead_h)W^O \ \\ Trhead_j=Attention(\Phi ^Q_j\star \mathbf{Q},\Phi ^K_j\star \mathbf{K},\mathbf{V}W^V_j)\ (4)$

其中， $\star$ 表示卷积操作， $\Phi _j^Q,\Phi _j^K$ 是卷积核得参数。

在编码器的第l层，令输入为 $\mathcal{X}^{(l-1)}$ ，在对所有节点进行时间趋势感知多头自注意力之后，得到一个中间序列表示： $\mathcal{Z}^{(l-1)} =(\mathbf{Z}_{t-T_h+1}^{(l-1)},\mathbf{Z}_{t-T_h+2}^{(l-1)} ,...,\mathbf{Z}_{t}^{(l-1)}) \in \mathbb{R}^{N\times d_{model}\times T_h}$ 。与之前基于RNN和CNN的STGNN相对于时间步长的不变性不同，由于趋势感知自注意力机制，我们模型中的时间动态参数是根据输入计算的。

空间动态图卷积

本文基于GCNs设计了一个DGCN(Dynamic Graph Convolution Net)来捕获空间维度的动态变化。GCN模型的公式表述如下：

$GCN(\mathbf{Z}_t^{(t-1)})=\sigma (\mathbf{A}\mathbf{Z}_t^{(t-1)}\mathbf{W}^{(l)})$

其中， $\mathbf{Z}_t^{(l-1)} \in \mathbb{R}^{N\times d_{model}}$ 是节点表示， $\mathbf{W}^{(l)} \in \mathbb{R}^{d_{model}\times d_{model}}$ 是投影矩阵， $\sigma$ 是非线性激活函数， $\mathbf{A} \in \mathbb{R}^{N \times N}$ 表示节点之间的关系，定义如下：

$\mathbf{A}= \left\{\begin{matrix} \tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} ,& undirected \ graph\\ \tilde{\mathbf{D}}^{-1} \tilde{\mathbf{A}} & directed\ graph\end{matrix}\right.$

其中， $\tilde{\mathbf{A}}$ 是图邻接矩阵， $\tilde{\mathbf{D}}_{ii}=\sum_{j} \tilde{\mathbf{A}}_{ij}$ 。

传统的卷积操作是时不变的，将其应用于交通数据无法捕获交通i网络节点之间关系的动态变化，因此，本文设计了一个能够自适应地调整节点之间相关性的DGCN。基本思想是利用自注意力来动态计算节点之间的空间相关性强度。令节点表示 $\mathbf{Z}_t^{(l-1)} \in \mathbb{R}^{N \times d_{model}}$ ，即时间趋势感知多头自注意力模块的输出，为输入，空间相关性权重矩阵 $\mathbf{S}_t$ 可由下式进行计算：

$\mathbf{S}_t=softmax(\frac{\mathbf{Z}_t^{(l-1)}\mathbf{Z}_t^{(l-1)^T}}{\sqrt{d_model}}) \in \mathbb{R}^{N \times N}$

直观上来讲， $S_{i,j}$ 表示节点i和节点j之间的相关性强度。得到 $\mathbf{S}_t$ 之后，就可以使用逐元素点积操作来调整静态权重矩阵 $\mathbf{A}$ ：

$\mathbf{X}_t^{(l)}=DGCN(\mathbf{Z}_t^{(l-1)})=\sigma ((\mathbf{A}\bigodot \mathbf{S}_t)\mathbf{Z_t}^{(l-1)}\mathbf{W}^{(l)})$

值得注意的是，本文的模型捕获的空间动态取决于输入，而先前所有的工作都认为节点之间的空间相关性是不变的。本模型还融合了基于变化的相关矩阵的邻域信息，这个相关矩阵是由输入 $\mathcal{Z}^{(l-1)}$ 决定的。最后，我们得到了一个空间信息输出：

$\mathcal{X}^{(l)} =(X_{t-T_h+1}^{(l)},X_{t-T_h+2}^{(l)},...,X_{t}^{(l)}) \in \mathbb{R}^{N \times d_{model} \times T_h}$

时空解码器

时空解码器由L'个相同的解码器层堆叠而成，每个解码器层包括两个时间趋势感知多头自注意力块和一个空间动态GCN块，以自回归方式生成输出序列，使用掩码机制来防止使用未来子序列的信息。具体来说，第一个时间趋势感知多头自注意力块捕获解码器序列中的相关性，为了掩盖未来信息，使用因果卷积替换请求和键上的一维卷积（因果卷积执行卷积操作时，只对当前位置左侧的位置进行滤波）；第二个时间趋势感知多头自注意力块用于捕获解码器序列（请求）和编码器输出序列（键）之间的关系，因果卷积用于请求，一维卷积用于键。

周期性处理和位置嵌入

周期性处理

本文进一步考虑隐藏在交通数据中的两种周期性模式，即全局周期性和局部周期性。全局周期性是由人类的规律性活动引起的，例如，通勤者每周一早上8点从家出发，因此每周内同一天同一时间的交通状况往往相似。局部周期性往往是由气候或天气变化引起的，例如，大雪三天的交通速度与其他日子有着显著的差异。为了在预测接下来 $T_p$ 步的交通时考虑两种周期性模式，除了过去 $T_h$ 步的历史数据外，本文还另外引入了两个数据源。

全局周期张量

将过去w周同一天的 $T_p$ 切片视为当前天，生成 $\mathcal{X}_g \in \mathbb{R}^{N \times C \times w\ast T_p}$ 。例如，假设时间步长为1小时，我们希望预测周一上午7点到11点（ $T_p=4$ ）的交通状况，我们获取过去三个周一（w=3）7点到11点的交通数据得到 $\mathcal{X}_g \in \mathbb{R}^{N \times C \times 12}$ 。

局部周期张量

我们根据过去连续d天的 $T_p$ 切片得到 $\mathcal{X}_l \in \mathbb{R}^{N \times C \times d\ast T_p}$ 。例如，假设时间步长为1小时，我们希望预测周一上午7点到11点（ $T_p=4$ ）的交通状况，我们获取过去两天（d=2）的交通数据得到 $\mathcal{X}_l \in \mathbb{R}^{N \times C \times 8}$ 。

得到全局周期张量 $\mathcal{X}_g$ 和局部周期张量 $\mathcal{X}_l$ 后，我们将其与过去 $T_h$ 步的张量 $\mathcal{X}$ 连接起来得到一个形状为 $\mathbb{R} ^{N \times C \times (w\ast T_p+d\ast T_p+T_h)}$ 的输入张量作为ASTGNN的输入。

时间位置嵌入

由于注意力通过加权和函数建立输入和目标之间的依赖关系，因此注意力机制完全不知道序列中symbols的顺序。然而，顺序信息在时间序列建模任务中起着重要作用，因为邻近的观测值通常更具有相关性。因此，显示地将顺序偏差引入模型可以生成更准确的结果。因此，我们在 $\mathcal{X}^{(0)}$ 的每个元素表示中加入了位置嵌入，使得邻近的元素往往具有接近的位置嵌入。为了简单起见，我们为t时刻的输入元素选择固定的位置嵌入，并且每个向量维数： $1\leq d\leq d_{model}$ ，如下式所示：

$E_{TP}(t,2d)=sin(t/10000^{2d/d_{model}}) \\ E_{TP}(t,2d+1)=cos(t/10000^{2d/d_{model}})$

其中，t时输入中每个元素的相对索引。另一个好处是，当输入包括全局周期张量和局部周期张量时，引入时间位置嵌入有助于我们的模型能更好地识别 $\mathcal{X}$ ， $\mathcal{X}_l$ 和 $\mathcal{X}_g$ 之间的相对位置关系，尽管它们只是简单地连接在一起。

空间位置嵌入

在交通预测问题中，空间节点的一些静态特征不会随时间的变化而变化，但随空间变化，这就是空间的异质性问题。并且一些空间节点的细节特征是不可得的。在这种情况下，可以采取以下几种方法对图片的空间异质性进行建模：

一种直接表示每个节点的独特空间异质性的方法是one-hot编码，稀疏化高维特征不仅需要大量的计算还会导致图结构信息的丢失。另一种方法是采用无监督图嵌入方法（如DeepWalk）来学习空间节点的表示。虽然他们能够保留图中邻域的相似性，但是大多数情况下，他们无法适应特定的监督任务。受无监督预训练的启发，我们尝试通过无监督图嵌入技术来学习节点的表示，然后将学习到的表示作为节点嵌入向量的初始化，随后基于监督信号对其进行微调。但是在预实验中没有看见任何的提升。图拉普拉斯正则化(Graph Laplacian Regularization) 是另一种保留图结构的表示方法。他将图拉普拉斯作为无监督正则化损失添加到监督损失中，但是需要仔细调整控制正则化强度的超参数。

GCN实际上是一种特殊形式的拉普拉斯平滑，控制节点的表示以接近其邻域。因此，为了在反映图结构信息的同时显式地对空间异质性进行建模，我们首先为每个节点分配一个额外地嵌入向量，生成一个初始空间位置嵌入矩阵 $E_{SP}^{(0)} \in \mathbb{R}^{N \times d_{model}}$ 。然后使用GCN层进行拉普拉斯平滑得到最后地空间位置嵌入矩阵 $E_{SP}$ 。

参考文献

Guo S, Lin Y, Wan H, et al. Learning dynamics and heterogeneity of spatial-temporal graph data for traffic forecasting[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 34(11): 5415-5428.(Learning Dynamics and Heterogeneity of Spatial-Temporal Graph Data for Traffic Forecasting | IEEE Journals & Magazine | IEEE Xplore)

标签：Forecasting,ASTGNN,卷积,Graph,节点,序列,空间,注意力,输入
From： https://blog.csdn.net/m0_55333280/article/details/140658720

ASTGNN (Learning Dynamics and Heterogeneity of Spatial-Temporal Graph Data forTraffic Forecasting)

引言

问题陈述

定义

交通网络

交通信号矩阵

问题陈述

流量预测

注意力机制

Scaled Dot-Product Attention

注意力时空图神经网络(Attention Based Spatial-Temporal Graph Neural Networks, ASTGNN)

时空编码器

时间趋势感知多头自注意力

空间动态图卷积

时空解码器

周期性处理和位置嵌入

周期性处理

全局周期张量

局部周期张量

时间位置嵌入

空间位置嵌入

参考文献

相关文章

赞助商

阅读排行