Introduction
Modern navigation systems often struggle with "black holes" in traffic data—side streets and minor residential roads that lack physical sensors. While major highways are well-monitored, the vast majority of urban road networks remain invisible to real-time routing algorithms. This paper, presented at AAAI-20, proposes the Spatial Factorization Machine (SFM) to infer traffic conditions on these un-monitored segments by leveraging spatial relationships with monitored roads.
The Challenge of Un-Monitored Roads
Urban traffic monitoring typically relies on fixed sensors like loop detectors or cameras, which are expensive to install and maintain. Consequently, they are restricted to major arteries. When congestion occurs on a main road, drivers often divert to secondary streets. Without data on these segments, routing apps may inadvertently direct traffic into secondary bottlenecks. The goal is to predict the "congested" or "not congested" status of these invisible segments using existing network data.
Methodology: Spatial Factorization Machines
The authors build upon Factorization Machines (FMs), which are effective at modeling feature interactions in sparse datasets. However, standard FMs treat features as independent, ignoring the inherent spatial correlation in traffic data. The SFM introduces several key innovations:
- Spatial Awareness: It incorporates distance and Laplacian matrices into the training process, weighting interactions based on physical proximity.
- Asymmetric Modeling: It accounts for real-world constraints like one-way streets, ensuring the spatial logic reflects actual driving patterns.
- Feature Coupling: It structures road segment information into a comprehensive feature vector that captures network topology.
As shown in the figure above, the model encodes not just the road segment itself, but also its relationship to adjacent nodes and its directional constraints. This allows the model to learn latent vectors that represent the traffic characteristics of roads even if they were not present in the training set.
Experimental Evaluation
The model was evaluated using taxi movement data from the Australian Traffic Management Centre, covering the Greater Sydney region from April to May 2018. The researchers binarized travel times into "congested" (above the 75th percentile) and "not congested" labels. To test predictive power, 20% of the roads were randomly designated as "un-monitored" and removed from the training data.
Results and Discussion
The SFM was compared against standard Factorization Machines (FM), Field-aware Factorization Machines (FFM), and Coupled Factorization Machines (CFM).
The SFM consistently outperformed all baselines. For instance, in the April dataset with $k=10$, SFM achieved an accuracy of 0.946, significantly higher than the 0.852 achieved by the standard FM. The reported p-values (e.g., $1 \times 10^{-4}$ against CFM) confirm that the performance gains from integrating spatial information are statistically significant and not due to random chance.
Conclusion
By treating physical distance as a structural guide rather than just another feature, the SFM effectively addresses data sparsity in urban traffic networks. While currently a binary classification model, future iterations could expand to exact travel time regression and incorporate more complex temporal dynamics. The authors also suggest that this spatial logic could be applied to other domains, such as location-based recommendations where physical distance is a critical factor.
Summary updated