Graph Convolutional Networks for traffic anomaly

Yue Hu, Ao Qu, Dan WorkarXiv 2020 · arXiv

Abstract

Detecting city-wide traffic anomalies is a complex task due to the high dimensionality and extreme sparsity of Origin-Destination (OD) travel data. This paper presents Con-GAE (Context-augmented Graph Autoencoder), a deep learning framework designed to identify large-scale traffic disruptions. By integrating Graph Convolutional Networks (GCNs) with temporal context embeddings, the model learns to distinguish between routine congestion and genuine anomalies. Evaluated on real-world datasets from Nashville, NYC, and Chicago, Con-GAE demonstrates significant improvements in detection accuracy over state-of-the-art baselines.

Introduction

Urban management relies heavily on the ability to detect large-scale traffic events, such as accidents, protests, or major public gatherings. However, data provided by taxi fleets or services like Uber Movement—represented as travel times between zones (Origin-Destination data)—presents three major challenges:

  1. Extreme Sparsity: Many zone pairs lack recorded trips during specific time intervals.
  2. High Dimensionality: Large cities with hundreds of zones create massive connectivity matrices.
  3. Spatio-Temporal Complexity: Traffic patterns are inherently periodic; a delay that is normal during Monday rush hour may be an anomaly on a Sunday morning.
Representation of urban traffic as a sparse Origin-Destination (OD) matrix and its corresponding directed graph.

Existing methods often fail to capture the global state of a city's traffic or ignore the daily and weekly cycles essential for accurate anomaly detection.

The Con-GAE Framework

The authors propose Con-GAE, which treats traffic data as a sequence of directed, weighted graphs. The framework utilizes a graph autoencoder architecture to learn "normal" urban states and flag deviations.

Weighted GraphSAGE Encoder

Unlike standard Graph Neural Networks that treat connections as binary, Con-GAE employs a modified GraphSAGE encoder with a weighted mean aggregator. This allows the model to incorporate actual travel times directly into node embeddings, preserving the intensity of traffic flow between zones.

Context-Augmented Embeddings

To address temporal periodicity, the model learns specific "context" vectors representing the hour of the day and the day of the week. These temporal embeddings are concatenated with spatial node embeddings to provide the model with the necessary situational awareness (e.g., "it is currently 8:00 AM on a Tuesday").

The Con-GAE encoder architecture, illustrating the integration of node embeddings via GCN and temporal context embeddings.

Global Graph Reconstruction

Rather than focusing on individual nodes, Con-GAE aggregates all node and context information into a single low-dimensional vector representing the entire city's state. The decoder then attempts to reconstruct the original OD matrix. High reconstruction error—the difference between predicted and actual travel times—serves as the primary indicator of a traffic anomaly.

Experimental Evaluation

The study utilized three real-world datasets: Uber Movement data for Nashville, TN, and taxi trip records for New York City and Chicago. Due to the scarcity of labeled ground-truth anomalies, the authors benchmarked the model using synthetic spatial and temporal perturbations.

Key Results

  • Performance Gains: Con-GAE achieved an AUC improvement of 0.1 to 0.4 over baselines like Robust Tensor Recovery (RTC) and standard LSTMs, maintaining an AUC above 0.9 in spatial anomaly detection for Uber and Chicago data.
  • Real-World Case Study: In a qualitative analysis of Nashville during the 2019 NFL Draft, the model successfully identified the highest anomaly scores during the event dates (April 25-27). It also discovered unmapped nightly road maintenance on the I-24 freeway.
  • The Importance of Asymmetry: Traffic flow is rarely identical in both directions (A to B vs. B to A). By using a parameterized MLP for edge prediction, Con-GAE effectively preserved the directed nature of urban movement, reducing bias compared to symmetric predictors.

Conclusion

Con-GAE provides a robust solution for city-scale traffic monitoring by treating the urban environment as a dynamic, weighted graph. By explicitly modeling temporal context and global graph states, the framework overcomes the limitations of sparsity and high dimensionality inherent in OD data. Future work will focus on scaling the model to thousands of zones and exploring dynamic topologies where nodes and edges may appear or disappear over time.

Summary updated

BibTeX
@misc{hu2020graph,
  author = {Yue Hu and Ao Qu and Dan Work},
  title = {{Graph Convolutional Networks for traffic anomaly}},
  year = {2020},
  eprint = {2012.13637},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.13637},
}
Figure