# ETA Prediction with Graph Neural Networks in Google Maps

arXiv: https://arxiv.org/abs/2108.11482 · HTML: https://mlsanity.com/paper/2108.11482/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph WaveNet for Deep Spatial-Temporal Graph Modeling](https://mlsanity.com/paper/1906.00121/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [GMAN: A Graph Multi-Attention Network for Traffic Prediction](https://mlsanity.com/paper/1911.08415/) (2019)
- [Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting](https://mlsanity.com/paper/2103.07719/) (2021)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs](https://mlsanity.com/paper/1803.07294/) (2018)
- [Meta-Gradient Reinforcement Learning](https://mlsanity.com/paper/1805.09801/) (2018)
- [AliGraph: A Comprehensive Graph Neural Network Platform](https://mlsanity.com/paper/1902.08730/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [Knowing your FATE: Friendship, Action and Temporal Explanations for User Engagement Prediction on Social Apps](https://mlsanity.com/paper/2006.06427/) (2020)
- [Machine Learning for Spatiotemporal Sequence Forecasting: A Survey](https://mlsanity.com/paper/1808.06865/) (2018)

## Built on by (most cited first, 30 of 130)

- [Spatio-Temporal Graph Neural Networks for Predictive Learning in Urban Computing: A Survey](https://mlsanity.com/paper/2303.14483/) (2023)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [Expander Graph Propagation](https://mlsanity.com/paper/2210.02997/) (2022)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Anti-Symmetric DGN: a stable architecture for Deep Graph Networks](https://mlsanity.com/paper/2210.09789/) (2022)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Message passing all the way up](https://mlsanity.com/paper/2202.11097/) (2022)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [Relating Graph Neural Networks to Structural Causal Models](https://mlsanity.com/paper/2109.04173/) (2021)
- [Practical Adversarial Attacks on Spatiotemporal Traffic Forecasting Models](https://mlsanity.com/paper/2210.02447/) (2022)
- [Transformers are Graph Neural Networks](https://mlsanity.com/paper/2506.22084/) (2025)
- [Long Range Propagation on Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2406.02740/) (2024)
- [RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network](https://mlsanity.com/paper/2202.13547/) (2022)
- [Provably Powerful Graph Neural Networks for Directed Multigraphs](https://mlsanity.com/paper/2306.11586/) (2023)
- [Towards Deep Attention in Graph Neural Networks: Problems and Remedies](https://mlsanity.com/paper/2306.02376/) (2023)
- [Latent Graph Inference using Product Manifolds](https://mlsanity.com/paper/2211.16199/) (2022)
- [E(n) Equivariant Message Passing Simplicial Networks](https://mlsanity.com/paper/2305.07100/) (2023)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Multimodal Data Integration for Oncology in the Era of Deep Neural Networks: A Review](https://mlsanity.com/paper/2303.06471/) (2023)
- [Beyond Euclid: An Illustrated Guide to Modern Machine Learning with Geometric, Topological, and Algebraic Structures](https://mlsanity.com/paper/2407.09468/) (2024)
- [VACA: Design of Variational Graph Autoencoders for Interventional and Counterfactual Queries](https://mlsanity.com/paper/2110.14690/) (2021)
- [Deep learning for dynamic graphs: models and benchmarks](https://mlsanity.com/paper/2307.06104/) (2023)
- [Sports-Traj: A Unified Trajectory Generation Model for Multi-Agent Movement in Sports](https://mlsanity.com/paper/2405.17680/) (2024)
- [Distill n' Explain: explaining graph neural networks using simple surrogates](https://mlsanity.com/paper/2303.10139/) (2023)

## 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).