Review of Construction and Applications of Spatio-Temporal Graph Neural Network in Traffic Flow Prediction

doi:10.3778/j.issn.1002-8331.2307-0133

Abstract

Abstract: The prediction of traffic flow is a pivotal concern within urban traffic management and planning, yet conventional forecasting techniques prove inadequate in addressing challenges like data sparsity, nonlinear associations, and intricate dynamics. Graph neural network is a deep learning approach based on non-Euclidean structural data, which has been widely used in various complex network modeling and predictive tasks in recent times. To address traffic flow prediction, a spatiotemporal graph neural network is proposed, which can capture spatial and temporal correlations, making significant progress compared to earlier predictive models. An analysis is conducted on models utilizing spatiotemporal graph neural network for the prediction of traffic flow in recent times Firstly, various construction methods of adjacency matrices are summarized and compared. Then, the common components of traffic flow prediction models are listed from the perspective of spatial correlation and temporal correlation, and different spatio-temporal fusion modes are classified and compared. On the application front, spatiotemporal graph neural network models are categorized into three classes based on temporal scales: long-term prediction, short-term prediction, and combined long-short-term prediction. Analysis of respective objectives and requisites is conducted, accompanied by enumeration and comparison of prominent recent models. Finally, limitations of existing research are deliberated upon, and prospects for future studies pertaining to relevant models are outlined.

Key words: smart transportation, traffic flow forecasting, time series forecasting, deep learning, graph neural network

摘要： 交通流量预测是城市交通管理和规划中的关键问题，而传统预测方法在面对数据稀疏性、非线性关系和复杂动态性等挑战时表现不佳。图神经网络是一种基于非欧结构数据的深度学习方法，近年来在各种复杂网络建模和预测任务中得到广泛应用。为了应用于交通流量预测领域，提出了时空图神经网络，其能够捕捉空间和时间相关性，相较之前的预测模型有显著进步。对近年来使用时空图神经网络进行交通流量预测的模型进行分析，概述和比较了多种邻接阵的构造方式，然后从空间相关性和时间相关性的角度列举了构建交通流预测模型的常用组件，并对不同的时空融合方式进行了分类和对比；在应用方面，根据时间尺度的不同将时空图神经网络模型分为长期预测、短期预测与兼顾长短期的预测三类，分析了各自的目标与要求，并列举比较了近年来较为突出的新模型。最后，讨论了现有研究的局限性，对相关模型的未来研究做出展望。

关键词: 智能交通, 交通流量预测, 时间序列预测, 深度学习, 图神经网络

WANG Weitai, WANG Xiaoqiang, LI Leixiao, TAO Yihao, LIN Hao. Review of Construction and Applications of Spatio-Temporal Graph Neural Network in Traffic Flow Prediction[J]. Computer Engineering and Applications, 2024, 60(8): 31-45.

汪维泰, 王晓强, 李雷孝, 陶乙豪, 林浩. 时空图神经网络在交通流预测研究中的构建与应用综述[J]. 计算机工程与应用, 2024, 60(8): 31-45.

References

[1] HAN L, DU B, SUN L, et al. Dynamic and multi-faceted spatio-temporal deep learning for traffic speed forecasting[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021: 547-555.
[2] LI Z, LI L, PENG Y, et al. A two-stream graph convolutional neural network for dynamic traffic flow forecasting[C]//Proceedings of the 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), 2020: 355-362.
[3] PAN Z, LIANG Y, WANG W, et al. Urban traffic prediction from spatio-temporal data using deep meta learning[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019: 1720-1730.
[4] 刘宜成, 李志鹏, 吕淳朴, 等.基于动态时间调整的时空图卷积路网交通流量预测[J].交通运输系统工程与信息, 2022, 22(3): 147-157.
LIU Y C, LI Z P, LV C P, et al. Network-wide traffic flow prediction research based on dtw algorithm spatial-temporal graph convolution[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 147-157.
[5] SHUMAN D I, NARANG S K, FROSSARD P, et al. The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Signal Processing Magazine, 2013, 30(3): 83-98.
[6] GENG X, LI Y, WANG L, et al. Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 3656-3663.
[7] SHAO W, JIN Z, WANG S, et al. Long-term spatio-temporal forecasting via dynamic multiple-graph attention[J]. arXiv: 2204.11008, 2022.
[8] LI M, ZHU Z. Spatial-temporal fusion graph neural networks for traffic flow forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 4189-4196.
[9] ZHANG W, ZHU F, LV Y, et al. AdapGL: an adaptive graph learning algorithm for traffic prediction based on spatiotemporal neural networks[J]. Transportation Research Part C: Emerging Technologies, 2022, 139: 103659.
[10] CHAI D, WANG L, YANG Q. Bike flow prediction with multi-graph convolutional networks[C]//Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2018: 397-400.
[11] JIN G, XI Z, SHA H, et al. Deep multi-view graph-based network for citywide ride?hailing demand prediction[J]. Neurocomputing, 2022, 510: 79-94.
[12] WU Z, PAN S, LONG G, et al. Graph wavenet for deep spatial-temporal graph modeling[J]. arXiv:1906.00121, 2019.
[13] LI Y, YU R. Diffusion convolutional recurrent neural network: data-driven traffic forecasting[J]. arXiv:1707.01926, 2017.
[14] WU Z, PAN S, LONG G, et al. Connecting the dots: multivariate time series forecasting with graph neural networks[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020: 753-763.
[15] 王杨, 郑津, 刘影, 等.基于自适应门控图神经网络的交通流预测[J].计算机应用研究, 2022, 39(8): 2306-2310.
WANG Y, ZHENG J, LIU Y, et al. Traffic flow prediction based on adaptive gated graph neural network [J]. Application Research of Computers, 2022, 39(8): 2306-2310.
[16] SHEN Y, LI L, XIE Q, et al. A two-tower spatial-temporal graph neural network for traffic speed prediction[C]//Advances in Knowledge Discovery and Data Mining: 26th Pacific-Asia Conference, Chengdu, May 16-19, 2022. Cham: Springer International Publishing, 2022: 406-418.
[17] SONG C, LIN Y, GUO S, et al. Spatial-temporal synchronous graph convolutional networks: a new framework for spatial-temporal network data forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2020: 914-921.
[18] RONNEBERGER O, FISCHER P, BROX T. U-Net: convolutional networks for biomedical image segmentation[C]// Proceedings of the 18th International Conference on Medical Image Computing and Computer-Assisted Intervention, Munich, October 5-9, 2015: 234-241.
[19] YU B, YIN H, ZHU Z. ST-UNet: a spatio-temporal u-network for graph-structured time series modeling[J]. arXiv:1903. 05631, 2019.
[20] LEI X, MEI H, SHI B, et al. Modeling network-level traffic flow transitions on sparse data[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022: 835-845.
[21] FANG Z, LONG Q, SONG G, et al. Spatial-temporal graph ode networks for traffic flow forecasting[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021: 364-373.
[22] SUN J, LI J, WU C, et al. Ada-STNet: a dynamic AdaBoost spatio-temporal network for traffic flow prediction[C]//Proceedings of the 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022: 5478-5482.
[23] XU K, HU W, LESKOVEC J, et al. How powerful are graph neural networks?[J]. arXiv:1810.00826, 2018.
[24] DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in Neural Information Processing Systems, 2016.
[25] BAHDANAU D, CHO K, BENGIO Y. Neural machine translation by jointly learning to align and translate[J]. arXiv: 1409.0473, 2014.
[26] VELI?KOVI? P, CUCURULL G, CASANOVA A, et al. Graph attention networks[J]. arXiv:1710.10903, 2017.
[27] GILMER J, SCHOENHOLZ S S, RILEY P F, et al. Neural message passing for quantum chemistry[C]//Proceedings of the International Conference on Machine Learning, 2017: 1263-1272.
[28] GUO S, LIN Y, FENG N, et al. Attention based spatial-temporal graph convolutional networks for traffic flow forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 922-929.
[29] ROY A, ROY K K, ALI A A, et al. Unified spatio-temporal modeling for traffic forecasting using graph neural network[C]//Proceedings of the 2021 International Joint Conference on Neural Networks (IJCNN), 2021: 1-8.
[30] HYNDMAN R J. A brief history of forecasting competitions[J]. International Journal of Forecasting, 2020, 36(1): 7-14.
[31] MAKRIDAKIS S, SPILIOTIS E, ASSIMAKOPOULOS V. Statistical and machine learning forecasting methods: concerns and ways forward[J]. PloS One, 2018, 13(3): e0194889.
[32] SEN R, YU H F, DHILLON I S. Think globally, act locally: a deep neural network approach to high-dimensional time series forecasting[C]// Advances in Neural Information Processing Systems, 2019.
[33] SALINAS D, FLUNKERT V, GASTHAUS J, et al. DeepAR: probabilistic forecasting with autoregressive recurrent networks[J]. International Journal of Forecasting, 2020, 36(3): 1181-1191.
[34] YOUNG T, HAZARIKA D, PORIA S, et al. Recent trends in deep learning based natural language processing[J]. IEEE Computational Intelligence Magazine, 2018, 13(3): 55-75.
[35] RANGAPURAM S S, SEEGER M W, GASTHAUS J, et al. Deep state space models for time series forecasting[C]//Advances in Neural Information Processing Systems, 2018.
[36] WANG Y, SMOLA A, MADDIX D, et al. Deep factors for forecasting[C]//Proceedings of the International Conference on Machine Learning, 2019: 6607-6617.
[37] LIM B, ZOHREN S, ROBERTS S. Recurrent neural filters: learning independent bayesian filtering steps for time series prediction[C]//Proceedings of the 2020 International Joint Conference on Neural Networks (IJCNN), 2020: 1-8.
[38] BENGIO Y, SIMARD P, FRASCONI P. Learning long-term dependencies with gradient descent is difficult[J]. IEEE Transactions on Neural Networks, 1994, 5(2): 157-166.
[39] HOCHREITER S, BENGIO Y, FRASCONI P, et al. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies[M]//A field guide to dynamical recurrent networks. Hoboken: Wiley-IEEE Press, 2001:?237-243.
[40] HUANG L, WU L, ZHANG J, et al. Dynamic relation discovery and utilization in multi-entity time series forecasting[J]. arXiv:2202.10586, 2022.
[41] KAN J, HU K, HAGENBUCHNER M, et al. Sign language translation with hierarchical spatio-temporal graph neural network[C]//Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2022: 3367-3376.
[42] SIMEUNOVI? J, SCHUBNEL B, ALET P J, et al. Spatio-temporal graph neural networks for multi-site PV power forecasting[J]. IEEE Transactions on Sustainable Energy, 2021, 13(2): 1210-1220.
[43] NICOLICIOIU A, DUTA I, LEORDEANU M. Recurrent space-time graph neural networks[C]//Advances in Neural Information Processing Systems, 2019.
[44] CHEN C, LI K, TEO S G, et al. Gated residual recurrent graph neural networks for traffic prediction[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 485-492.
[45] HOCHREITER S, SCHMIDHUBER J. Long short-term memory[J]. Neural Computation, 1997, 9(8): 1735-1780.
[46] LAI G, CHANG W C, YANG Y, et al. Modeling long-and short-term temporal patterns with deep neural networks[C]//Proceedings of the 41st international ACM SIGIR Conference on Research & Development in Information Retrieval, 2018: 95-104.
[47] SHEN L, LI Z, KWOK J. Timeseries anomaly detection using temporal hierarchical one-class network[C]//Advances in Neural Information Processing Systems, 2020: 13016-13026.
[48] FRANCESCHI J Y, DIEULEVEUT A, JAGGI M. Unsupervised scalable representation learning for multivariate time series[C]//Advances in Neural Information Processing Systems, 2019.
[49] HE Y, ZHAO J. Temporal convolutional networks for anomaly detection in time series[J]. Journal of Physics: Conference Series, 2019 (4): 042050.
[50] YU B, YIN H, ZHU Z. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting[J]. arXiv:1709.04875, 2017.
[51] ZHENG C, FAN X, WANG C, et al. GMAN: a graph multi-attention network for traffic prediction[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2020: 1234-1241.
[52] LI Q, YANG X, WANG Y, et al. Spatial-temporal traffic modeling with a fusion graph reconstructed by tensor decomposition[J]. arXiv:2212.05653, 2022.
[53] WU Z, ZHENG D, PAN S, et al. TraverseNet: unifying space and time in message passing for traffic forecasting[J]. arXiv:2109.02474, 2021.
[54] JIN G, LI F, ZHANG J, et al. Automated dilated spatio-temporal synchronous graph modeling for traffic prediction[J]. arXiv:2207.10830, 2022.
[55] WANG T, CHEN J, LYU J, et al. Synchronous spatiotemporal graph transformer: a new framework for traffic data prediction[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34(12): 10589-10599.
[56] LI H, JIN D, LI X, et al. Multi-task synchronous graph neural networks for traffic spatial-temporal prediction[C]//Proceedings of the 29th International Conference on Advances in Geographic Information Systems, 2021: 137-140.
[57] FANG Y, QIN Y, LUO H, et al. CDGNet: a cross-time dynamic graph-based deep learning model for traffic forecasting[J]. arXiv:2112.02736, 2021.
[58] Kapoor A, BEN X, LIU L, et al. Examining covid-19 forecasting using spatio-temporal graph neural networks[J]. arXiv:2007.03113, 2020.
[59] ZHANG X, HUANG C, XU Y, et al. Traffic flow forecasting with spatial-temporal graph diffusion network[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 15008-15015.
[60] VLAHOGIANNI E I, KARLAFTIS M G, GOLIAS J C. Optimized and meta-optimized neural networks for short-term traffic flow prediction: a genetic approach[J]. Transportation Research Part C: Emerging Technologies, 2005, 13(3): 211-234.
[61] 李斐轩.基于图神经网络的短时交通流预测技术研究[J].信息系统工程, 2023(6): 12-15.
LI F X. Research on short-term traffic flow prediction technology based on graph neural networks[J]. Engineering of Information Systems, 2023(6): 12-15.
[62] XIA M, JIN D, CHEN J. Short-term traffic flow prediction based on graph convolutional networks and federated learning[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 24(1): 1191-1203.
[63] CHEN Z, LU Z, CHEN Q, et al. Spatial-temporal short-term traffic flow prediction model based on dynamical-learning graph convolution mechanism[J]. Information Sciences, 2022, 611: 522-539.
[64] JIANG Y, FAN J, LIU Y, et al. Deep graph Gaussian processes for short-term traffic flow forecasting from spatiotemporal data[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(11): 20177-20186.
[65] TANG C, SUN J, SUN Y. Dynamic spatial-temporal graph attention graph convolutional network for short-term traffic flow forecasting[C]//Proceedings of the 2020 IEEE International Symposium on Circuits and Systems (ISCAS), 2020: 1-5.
[66] JIANG J, HAN C, ZHAO W X, et al. PDFormer: propagation delay-aware dynamic long-range transformer for traffic flow prediction[J]. arXiv:2301.07945, 2023.
[67] ZHONG W, MALLICK T, MEIDANI H, et al. Explainable graph pyramid autoformer for long-term traffic forecasting[J]. arXiv:2209.13123, 2022.
[68] 齐涛. 基于图卷积和深度学习的交通流预测算法研究[D]. 无锡: 江南大学, 2022.
QI T. Research on traffic flow prediction algorithm based on graph convolution and deep learning[D]. Wuxi: Jiangnan University, 2022.
[69] PENG H, DU B, LIU M, et al. Dynamic graph convolutional network for long-term traffic flow prediction with reinforcement learning[J]. Information Sciences, 2021, 578: 401-416.
[70] QI X, MEI G, TU J, et al. A deep learning approach for long-term traffic flow prediction with multifactor fusion using spatiotemporal graph convolutional network[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(8): 8687-8700.
[71] FANG Y, QIN Y, LUO H, et al. Spatio-temporal meets wavelet: disentangled traffic flow forecasting via efficient spectral graph attention network[J]. arXiv:2112.02740, 2021.
[72] LI M, TONG P, LI M, et al. Traffic flow prediction with vehicle trajectories[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 294-302.
[73] LEI B, HUANG S, DING C, et al. Efficient traffic state forecasting using spatio-temporal network dependencies: a sparse graph neural network approach[J]. arXiv:2211.03033, 2022.
[74] HUI B, YAN D, CHEN H, et al. TrajNet: a trajectory-based deep learning model for traffic prediction[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021: 716-724.
[75] ZHOU Z, LIN G, YANG K, et al. GReTo: remedying dynamic graph topology-task discordance via target homophily[C]//Proceedings of the Eleventh International Conference on Learning Representations, 2023.
[76] ORESHKIN B N, CARPOV D, CHAPADOS N, et al. N-BEATS: neural basis expansion analysis for interpretable time series forecasting[J]. arXiv: 1905.10437, 2019.
[77] ORESHKIN B N, AMINI A, COYLE L, et al. FC-GAGA: fully connected gated graph architecture for spatio-temporal traffic forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 9233-9241.