Last year, German artist Simon Weckert pulled off a prank using 99 mobile phones. Using a handcraft full of smartphones, Weckert searched for directions within Google Maps app on the smartphones and walked them all down several main roads in Berlin, including the area just outside the Google headquarters. This tricked the app into showing large traffic jam and update its map directions accordingly. 

While this one-off stunt grabbed eyeballs, poor travel time estimation is a highly undesirable feature of route mapping services like Google Maps. In a world where people are racing against time, wasting even a few minutes commuting can be a major source of frustration. 

Web mapping services like Google Maps regularly serve vast quantities of travel time predictions from users and enterprises, helping commuters cut down on the time they spend on roads. To estimate total travel time, one needs to account for complex spatiotemporal interactions, including road conditions and the traffic in a particular route.

This offers a great opportunity to use graphical representations at a scale. A paper titled “ETA Prediction with Graph Neural Networks in Google Maps”, authored by researchers from Google, Deepmind, Facebook AI and others presents a graph neural network estimator for an estimated time of travel (ETA). To this end, the researchers have developed an architecture that consists of standard GNN building blocks and uses training schedule methods such as MetaGradients to make the model robust and production-ready. This paper was recently accepted for the CIKM 2021 conference.

Estimating ETA

The significance of an accurate ETA predictor is that it allows drivers to make an informed decision and minimise overall time spent in traffic. Powerful ETA predictors should be able to make decisions about conditions that may take place in the future and may not be immediately observable from the current road state. The availability of a vast amount of historical information can be used to support the detection and exploitation of such subtleties.

Road networks are modelled using a graph of road segments and intersections. Because of this, ETA predictions are amenable to graph representation learning approaches and graph neural networks in particular.

In this research, the task of arrival time estimation is described as providing an estimated travel time framework when the system is provided with inputs like starting location and a route suggested by a prior system. The challenge here is to take into account spatial information captured within the road network and temporal information, which is the evolution of traffic conditions over time. This also means that the app needs to anticipate the travel times across road segments that may not be immediately on the user track while accounting for factors like background signals, such as traffic light configurations.

The researchers demonstrated how a graph neural network-based estimator constructed with simple design principles and carefully designed loss functions can be used for ETA prediction tasks. This GNN is stable and performant in production deployment and offers substantial gains against prior production baselines that do not use the road network graph representations.

The team modelled the road networks using supersegments. These are sequences of connected road segments that follow typical traffic routes. For a given starting time, the travel time of each supersegment is learnt for different fixed time horizons into the future. The sequence of supersegments in the route of consideration is queried sequentially to increase horizons into the future. 

The whole process involves sequentially using the prediction time of a previous supersegment and determining the relevant fixed horizons for the next while interpolating between the prediction times of the fixed horizons to estimate the travel time for the next supersegment. It is a scalable process that takes into account both spatial and temporal information.

Read the full paper here.

Wrapping up

Using GNNs for traffic forecasting is an active area of research. Some of the most influential papers on spatiotemporal graph representation rely on traffic datasets. While the GNN model proposed in this study does not directly forecast future speed, it gives an idea about future traffic flow behaviour, which is useful for ETA prediction.

speed, it gives an idea about future traffic flow behaviour, which is useful for ETA prediction.