Graph Markov Network for Traffic Forecasting with Missing Data

Introduction

• Missing values from sensor failures or irregular probe-vehicle sampling degrade forecasting, while many missing-data models treat links as multivariate time series and omit network structure.Other deep-learning methods account for spatial factors but still do not incorporate the traffic network's intrinsic structure into forecasting.Source: §1 · p. 2
• Long-term-data-dependent imputation methods, including Bayesian tensor decomposition and generative adversarial imputation, may be infeasible for online forecasting on resource-limited devices.The introduction notes that long-period datasets may be unavailable and connected-vehicle or edge devices have limited storage and computational capabilities.Source: §1 · p. 2
• GMN models traffic-state transitions as a graph Markov process using Markov and graph-localization properties, while SGMN adds spectral graph convolution.The models are designed to handle missing values and forecast traffic states while incorporating spatial-temporal relationships among network links.Source: §1 · pp. 2–3
• Experiments on three real-world network-wide traffic datasets show that GMN and SGMN achieve superior prediction performance in accuracy and efficiency.The introduction reports the comparison without specifying numerical results or baselines.Source: §1 · pp. 2–3

2. Literature Review

• Classical traffic forecasting includes statistical models such as ARIMA and Kalman filtering, alongside machine-learning approaches such as support vector regression and Bayesian networks.Statistical methods use predefined structures and calibrate parameters with historical data; the passage states that emerging deep learning methods outperform classical methods.Source: §2 · p. 3

2.1. Deep learning-based traffic forecasting methods

• Deep learning traffic forecasters process spatial-temporal data as matrices, geospatial images, or graphs; matrices incompletely represent network features, while images contain noisy and blank pixels.Matrix-based methods use LSTM, bi-directional LSTM, CNN, GAN, or combinations; graph approaches incorporate graph convolutional networks [22] [23] [24], while image-based methods map roads using geospatial properties [21].Source: §2.1 · p. 3

2.2. Deep learning-based traffic forecasting with missing values

• Deep learning-based imputation methods may require long-period datasets, while RNN-based forecasting can fill missing values but cannot capture road-link interactions or expose spatial and temporal dependencies.Prior imputation approaches include probabilistic PCA, tensor decomposition, clustering, denoising stacked autoencoder, and generative adversarial imputation network; LSTM-M builds on GRU-D.Source: §2.2 · p. 4
• The proposed graph Markov network models traffic-state transitions as a graph Markov process, incorporating spatial-temporal link relationships and using network topology for accurate prediction with efficient training and testing.The study presents the model for traffic forecasting with missing values.Source: §2.2 · p. 4

3.1. Traffic Forecasting

• Traffic forecasting predicts all links’ or sensor stations’ next-step states from T-step historical data, represented as a T-by-S sequence of network-wide states.Source: §3.1 · p. 4

3.2. Graph Representations of Traffic Network

• The traffic network is modeled as an undirected graph with binary adjacency and optional self-connections; its Laplacian supports spectral analysis.The section defines combinatorial and normalized Laplacians and their eigendecomposition.Source: §3.2 · p. 5

3.3. Missing Values

• A sequence of masking vectors marks which traffic states are missing when sensors fail or probe vehicles do not traverse links.Source: §3.3 · p. 5

3.4. Traffic Forecasting with Missing Values

• Long-term-data imputation methods are unsuitable for some real-time CAV and edge-computing settings, motivating forecasting models that handle missing values directly.Large data volumes and limited device computing capacity can prevent sequential imputation and forecasting.Source: §3.4 · pp. 5–6

4.1. Properties

• The graph Markov process assumes future traffic states depend on the present, weights transitions for temporal effects, and represents localized link influence through graph structure.The authors also define a spectral version using spectral graph convolution.Source: §4.1 · pp. 6–7

4.2. Handling Missing Values in the Graph Markov Process

• Missing values are inferred from historical completed states using masks and graph Markov transitions; the method treats sufficiently old-state contributions as negligible.The derivation relies on the decay parameter γ ∈ (0, 1) and products of masking vectors that approach zero as the history length grows.Source: §4.2 · pp. 8–9

4.3. Graph Markov Network

• GMN replaces products of transition matrices with learned adjacency-masked weights for each lag, retaining the parameter count while reducing matrix multiplications.The simplification skips intermediate state transitions and reduces the total by n(n−1)/2 multiplications between S × S matrices.Source: §4.3 · p. 10
• SGMN uses learned diagonal spectral weights in place of transition-matrix products, preserving learning capacity while reducing vector multiplications.Its transitions use UΛjU^T in place of adjacency-masked weights.Source: §4.3 · p. 11

5. Experimental Results

• The proposed approach is compared with state-of-the-art traffic forecasting models capable of handling missing values.The section introduces the datasets, hyper-parameters, software, and hardware used in the experiments.Source: §5 · p. 11

5.1. Datasets

• Experiments use three real-world network-wide traffic state datasets and their traffic-network topologies.Source: §5.1 · p. 11

5.1.1. PEMS-BAY

• PEMS-BAY contains 5-minute speed readings from 325 Bay Area sensors over six months in 2017, totaling 16,941,600 observed data points.The dataset spans Jan 1st through Jun 30th, 2017.Source: §5.1.1 · p. 11

5.1.2. METR-LA

• METR-LA contains 5-minute speed readings from 207 Los Angeles County freeway sensors over four months in 2012, totaling 6,519,002 observed data points.The dataset spans Mar 1st through Jun 30th, 2012.Source: §5.1.2 · p. 12

5.1.3. INRIX-SEA

• INRIX-SEA contains 5-minute speed data for 725 Seattle road segments over 2012, totaling 76,212,000 observed data points.The network covers freeways and urban roadways; privacy policies prevent publication of the dataset.Source: §5.1.3 · p. 12

5.2. Missing Values and Data formatting

• Each dataset is represented as a sensor-by-time matrix, split into training, validation, and test sets at a 6:2:2 ratio, with speeds normalized to [0,1].Source: §5.2 · p. 12
• PEMS-BAY and METR-LA originally have 0.003% and 8.11% missing values, respectively, while INRIX-SEA has none; experiments add random zero-valued inputs at 10%, 20%, and 40% missing rates.Masking vectors are generated for the added missing values.Source: §5.2 · p. 12

5.3. Hardware and Software Environments

• Experiments used 128GB memory, an Intel Core i9-7900X CPU, an NVIDIA GTX 1080 Ti GPU, PyTorch 1.0.1, and Python 3.6.8.The proposed approach and all neural-network-based baseline models were implemented using PyTorch 1.0.1 and Python 3.6.8.Source: §5.3 · p. 12

5.4. Baseline Models •

• GRU is a recurrent neural network based on gated recurrent units and can be viewed as a simplified LSTM.Source: §5.4 · p. 12
• GRU-I uses previous-step predictions to infer missing values in the next traffic state.It completes the state by adding predicted values where the next-step mask indicates missing data.Source: §5.4 · p. 13
• GRU-D captures long-term temporal dependencies and uses masks and missing-value time intervals to exploit missing patterns.Source: §5.4 · p. 13
• LSTM is a recurrent-network variant that addresses exploding or vanishing gradients and is suitable as a traffic-forecasting model structure.Source: §5.4 · p. 13
• LSTM-I is based on LSTM and infers missing values using a process similar to GRU-I.Source: §5.4 · p. 13
• LSTM-M predicts traffic with missing data by using multi-scale temporal smoothing to infer lost values.Source: §5.4 · p. 13

5.5. Model Parameters

• GMN and SGMN variants use 6, 8, or 10 historical steps, while all RNN-based baselines use 10 input steps.The variants are denoted GMN-6/8/10 and SGMN-6/8/10, respectively.Source: §5.5 · p. 13
• The tested-data batch size is 64.Source: §5.5 · p. 13
• The decay parameter γ is set to 0.9.Source: §5.5 · p. 13

5.6. Training and Hyper-Parameters

• Training minimizes MSE between labels and predictions and updates GMN and baseline parameters with Adam [39].MSE is defined over the sample size N.Source: §5.6 · p. 13
• Training stops after 5 consecutive epochs without improvement, with minimum MSE improvement set to 0.00001.Source: §5.6 · p. 13
• All models start with a 10^-3 learning rate, reduced tenfold after 4 unimproved epochs until it reaches 10^-5.Source: §5.6 · p. 13

• All tested models are evaluated with mean absolute error (MAE), mean absolute percentage error (MAPE), and root mean square error (RMSE).Source: §5.7 · p. 14

5.8.1. Comparing with baseline models

• SGMN models are superior to baselines overall, while GMN performs well—especially on PEMS-BAY—but degrades faster as missing rates rise.SGMN performs especially well when missing rates are not very high; METR-LA already has 8.11% originally missing values.Source: Table 1 · p. 14, §5.8.1 · pp. 14–16, Table 2 · p. 15
• On PEMS-BAY, SGMN-10 has the smallest MAEs and MAPEs at all three missing rates, while GRU-I has the smallest RMSEs.On INRIX-SEA, SGMN performs better on MAE and MAPE, while GRU-I performs better on RMSE; on METR-LA, SGMN leads at 10% and 20% missing, but GRU-I, LSTM-I, and LSTM-D lead on all three metrics at 40%.Source: Table 1 · p. 14, §5.8.1 · pp. 14–15, Table 2 · p. 15

5.8.2. Analysis on Training Time

• GMN and SGMN take less training time per epoch than baselines by avoiding recurrent structure; GMN is slightly faster than SGMN, and both slow as historical steps increase.GRU-I and LSTM-I take a little longer than GRU and LSTM due to imputation, while GRU-D and LSTM-M take much longer because they use more input types.Source: Figure 3 · p. 16, §5.8.2 · p. 16

5.8.3. Analysis on Decay Rates of GMN and SGMN

• SGMN-10 MAE generally decreases as decay rate γ rises, then flattens near one, whereas GMN-10 curves are non-monotonic and errors rise near one, especially on METR-LA.SGMN-10’s METR-LA MAE rises slightly from γ=0.9 to 0.99; the authors note GMN can outperform SGMN at smaller decay rates and suggest its larger number of weight parameters as a possible reason.Source: §5.8.3 · pp. 16–17, Figure 4 · p. 17

5.8.4. Analysis on Forecasting Residuals

• Most residual distributions are approximately normal with zero means, except for GMN-10 on INRIX-SEA, indicating the proposed models capture predictive information from inputs.Across weekdays, SGMN-10 residuals are nearly alike; hourly peak effects are especially evident on PEMS-BAY, METR-LA varies little by hour, and INRIX-SEA residuals are large in the afternoon and at midnight.Source: §5.8.4 · pp. 17–18, Figure 5 · p. 18

5.8.5. Model Weight Analysis and Visualization

• Weight visualizations show influential sensors mostly near intersections, and neighboring locations are more strongly influenced by nearby traffic states.For sensor 767351, GMN-10’s displayed influence is confined to a one-hop neighborhood, while the weight matrices provide a way to measure node influence on neighbors.Source: Figure 7 · p. 20, §5.8.5 · pp. 20–21

5.8.6. Traffic Forecasting Result Visualization

• At 20% missingness, both models forecast PEMS-BAY examples well, and SGMN-10 performs better than GMN-10 on INRIX-SEA; the examples demonstrate forecasting with missing values.The METR-LA visualization includes blue spikes at the bottom that represent values originally missing from the dataset.Source: Figure 8 · p. 21, §5.8.6 · pp. 21–22

• GMN models traffic-state transitions as a graph Markov process to incorporate neighboring-link spatial relationships and temporal dependencies, while SGMN adds spectral graph convolution.The authors report superior prediction performance for both models on a real-world dataset.Source: §6 · p. 22
• Future work will strengthen the theoretical basis of the graph Markov process, examine its connection to Markov random fields, and conduct more experiments on publicly accessible datasets.The authors aim to use the connection to analyze hidden factors influencing traffic states.Source: §6 · p. 22