一种基于时空稀疏注意力的时空图挖掘算法

doi:10.19678/j.issn.1000-3428.0063731

计算机工程 ›› 2023, Vol. 49 ›› Issue (4): 108-113. doi: 10.19678/j.issn.1000-3428.0063731

一种基于时空稀疏注意力的时空图挖掘算法

谢毅¹, 王强², 李海宏², 金诚², 任洪润¹, 薛雯¹, 熊贇¹

1. 复旦大学计算机科学技术学院上海市数据科学重点实验室, 上海 200433;
2. 上海市气象灾害防御技术中心, 上海 200030

收稿日期:2022-01-10 修回日期:2022-05-02 发布日期:2023-04-07
作者简介:谢毅(1994-),男,博士研究生,主研方向为数据挖掘、时序数据建模;王强,高级工程师、博士;李海宏、金诚,工程师、硕士;任洪润,博士研究生;薛雯,硕士研究生;熊贇,教授、博士。
基金资助:
国家自然科学基金（U1936213）；上海市科委基金（19DZ1200802）；上海市气象灾害防御技术中心业务型科研项目（ZFYW2020002）。

A Spatial-Temporal Graph Mining Algorithm Based on Spatial-Temporal Sparse Attention

XIE Yi¹, WANG Qiang², LI Haihong², JIN Cheng², REN Hongrun¹, XUE Wen¹, XIONG Yun¹

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

Received:2022-01-10 Revised:2022-05-02 Published:2023-04-07

摘要/Abstract

摘要： 当前用于时空图挖掘的算法通常基于专家预定义或者经过特征增强的静态图结构，这些静态的图结构往往依赖于主观先验知识构建，并且不包含时间动态性的变化。为完成自动获取时空图数据中动态图特征的任务，提出一种基于时空稀疏注意力的时空图挖掘算法（STSAN）。构造空间稀疏注意力层，通过对每个时间片上节点间的关系进行度量生成稀疏图，并在各个稀疏图结构上使用注意力机制完成节点空间（纵向）特征的提取。时间稀疏注意力层通过类似的方式完成节点时序（横向）特征的提取。在此基础上，将空间稀疏注意力层和时间稀疏注意力层堆叠为时空稀疏Transformer模块，完成时空依赖关系建模。实验结果表明，与DCRNN、STGCN等方法相比，该算法在2个公开的交通数据集上能够获得2.65%～16.35%的性能提升，将所提出的空间稀疏注意力层直接用于替换现有算法的空间特征模块，能够在原算法基础上获得平均3.18%～9.14%的性能提升。

关键词: 时空图, 稀疏注意力, 图结构, 时空依赖, 动态性

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, dynamic

中图分类号:

TP181

谢毅, 王强, 李海宏, 金诚, 任洪润, 薛雯, 熊贇. 一种基于时空稀疏注意力的时空图挖掘算法[J]. 计算机工程, 2023, 49(4): 108-113.

XIE Yi, WANG Qiang, LI Haihong, JIN Cheng, REN Hongrun, XUE Wen, XIONG Yun. A Spatial-Temporal Graph Mining Algorithm Based on Spatial-Temporal Sparse Attention[J]. Computer Engineering, 2023, 49(4): 108-113.

http://www.ecice06.com/CN/Y2023/V49/I4/108

图/表 7

20230417183404

20230417183408

20230417183412

20230417183416

20230417183420

20230417183423

20230417183426

参考文献

[1] WU Z, PAN S, LONG G, et al.Graph WaveNet for deep spatial-temporal graph modeling[EB/OL].[2022-01-02].https://arxiv.org/abs/1906.00121.
[2] YU B, YIN H, ZHU Z.Spatio-temporal graph convolutional networks:a deep learning framework for traffic forecasting[EB/OL].[2022-01-02].https://arxiv.org/abs/1709.04875.
[3] LI Y, YU R, SHAHABI C, et al.Diffusion convolutional recurrent neural network:data-driven traffic forecasting[EB/OL].[2022-01-02].https://arxiv.org/abs/1707.01926.
[4] COVERT I, KRISHNAN B, NAJM I, et al.Temporal graph convolutional networks for automatic seizure detection[EB/OL].[2022-01-02].https://arxiv.org/abs/1905.01375.
[5] MESZLÉNYI R J, BUZA K, VIDNYÁNSZKY Z.Resting state fMRI functional connectivity-based classification using a convolutional neural network architecture[J].Frontiers in Neuroinformatics, 2017, 11:61.
[6] JI S W, XU W, YANG M, et al.3D convolutional neural networks for human action recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1):221-231.
[7] YAN S J, XIONG Y J, LIN D H.Spatial temporal graph convolutional networks for skeleton-based action recognition[C]//Proceedings of AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2018:1-10.
[8] GAO Q, ZHOU F, TRAJCEVSKI G, et al.Predicting human mobility via variational attention[C]//Proceedings of World Wide Web Conference.New York, USA:ACM Press, 2019:2750-2756.
[9] FENG J, LI Y, ZHANG C, et al.DeepMove:predicting human mobility with attentional recurrent networks[C]//Proceedings of World Wide Web Conference.New York, USA:ACM Press, 2018:1459-1468.
[10] HUANG Y F, BI H K, LI Z X, et al.STGAT:modeling spatial-temporal interactions for human trajectory prediction[C]//Proceedings of IEEE/CVF International Conference on Computer Vision.Washington D.C., USA:IEEE Press, 2020:6271-6280.
[11] GUO S N, LIN Y F, FENG N, et al.Attention based spatial-temporal graph convolutional networks for traffic flow forecasting[C]//Proceedings of AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2019:922-929.
[12] SONG C, LIN Y F, GUO S N, et al.Spatial-temporal synchronous graph convolutional networks:a new framework for spatial-temporal network data forecasting[C]//Proceedings of AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2020:34(1):914-921.
[13] LI S W, GE L, LIN Y Q, et al.Adaptive spatial-temporal fusion graph convolutional networks for traffic flow forecasting[C]//Proceedings of International Joint Conference on Neural Networks.Washington D.C., USA:IEEE Press, 2022:1-8.
[14] FANG Z, LONG Q Q, SONG G J, et al.Spatial-temporal graph ODE networks for traffic flow forecasting[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.New York, USA:ACM Press, 2021:364-373.
[15] BAI L, YAO L N, LI C, et al.Adaptive graph convolutional recurrent network for traffic forecasting[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems.New York, USA:ACM Press, 2020:17804-17815.
[16] ZHOU H Y, ZHANG S H, PENG J Q, et al.Informer:beyond efficient transformer for long sequence time-series forecasting[C]//Proceedings of AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2021:11106-11115.
[17] VASWANI A, SHAZEER N, PARMAR N, et al.Attention is all you need[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems.New York, USA:ACM Press, 2017:6000-6010.
[18] KITAEV N, KAISER Ł, LEVSKAYA A.Reformer:the efficient transformer[EB/OL].[2022-01-02].https://arxiv.org/abs/2001.04451.
[19] WANG S N, LI B Z, KHABSA M, et al.Linformer:self-attention with linear complexity[EB/OL].[2022-01-02].https://arxiv.org/abs/2006.04768.
[20] TSAI Y H H, BAI S J, YAMADA M, et al.Transformer dissection:a unified understanding of transformer's attention via the lens of kernel[EB/OL].[2022-01-02].https://arxiv.org/abs/1908.11775.
[21] BA J L, KIROS J R, HINTON G E.Layer normalization[EB/OL].[2022-01-02].https://arxiv.org/abs/1607.06450.
[22] HE K M, ZHANG X Y, REN S Q, et al.Deep residual learning for image recognition[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C., USA:IEEE Press, 2016:770-778.
[23] CRYER J D.Time series analysis[M].Boston, USA:PWS-Kent Pub.Co., 1986.
[24] HOCHREITER S, SCHMIDHUBER J.Long short-term memory[J].Neural Computation, 1997, 9(8):1735-1780.
[25] KLICPERA J, BOJCHEVSKI A, GÜNNEMANN S.Predict then propagate:graph neural networks meet personalized PageRank[EB/OL].[2022-01-02].https://arxiv.org/abs/1810.05997.

选择文件类型/文献管理软件名称

选择包含的内容

一种基于时空稀疏注意力的时空图挖掘算法

A Spatial-Temporal Graph Mining Algorithm Based on Spatial-Temporal Sparse Attention

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 13

编辑推荐

Metrics

本文评价

[1]	马坤, 安敬民, 李冠宇. 动态聚合实体和关系上下文的知识图谱补全[J]. 计算机工程, 2023, 49(8): 77-84, 95.
[2]	赵世豪, 毛国君, 熊保平, 黄山, 林江宏. 基于图小波卷积神经网络的时空图挖掘模型[J]. 计算机工程, 2023, 49(7): 85-93.
[3]	胡承佐, 王庆梅, 李迪超, 王铮. 基于复杂结构信息的图神经网络序列推荐算法[J]. 计算机工程, 2022, 48(5): 82-90,97.
[4]	王庆荣, 魏怡萌, 朱昌锋, 田可可. 基于时空图卷积网络的交通事故风险预测研究[J]. 计算机工程, 2022, 48(11): 22-29.
[5]	王健宗, 孔令炜, 黄章成, 肖京. 图神经网络综述[J]. 计算机工程, 2021, 47(4): 1-12.
[6]	肖宝,李璞,胡娇娇,蒋运承. 基于潜在语义与图结构的微博语义检索[J]. 计算机工程, 2017, 43(6): 182-188,194.
[7]	郭竹为,刘胜全,刘艳,赵美玲,符贤哲. 基于最大公共子图的本体映射方法研究[J]. 计算机工程, 2017, 43(5): 197-203,209.
[8]	张月,刘春凤,赵增华,舒炎泰. 基于有效覆盖区域的VANET链路持续时间建模与仿真[J]. 计算机工程, 2016, 42(3): 22-28.
[9]	廖涛, 刘宗田, 王先传. 基于事件的多主题文本自动文摘方法[J]. 计算机工程, 2013, 39(3): 236-240.
[10]	刘弹, 焦远东, 徐光华, 罗爱玲, 梁霖. 基于反射的机床整机动态性能测试系统研究[J]. 计算机工程, 2012, 38(20): 239-242.
[11]	江道平;班晓娟;尹怡欣. 基于交互的Agent行为选择动态性分析[J]. 计算机工程, 2008, 34(4): 16-18.
[12]	段广云. 基于Matlab的测控系统动态性能优化与仿真[J]. 计算机工程, 2008, 34(15): 236-237,.
[13]	田广利;蔡皖东;王伟. Ad Hoc网络链路持续时间计算模型[J]. 计算机工程, 2008, 34(12): 82-84.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种基于时空稀疏注意力的时空图挖掘算法

A Spatial-Temporal Graph Mining Algorithm Based on Spatial-Temporal Sparse Attention

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 13

编辑推荐

Metrics

本文评价