[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3580305.3599357acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
research-article
Free access

Frigate: Frugal Spatio-temporal Forecasting on Road Networks

Published: 04 August 2023 Publication History

Abstract

Modelling spatio-temporal processes on road networks is a task of growing importance. While significant progress has been made on developing spatio-temporal graph neural networks (Gnns), existing works are built upon three assumptions that are not practical on real-world road networks. First, they assume sensing on every node of a road network. In reality, due to budget-constraints or sensor failures, all locations (nodes) may not be equipped with sensors. Second, they assume that sensing history is available at all installed sensors. This is unrealistic as well due to sensor failures, loss of packets during communication, etc. Finally, there is an assumption of static road networks. Connectivity within networks change due to road closures, constructions of new roads, etc. In this work, we develop Frigate to address all these shortcomings. Frigate is powered by a spatio-temporal Gnn that integrates positional, topological, and temporal information into rich inductive node representations. The joint fusion of this diverse information is made feasible through a novel combination of gated Lipschitz embeddings with Lstms. We prove that the proposed Gnn architecture is provably more expressive than message-passing Gnns used in state-of-the-art algorithms. The higher expressivity of Frigate naturally translates to superior empirical performance conducted on real-world network-constrained traffic data. In addition, Frigate is robust to frugal sensor deployment, changes in road network connectivity, and temporal irregularity in sensing.

Supplementary Material

MP4 File (Frigate2-720p-230623.mp4)
Frigate: Frugal Spatio-temporal Forecasting on Road Networks Mridul Gupta, Hariprasad Kodamana, Sayan Ranu Frigate is a traffic forecasting technique that works with less sensors, handles sensor failures and changes to the road network by employing a siamese stack of inductive Graph Neural Networks with LSTMs. It uses sigmoid gated GNNs to capture long range dependencies and Lipschitz embeddings to represent sensor locations. This research was supported by Yardi School of AI, IIT Delhi.

References

[1]
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, Vol. 33 (2020), 17804--17815.
[2]
021)]% zigzag, Yuzhou Chen, Ignacio Segovia, and Yulia R Gel. 2021. Z-GCNETs: time zigzags at graph convolutional networks for time series forecasting. In International Conference on Machine Learning. PMLR, 1684--1694.
[3]
Vijay Prakash Dwivedi, Ladislav Rampávs ek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. 2022. Long Range Graph Benchmark. In NeurIPS.
[4]
Zheng Fang, Qingqing Long, Guojie Song, and Kunqing Xie. 2021. Spatial-temporal graph ode networks for traffic flow forecasting. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 364--373.
[5]
Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems, Vol. 30 (2017).
[6]
Jayant Jain, Vrittika Bagadia, Sahil Manchanda, and Sayan Ranu. 2021. NeuroMLR: Robust & Reliable Route Recommendation on Road Networks. Advances in Neural Information Processing Systems, Vol. 34 (2021), 22070--22082.
[7]
Manas Joshi, Arshdeep Singh, Sayan Ranu, Amitabha Bagchi, Priyank Karia, and Puneet Kala. 2021. Batching and matching for food delivery in dynamic road networks. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 2099--2104.
[8]
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.
[9]
Mingxi Li, Yihong Tang, and Wei Ma. 2022. Few-Sample Traffic Prediction With Graph Networks Using Locale as Relational Inductive Biases. IEEE Transactions on Intelligent Transportation Systems (2022).
[10]
Mengzhang Li and Zhanxing Zhu. 2021. Spatial-temporal fusion graph neural networks for traffic flow forecasting. In Proceedings of the AAAI conference on artificial intelligence, Vol. 35. 4189--4196.
[11]
Xiucheng Li, Gao Cong, Aixin Sun, and Yun Cheng. 2019. Learning travel time distributions with deep generative model. In The World Wide Web Conference. 1017--1027.
[12]
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting. In International Conference on Learning Representations (ICLR '18).
[13]
Jing Lian and Lin Zhang. 2018. One-month beijing taxi GPS trajectory dataset with taxi IDs and vehicle status. In Proceedings of the First Workshop on Data Acquisition To Analysis. 3--4.
[14]
Nathan Linial, Eran London, and Yuri Rabinovich. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica, Vol. 15 (1995), 215--245.
[15]
Dachuan Liu, Jin Wang, Shuo Shang, and Peng Han. 2022. Msdr: Multi-step dependency relation networks for spatial temporal forecasting. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1042--1050.
[16]
Sourav Medya, Sayan Ranu, Jithin Vachery, and Ambuj Singh. 2018. Noticeable network delay minimization via node upgrades. Proceedings of the VLDB Endowment, Vol. 11, 9 (2018), 988--1001.
[17]
Shubhadip Mitra, Sayan Ranu, Vinay Kolar, Aditya Telang, Arnab Bhattacharya, Ravi Kokku, and Sriram Raghavan. 2015. Trajectory aware macro-cell planning for mobile users. In 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE, 792--800.
[18]
Shubhadip Mitra, Priya Saraf, Richa Sharma, Arnab Bhattacharya, Sayan Ranu, and Harsh Bhandari. 2017. Netclus: A scalable framework for locating top-k sites for placement of trajectory-aware services. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 87--90.
[19]
Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, and Sayan Ranu. 2021. GraphReach: Position-Aware Graph Neural Network using Reachability Estimations. IJCAI (2021).
[20]
OpenStreetMap contributors. 2017. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org.
[21]
Shiladitya Pande, Sayan Ranu, and Arnab Bhattacharya. 2017. SkyGraph: Retrieving regions of interest using skyline subgraph queries. Proceedings of the VLDB Endowment, Vol. 10, 11 (2017), 1382--1393.
[22]
Chao Song, Youfang Lin, Shengnan Guo, and Huaiyu Wan. 2020. Spatial-temporal synchronous graph convolutional networks: A new framework for spatial-temporal network data forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 914--921.
[23]
Petar Velivc ković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph attention networks. ICLR (2018).
[24]
Pengkun Wang, Chaochao Zhu, Xu Wang, Zhengyang Zhou, Guang Wang, and Yang Wang. 2022. Inferring intersection traffic patterns with sparse video surveillance information: An st-gan method. IEEE Transactions on Vehicular Technology, Vol. 71, 9 (2022), 9840--9852.
[25]
Yang Wang, Yiwei Xiao, Xike Xie, Ruoyu Chen, and Hengchang Liu. 2018. Real-time Traffic Pattern Analysis and Inference with Sparse Video Surveillance Information. In IJCAI. 3571--3577.
[26]
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang. 2020. Connecting the dots: Multivariate time series forecasting with graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 753--763.
[27]
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. 2019. Graph wavenet for deep spatial-temporal graph modeling. International Joint Conference on Artificial Intelligence, Vol. 28 (2019).
[28]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks? ICLR (2019).
[29]
Can Yang and Gyozo Gidofalvi. 2018. Fast map matching, an algorithm integrating hidden Markov model with precomputation. International Journal of Geographical Information Science, Vol. 32, 3 (2018), 547--570.
[30]
Song Yang, Jiamou Liu, and Kaiqi Zhao. 2021. Space Meets Time: Local Spacetime Neural Network For Traffic Flow Forecasting. In 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 817--826.
[31]
Pranali Yawalkar and Sayan Ranu. 2019. Route recommendations on road networks for arbitrary user preference functions. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 602--613.
[32]
Jiaxuan You, Rex Ying, and Jure Leskovec. 2019. Position-aware Graph Neural Networks. In ICML, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. 7134--7143.
[33]
Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. International Joint Conference on Artificial Intelligenc, Vol. 27 (2018).
[34]
Chuanpan Zheng, Xiaoliang Fan, Cheng Wang, and Jianzhong Qi. 2020. Gman: A graph multi-attention network for traffic prediction. In Proceedings of the AAAI conference on artificial intelligence, Vol. 34. 1234--1241.
[35]
Zhengyang Zhou, Kuo Yang, Wei Sun, Binwu Wang, Min Zhou, Yunan Zong, and Yang Wang. 2023. Towards Learning in Grey Spatiotemporal Systems: A Prophet to Non-consecutive Spatiotemporal Dynamics. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM). SIAM, 190--198. io

Cited By

View all
  • (2025)A novel spatio-temporal feature interleaved contrast learning neural network from a robustness perspectiveKnowledge-Based Systems10.1016/j.knosys.2024.112788309(112788)Online publication date: Jan-2025
  • (2025)Spatio-spectral graph neural operator for solving computational mechanics problems on irregular domain and unstructured gridComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117659435(117659)Online publication date: Feb-2025
  • (2024)Frequency Enhanced Pre-training for Cross-City Few-shot Traffic ForecastingMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70344-7_3(35-52)Online publication date: 22-Aug-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
August 2023
5996 pages
ISBN:9798400701030
DOI:10.1145/3580305
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 August 2023

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. graph neural networks
  2. inductive learning
  3. spatio-temporal prediction
  4. traffic prediction

Qualifiers

  • Research-article

Conference

KDD '23
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)379
  • Downloads (Last 6 weeks)18
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2025)A novel spatio-temporal feature interleaved contrast learning neural network from a robustness perspectiveKnowledge-Based Systems10.1016/j.knosys.2024.112788309(112788)Online publication date: Jan-2025
  • (2025)Spatio-spectral graph neural operator for solving computational mechanics problems on irregular domain and unstructured gridComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117659435(117659)Online publication date: Feb-2025
  • (2024)Frequency Enhanced Pre-training for Cross-City Few-shot Traffic ForecastingMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70344-7_3(35-52)Online publication date: 22-Aug-2024
  • (2023)GRAFENNEProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618898(12165-12181)Online publication date: 23-Jul-2023
  • (2023)Performance Evaluation of Building Blocks of Spatial-Temporal Deep Learning Models for Traffic ForecastingIEEE Access10.1109/ACCESS.2023.333822311(136478-136495)Online publication date: 2023
  • (2020)Network level spatial temporal traffic forecasting with hierarchical attention LSTM (HierAttnLSTM)Digital Transportation and Safety10.48130/dts-0024-0021(1-13)Online publication date: 2020

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media