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

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

References in corpus (19)

• Adam: A Method for Stochastic Optimization
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Geometric deep learning: going beyond Euclidean data
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• Variational Graph Auto-Encoders
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs
• Principal Neighbourhood Aggregation for Graph Nets
• SIGN: Scalable Inception Graph Neural Networks
• ST-GRAT: A Novel Spatio-temporal Graph Attention Network for Accurately Forecasting Dynamically Changing Road Speed
• Meta-Gradient Reinforcement Learning
• Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting
• PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest
• Temporal Graph Networks for Deep Learning on Dynamic Graphs
• Machine Learning for Spatiotemporal Sequence Forecasting: A Survey
• 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 (22)

• Multimodal Data Integration for Oncology in the Era of Deep Neural Networks: A Review
• Trustworthy Graph Neural Networks: Aspects, Methods and Trends
• GeoShapley: A Game Theory Approach to Measuring Spatial Effects in Machine Learning Models
• Graph Neural Networks for Pressure Estimation in Water Distribution Systems
• MobilityDL: A Review of Deep Learning From Trajectory Data
• RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network
• Deep learning for dynamic graphs: models and benchmarks
• DuETA: Traffic Congestion Propagation Pattern Modeling via Efficient Graph Learning for ETA Prediction at Baidu Maps
• CLDG: Contrastive Learning on Dynamic Graphs
• GNNBuilder: An Automated Framework for Generic Graph Neural Network Accelerator Generation, Simulation, and Optimization
• 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
• Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks
• Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent
• CAMETA: Conflict-Aware Multi-Agent Estimated Time of Arrival Prediction for Mobile Robots
• A Dataset for Learning Graph Representations to Predict Customer Returns in Fashion Retail
• Eco-PiNN: A Physics-informed Neural Network for Eco-toll Estimation
• Efficient Mixed Precision Quantization in Graph Neural Networks
• Link Representation Learning for Probabilistic Travel Time Estimation
• VACA: Design of Variational Graph Autoencoders for Interventional and Counterfactual Queries
• On the Impact of Sybil-based Attacks on Mobile Crowdsensing for Transportation