Source-linked AI summary
ETA Prediction with Graph Neural Networks in Google Maps
Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, Peter W. Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez, Yujia Li, Petar Veličković
TL;DR
ETA prediction must account for road-network structure and traffic conditions that evolve before users reach later route segments. The paper presents a graph neural network estimator with training stabilization methods, deploys it in Google Maps, and reports substantial reductions in negative ETA outcomes, including above 40% in Sydney. The authors also provide ablations and practical guidance for production deployment.
Problem
ETA prediction requires modeling both spatial road-network information and temporal changes in traffic conditions to estimate travel time along candidate routes.
Method
The paper uses a graph neural network over supersegments and applies MetaGradients and exponential moving averages to stabilize training and serving.
Results
Above 40% relative reduction in negative ETA outcomes was observed in cities like Sydney compared with the previous production baseline.
Takeaways & Limitations
The deployed GNN serves Google Maps queries worldwide and the paper offers prescriptive guidance from architectural, featurization, and training ablations.
Takeaways & Limitations
The paper notes that some potential performance improvements were not considered worthwhile because their production costs were too high.
Abstract
from arXiv · showhide
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).
1 INTRODUCTION
ETA prediction supports route decisions but must model both road-network structure and future traffic conditions. The paper presents a deployed GNN estimator with production gains and studies design, training, and real-world behavior.
- ETA prediction estimates travel time for a candidate route under current road-network conditions.
- Accurate ETAs can help traffic participants make informed decisions, potentially avoiding congestion and reducing time in traffic.
- The paper presents a graph neural network ETA model deployed in production at Google Maps.
- Above 40% relative reduction in negative ETA outcomes was observed in cities like Sydney versus the previous production baseline.Negative ETA outcomes occur when ETA error exceeds a threshold relative to observed travel duration.
- The task requires reasoning over spatial structure, distant traffic conditions, background signals, and traffic changes occurring before later route segments are reached.
- The work studies road-network featurization, GNN design, training regimes, ablations, and traffic situations where the model outperforms the prior baseline.
2 RELATED WORK
Related work connects this approach to graph representation learning, travel-time prediction, spatiotemporal traffic forecasting, scalable web applications, and training methods for unstable production settings.
- Graph representation learning: The model builds on the Graph Network framework and encode-process-decode paradigm to align GNN computation with traffic and pathfinding operations.
- Travel-time prediction: Prior travel-time work combines spatially aware convolutions or graph neural networks with recurrent mechanisms, while historical time-of-day travel times are an important predictor.
- Spatiotemporal traffic forecasting: Spatiotemporal traffic forecasting commonly combines graph structure with node-level time series, including architectures such as DCRNN, STGCN, and Graph WaveNet.
- Spatiotemporal traffic forecasting: Dynamic graph representation learning addresses settings where time series are asynchronous across nodes.
- Graph neural networks at scale: Web-scale GNN applications include recommendation, engagement forecasting, friend ranking, and traffic prediction in Baidu Maps.
- Training regimes and components: MetaGradients dynamically tune the learning rate to stabilize training across uneven query batches and support production-ready GNN deployment.
- Training regimes and components: The paper adapts graph auto-encoders, deep graph infomax, and combinations of aggregation functions for road-network modeling.
3 METHOD
The method operates on route-segment networks, predicts multiple future horizons, and uses stabilization techniques to make production deployment reliable.
- The GNN models operate on networks of route segments and predict travel times across multiple future horizons for more accurate ETAs.
- Stabilizing methods reduce training instability and support production-ready model behavior.
3.1 Problem Setup
The method represents connected road segments as supersegments and predicts their travel times at future horizons using real-time and historical traffic features. At serving time, predictions are composed sequentially along a route.
- Serving procedure: Supersegments are sequences of connected road segments that follow typical traffic routes.
- Serving procedure: At serving time, supersegments are queried sequentially, using earlier predictions to select later horizons and interpolating between fixed-horizon predictions.
- Problem Setup: A supersegment is a graph whose nodes are road segments and whose edges connect adjacent segments.
- Problem Setup: For each supersegment, the model predicts travel time at the current time and several fixed future horizons.
- Data and features: Node and graph labels use traversal times, while features include real-time and historical speeds and times, segment length, and segment priority.
- Baselines: Segment-level baselines bypass the supersegment graph and sum independently predicted segment travel times; prior production models used linear regression.
3.2 Model Architecture
The model uses Graph Network blocks to update edge, node, and supersegment representations, then predicts travel times at multiple levels for separate future horizons.
- Graph Network blocks: Each GN block applies edge, node, and global update functions alongside aggregation functions to propagate road-network information.Edge updates use edge, endpoint-node, and supersegment features; node updates use node features and aggregated edge representations; global updates use aggregated node and edge representations.
- Architecture: The architecture composes three GN blocks into an encode-process-decode model with a separate model for each horizon.The encoder creates latent node, edge, and supersegment representations; the processor updates them twice with shared parameters before decoding predictions.
- Outputs: The decoder produces supersegment, segment, and cumulative segment travel-time predictions for each future horizon.Although multiple outputs support representation learning, production uses the supersegment-level output to avoid accumulated segment-level prediction error.
- Aggregation: The model uses summation aggregation by default, while combinations of aggregators provided offline benefits for some regions and horizons.The investigated combinations concatenate outputs from functions such as Min, Max, SqrtN, and Sum.
3.3 Model Training
Training combines multiple loss signals with stabilization methods designed to control variability during training and serving, including MetaGradients and exponential moving averages.
- EMA: Exponential moving averages of model parameters are applied during evaluation and serving to reduce variance in saved models.The decay factor is α = 0.99.
- Losses: A combination of loss functions was useful for training, including auxiliary segment-level objectives alongside the primary supersegment-level travel-time objective.The final objective also includes predictions for segment and supersegment travel times, with Huber losses used across segments and supersegments.
- Losses: Huber loss is less sensitive to outliers, and losses are summed across segments and supersegments with different dependence on supersegment length.Supersegment-level losses are more influenced by length, whereas segment-level losses are more independent of length.
- MetaGradients: MetaGradients adapt the learning rate during training by jointly optimizing the learning-rate hyperparameter with model parameters.The method follows an online cross-validation paradigm and was combined with Adam in this application.
4 EXPERIMENTS
Experiments evaluate the launched GNNs across selected regions, baselines, and architectural or training variants, including extended spatial context and auxiliary losses.
- Evaluation setup: Offline evaluation uses data from January 2020 and focuses on New York, Los Angeles, Tokyo, and Singapore, while online evaluation uses November 2020 data.The authors note that November 2020 traffic may reflect COVID-19 patterns and selected regions intended to minimize this deviation.
- Baselines: The evaluation compares GNNs with real-time and historical travel-time baselines and with models that do not leverage graph structure.The baselines include DeepSets and nonparametric travel times computed from recent or historical speeds.
- Ablations: Ablations examine learnable segment and supersegment embeddings, MetaGradients, EMA, aggregator combinations, extended supersegments, and unsupervised auxiliary losses.Embedding vocabularies are region-specific, and MetaGradients and EMA are directly compared with and without their use.
- Baseline comparison: Offline GN performance significantly exceeds all reported baselines for every evaluated region and horizon (p < 0.01, t-test).Table 2 reports RMSE averaged across five random seeds.
- Extended Supersegments: Extended supersegments add neighboring, potentially connected segments while preserving the original prediction task and labels.This adds spatial context such as congestion on connecting routes, at the cost of storage, training, and inference speed.
- Auxiliary losses: Unsupervised auxiliary losses target graph structure through global-structure contrastive learning with DGI and local-topology link prediction with GAE.Both are combined with the supervised objective to assist learning.
4.2 Offline Evaluation
Offline evaluation shows that the GNN consistently improves RMSE over baselines across regions and horizons, while several architectural and training choices reduce error or variance. Some gains depend on region, horizon, and added production costs.
- Baseline Comparison: Across all studied regions and horizons, the GNN outperforms baselines, improving RMSE by 0.12 to 0.77 versus DeepSets.These improvements are statistically significant across five runs with p<0.01.
- Embeddings: Learnable segment and supersegment embeddings improve RMSE across most regions and horizons.Table 3 evaluates these embeddings through ablation.
- MetaGradients & EMA: Both MetaGradients and EMA reduce within-run and across-run variance, while MetaGradients consistently decays the learning rate to stabilize training.The variance analysis aggregates validation RMSE across five seeds and reports trends across regions and horizons.
- Extended Supersegments: Extended supersegments with binary original-segment indicators improve RMSE by 0.01 to 0.29.They may be useful when increased data-storage and inference costs are not central concerns.
- Unsupervised Auxiliary Losses: Deep graph infomax or graph auto-encoder auxiliary losses improve RMSE by 0.05 to 0.23, but optimal variants differ by region and horizon.GN+DGI improves in all cases, while tuning these losses across regions and horizons is likely expensive.
- Combinations of Aggregators: Using all five aggregation functions is a practical preference because the best aggregator varies by region and prediction horizon.Individual alternatives improve RMSE by up to 0.34 over the production default of sum, depending on region and horizon.
4.3 Online Evaluation
Online evaluation shows that GNNs outperform baseline methods, while qualitative LAX analyses illustrate benefits from broader spatial context and multiple prediction horizons.
- Online evaluation: Online evaluation reports RMSE of track travel times for GNN models and baseline methods.The evaluation compares models during serving, with real-time and historical travel times used in precursor and fallback systems.
- Qualitative analysis: In LAX, GNN predictions match congestion-related increases in actual travel times better than the real-time travel-times baseline.The model uses traffic information from a larger neighborhood to detect congestion more accurately.
- Qualitative analysis: For a 60-minute-ahead prediction, the GNN with h=3600 matches actual travel times better than the GNN with h=0.The example illustrates why multiple prediction horizons support accurate ETA estimation.
5 ENGINEERING CHALLENGES
Production deployment requires controlling inference cost and defining coverage strategies for route representations and less frequently visited roads.
- Caching: A shared lookup-table cache addresses the impracticality of evaluating multiple supersegments on the fly for every ETA request.Caching is used to meet Google Maps latency requirements while keeping Graph Net evaluation costs low.
- Turn speeds: Turn-specific real-time and historical speeds are used when busy road segments have multimodal speed distributions near traffic splits.This handling targets cases such as intersections or highway ramps.
- Coverages: About 1 million predefined supersegments cover common routes, while less frequently visited road segments use simpler per-segment models.Coverage emphasizes freeways, major arterials, and popular shortcuts in metropolitan areas.
6 CONCLUSION
The paper concludes that a production-engineered GNN can improve ETA prediction at global scale, supported by stabilizing methods, evaluations, and deployment-oriented analyses.
- Conclusion: The deployed GNN serves Google Maps user queries worldwide and shows significant quantitative improvements in offline metrics, online evaluations, and user studies.The conclusion also reports extensive ablations of design and featurization choices.
- Conclusion: MetaGradients and exponential moving averages were necessary additions for making the GNN production-ready.These stabilizing techniques supported accurate travel-time prediction in deployment.
- Conclusion: The paper provides prescriptive advice for deploying GNNs in transportation-network analysis.The authors frame transportation-network analysis as an important application area for graph representation learning.