Ising-Traffic: Using Ising Machine Learning to Predict Traffic Congestion under Uncertainty

Zhenyu Pan, Anshujit Sharma, Jerry Yao-Chieh Hu, Zhuo Liu, Ang Li, Han Liu, Michael C. Huang, Tong Geng

Presented at AAAI-23, Ising-Traffic introduces a paradigm shift in urban traffic management. By leveraging physics-inspired Ising models and specialized "Ising machines," the researchers have developed a framework that redefines traffic prediction as an energy-minimization problem, effectively bypassing the traditional trade-offs between algorithmic complexity and computational speed.

The Challenge: Uncertainty and Latency

Predicting urban traffic is notoriously difficult due to inherent uncertainty. Real-world sensor data is frequently incomplete due to hardware failures, and "external shocks"—such as sudden accidents or extreme weather—can render historical patterns obsolete.

Current State-of-the-Art (SOTA) solutions, primarily Deep Learning models like Graph Neural Networks (GNNs) and Recurrent Neural Networks (RNNs), face a fundamental dilemma: higher accuracy requires increased model complexity, which in turn leads to significant prediction latency. As Moore’s Law slows, traditional hardware (CPUs/GPUs) struggles to provide the real-time performance necessary for massive, interconnected urban road networks. Ising-Traffic aims to deliver both high accuracy and ultra-low latency simultaneously.

The Ising-Traffic Framework

The proposed framework utilizes a dual-model architecture designed to optimize both spatial and temporal correlations through Ising Machine Learning (IML).

The Ising-Traffic framework maps traffic networks to Ising models and employs a dual-model learning approach for data imputation and prediction.
  1. Reconstruct-Ising (Spatial Correlation): This model handles data imputation, filling in missing sensor data by mapping the traffic network to an Ising model where road segments are treated like magnetic spins (Congested vs. Non-Congested). This is mapped onto a specialized CMOS-compatible Ising machine (BRIM), which can find the system's "ground state" (the most likely traffic configuration) in under 100 nanoseconds.
  2. Predict-Ising (Temporal Correlation): This model predicts future states based on historical data. While it runs on traditional processors, it is mathematically formulated to be extremely lightweight, requiring only 1.8% of the arithmetic operations used by traditional SOTA models.

Key Innovations

  • Inverse Ising Learning: A process to learn coupling parameters (how road segments influence one another) from historical data.
  • Geographical Embedding: Incorporates physical distance directly into the model's logic.
  • Dynamic Message Passing: Uses a "Neighboring Influence Matrix" as an attention mechanism to propagate congestion effects through the network.
  • Robust Learning: The model is trained with varying noise levels to ensure stability under real-world data uncertainty.

Key Results and Performance

The framework was evaluated on four large-scale datasets: Q-traffic (Beijing), PEMS4 (San Francisco), PEMS8 (San Bernardino), and PEMS-BAY (Bay Area).

Ising-Traffic breaks the Pareto frontier by achieving higher accuracy with orders of magnitude fewer operations.

Ising-Traffic effectively "breaks" the Pareto frontier of current traffic prediction solutions. Key performance metrics include:

  • Speed: An average 98× speedup over SOTA methods. The reconstruction phase on an Ising machine is approximately $10^6$ times faster than traditional imputation.
  • Accuracy: A 5% accuracy improvement on average. Remarkably, even with 50% of data missing, the framework maintained over 99% prediction accuracy.
  • Efficiency: Predict-Ising reaches peak accuracy in just 10 epochs, compared to the 100+ epochs required by traditional baselines.

Conclusion and Future Work

By treating a traffic network like a physical system of spins, Ising-Traffic demonstrates that physics-inspired computing can solve complex urban challenges more efficiently than pure deep learning. While the most significant speedups currently require specialized Ising hardware, the framework's efficiency on standard CPUs already outperforms heavy GNNs. Future research will look toward mapping temporal analysis directly to Ising hardware and extending the binary (Congested/Non-Congested) model to continuous speed values.

Summary updated

Abstract

This paper addresses the challenges in accurate and real-time traffic congestion prediction under uncertainty by proposing Ising-Traffic, a dual-model Ising-based traffic prediction framework that delivers higher accuracy and lower latency than SOTA solutions. While traditional solutions face the dilemma from the trade-off between algorithm complexity and computational efficiency, our Ising-based method breaks away from the trade-off leveraging the Ising model's strong expressivity and the Ising machine's strong computation power. In particular, Ising-Traffic formulates traffic prediction under uncertainty into two Ising models: Reconstruct-Ising and Predict-Ising. Reconstruct-Ising is mapped onto modern Ising machines and handles uncertainty in traffic accurately with negligible latency and energy consumption, while Predict-Ising is mapped onto traditional processors and predicts future congestion precisely with only at most 1.8% computational demands of existing solutions. Our evaluation shows Ising-Traffic delivers on average 98X speedups and 5% accuracy improvement over SOTA.
BibTeX
@inproceedings{pan2023ising,
  author = {Zhenyu Pan and Anshujit Sharma and Jerry Yao-Chieh Hu and Zhuo Liu and Ang Li and Han Liu and Michael C. Huang and Tong Geng},
  title = {{Ising-Traffic: Using Ising Machine Learning to Predict Traffic Congestion under Uncertainty}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i8.26121},
}
Figure