Unboxing the graph: Towards interpretable graph neural networks for transport prediction through neural relational inference

Mathias Niemann Tygesen, Francisco C. Pereira, Filipe Rodrigues

TL;DR

This paper introduces a method to automatically learn the underlying "hidden" graph structure of transport systems using Neural Relational Inference (NRI). By replacing static, human-defined heuristics with a dynamic, learnable adjacency matrix, the authors achieve state-of-the-art results in taxi demand and traffic speed prediction while gaining unique, interpretable insights into how urban zones interact.

What Problem Does This Paper Address?

Predicting transport supply and demand (like where taxis are needed or how fast traffic is moving) is notoriously difficult because spatial dependencies are "non-Euclidean." For example, a residential neighborhood and a business district might be miles apart but highly dependent on each other during morning rush hour.

Currently, researchers use Graph Neural Networks (GNNs) to model these relationships. However, GNNs usually require a predefined "graph" (a map of which nodes connect to which). To build these graphs, researchers rely on heuristics—like connecting zones that are physically close or have similar historical patterns.

The problem? These heuristic graphs are static (they don't change over time) and often biased (they might miss true correlations). This paper tackles the "graph inference" problem: instead of telling the model how zones are connected, can the model learn the optimal connections directly from the data?

Methods

The authors adapt a framework called Neural Relational Inference (NRI), which treats the graph structure as a "latent variable" in a Variational Auto-Encoder (VAE).

  1. The Encoder: Takes historical transport data and global features (like weather or time of day) and predicts a distribution over possible edges between nodes. It uses a "Gumbel-Softmax" trick to allow the model to pick discrete edges while still being able to train via backpropagation.
  2. The Latent Space: This is where the "unboxing" happens. The model samples a graph that represents the most likely dependencies for the current time step.
  3. The Decoder: A recurrent GNN (using GRU cells) that uses the sampled graph to predict future states.
  4. Bayesian Priors: Unlike previous black-box approaches, this method allows researchers to inject domain knowledge by placing "priors" on the graph (e.g., a "local prior" that suggests nearby zones are more likely to be connected, but allows the model to override this if the data suggests otherwise).

Datasets

The model was evaluated on two major open-source benchmarks:

  • NYC Yellow Taxi Data (2019): 84 million trips aggregated into 66 Manhattan zones. The task is to predict hourly pickups and dropoffs.
  • PEMS (Performance Measurement System): Traffic speed data from 325 loop sensors in the California Bay Area. The task is to predict speeds 15, 30, and 60 minutes into the future.

Key Insights and Ideas

  • Dynamic Connectivity: The model learns that relationships change. In NYC, the "edge probability" (the strength of connections) is high during weekdays but dips significantly on weekends. The model "knows" that weekday rush hour patterns are more predictable and impactful for the loss function.
  • Information Routing: In the NYC dataset, the model learns to send the most "messages" (information) to high-activity zones. Because these zones have the biggest impact on the overall error (NLL loss), the model prioritizes getting their predictions right by gathering more data from surrounding nodes.
  • Congestion Awareness: In traffic speed prediction, the model exhibits "congestion-seeking" behavior. When a sensor detects a traffic jam, the model automatically starts looking at sensors further away to understand how the congestion is spreading—a behavior that static, distance-based graphs cannot capture.
  • Interpretability: By visualizing the learned adjacency matrices, the authors show that the model isn't just a black box; it's effectively "mapping" the functional relationships of the city.

Key Results

The NRI-based models consistently outperformed traditional heuristic-based GNNs and standard baselines:

  • NYC Taxi: The NRI model with a "DTW" (Dynamic Time Warping) prior achieved the best overall performance, reducing Mean Absolute Error (MAE) to 17.65, compared to 19.41 for a fully connected graph and 22.80 for a standard local-neighbor graph.
  • PEMS Traffic: The NRI model outperformed the well-known DCRNN (Diffusion Convolutional Recurrent Neural Network). For 60-minute predictions, NRI achieved an MAE of 1.78 vs. DCRNN’s 2.07.
  • Sparsity: The model achieved these results using much sparser graphs than "full" models, proving that "more connections" isn't always better—smarter connections are.

Limitations and Future Work

  • Pre-training Requirements: For the NYC dataset, the authors found that the encoder was initially too noisy. They had to "pre-train" the encoder for 30 epochs using only the KL divergence part of the loss to get it to converge properly.
  • Computational Complexity: Inferring a graph for every time step is more computationally expensive than using a fixed one, though the authors argue the performance gain and interpretability are worth the trade-off.
  • Meta-Learning: A promising future direction mentioned is using this for "transfer learning." Since the model isn't locked to a specific number of nodes, a model trained on a data-rich city (like NYC) could potentially be fine-tuned for a city with very few sensors.

Summary updated

Abstract

Predicting the supply and demand of transport systems is vital for efficient traffic management, control, optimization, and planning. For example, predicting where from/to and when people intend to travel by taxi can support fleet managers in distributing resources; better predictions of traffic speeds/congestion allows for pro-active control measures or for users to better choose their paths. Making spatio-temporal predictions is known to be a hard task, but recently Graph Neural Networks (GNNs) have been widely applied on non-Euclidean spatial data. However, most GNN models require a predefined graph, and so far, researchers rely on heuristics to generate this graph for the model to use. In this paper, we use Neural Relational Inference to learn the optimal graph for the model. Our approach has several advantages: 1) a Variational Auto Encoder structure allows for the graph to be dynamically determined by the data, potentially changing through time; 2) the encoder structure allows the use of external data in the generation of the graph; 3) it is possible to place Bayesian priors on the generated graphs to encode domain knowledge. We conduct experiments on two datasets, namely the NYC Yellow Taxi and the PEMS-BAY road traffic datasets. In both datasets, we outperform benchmarks and show performance comparable to state-of-the-art. Furthermore, we do an in-depth analysis of the learned graphs, providing insights on what kinds of connections GNNs use for spatio-temporal predictions in the transport domain and how these connections can help interpretability.
BibTeX
@inproceedings{tygesen2022unboxing,
  author = {Mathias Niemann Tygesen and Francisco C. Pereira and Filipe Rodrigues},
  title = {{Unboxing the graph: Towards interpretable graph neural networks for transport prediction through neural relational inference}},
  booktitle = {Transportation},
  year = {2022},
  doi = {10.1016/j.trc.2022.103946},
}
Figure