《Meta Graph Transformer：一种时空交通预测模型》

c26fdfce754bfef290199ff2280c8e77.png

文章信息

cec012b7f72e8db05222c06ec3447489.png

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

8bb080f0f1c6c218daba53134f8aaf4f.png

摘要

0dea4ac5ca3a39adcbbaf17860bc04e9.png

       精确的交通预测对于提高智能交通系统的性能非常重要。这项任务的关键是在学习和利用交通数据时空异质性的同时，对其复杂动态进行准确建模。本文提出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的效果优于最先进的方法。

0f58c9e98a54d0b9b37675031830fd7d.png

介绍

67d5799adcda1fff5216d20bbdaf9529.png

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

8144853e0ad4171618ce1e779c466f34.png

图1 时空交通流量预测

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

近年来，深度学习在多个领域迎来突破，例如图像识别、目标检测等，其强大的能力同样吸引了交通领域的学者。通过将区域划分为网格，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的方法沿时间维度采用1D卷积实现并行化。然而，1D卷积受限于卷积核大小无法有效捕捉长时依赖。虽然随着足够多的1D卷积层的堆叠，任何一对时间点最终都会相互关联，但时间点的相关性将被稀释而无法有效利用。相比之下，基于注意力机制的方法通过关注每个时间位置有效学习长时依赖，并且可以实现计算并行化。

正如空间建模一样，可以利用时空异质性来提高时间建模的能力。以图2中（e, b）和（f, d）数据对为例，它们分别具有相同的时间间隔（一小时）和相同的客流数据。由于（e, b）取自高峰时段，它们的相关性会比（f, d）的更加明显，这种差异无法在时空同质的方法中体现。

49ceba52fddd45b5adfebb911be7eeda.png

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

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

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

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

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

  4. 在三个交通数据集上进行了大量实验，以评估文章提出的模型。结果表明，MGT明显优于最先进的模型。

1983ee0e4b5c85dedcd3294301689b38.png

预备知识

387e88555daba7d97f58cd60c0beb535.png

  1. Problem Formulation

Definition1 (Traffic Network): 交通网络是一个有向图网络ca4fe8fcc66846897fb39edf5c681752.png，其中a0ef8a7051e2bf850dcb790fccb8afa0.png是交通系统中N个节点的集合（例如道路传感器、路段、交叉口节点或者地铁车站节点），E是由多组有序节点对组成的边，例如74f76393fac7a1f2c0b1d1f983f16ca9.png表示节点i和节点j之间的一条有向边，而A表示邻接矩阵，如下所示：

61fb0536050f23569f05e3085cfe74e2.png

Definition 2 (Traffic States): 节点i在时间段t的交通状态定义为0812155d5dc74b3b8b7610f038973fc9.png，其中C表示特征的数量（如速度和流量）。同时将所有节点在时间段t的交通状态定义26c6e6b637b7b39b1b95661ec1a92972.png。

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

Definition 4 (Multiple Graph): 基于图结构的相关知识，构造多个图结构来解释节点间的不同关系。这些图被定义为4d335b26985dcc7c816604ed0fc733da.png，其中是边的集合，是的权重矩阵，B是可行图的数量。所有图共享相同的节点集合V。

Problem. 给定过去P个时间段的历史交通状态：0f152bcaf32af83b7272f852a0d9a92f.png给定过去P个时间段和未来H个时间段的时间特征：139c19556ebc04cb7fb8e746f058bc95.png以及多重预构建的图aa8dabbcce84f6aa4051f12693be4101.png，文章的目标是预测未来H个时间段的交通状态：f83fe254aeb667610a949f6d8325a25d.png

2. Multi-Head Attention

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

f34e62b57a12594221fc8b83030a75ea.png

式中，6fd3854c1eaecd3c3c032095b0ee7685.png分别表示queries、keys以及values。

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

de34993be726ddb53f049fa390c5dcb6.png

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

76961d2f3338bacef068dd605cfe45f0.png

模型

1056e654fc2fc5e657312d7841e95281.png

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函数对其进行线性变化得到d13926917324f2e64eb1f34a78c5b2cf.png，其中表示模型的特征尺寸大小。

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

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

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

07eb79b35a1f9fe201a5b5780e97802e.png

图3 MGT模型框架图

c277da83cf047571d58ef1f2183a585f.png

图4 MGT自回归预测框架

(2) Spatial-Temporal Embeddings（STE）

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

1) Temporal Embeddings（TE）

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

f203bf3e40fca851a5795793bac621e4.png

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

2) Spatial Embeddings

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

3) Spatial-Temporal Embeddings

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

(3) Transition Matrices

1) Construction of Multiple Graphs

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

1807b30164e752d2af39f8d60ed98c54.png

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

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

ca188aca647524d84c127e4ff1dc93ec.png

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

942007629a62bd1c43c5584a7e79e3b4.png

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

2) Transition Matrices

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

417500df1e008cbfc0616c7abb9d5b34.png

(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层2618af31f8c62613a369def687849098.png中沿时间维度的输出，等同于计算：

aa0771c7b5b0b50bb8c6d24c06ef026c.png

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

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

b583931b543d87b850fb8a58dfe08087.png

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

50c1a9a6c06221bad5a152c41747f87b.png

2）Spatial Self-Attention

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

960ab3479067d9c7369f13cfbee2be39.png

3）Feed forward Network

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

11df25f0187202419913449cc05a65fe.png

(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的矩阵。具体改进如下：

e7c7f49723072a2c566eaf28b837975b.png

2）Temporal Encoder-Decoder Attention

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

15ce62a33a7357c929b9813b2b318641.png

050a5179948faced12628ba3b7b52e44.png

结论

31810e47fcbf8c6eeef50cd7e25a91d1.png

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

fd078aeeec95e86c7b848fbbc67ce726.png

Attention

e43842ba40a143332223aba63418f40d.png

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