A spatiotemporal adaptive local search method for tracking congestion propagation in dynamic networks

Weihua Huan, Kuan Yen Tan, Xintao Liu, Shaobin Jia, Shijun Lu, Jing Zhang, Wei Huang

TL;DR

Researchers have developed STALS (Spatiotemporal Adaptive Local Search), an unsupervised method that tracks traffic congestion as it ripples through a city. By using dynamic graph learning and frequency-domain analysis, STALS identifies congestion "bottlenecks" and their propagation pathways with 97% accuracy, outperforming existing models in both speed and robustness across different data scales.

What Problem Does This Paper Address?

Traffic isn't static; it’s a "cascading effect." A single accident or a surge in commuters creates a wave of congestion that propagates asymmetrically across a network.

Existing models for tracking this spread usually fall into two traps:

  1. Static Assumptions: They rely on predefined road maps (static graphs) that don't account for how the functional relationship between road segments changes during a jam.
  2. Granularity Sensitivity: Most models struggle when data intervals change (e.g., switching from 5-minute sensor data to 1-hour GPS aggregates), leading to "distortions" in the predicted propagation path.

The authors aim to create a method that is "scale-invariant"—meaning it works regardless of how often you sample the data—and "adaptive," meaning it learns the rules of the traffic jam from the data itself rather than relying on a fixed road hierarchy.

Methods

The authors propose the Spatiotemporal Adaptive Local Search (STALS) method, which consists of two main data-driven modules:

  1. Dynamic Adjacency Matrix Learning: Instead of just looking at which roads touch, STALS builds a "functional" map of the city by fusing four features:
  2. Node Geometry (Curvature): Captures the physical complexity of the road.
  3. Node Topology (Degree): Identifies central hubs in the network.
  4. Spatial Proximity: Uses Euclidean distance to account for neighborhood effects.
  5. TSI Semantics (The Secret Sauce): They apply a Fast Fourier Transform (FFT) to the Traffic State Index (TSI). By moving from the time domain to the frequency domain, they can isolate recurring commuting rhythms from random noise, making the model robust to different time granularities.
  6. These features are fused using Entropy Weight (EW) to ensure the most informative features dominate the calculation.
  7. Local Search Module: This module treats congestion as an evolving "community" in a graph. It uses local dominance to identify "leaders" (the epicenters of congestion) and "followers" (segments affected by the spread). It then builds a hierarchical tree to track how these communities merge, split, or dissipate over time.

Datasets

The model was put through its paces using both synthetic and real-world data:

  • Synthetic Benchmarks: Four networks (Birthdeath, Expandcontract, Hide, and Mergesplit) based on the Lancichinetti-Fortunato-Radicchi (LFR) benchmark, featuring ~15,000 nodes.
  • Real-World Case Studies:
    • New York City: Uber Movement data (1-hour intervals).
  • Shanghai: Taxi trajectory data (aggregated to 5-minute intervals).
  • Urumqi: Floating car data (5-minute intervals).

Key Insights and Ideas

  • Frequency Over Time: The most striking finding is that frequency-domain features (F) are far more reliable than raw time-series data (T). FFT allows the model to "see" the underlying pulse of the city, filtering out the "noise" of individual car movements to focus on the systematic propagation of the jam.
  • Urban Morphology Matters: The paper highlights how a city's shape dictates its traffic. In polycentric cities like NYC, congestion is distributed across multiple boroughs and lasts longer due to "last-mile" connectivity gaps. In monocentric cities like Urumqi, congestion is intensely concentrated in the core but clears much faster.
  • Asymmetric Decay: Traffic jams don't disappear the same way they form. High-grade bottlenecks are likely to "self-shift" (staying in the same area) rather than slowly degrading through every intermediate level, suggesting that mitigation strategies need to be different from formation-prevention strategies.

Key Results

  • Accuracy: On benchmark datasets, STALS achieved a Normalized Mutual Information (NMI) score of 0.97, indicating nearly perfect alignment with ground-truth community structures.
  • Efficiency: The average execution time was just 27.66 seconds for a 15,000-node network, outperforming six other state-of-the-art methods.
  • Robustness: In real-world cities, the model maintained a high modularity score (average 0.78), proving it can effectively identify functional congestion clusters without needing manual labels or "ground truth" training data.

Limitations and Future Work

While powerful, the authors note a few areas for improvement:

  • External Factors: The current model relies purely on trajectory data. It does not yet integrate "multimodal" data like weather conditions, traffic accidents, or special events, which are major drivers of non-recurrent congestion.
  • Feature Fusion: The Entropy Weight method is effective but might be too simple to capture complex, non-linear relationships between road geometry and traffic flow. Future work may involve more sophisticated deep-learning-based fusion techniques.
  • Unsupervised Comparison: The study was conducted specifically within the context of community detection. Expanding the comparison to include supervised deep learning models (provided labeled data is available) could offer further validation.

Summary updated

Abstract

Traffic congestion propagation poses significant challenges to urban sustainability, disrupting spatial accessibility. The cascading effects of traffic congestion propagation can cause large-scale network disruptions. Existing studies have laid a solid foundation for characterizing the cascading effects. However, they typically rely on predefined graph structures and lack adaptability to diverse data granularities. To address these limitations, we propose a spatiotemporal adaptive local search (STALS) method, which incorporates the dynamically adaptive adjacency matrices into the local search algorithm to learn propagation rules. Specifically, the STALS is composed of two data-driven modules. One is a dynamic adjacency matrix learning module, which captures the spatiotemporal relationship from congestion graphs by fusing four node features. The other one is the local search module, which employs local dominance to identify multi-scale congestion bottlenecks and trace their propagation pathways. We test our method on the four benchmark networks with an average of 15,000 nodes. The STALS remains a Normalized Mutual Information (NMI) score at 0.97 and an average execution time of 27.66 s, outperforming six state-of-the-art methods in robustness and efficiency. We also apply the STALS to three large-scale traffic networks in New York City, the United States, Shanghai, China, and Urumqi, China. The ablation study reveals an average modularity of 0.78 across the three cities, demonstrating the spatiotemporal-scale invariance of frequency-transformed features and the spatial heterogeneity of geometric-topological features. By integrating dynamic graph learning with Geo-driven spatial analytics, STALS provides a scalable tool for congestion mitigation.
BibTeX
@inproceedings{huan2025spatiotemporal,
  author = {Weihua Huan and Kuan Yen Tan and Xintao Liu and Shaobin Jia and Shijun Lu and Jing Zhang and Wei Huang},
  title = {{A spatiotemporal adaptive local search method for tracking congestion propagation in dynamic networks}},
  booktitle = {GIScience},
  year = {2025},
  doi = {10.1080/15481603.2025.2602215},
}

Loading related content...

Figure