ETA Prediction with Graph Neural Networks in Google Maps

Derrow-Pinion, Austin; She, Jennifer; Wong, David; Lange, Oliver; Hester, Todd; Pérez, Luís G.; Nunkesser, Marc; Lee, Seongjae; Guo, Xueying; Wiltshire, Brett; Battaglia, Peter; Gupta, Vishal K.; Li, Ang; Xu, Zhongwen; Álvaro Sánchez‐González; Li, Yujia; Veličković, Petar · 2021 · OpenAlex-citations

DOI: 10.1145/3459637.3481916

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper presents a Graph Neural Network (GNN) estimator for Estimated Time of Arrival (ETA) prediction, deployed in production at Google Maps. The research addresses the challenge of accurately predicting travel times by accounting for complex spatiotemporal interactions within road networks. Accurate ETA prediction is critical for user experience and enterprise logistics, requiring models to reason about future traffic conditions, such as rush hours, which may not be immediately evident from current road states. The authors argue that because road networks are naturally graph-structured, GNNs are an ideal approach for capturing both topological properties and temporal dynamics. The method models the road network using "supersegments," defined as sequences of connected road segments that follow typical traffic routes. The architecture employs a standard Graph Network framework organized into an encode-process-decode structure. For each supersegment, the model predicts travel times across multiple fixed future horizons (0, 600, 1200, 1800, and 3600 seconds). Features include real-time and historical travel speeds, segment lengths, and road classifications. To ensure training stability and production readiness, the authors utilized MetaGradients to dynamically tune the learning rate and applied exponential moving averages to model parameters. The training objective combined a primary supersegment-level loss with auxiliary segment-level and cumulative segment-level losses to prevent error accumulation and improve representation learning. The model was evaluated on datasets from New York, Los Angeles, Tokyo, and Singapore, comparing performance against non-parametric baselines and segment-level linear regression models. The deployed GNN significantly reduced negative ETA outcomes—instances where the prediction error exceeded a specific threshold—compared to the previous production baseline. Improvements were observed globally, with reductions exceeding 40% in cities like Sydney. Ablation studies confirmed that specific architectural choices, such as the combination of aggregation functions and the use of auxiliary losses, contributed to these gains. The model demonstrated robustness across different regions and traffic conditions, including those affected by pandemic-related disruptions. The significance of this work lies in demonstrating the efficacy of GNNs for large-scale, real-world traffic forecasting. By successfully deploying a GNN in a high-volume production environment, the authors provide evidence that graph representation learning can outperform traditional methods in capturing spatial and temporal dependencies in transportation networks. The paper also offers prescriptive insights for practitioners, highlighting the importance of training regimes like MetaGradients and careful loss function design for stabilizing GNNs in unstable, real-world data distributions. This contributes to the broader field of applied machine learning by showcasing a scalable solution for a critical urban infrastructure problem.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• anticipation