{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:22:45Z","timestamp":1778167365026,"version":"3.51.4"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>\n            Spatio-Temporal Graph Neural Network (STGNN) has been used as a common workhorse for traffic forecasting. However, most of them require prohibitive quadratic computational complexity to capture long-range spatio-temporal dependencies, thus hindering their applications to long historical sequences on large-scale road networks in the real-world. To this end, in this paper, we propose BigST, a linear complexity spatio-temporal graph neural network, to efficiently exploit long-range spatio-temporal dependencies for large-scale traffic forecasting. Specifically, we first propose a scalable long sequence feature extractor to encode node-wise long-range inputs (\n            <jats:italic>e.g.<\/jats:italic>\n            , thousands of time-steps in the past week) into low-dimensional representations encompassing rich temporal dynamics. The resulting representations can be pre-computed and hence significantly reduce the computational overhead for prediction. Then, we build a linearized global spatial convolution network to adaptively distill time-varying graph structures, which enables fast runtime message passing along spatial dimensions in linear complexity. We empirically evaluate our model on two large-scale real-world traffic datasets. Extensive experiments demonstrate that BigST can scale to road networks with up to one hundred thousand nodes, while significantly improving prediction accuracy and efficiency compared to state-of-the-art traffic forecasting models.\n          <\/jats:p>","DOI":"10.14778\/3641204.3641217","type":"journal-article","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:05:43Z","timestamp":1714687543000},"page":"1081-1090","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["BigST: Linear Complexity Spatio-Temporal Graph Neural Network for Traffic Forecasting on Large-Scale Road Networks"],"prefix":"10.14778","volume":"17","author":[{"given":"Jindong","family":"Han","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]},{"given":"Weijia","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou)"}]},{"given":"Hao","family":"Liu","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), The Hong Kong University of Science and Technology"}]},{"given":"Tao","family":"Tao","sequence":"additional","affiliation":[{"name":"Didichuxing Co. Ltd"}]},{"given":"Naiqiang","family":"Tan","sequence":"additional","affiliation":[{"name":"Didichuxing Co. Ltd"}]},{"given":"Hui","family":"Xiong","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), The Hong Kong University of Science and Technology"}]}],"member":"320","published-online":{"date-parts":[[2024,5,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Adaptive graph convolutional recurrent network for traffic forecasting. Advances in neural information processing systems 33","author":"Bai Lei","year":"2020","unstructured":"Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. 2020. Adaptive graph convolutional recurrent network for traffic forecasting. Advances in neural information processing systems 33 (2020), 17804--17815."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i6.20587"},{"key":"e_1_2_1_3_1","volume-title":"Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller.","author":"Choromanski Krzysztof Marcin","year":"2020","unstructured":"Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller. 2020. Rethinking attention with performers. arXiv preprint arXiv:2009.14794 (2020)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489503"},{"key":"e_1_2_1_5_1","volume-title":"Funnel-transformer: Filtering out sequential redundancy for efficient language processing. Advances in neural information processing systems 33","author":"Dai Zihang","year":"2020","unstructured":"Zihang Dai, Guokun Lai, Yiming Yang, and Quoc Le. 2020. Funnel-transformer: Filtering out sequential redundancy for efficient language processing. Advances in neural information processing systems 33 (2020), 4271--4282."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467330"},{"key":"e_1_2_1_7_1","volume-title":"An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929","author":"Dosovitskiy Alexey","year":"2020","unstructured":"Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2020. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929 (2020)."},{"key":"e_1_2_1_8_1","volume-title":"International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=AJAR-JgNw___","author":"Fan Wei","year":"2022","unstructured":"Wei Fan, Shun Zheng, Xiaohan Yi, Wei Cao, Yanjie Fu, Jiang Bian, and Tieyan Liu. 2022. DEPTS: Deep expansion learning for periodic time series forecasting. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=AJAR-JgNw___"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467430"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457394"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33013656"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301922"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3056502"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.117921"},{"key":"e_1_2_1_15_1","volume-title":"Spatio-Temporal Graph Neural Networks for Predictive Learning in Urban Computing: A Survey. arXiv preprint arXiv:2303.14483","author":"Jin Guangyin","year":"2023","unstructured":"Guangyin Jin, Yuxuan Liang, Yuchen Fang, Jincai Huang, Junbo Zhang, and Yu Zheng. 2023. Spatio-Temporal Graph Neural Networks for Predictive Learning in Urban Computing: A Survey. arXiv preprint arXiv:2303.14483 (2023)."},{"key":"e_1_2_1_16_1","first-page":"7","article-title":"A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis","volume":"38","author":"Karypis George","year":"1998","unstructured":"George Karypis and Vipin Kumar. 1998. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, MN 38 (1998), 7--1.","journal-title":"MN"},{"key":"e_1_2_1_17_1","volume-title":"International Conference on Machine Learning. PMLR, 5156--5165","author":"Katharopoulos Angelos","year":"2020","unstructured":"Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and Francois Fleuret. 2020. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning. PMLR, 5156--5165."},{"key":"e_1_2_1_18_1","volume-title":"Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451","author":"Kitaev Nikita","year":"2020","unstructured":"Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. 2020. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451 (2020)."},{"key":"e_1_2_1_19_1","volume-title":"International Conference on Machine Learning. PMLR, 11906--11917","author":"Lan Shiyong","year":"2022","unstructured":"Shiyong Lan, Yitong Ma, Weikang Huang, Wenwu Wang, Hongyu Yang, and Pyang Li. 2022. Dstagnn: Dynamic spatial-temporal aware graph neural network for traffic flow forecasting. In International Conference on Machine Learning. PMLR, 11906--11917."},{"key":"e_1_2_1_20_1","volume-title":"Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting. Advances in neural information processing systems 32","author":"Li Shiyang","year":"2019","unstructured":"Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, and Xifeng Yan. 2019. Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_2_1_21_1","volume-title":"Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv:1707.01926","author":"Li Yaguang","year":"2017","unstructured":"Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2017. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv:1707.01926 (2017)."},{"key":"e_1_2_1_22_1","first-page":"19035","article-title":"Practical adversarial attacks on spatiotemporal traffic forecasting models","volume":"35","author":"Liu Fan","year":"2022","unstructured":"Fan Liu, Hao Liu, and Wenzhao Jiang. 2022. Practical adversarial attacks on spatiotemporal traffic forecasting models. Advances in Neural Information Processing Systems 35 (2022), 19035--19047.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403281"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i1.16107"},{"key":"e_1_2_1_25_1","volume-title":"International conference on learning representations.","author":"Liu Shizhan","year":"2021","unstructured":"Shizhan Liu, Hang Yu, Cong Liao, Jianguo Li, Weiyao Lin, Alex X Liu, and Schahram Dustdar. 2021. Pyraformer: Low-complexity pyramidal attention for long-range time series modeling and forecasting. In International conference on learning representations."},{"key":"e_1_2_1_26_1","volume-title":"Do We Really Need Graph Neural Networks for Traffic Forecasting? arXiv preprint arXiv:2301.12603","author":"Liu Xu","year":"2023","unstructured":"Xu Liu, Yuxuan Liang, Chao Huang, Hengchang Hu, Yushi Cao, Bryan Hooi, and Roger Zimmermann. 2023. Do We Really Need Graph Neural Networks for Traffic Forecasting? arXiv preprint arXiv:2301.12603 (2023)."},{"key":"e_1_2_1_27_1","unstructured":"Yijing Liu Qinxian Liu Jianwei Zhang Haozhe Feng Zhongwei Wang Zihan Zhou and Wei Chen. 2022. Multivariate Time-Series Forecasting with Temporal Polynomial Graph Neural Networks. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_28_1","first-page":"136","article-title":"Integrating granger causality and vector auto-regression for traffic prediction of large-scale WLANs","volume":"10","author":"Lu Zheng","year":"2016","unstructured":"Zheng Lu, Chen Zhou, Jing Wu, Hao Jiang, and Songyue Cui. 2016. Integrating granger causality and vector auto-regression for traffic prediction of large-scale WLANs. KSII Transactions on Internet and Information Systems (TIIS) 10, 1 (2016), 136--151.","journal-title":"KSII Transactions on Internet and Information Systems (TIIS)"},{"key":"e_1_2_1_29_1","volume-title":"A Time Series is Worth 64 Words: Long-term Forecasting with Transformers. arXiv preprint arXiv:2211.14730","author":"Nie Yuqi","year":"2022","unstructured":"Yuqi Nie, Nam H Nguyen, Phanwadee Sinthong, and Jayant Kalagnanam. 2022. A Time Series is Worth 64 Words: Long-term Forecasting with Transformers. arXiv preprint arXiv:2211.14730 (2022)."},{"key":"e_1_2_1_30_1","unstructured":"Alec Radford Karthik Narasimhan Tim Salimans and Ilya Sutskever. 2018. Improving language understanding by generative pre-training. (2018)."},{"key":"e_1_2_1_31_1","volume-title":"Random features for large-scale kernel machines. Advances in neural information processing systems 20","author":"Rahimi Ali","year":"2007","unstructured":"Ali Rahimi and Benjamin Recht. 2007. Random features for large-scale kernel machines. Advances in neural information processing systems 20 (2007)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557702"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539396"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551827"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514067"},{"key":"e_1_2_1_36_1","volume-title":"Attention is all you need. Advances in neural information processing systems 30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_1_37_1","volume-title":"Exploring the generalizability of spatio-temporal traffic prediction: meta-modeling and an analytic framework","author":"Wang Leye","year":"2021","unstructured":"Leye Wang, Di Chai, Xuanzhe Liu, Liyue Chen, and Kai Chen. 2021. Exploring the generalizability of spatio-temporal traffic prediction: meta-modeling and an analytic framework. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"key":"e_1_2_1_38_1","first-page":"27387","article-title":"Node-former: A scalable graph structure learning transformer for node classification","volume":"35","author":"Wu Qitian","year":"2022","unstructured":"Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. 2022. Node-former: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems 35 (2022), 27387--27401.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503604"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403118"},{"key":"e_1_2_1_41_1","volume-title":"Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint arXiv:1906.00121","author":"Wu Zonghan","year":"2019","unstructured":"Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. 2019. Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint arXiv:1906.00121 (2019)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33015668"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539274"},{"key":"e_1_2_1_44_1","volume-title":"Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.04875","author":"Yu Bing","year":"2017","unstructured":"Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2017. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.04875 (2017)."},{"key":"e_1_2_1_45_1","volume-title":"Multi-scale context aggregation by dilated convolutions. arXiv preprint arXiv:1511.07122","author":"Yu Fisher","year":"2015","unstructured":"Fisher Yu and Vladlen Koltun. 2015. Multi-scale context aggregation by dilated convolutions. arXiv preprint arXiv:1511.07122 (2015)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10735"},{"key":"e_1_2_1_47_1","volume-title":"The Eleventh International Conference on Learning Representations.","author":"Zhang Yunhao","year":"2022","unstructured":"Yunhao Zhang and Junchi Yan. 2022. Crossformer: Transformer utilizing cross-dimension dependency for multivariate time series forecasting. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17325"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3641204.3641217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:09:23Z","timestamp":1714687763000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3641204.3641217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.14778\/3641204.3641217"],"URL":"https:\/\/doi.org\/10.14778\/3641204.3641217","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"2024-05-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}