一种基于时空稀疏注意力的时空图挖掘算法_谢毅.pdf

第 49卷 第 4期2023年 4月Computer Engineering 计算机工程一种基于时空稀疏注意力的时空图挖掘算法谢毅1，王强2，李海宏2，金诚2，任洪润1，薛雯1，熊贇1（1.复旦大学 计算机科学技术学院 上海市数据科学重点实验室，上海 200433；2.上海市气象灾害防御技术中心，上海 200030）摘要：当前用于时空图挖掘的算法通常基于专家预定义或者经过特征增强的静态图结构，这些静态的图结构往往依赖于主观先验知识构建，并且不包含时间动态性的变化。为完成自动获取时空图数据中动态图特征的任务，提出一种基于时空稀疏注意力的时空图挖掘算法（STSAN）。构造空间稀疏注意力层，通过对每个时间片上节点间的关系进行度量生成稀疏图，并在各个稀疏图结构上使用注意力机制完成节点空间（纵向）特征的提取。时间稀疏注意力层通过类似的方式完成节点时序（横向）特征的提取。在此基础上，将空间稀疏注意力层和时间稀疏注意力层堆叠为时空稀疏 Transformer模块，完成时空依赖关系建模。实验结果表明，与 DCRNN、STGCN 等方法相比，该算法在 2个公开的交通数据集上能够获得 2.65%16.35%的性能提升，将所提出的空间稀疏注意力层直接用于替换现有算法的空间特征模块，能够在原算法基础上获得平均 3.18%9.14%的性能提升。关键词：时空图；稀疏注意力；图结构；时空依赖；动态性开放科学（资源服务）标志码（OSID）：中文引用格式：谢毅，王强，李海宏，等.一种基于时空稀疏注意力的时空图挖掘算法 J.计算机工程，2023，49（4）：108-113.英文引用格式：XIE Y，WANG Q，LI H H，et al.A spatial-temporal graph mining algorithm based on spatial-temporal sparse attention J.Computer Engineering，2023，49（4）：108-113.A Spatial-Temporal Graph Mining Algorithm Based on Spatial-Temporal Sparse AttentionXIE Yi1，WANG Qiang2，LI Haihong2，JIN Cheng2，REN Hongrun1，XUE Wen1，XIONG Yun1（1.Shanghai Key Laboratory of Data Science，School of Computer Science，Fudan University，Shanghai 200433，China；2.Shanghai Center for Meteorological Disaster Prevention Technology，Shanghai 200030，China）【Abstract】Existing spatial-temporal graph mining algorithms are typically based on static graph structures，which are pre-defined by experts or constructed via feature augmentation.These static graph structures rely on subjective prior knowledge and are not easily adaptable to temporal dynamic changes.Thus，automatically extracting dynamic graph features from spatial-temporal graph data is challenging.Therefore，this study proposes a spatial-temporal graph mining algorithm based on a Spatial-Temporal Sparse Attention Network（STSAN）.First，a spatial sparse attention layer is constructed by generating a sparse graph by determining the relationship between nodes at each time slice，and the attention mechanism is used on each sparse graph structure to extract the spatial（vertical）features of the nodes.Subsequently，the temporal sparse attention layer further extracts the temporal（horizontal）features of the nodes in a similar manner.Finally，the spatial-temporal dependency modeling is completed by stacking the spatial and temporal sparse attention layers in the spatial-Temporal sparse Transformer module.Experimental results demonstrate that，compared with DCRNN，STGCN algorithms，et al，STSAN can achieve performance improvements of 2.65%-16.35%on two public traffic flow datasets.The experiments also demonstrate that directly replacing the spatial feature capturing module of existing algorithms with the spatial sparse attention layer proposed in this study can achieve an average performance improvement of 3.18%-9.14%relative to the original algorithm.【Key words】spatial-temporal graph；sparse attention；graph structure；spatial-temporal dependence；dynamicDOI：10.19678/j.issn.1000-3428.00637310概述时空图是一组具有空间关系和时间趋势的数据1。时空图已被广泛应用于交通预测2-3、疾病诊断4-5、姿态识别6-7、轨迹预测8-10等领域，其中，对图结构的构造是时空图挖掘建模的关键。目前已有大基金项目：国家自然科学基金（U1936213）；上海市科委基金（19DZ1200802）；上海市气象灾害防御技术中心业务型科研项目（ZFYW2020002）。作者简介：谢毅（1994），男，博士研究生，主研方向为数据挖掘、时序数据建模；王强，高级工程师、博士；李海宏、金 诚，工程师、硕士；任洪润，博士研究生；薛雯，硕士研究生；熊贇，教授、博士。收稿日期：2022-01-10 修回日期：2022-05-02 Email：人工智能与模式识别文章编号：1000-3428（2023）04-0108-06 文献标志码：A 中图分类号：TP181第 49卷 第 4期谢毅，王强，李海宏，等：一种基于时空稀疏注意力的时空图挖掘算法量构造图结构的启发式方法：在交通预测任务中，有基于传感器真实地理距离的高斯核函数所构造的带权图2-3，或基于真实地理距离构建并以阈值截断的无权图11-12；在神经科学中，有基于脑功能分区的图4-5。这些基于先验专家知识、预定义的图结构的质量会对下游模型的性能产生直接影响，依赖专家知识构造图结构是一项耗时耗力的困难任务。之后有工作提出使用辅助邻接矩阵构建图结构：用于交通流预测的时空融合图神经网络（Spatial-Temporal Fusion Graph Neural Networks for traffic flow forecasting，STFGNN）13和用于交通流预测的时空图 ODE 网络（Spatial-Temporal Graph ODE Networks for traffic flow forecasting，STGODE）14使用DTW距离定义辅助邻接矩阵，在原有邻接矩阵提供的地理位置相似性的基础上，从功能相似性的角度完成特征增强；用 于 深 度 时 空 图 建 模 的 图 小 波 网 络（Graph WaveNet for deep spatial-temporal graph modeling，GraphWaveNet）1和用于交通预测的自适应图卷积循 环 网 络（Adaptive Graph Convolutional Recurrent Network for traffic forecasting，AGCRN）15包含自适应邻接矩阵的概念，通过对 2 个带梯度的低秩矩阵进行外积生成可学习的邻接矩阵，在优化模型的同时，将邻接矩阵当作参数进行优化，从而使用该邻接矩阵编码相似度信息。虽然上述方法对图结构进行了一定的特征增强，但由于生成的图结构在优化之后就被固定，图结构不会随着时间动态变化，难以在每一个时间片上生成个性化的图结构，即缺乏图结构的时间动态性表示，因此在表达能力上受到了限制。为了实现建模时间动态性，受 Informer16中探测稀疏自注意力所呈现的稀疏性优点的启发，引入时空稀疏注意力机制动态确定每个时间片上的稀疏图结构。通过对比注意力期望分布与均匀分布，以自适应的方式自动筛选出最重要的节点对进行连边。1问题定义定义 1（时空图）时空图是指由一系列节点固定、特征随着时间演化的图构成。具体来说，在时刻t上给定一个图Gt=(V,Et,Xt)。其中：V表示节点集合，|V|=n；Et表 示 图Gt在 时 刻t上 的 边 集 合；Xt Rn d表示节点特征，d为特征维度，Xt会随着时间演化而改变。图 1所示为图结构随时间动态变化的时空图。定义 2（时空图预测）给定一组从（t-h)时刻到（t-1)时 刻 的h个 历 史 时 刻 的 时 空 图 节 点 特 征X(t-h：t-1)=Xt-h,Xt-h+1,Xt-1，为方便表述，将其堆叠为一个张量，即X(t-h：t-1)Rh n d。本文算法的目标是找到一个函数F用来预测未来p个时刻的图节点的特征X(t：t+p-1)=Xt,Xt+1,Xt+p-1 Rp n d，即：X(t：t+p-1)=F(X(t-h：t-1)（1）2STSAN算法STSAN 算法框架如图 2所示。整个算法由多个空间稀疏注意力层和时间稀疏注意力层组成的时空稀疏 Transformer模块堆叠而成。具体来说，首先对输入数据完成位置编码，然后经过堆叠的多个时空稀疏 Transformer模块对特征进行压缩，最后使用多层感知机完成特征的解码并输出。其中空间稀疏注意力层和时间稀疏注意力层共享相似的注意力运算方式。具体来说，在每个时刻根据当前的图特征自动生成动态变化的自适应的图结构，即为每个时间片生成节点相同但节点间连边不同（即空间结构不同）的图结构，通过这种方式为当前的节点特征提供更强的表征能力。图 1图结构动态变化的时空图Fig.1Spatial-temporal graph with dynamic graph structure图 2STSAN算法的整体结构Fig.2The overall stru