ETA Prediction with Graph Neural Networks in Google Maps

Abstract

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

To appear at CIKM 2021 (Applied Research Track). 10 pages, 4 figures

References in corpus (7)

• Semi-Supervised Classification with Graph Convolutional Networks
• Variational Graph Auto-Encoders
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting
• PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest
• Graph WaveNet for Deep Spatial-Temporal Graph Modeling
• Knowing your FATE: Friendship, Action and Temporal Explanations for User Engagement Prediction on Social Apps

Cited by in corpus (8)

• RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network
• DuETA: Traffic Congestion Propagation Pattern Modeling via Efficient Graph Learning for ETA Prediction at Baidu Maps
• Relating Graph Neural Networks to Structural Causal Models
• A Multidimensional Graph Fourier Transformation Neural Network for Vehicle Trajectory Prediction
• CARL-G: Clustering-Accelerated Representation Learning on Graphs
• A Dataset for Learning Graph Representations to Predict Customer Returns in Fashion Retail
• Eco-PiNN: A Physics-informed Neural Network for Eco-toll Estimation
• VACA: Design of Variational Graph Autoencoders for Interventional and Counterfactual Queries