mlsanityData to 7 Oct 2026

ETA Prediction with Graph Neural Networks in Google Maps

arXiv 2108.11482 ↗First posted 25 Aug 2021cs.LG cs.AI cs.SIcited by 130

Not on the map. Why?

Abstract (arXiv)

Travel-time prediction constitutes a task of high importance in transportation networks, with web mapping services like Google Maps regularly serving vast quantities of travel time queries from users and enterprises alike. Further, such a task requires accounting for complex spatiotemporal interactions (modelling both the topological properties of the road network and anticipating events -- such as rush hours -- that may occur in the future). Hence, it is an ideal target for graph representation learning at scale. Here we present a graph neural network estimator for estimated time of arrival (ETA) which we have deployed in production at Google Maps. While our main architecture consists of standard GNN building blocks, we further detail the usage of training schedule methods such as MetaGradients in order to make our model robust and production-ready. We also provide prescriptive studies: ablating on various architectural decisions and training regimes, and qualitative analyses on real-world situations where our model provides a competitive edge. Our GNN proved powerful when deployed, significantly reducing negative ETA outcomes in several regions compared to the previous production baseline (40+% in cities like Sydney).

Key facts. Cited by 130 papers in the map (data through 7 Oct 2026). Builds on 28 of its 40 references that are in the map. First posted on arXiv 25 Aug 2021.

Builds on

28 of 40 references.

References · 28

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2017Deep Setscited by 1,394
  7. 2016Variational Graph Auto-Encoderscited by 1,373
  8. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  9. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  10. 2017Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecastingcited by 1,125
  11. 2018Deep Graph Infomaxcited by 1,101
  12. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
16 more
  1. 2019Graph WaveNet for Deep Spatial-Temporal Graph Modelingcited by 820
  2. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  3. 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 521
  4. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  5. 2020Inductive Representation Learning on Temporal Graphscited by 454
  6. 2019GMAN: A Graph Multi-Attention Network for Traffic Predictioncited by 433
  7. 2021Spectral Temporal Graph Neural Network for Multivariate Time-series Forecastingcited by 298
  8. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  9. 2018GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphscited by 164
  10. 2018Meta-Gradient Reinforcement Learningcited by 156
  11. 2019AliGraph: A Comprehensive Graph Neural Network Platformcited by 152
  12. 2019Neural Execution of Graph Algorithmscited by 118
  13. 2020PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterestcited by 75
  14. 2018Relational inductive bias for physical construction in humans and machinescited by 41
  15. 2020Knowing your FATE: Friendship, Action and Temporal Explanations for User Engagement Prediction on Social Appscited by 23
  16. 2018Machine Learning for Spatiotemporal Sequence Forecasting: A Surveycited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 28; 2023: 39; 2024: 28; 2025: 20; 2026: 13.

130 papers.

Sort:

By area:

  1. 2023Spatio-Temporal Graph Neural Networks for Predictive Learning in Urban Computing: A Surveycited by 140
  2. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  3. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  4. 2023Everything is Connected: Graph Neural Networkscited by 85
  5. 2022Expander Graph Propagationcited by 75
  6. 2022A Survey on Graph Representation Learning Methodscited by 66
  7. 2022Empowering Graph Representation Learning with Test-Time Graph Transformationcited by 66
  8. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  9. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 58
  10. 2022Provably expressive temporal graph networkscited by 56
  11. 2022Graph Filters for Signal Processing and Machine Learning on Graphscited by 53
  12. 2023How does over-squashing affect the power of GNNs?cited by 53
38 more
  1. 2022Message passing all the way upcited by 47
  2. 2022Certified Graph Unlearningcited by 46
  3. 2021Relating Graph Neural Networks to Structural Causal Modelscited by 39
  4. 2025Transformers are Graph Neural Networkscited by 29
  5. 2022Practical Adversarial Attacks on Spatiotemporal Traffic Forecasting Modelscited by 28
  6. 2022RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Networkcited by 27
  7. 2024Long Range Propagation on Continuous-Time Dynamic Graphscited by 26
  8. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  9. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 24
  10. 2022Latent Graph Inference using Product Manifoldscited by 23
  11. 2023E(n) Equivariant Message Passing Simplicial Networkscited by 23
  12. 2025Relational Deep Learning: Challenges, Foundations and Next-Generation Architecturescited by 22
  13. 2023Multimodal Data Integration for Oncology in the Era of Deep Neural Networks: A Reviewcited by 20
  14. 2024Beyond Euclid: An Illustrated Guide to Modern Machine Learning with Geometric, Topological, and Algebraic Structurescited by 20
  15. 2023Deep learning for dynamic graphs: models and benchmarkscited by 19
  16. 2024Sports-Traj: A Unified Trajectory Generation Model for Multi-Agent Movement in Sportscited by 19
  17. 2021VACA: Design of Variational Graph Autoencoders for Interventional and Counterfactual Queriescited by 18
  18. 2023Distill n' Explain: explaining graph neural networks using simple surrogatescited by 18
  19. 2023A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardwarecited by 18
  20. 2022Traffic4cast at NeurIPS 2021 -- Temporal and Spatial Few-Shot Transfer Learning in Gridded Geo-Spatial Processescited by 15
  21. 2022Geometry-Complete Perceptron Networks for 3D Molecular Graphscited by 15
  22. 2023Asynchronous Algorithmic Alignment with Cocyclescited by 13
  23. 2024Bundle Neural Networks for message diffusion on graphscited by 13
  24. 2024UrbanLLM: Autonomous Urban Activity Planning and Management with Large Language Modelscited by 13
  25. 2023A Survey of Graph Unlearningcited by 12
  26. 2022Transforming PageRank into an Infinite-Depth Graph Neural Networkcited by 11
  27. 2022Link Prediction with Non-Contrastive Learningcited by 11
  28. 2023Massively Scalable Inverse Reinforcement Learning in Google Mapscited by 11
  29. 2024Temporal Graph ODEs for Irregularly-Sampled Time Seriescited by 11
  30. 2024Safety in Graph Machine Learning: Threats and Safeguardscited by 11
  31. 2024CLDG: Contrastive Learning on Dynamic Graphscited by 11
  32. 2022DuETA: Traffic Congestion Propagation Pattern Modeling via Efficient Graph Learning for ETA Prediction at Baidu Mapscited by 10
  33. 2022Forecasting Unobserved Node States with spatio-temporal Graph Neural Networkscited by 9
  34. 2024Micro-Macro Spatial-Temporal Graph-based Encoder-Decoder for Map-Constrained Trajectory Recoverycited by 9
  35. 2023Graph Neural Networks Go Forward-Forwardcited by 8
  36. 2023A Multidimensional Graph Fourier Transformation Neural Network for Vehicle Trajectory Predictioncited by 8
  37. 2023Graph Neural Networks for Pressure Estimation in Water Distribution Systemscited by 8
  38. 2025GiGL: Large-Scale Graph Neural Networks at Snapchatcited by 8

50 most cited of 130 All 130 (JSON)