文章信息

本周阅读的论文是题目《Meta Graph Transformer: A Novel Framework for Spatial-Temporal Traffic Prediction》2022年发表的一篇文章发表在2022年《Neurocomputing》上的使用Transformer交通预测文章。

摘要

精确的交通预测对提高智能交通系统的性能非常重要。这项任务的关键是在学习和利用交通数据时空异质性的同时准确建模其复杂动态。本文提出Meta Graph Transformer（MGT）为了解决这个问题，模型是原始的Transformer 改进推广，原始Transformer在自然语言处理中建模向量序列。具体来说，MGT包含encoder-decoder架构，其中encoder将历史交通流数据编码为中间状态decoder回归预测未来交通状态。MGT注意力层的主要构建模块有三种，即时间自注意力层（TSA）、空间自注意层（SSA）时间编码-解码注意力层（TEDA），它们都由多头注意力结构组成。encoder和decoder均使用了TSAs和SSAs捕捉时空相关性。TEDAs被应用于decoder，使decoder输入序列中的每个位置对应。使用多图，SSA空间注意力稀疏可以实现。为了方便模型对时空条件的感知，从外部属性中学习时空嵌入（STEs），外部属性包括时间属性(序列顺序、时间)和空间属性(如拉普拉斯特征映射)。然后，所有的注意力层通过元学习学习这些映射嵌入，从而赋予注意力层时空异质性感知（STHA）属性。三个真实交通数据集的实验表明MGT的效果优于最先进的方法。

介绍

交通基础设施的发展和人们不断变化的出行需求需要交通资源的有效优化和配置。智能交通系统（ITS）这些问题需要解决。智能交通系统的核心是智能交通基础设施和数据分析算法。前者可以从各种设备（如环路探测器和地铁票价收集系统）收集大量的交通数据，后者在将交通数据转化为有用信息方面起着关键作用。交通预测是ITS该系统的基本任务之一是预测未来的交通状态（未来第H时间步）。图1简要说明了时空流量预测。准确的交通预测可以帮助交通部门更好地管理和规划，但复杂的时空相关性使这项任务具有挑战性。

图1 时空交通流量预测

在早期阶段，学者们通常使用统计模型来解决交通预测问题，如基于自回归综合移动平均方法、卡尔曼滤波器和向量自回归模型的严格数学理论。然而，这种模型对交通数据的假设可能不正确（线性、稳定性等）。随后，学者们提出了各种基于机器学习的交通预测模型，如支持向量机、随机森林和近邻模型。特别是在大规模数据的情况下，这些模型可以学习非线性依赖关系，提取更复杂的相关性。然而，这些模型的有效性很大程度上取决于复杂的特征工程，不仅耗时而且困难。

近年来，深度学习在图像识别、目标检测等多个领域取得了突破，其强大的能力也吸引了交通领域的学者。将区域划分为网格，2D或者3D卷积神经网络可用于交通预测，但这种方法不考虑交通流数据的拓扑结构。另一个研究方向是时空图神经网络（STGNNs），近年来，通过图结构反映交通流数据的空间信息非常流行。典型的模型包括STGCN和DCRNN。如名称所示，STGCN通常包括两部分的建模，一部分是空间维度，另一部分是时间维度。这两部分的建模可以同时进行。后者的一种常见做法是用图卷积代替循环神经网络（RNN）中矩阵乘法。STGCN框架面临的主要挑战是有效捕获交通网络演化过程中复杂的时空相关性，从而尽可能提高预测准确性。

就空间相关性建模而言，许多模型基于静态图实现图卷积网络。这种静态图通常是根据实际路网构建的，侧重反映了两个节点在距离上的接近程度。虽然基于节点距离的图表在一定程度上揭示了地理位置相似的节点之间的相互影响，但在长期建模中还远远不够。要解决这个问题，Graph WaveNet和AGCRN学习隐藏的空间依赖性是通过节点嵌入的PVCGN和Multi-STGCnet从多角度构建多图，学习空间特征。这些方法的问题是，训练后分配给相邻节点的每张图习）分配给相邻节点的权重固定，不适用于可能随时间变化的空间相关性的交通流任务。因此，一些学者考虑利用注意机制动态确定邻接的权重。通常来说，邻接节点分配到的注意力系数是通过参数化函数计算的，将目标节点和相邻节点的特征作为输入。通过这种方式，动态权重取代静态权重，以增强模型的适应性。

然而，基于注意机制的大多数方法都有一个显著的缺点，即参数在所有位置和时间间隔之间共享，因此节点之间的相关性完全取决于各自的特点。以图2中的地铁站对为例，站A位于商业中心，站B位于居住区。高峰时段，出行主要是通勤，所以站A的出站流量与站B的进站流量有很强的相关性；相反，在非高峰时段，交通流量更随机，导致站A与站B的相关性较弱。考虑7:00到14:00的数据对（a, b）和（c, d），前者取自高峰期，后者不是。a时刻和c时刻的客流数据保持一致，时刻b和d同样，如果相关性仅取决于客流特征，那么总是a、b分别和时刻c、d但事实并非如此。这表明，由于典型交通网络中不同节点的拓扑结构不同，空间相关性会受到时间变化的影响。因此，考虑时空异质性是优化空间建模的可选方向。

就时间相关性建模而言，大多数现有方法可以分为三类：基于RNNs基于CNNs基于注意机制的方法和方法。RNN最早提出应用于自然语言处理，试图学习长短时间的记忆信息，但由于梯度消失，RNN其实很难同时捕捉长期依赖性RNN在训练过程中，模型不能并行化。基于CNN沿时间维度采用1的方法D卷积并行化。然而，1D卷积受卷积核大小限制，无法有效捕捉长期依赖。尽管有足够的1D任何一对时间点最终都会相互关联，但时间点的相关性会被稀释，无法有效利用。相比之下，基于注意力机制的方法可以通过关注每个时间位置的长期有效学习来实现计算并行化。

就像空间建模一样，时空异质性可以用来提高时间建模的能力。（e, b）和（f, d）例如，它们有相同的时间间隔（一小时）和相同的客流数据。（e, b）从高峰期来看，它们的相关性会比较（f, d）更明显的是，这种差异不能体现在时空同质的方法中。

图2 时空异质性的含义。A和B是两个地铁站

本文提出了一个叫做深度学习的框架Meta Graph Transformer（MGT）解决交通预测问题。MGT充分利用注意力机制，实现动态联系、高效的长期依赖建模和计算并行化。此外，本文设计了一个元学习过程，将外部时空属性中学到的元知识整合到注意力层，使模型能够实现时空异质性感知注意。此外，多图结构被整合到模型的空间注意力层中以便考虑各种类型的空间相关性。文章的主要贡献如下：

1. 本文将元学习整合到注意机制中，以捕获交通预测任务中交通流数据的时空异质性。

2. 将外部空间和时间属性融入空间-时间嵌入模块（STEs）中，在STE在指导下，提出了三种类型的注意力层来实现时间和空间维度STHA操作。

3. 提出了多图下的空间注意力机制，以更好地捕捉不同类型的空间依赖性。

4. 对文章中提出的模型进行了大量的实验。结果表明，MGT明显优于最先进的模型。

预备知识

1. Problem Formulation

Definition1 (Traffic Network): 在交通系统中，交通网络是一个向图网络N收集节点(如道路传感器、路段、交叉口节点或地铁站节点)，E它由多组有序节点组成，如表示节点i和节点j两者之间有向边，而A表示邻接矩阵，如下所示：

Definition 2 (Traffic States): 节点i在时间段t交通状态定义为C表示特征的数量(如速度和流量)。同时，所有节点都在时间段t定义交通状态。

Definition 3 (Temporal Attributes): 每个时间间隔t包含几个时间特征，如一天的观测时间、一周的观测天数等。假设有M个有效的时间属性和时间段t中第m个属性定义为，表示可能的状态数。

Definition 4 (Multiple Graph): 根据图形结构的相关知识，构建多个图形结构来解释节点之间的不同关系。这些图被定义为边缘集合和权重矩阵，B是可行图的数量。所有图片共享相同的节点集合V。

Problem. 给定过去P个时间段的历史交通状态：给定过去P时间段和未来H文章的目标是预测未来H交通状态：

2. Multi-Head Attention

注意机制可视为一种query和key与value集合映射到输出函数中query、key和value都是向量。添加这些值。求和计算得到输出，权重的设定是通过兼容性函数计算所得，其变量是query和相应的key。文章采用“Scaled Dot-Product Attention”，对所有的quries执行矩阵乘法操作。具体来说，给定queries和keys的维度，注意力计算公式如下：

式中，分别表示queries、keys以及values。

为了使模型能够捕捉不同子空间的注意力，学者提出了多头注意力机制。本文使用表示模型的特征尺寸。给定初始的queries、keys以及values，多头注意力可以通过以下公式计算得出：

式中，表示多头的数量，其余的W表示需要学习的权重。

模型

Meta Graph Transformer

(1) Overall Pipeline

MGT的主要目的是在外部时空属性的指导下，通过构建时空异质性感知（STHA）注意力层以学习复杂的时空相关性。MGT的整体框架如图3（a）所示，模型具有encoder-decoder架构，并且encoder和decoder均是由多个子层堆叠组成。为了在深度神经网络中有效学习，每个子层的输出都是进行残差连接并与最后一个子层的输出相加。在子层中，利用三种类型的注意力层学习时间和空间的相关性，这三种类型的注意力层分别被称为时间自注意力（TSA）、空间自注意力（SSA）以及时间编码-解码注意力（TEDA）。Encoder和decoder均利用TSAs和SSAs分别对时间和空间依赖性进行建模。Decoder利用TEDAs使得decoder中的每个位置与输入序列的时间顺序对应。所有的注意力层均包含一个多头构架，并利用从外部空间和时间属性学习到的空间-时间嵌入（STEs）来实现STHA操作。此外，SSAs利用多重图结构或这等效利用图结构的转移矩阵（TMs）来捕捉各种类型的空间相关性。为了避免decoder中任何时间位置在训练时出行在前面的位置，decoder中所有的TSAs均采用掩码操作。总的来说，MGT模型的总体框架描述如下：

1) Encoder的输入是历史交通流状态 ，encoder通过激活函数ReLU函数对其进行线性变化得到，其中表示模型的特征尺寸大小。

2) 经过线性变化后的特征输入到长度为且包含残差连接的encoder。将第l层encoder 的输出定义为，则encoder的输出可以表示为。

3) 以为输入，decoder以自回归的方式预测未来的交通状态。具体来说，encoder以和先前的预测值作为输入。与encoder相似的是，其输入首先通过线性变化使维度满足特征尺寸大小，接着输入到长度为且具有残差连接的decoder层。最后，特征大小使用线性变化映射为C，最后一个时间序列位置的输出被保留作为下一个时间段的预测值。

4) 步骤3重复H次以逐步生成期望的未来交通流状态。

图3 MGT模型框架图

图4 MGT自回归预测框架

(2) Spatial-Temporal Embeddings（STE）

文章针对特定的时空节点 (i, t ), 其中i表示节点i，t 表示特定的时间段，建立了时空嵌入模块(STEs)，可以将该节点的外部空间和时间属性encoder成固定长度的向量。图3（b）为STE的基本构架。

1) Temporal Embeddings（TE）

值得注意的是，除了时间段t所有的时间时间属性外，还有另一个动态属性即与输入相关的时间位置pos需要考虑。具体来说，时间段t的时间嵌入模块（TE）由以下方式构建。首先，每个通过one-hot编码形成长度为的向量，接着使用M个可学习的矩阵将这些向量线性转化为长度为的向量。这两步相当于将每个时刻的时间属性嵌入到长度为的向量中。至于时间位置pos，其位置编码是一个长度为的向量，第i个位置编码计算如下：

将时间属性和时间位置进行拼接计算得到维度为的向量，并使用可学习的参数进行线性转换生成最后的时间段t的时间嵌入。

2) Spatial Embeddings

文章通过一种经典的图嵌入技术Eigenmaps将图结构信息编入空间嵌入（SE）中。为了满足要求，邻接矩阵A通过实现对称化，并假设得到的无向图是连通的。Eigenmaps算法可以定义如下：首先通过计算得到归一化拉普拉斯矩阵，其中是矩阵的度矩阵，表示为，I为单位矩阵。接着对拉普拉斯算子进行特征分解，其中是特征值矩阵满足，而为特征矩阵。最后，节点i的K维嵌入可以表示为。在计算特征映射以后，通过可学习的线性转化生成节点i 的空间嵌入。

3) Spatial-Temporal Embeddings

特定的时空节点 (i, j)的时空嵌入可以通过线性层将空间嵌入（SE）和时间嵌入（TE）进行拼接所获得。

(3) Transition Matrices

1) Construction of Multiple Graphs

交通网络本身可以视为一个简单的加权图，其中所有边的权重取值为1，这类图被称为连通图。给定距离信息，可以对连通图的边的权重进行修改以反映节点间的真实距离。节点i和节点j基于距离的权重通常可以表示为：

其中dist(i, j)表示节点i 和节点j 之间的距离（或者费用），表示两节点间距离的标准差。

除了物理连通性，功能相似性也是探索空间相关性的重要因素。虽然一些节点在实际中可能没有相连或者相距很远，但是在交通网络中可能承担着相似的功能，因此具有相同的交通模式。定义节点i的历史交通状态为（为训练集时间段的总数），节点i和节点j的相似性可以定义公式（10）所示。通过选择相似度大于给定阈值的边，可以构造基于相似度的权重矩阵。

另外一种图是基于交通流数据中OD信息搭建的。通常来说，从节点i 到节点j 的OD相关性可以定义为：

其中count(i, j)表示由节点i到节点j的实体数量（车辆或者乘客），最后通过选择权重大于阈值的边或者保留每个节点周围top-k个邻接节点构成基于OD的权重矩阵。

2) Transition Matrices

给定权重图，相应的转移矩阵通过以下方式计算。首先将的对角线元素设为1（增加自环以确保自己的信息可以流通），然后对行进行归一化，转移矩阵的计算过程如公式（12）所示。图3（c）展示了TM的计算过程。

(4) Encoder

Encoder由一个输入投影层和层数为且包含残差连接的encoder层堆叠构成。每个encoder层由三个部分组成，分别是TSA、SSA和一个前馈神经网络（FFN）。其中TSA和SSA均包含多头结构，分别负责学习时间和空间相关性，FFN则负责位置转换。TSA和SSA可以实现STHA注意力操作，使学习过程更加适应特定的时空条件。同时，使用多重图结构或等效的TMs，SSA可以从不同角度捕捉空间相关性。这三个部分按顺序连接共同学习时空表示。

1）Temporal Self-Attention

当queries、keys以及values为相同的向量序列， 即Q=K=V时，多头注意力机制即为多头自注意力机制。文章将多头注意力机制直接应用于第l-1层中沿时间维度的输出，等同于计算：

式中，是节点i的序列特征，其参数在所有节点上共享。事实上所有时间位置的参数也是共享的，如公式（7）所示。这种共享机制忽略了交通状态在时间和地点上存在较大的动态变化。

针对上述提到的时间多头自注意力存在的缺点，文章提出一种由STEs指导的多头TSA框架，其关键思路是使用相关STE函数（或元知识）替换共享参数机制从而将queries、keys和values的学习与特定时空条件相互联系。这种方式下，TSA可以实现STHA自注意力操作。更具体来说，每个多头创建了一个带有一层隐藏层地多层感知机：

式中，均是可训练参数。网络以作为输入，生成三个权重矩阵将转化成为query、key和value向量，在此基础上实现时间自注意机制。此外，残差连接和层归一化被采用以更好训练深度网络。TSA框架的细节如算法1所示：

2）Spatial Self-Attention

与TSA相似，由STE指导的多头SSA考虑了多重图以学习空间特征。“多重图”的应用可以更合理高效地关注那些可能根据图领域知识与中心节点关联的相关节点。因此，多重图或者等价的TMs可以捕捉节点间不同类型的关系以实现稀疏自注意力。此外通过元素相乘，由动态注意力系数和转移矩阵中的静态值共同确定分配相邻节点的权值。为了保证STHA操作，STEs用于生成注意力参数，另外残差连接和层归一化被应用于此。SSA框架的细节如算法2所示。

3）Feed forward Network

前馈神经网络是一个位置变换层。每个时空点的参数都可以共享。给定一个任何位置的特征矩阵，FFN的计算过程如下：

(5) Decoder

Decoder由一个投影层、个具有残差连接的decoder层和用于预测的线性层堆叠而成。每个decoder层由四个组件组成，即带掩码的TSA、SSA、TEDA和FNN。SSA和FFN的结构与encoder中的结构一致，但对TSA进行掩码操作，防止任何位置提前出行在前面位置的预测。TEDA将encoder的输出与每层decoder相连，使decoder可以从历史数据中自适应学习特征。

1）TSA with Mask

带有编码的TSA的工作原理与TSA基本相同，唯一不同是在scaled dot-product后添加了掩码，以防止任何位置的数据提前出现在前面位置的预测。掩码矩阵是一个大小为，对角线元素为负无穷其余元素为0的矩阵。具体改进如下：

2）Temporal Encoder-Decoder Attention

TEDA是为decoder创建用于自适应处理时间维度上的编码特征。这种情况下，查询向量来自decoder，而键向量和值向量来自encoder。与算法1相同，多头键向量和值向量可以根据encoder的输出计算。分别定义键向量和值向量为和。Decoder中的TEDA利用键向量和值向量实现由STEs引导的时间注意力操作。TEDA的细节如算法3所示。

结论

以上是对该文章所提出模型的框架及算法的具体介绍，实验部分在此不展开详细讲述，感兴趣的读者可以自行查看文章。这篇文章提出了一种新的交通流时空预测模型，称为Meta Graph Transformer。MGT框架在时间和空间维度上均采用了注意力机制。对于每个时空点，外部属性被嵌入作为时空嵌入信息，然后被所有的注意力层用以实现时空异质感知的注意力操作。另外，“Multiple Graph”的概念被提出以实现稀疏空间注意力计算，使模型可以从多个角度捕捉空间相关性。在三个大规模的交通数据集上的实验表明，文章提出的模型优于几种最先进的方法。

Attention

如果你和我一样是轨道交通、道路交通、城市规划相关领域的，可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望我们共同进步！