PaperlayerView exact revision on arXiv

Source-linked AI summary

Latent Space Model for Road Networks to Predict Time-Varying Traffic

Dingxiong Deng, Cyrus Shahabi, Ugur Demiryurek, Linhong Zhu, Rose Yu, Yan Liu

arXiv:1602.04301v3cs.SIcs.DB

TL;DR

Real-time traffic prediction must handle changing topology, temporal dynamics, and incomplete sensor data. LSM-RN learns topology- and time-dependent latent attributes and updates them online as feedback arrives. Experiments report better accuracy than time-series and baseline latent-space methods while scaling to large road networks.

  • Problem

    Real-time prediction must forecast future edge speeds from historical readings despite complex spatial dependencies, rapidly changing conditions, and missing road-network data.

  • Method

    LSM-RN embeds road-network vertices using topology-aware and time-dependent latent attributes, then incrementally updates them from temporal traffic feedback.

  • Results

    Experiments on real-world traffic data show better accuracy than ARIMA, SVR, and LSM-SN, with prediction in 4 seconds for a network of 19,986 edges.

  • Takeaways & Limitations

    Real-time feedback can adjust existing latent spaces, while on-the-fly training and prediction support traffic forecasting with small amounts of arriving data.

  • Takeaways & Limitations

    The model fixes the attribute interaction matrix B across timestamps, although vertex behavior can change over time.

Abstract

from arXiv · show

Real-time traffic prediction from high-fidelity spatiotemporal traffic sensor datasets is an important problem for intelligent transportation systems and sustainability. However, it is challenging due to the complex topological dependencies and high dynamics associated with changing road conditions. In this paper, we propose a Latent Space Model for Road Networks (LSM-RN) to address these challenges. In particular, given a series of road network snapshots, we learn the attributes of vertices in latent spaces which capture both topological and temporal properties. As these latent attributes are time-dependent, they can estimate how traffic patterns form and evolve. In addition, we present an incremental online algorithm which sequentially and adaptively learn the latent attributes from the temporal graph changes. Our framework enables real-time traffic prediction by 1) exploiting real-time sensor readings to adjust/update the existing latent spaces, and 2) training as data arrives and making predictions on-the-fly with given data. By conducting extensive experiments with a large volume of real-world traffic sensor data, we demonstrate the utility superiority of our framework for real-time traffic prediction on large road networks over competitors as well as a baseline graph-based LSM.

1. INTRODUCTION

The paper addresses real-time traffic prediction on dynamic road networks, where traffic varies across topology and time and sensor data may be incomplete. LSM-RN combines topology-aware latent representations with temporal modeling and incremental online learning for scalable forecasting.

  • Motivation: High-fidelity traffic sensing enables prediction, but road-network topology, rapid traffic changes, and missing sensor readings make the task challenging.Traffic datasets can contain missing road-segment data and failed sensor reports.
  • LSM-RN: LSM-RN embeds road-network vertices so similarity reflects both time-series traffic behavior and network topology.Its latent attributes represent traffic patterns, while graph-Laplacian constraints enforce topology similarity and support missing-data completion.
  • Online learning: The incremental online algorithm sequentially updates latent attributes from newly available temporal traffic feedback, unlike slower global learning.Predictions use prior latent attributes, then feedback from the next snapshot updates the representation.
  • Real-time forecasting: A batched combination of global and incremental learning balances forecasting accuracy with efficiency for streaming traffic data.The framework updates on smaller windows and periodically recomputes the model over a larger window.
  • Results: 4 seconds is sufficient to make a prediction for a network with 19,986 edges, while incremental learning is one order of magnitude faster than global learning.The incremental method incorporates real-time feedback information in less than 1 seconds.

2. BACKGROUND AND RELATED WORKS

Prior traffic-prediction studies address temporal modeling, spatial relationships, or selected missing-data problems, but not all challenges together. This paper explores dynamic NMF with global and topology-aware incremental algorithms for road-network traffic prediction.

  • Research gap: Existing studies separately address missing values, missing sensors, temporal patterns, or spatial relationships rather than the full combination of challenges.The related work identifies a lack of holistic treatment across these problem aspects.
  • Latent space models: Latent space learning represents graph vertices with attributes, placing vertices close together when they share latent structure and may form links or clusters.The paper situates road-network modeling within prior applications such as community detection and recommendation.
  • Modeling approach: The paper investigates dynamic Non-negative Matrix Factorization as a way to learn latent properties for traffic prediction.NMF is highlighted for interpretability and flexibility.
  • Algorithmic contribution: The proposed topology-aware incremental algorithm adaptively updates each road-network node’s latent representation under topology constraints.This differs from traditional online NMF methods that independently perform each online update.

3. PROBLEM DEFINITION

The paper models a road network as a sequence of directed, weighted snapshots built from aggregated sensor readings. The prediction problem jointly requires completing missing network data and forecasting future edge readings.

  • Road-network representation: A road network is a directed graph whose vertices represent intersections or road ends and whose edges represent directed road segments.Each edge has an associated travel speed and an adjacency-matrix representation.
  • Snapshot construction: Snapshots aggregate loop-detector readings for each road segment over fixed time intervals.For example, a 5-minute span produces 288 intervals per day.
  • Dynamic network: A dynamic road network is a sequence of snapshots whose edge weights denote time-dependent travel cost.The objective is to predict future traffic conditions from the snapshot sequence.
  • Prediction objectives: The formal problem includes completing both missing values and missing sensors in each snapshot.Missing edges can arise when road segments lack sensor readings.
  • Prediction objectives: The second objective is to predict future readings at horizon h, with h = 1 representing the next timestamp.The target is the future traffic condition of the network’s edges.

4. LATENT SPACE MODEL FOR ROAD NETWORKS (LSM-RN)

LSM-RN represents road-network vertices with latent attributes and models traffic through their interactions, topology, and temporal evolution. It supports missing-data completion and future edge-traffic prediction from learned latent states.

  • 4.1 Topology in LSM-RN: LSM-RN learns vertex latent attributes and an attribute-interaction matrix whose product approximates directed road-network traffic.The latent representation is overlapping, and B is asymmetric because the road network is directed.
  • 4.1 Topology in LSM-RN: The model uses graph topology and Laplacian regularization to exploit global similarity and reduce sparsity from uninstrumented or failed sensors.The loss is defined on observed readings, while Laplacian smoothing supports an in-filling method for the estimated network.
  • 4.2 Temporal effect of latent attributes: Time-dependent latent matrices capture evolving vertex behavior, while the interaction matrix B is held fixed across timestamps as an inherent property.The model therefore represents each vertex in a unified latent space containing spatial or temporal attributes.
  • 4.2 Temporal effect of latent attributes: A transition matrix A models how latent attributes change between successive snapshots, including periodic and incident-driven traffic evolution.The transition relation is expressed as U_t = U_t−1A, with A encoding transitions between attributes.
  • 4.3 LSM-RN Model: After learning U_t, B, and A, LSM-RN completes missing values and sensors and predicts edge traffic h future time spans ahead.The framework is organized around latent-attribute discovery, temporal traffic-pattern modeling, and future prediction.

5. INFERENCE OF LSM-RN

The paper combines global multiplicative inference with an incremental algorithm that updates latent spaces from streaming graph changes. The resulting online procedure uses feedback, topology-aware propagation, and a sliding-window strategy for real-time forecasting.

  • 5.1 Global inference: Global inference has worst-case per-iteration complexity O(T(nk^2+n^2k)), although sparse matrices reduce the practical cost.The dominant operations multiply n×n and n×k matrices and n×k and k×k matrices.
  • 5.1 Global inference: Global learning jointly and cyclically updates U_t, B, and A across all graph snapshots until convergence.The algorithm initializes the matrices, repeatedly updates each U_t, then updates B and A.
  • 5.2 Incremental inference: The incremental algorithm starts from a globally learned U_1 and updates each later latent space from U_t−1 and observed graph changes before learning A.It is designed to avoid recomputing all snapshots while preserving temporal information.
  • 5.2 Topology-aware incremental update: The update order follows reverse topology so dependent vertices are adjusted after the vertices they depend on, with strongly connected components handling cycles.This ordering is intended to improve convergence speed in the cyclic road network.
  • 5.2 Topology-aware incremental update: Incremental updates identify inaccurate vertices from feedback, adjust their latent attributes, and propagate changes to neighboring vertices.Candidate vertices are selected when prediction error exceeds δ, and updates continue while candidates remain and convergence has not been reached.
  • 5.3 Real-time forecasting: The real-time setting applies incremental learning at each timestamp and global learning only at the end of a sliding time window.This balances immediate predictions from streaming data against the computational cost of global inference.

6. EXPERIMENT

Experiments use large-scale Los Angeles traffic-sensor data and compare global, incremental, naive, and conventional prediction methods across completion and forecasting tasks.

  • Dataset: The dataset contains 15,000 sensors covering approximately 3,420 miles, with speed, volume, and occupancy sampled once per sensor per minute.Experiments use March and April 2014 data containing more than 60 million readings.
  • Dataset: The SMALL and LARGE road-network subgraphs contain 5,984 vertices and 12,538 edges, and 8,242 vertices and 19,986 edges, respectively.Sensor readings were mapped to network edges, producing two months of network snapshots.
  • Methods and baselines: LSM-RN-All denotes global learning, whereas LSM-RN-Inc denotes incremental learning.The evaluation also includes LSM-RN-Naive and conventional time-series baselines such as ARIMA and SVR.
  • Tasks: The study evaluates missing-value completion and edge traffic prediction, including one-step, multi-step, and online batch-window settings.Online prediction uses real observations as feedback after each prediction.
  • Evaluation protocol: Experiments vary snapshot count, snapshot span, and model parameters k, λ, and γ, using MAPE and RMSE for accuracy.ARIMA and SVR are trained on March data, while completion and prediction tasks use April data.

6.3 Comparison for missing value completion

LSM-RN methods achieve the strongest missing-value completion and edge-prediction accuracy, while performance worsens under more dynamic rush-hour and multi-step conditions.

  • Missing-value completion: LSM-RN-All and LSM-RN-Inc achieve much lower missing-value completion errors than the other methods on SMALL.LSM-RN-All performs better than LSM-RN-Inc, while both exploit spatial and temporal relationships.
  • Missing-value completion: Using both spatial and temporal properties yields a large gain over using only spatial properties for completion.This comparison distinguishes the LSM-RN methods from LSM-RN-One and KNN.
  • Missing-value completion: Completion performance is better during non-rush hours than rush hours because rush-hour traffic is more dynamic and its patterns and transitions change frequently.The same overall trends appear on the LARGE network.
  • One-step prediction: LSM-RN-All and LSM-RN-Inc achieve the best one-step prediction results, with LSM-RN-All slightly better than LSM-RN-Inc.ARIMA and SVR perform worse without imputation, while LSM-RN-Naive does not match the two proposed methods.
  • Multi-step prediction: For 30-minute multi-step prediction, LSM-RN-All and LSM-RN-Inc still outperform other methods, but their margin over baselines is smaller.Using predicted values recursively causes error accumulation in future predictions, with similar trends on LARGE.

6.5 Scalability of different methods

The incremental method provides the strongest scalability profile, combining on-the-fly learning with substantially lower running time than alternative approaches.

  • Running time: LSM-RN-Inc learns time-dependent latent attributes and predicts all network edges in under 500 milliseconds, and under five seconds on LARGE.The latter runtime is considered acceptable because practical snapshot spans are at least five minutes.
  • Running time: LSM-RN-Inc is the most efficient approach, averaging two times faster than LSM-RN-Naive and one order of magnitude faster than LSM-RN-All.Its efficiency comes from conditionally updating vertices in a small network portion rather than recomputing broadly.
  • Running time: LSM-RN-All and LSM-RN-Naive require substantially longer running times than LSM-RN-Inc, while LSM-RN-All is faster than LSM-RN-Naive.The difference reflects repeated global learning in the naive approach.
  • Running time: Unlike ARIMA and SVR, the LSM-RN methods train and predict on-the-fly without requiring extra training data.Table 3 defines training for LSM-RN methods as learning latent attributes while predicting the whole network with given data.
  • Convergence: LSM-RN-All tends to converge near 20 iterations on both SMALL and LARGE.The convergence criterion is the objective value in Equation 4.

6.6 Comparison for Real-time Forecasting

In online forecasting, LSM-RN-Inc matches full-batch accuracy while using real-time feedback to outperform alternatives and maintain a favorable efficiency profile.

  • Online accuracy: LSM-RN-Inc achieves accuracy comparable to LSM-RN-All in the online setting.The incremental method adjusts latent attributes using real-time feedback.
  • Online accuracy: LSM-RN-Inc performs significantly better than Old and LSM-RN-Naive, which ignore feedback or previous snapshots, respectively.The comparison is also observed on LARGE.
  • Online accuracy: Previous-window latent attributes are more reliable for near-future traffic, but can become less suitable for multi-step prediction because of error accumulation.Old performs better initially, whereas LSM-RN-Naive surpasses it at later timestamps.
  • Online efficiency: LSM-RN-Inc incorporates real-time feedback in under 1 second, while LSM-RN-Naive and LSM-RN-All take much longer.Its conditional latent-attribute updates support the reported efficiency advantage.
  • Conclusion: LSM-RN-Inc achieves a trade-off between prediction accuracy and efficiency suitable for real-time traffic prediction applications.This is the authors’ stated conclusion for the online forecasting experiments.

6.7 Varying parameters of our methods

The experiments examine how snapshot history, temporal span, latent-space size, and graph regularization affect prediction accuracy and runtime. They identify practical parameter ranges that balance accuracy with computational cost.

  • Experimental setup: The parameter experiments are reported on SMALL because parameter effects are described as weakly correlated with road-network size.The section varies model parameters using results shown in Figures 14–16.
  • Effect of varying T: At least 6 snapshots improve prediction, while performance stabilizes at T ≥6 and additional history increases running time.The recommended trade-off is to use 6–12 snapshots.
  • Effect of varying span: Increasing the time gap between snapshots reduces prediction performance because learned transitions may not apply when traffic evolves non-smoothly.Smaller spans are preferred for high-resolution sensor data, while span does not affect either algorithm's running time.
  • Effect of varying k and λ: Increasing the number of latent attributes improves results until performance stabilizes when k ≥20.The findings indicate that a low-rank latent representation can capture the traffic attributes; runtime rises with k when k ≤30.
  • Effect of varying k and λ: The graph Laplacian regularization parameter λ affects LSM-RN-All more than LSM-RN-Inc.LSM-RN-All jointly learns time-dependent latent attributes, making λ more influential for that algorithm.

7. CONCLUSION

The conclusion presents LSM-RN as a time-dependent latent-space approach for real-time traffic prediction on road networks. Its incremental learning algorithm supports large-network prediction and incorporates real-time feedback efficiently.

  • Conclusion: LSM-RN assigns vertices latent attributes that capture both topological and temporal road-network properties.The model uses time-dependent weights to estimate traffic patterns and their evolution.
  • Conclusion: The incremental online learning algorithm enables real-time traffic prediction for large road networks.The conclusion reports effectiveness, flexibility, and scalability across extensive experiments.
  • Conclusion: The incremental learning algorithm is orders of magnitude faster than global learning and takes less than 1 seconds to incorporate real-time feedback for a large road network.
  • Future work: Future work targets ride-sharing and vehicle-routing applications and incorporation of GPS and incident data.These extensions are intended to support more accurate time-dependent traffic prediction and navigation.

9. APPENDIX

The appendix details derivative calculations, update-rule derivations, RMSE-based experiments, and missing-data effects on conventional time-series predictors. It reports that missing data increasingly harms prediction and that ARIMA is particularly sensitive to incomplete datasets.

  • Derivative and update-rule derivations: The appendix derives derivatives of L with respect to U_t and uses Lagrangian multipliers and KKT conditions to obtain update rules for A and B.
  • Derivative and update-rule derivations: The derivation introduces Lagrangian multipliers φ and ω and applies KKT conditions to calculate updates for B_kk and A_kk.
  • RMSE experiments: RMSE measures how closely predictions match true observations in the appendix experiments.The reported experiments include missing-value completion, one-step prediction, six-step prediction, and online prediction.
  • Effect of missing data: Prediction error for ARIMA and SVR increases as the amount of training noise rises.The experiment evaluates missing-data effects during training for ARIMA and SVR.
  • Effect of missing data: ARIMA performs better than SVR when the missing ratio is below 10%, but ARIMA is less robust as missingness increases.The passage characterizes ARIMA as a candidate for accurate traffic conditions with complete data.
  • Effect of missing data: ARIMA is sensitive to missing values during both training and prediction, producing poor performance with incomplete datasets.
Loading 1602.04301v3…