Spatio-Temporal Partial Sensing Forecast for Long-term Traffic (2024)

2.1. Problem Definitions

Definition 1: Road Topology and Traffic Flow Rates.Consider a road system, and let $N$ be a set of chosen locations where traffic statistics are of interest. Let $n=|N|$. The road topology of these locations is represented as a graph $\mathcal{G}=(N,A)$. $A=[A_{i,j},i,j\in N]\in\mathbb{R}^{n\times n}$ is an adjacency matrix. $A_{i,j}=1$ indicates that there is a road between location $i$ and location $j$; otherwise $A_{i,j}=0$. A traffic flow consists of all the vehicles that pass a location in $N$; the flow rate is defined as the number of vehicles passing through the location during a preset time interval. It is a discrete function of time if we partition the time into a series of time intervals of a certain length, e.g., 5 min. For simplicity, we normalize each time interval as one unit of time. Let $M$ be a subset of locations, i.e., $M\subseteq N$, and $T$ be a series of time intervals. As an example, $T$ could be $\{t-l+1,...,t-1,t\}$ of $l$ intervals, where $t$ is the current time. The traffic matrix over locations $M$ and times $T$ is defined as $\mathcal{X}_{M,T}=[\mathcal{X}_{i,j},i\in M,j\in T]$, where $\mathcal{X}_{i,j}$ is the flow rate at location $i$ during time $j$. Further denote the rate vector at location $i$ as $\mathcal{X}_{i,T}=[\mathcal{X}_{i,j},j\in T]$. Hence, $\mathcal{X}_{M,T}=[\mathcal{X}_{i,T},i\in M]$.

Definition 2: Problem of Full-Sensing Traffic Forecast.Suppose all the locations in $N$ are equipped with permanent sensors to continuously measure the flow rates. The problem is to forecast a future traffic matrix $\mathcal{X}_{N,T^{\prime}}$ on all locations in $N$, based on a past traffic matrix $\mathcal{X}_{N,T}$ that has just been measured by the sensors, where $T^{\prime}=\{t+1,...,t+l^{\prime}\}$, $T=\{t-l+1,...,t-1,t\}$, and $t$ is the current time. It is called full-sensing traffic forecast because all locations under forecast are fully equipped with sensors to provide traffic information of recent past. In most work (fang2021spatial, ; song2020spatial, ; jin2022automated, ; shao2022spatial, ; jia2020residual, ; ji2022stden, ), both $l$ and $l^{\prime}$ are set to 1 hour for short-term forecast. Note that $l$ should not be too large to avoid excessively large models and computation costs that come with them. Moreover, research has shown that too large $l$ may actually degrade forecast accuracy (zeng2023transformers, ). For long-term forecast, $l^{\prime}$ is set much larger than $l$.

Definition 3: Problem of Partial-Sensing Traffic Forecast.Suppose only a subset $M$ of locations are equipped with permanent sensors to continuously measure their flow rates. The subset of locations without permanent sensors is denoted as $M^{\prime}=N-M$. Let $m=|M|$ and $m^{\prime}=|M^{\prime}|$. The partial adjacency matrix is $A_{M,M^{\prime}}=[A_{i,j},i\in M,j\in M^{\prime}]\in\mathbb{R}^{m\times m^{$. The problem is to forecast a future traffic matrix $\mathcal{X}_{M^{\prime},T^{\prime}}$ over the locations without sensors, based on a recent traffic matrix $\mathcal{X}_{M,T}$ that has been just measured at the locations with sensors, where $T^{\prime}=\{t+1,...,t+l^{\prime}\}$, $T=\{t-l+1,...,t-1,t\}$, and $t$ is the current time. It is called partial-sensing traffic forecast because locations in $N$ are partially equipped with sensors; for long-term forecast, $l^{\prime}>>l$. This problem is the focus of our work.

In practice, one may want to forecast both $\mathcal{X}_{M^{\prime},T^{\prime}}$ and $\mathcal{X}_{M,T^{\prime}}$ from $\mathcal{X}_{M,T}$. In this paper, we only consider $\mathcal{X}_{M^{\prime},T^{\prime}}$ because predicting $\mathcal{X}_{M,T^{\prime}}$ from $\mathcal{X}_{M,T}$ is essentially the full-sensing prediction problem, which has been thoroughly studied.

2.2. Inference vs Training

The problem of partial sensing traffic forecast is illustrated by the left plot of Fig.2. After a forecast model is trained and deployed, the sensors at the locations in $M$ will measure flow rates $\mathcal{X}_{M,T}$, which will be used as input to the model to inference (forecast) future rates of the locations in $M^{\prime}$, i.e., $\mathcal{X}_{M^{\prime},T^{\prime}}$. Hence, when we use the model for forecasting, the only available data is $\mathcal{X}_{M,T}$, which is shown in blue.

However, to train such a model (before its actual deployment), as illustrated in the middle plot, we will need the ground truth of $\mathcal{X}_{M^{\prime},T^{\prime}}$ in the training data, which is shown in gray. We assume that mobile sensors are deployed at the locations in $M^{\prime}$ for a period of time to collect the training data. This is reasonable because mobile sensors can be re-depolyed at different road systems for data collection, offering a lower overall cost than implementing permanent sensors at all locations of all road systems that need traffic forecast.

With mobile sensors deployed to collect $\mathcal{X}_{M^{\prime},T^{\prime}}$, we may naturally use them to collect $\mathcal{X}_{M^{\prime},T}$ as well. The permanent sensors at $M$ will collect $\mathcal{X}_{M,T^{\prime}}$. So, the training data will contain $\mathcal{X}_{M,T}$, $\mathcal{X}_{M^{\prime},T}$, $\mathcal{X}_{M,T^{\prime}}$ and $\mathcal{X}_{M^{\prime},T^{\prime}}$, as illustrated in gray in the third plot. While the input to the model is $\mathcal{X}_{M,T}$ and the output $\mathcal{X}_{M^{\prime},T^{\prime}}$, we should still fully utilize the information of $\mathcal{X}_{M^{\prime},T}$ and $\mathcal{X}_{M,T^{\prime}}$, which is available in the training data, to build an accurate model.

2.3. Embeddings

Embeddings are the common technique to enhance feature expression. We adopt the embedding setting in (shao2022spatial, ; liu2023spatio, ), where the time-of-day embedding and the day-of-week embedding capture the temporal information, and node embedding captures the spatial property of locations. We use $E^{tod}\in\mathbb{R}^{n\times d}$, $E^{dow}\in\mathbb{R}^{n\times d}$, and $E^{v}\in\mathbb{R}^{n\times d}$ to denote them respectively, where $d$ is the embedding dimension. A day is modelled as $N^{tod}=288$ discrete units of 5 minutes each. A week has $N^{tod}=7$ days. The time-of-day is $i/N^{tod}$ for the $i$th unit in the day, and the day-of-week is $i/N^{dow}$ for the $i$th day in the week. Trainable vectors $B_{i}^{tod}\in\mathbb{R}^{d}$, $i\in[0,N^{tod})$, and $B_{i}^{dow}\in\mathbb{R}^{d}$, $i\in[0,N^{tod})$, are the time-of-day embedding bank and the day-of-week bank. In practice, for the input flow rate data $\mathcal{X}_{N,T}\in\mathbb{R}^{{n}\times l}$, $T=\{t-l+1,...,t-1,t\}$, we only consider the time feature of flow rate data $\mathcal{X}_{N,t-l+1}\in\mathbb{R}^{n}$ at $t-l+1$, yielding $E^{tod}\in\mathbb{R}^{n\times d}$, $E^{dow}\in\mathbb{R}^{n\times d}$. For the node embedding, given any location $i\in N$, the trainable node embedding bank is $B_{i}^{v}\in\mathbb{R}^{d}$. For the flow rate data $\mathcal{X}_{N,T}$, we obtain $E^{v}\in\mathbb{R}^{n\times d}$ from node embedding bank $B_{i}^{v}$ over $n$ total locations. In the following, we will use $M$, $M^{\prime}$, $N$ as the subscript of the embedding bank $B$ and the embedding $E$ to represent the locations of interest.

In addition to the above, this paper will introduce a new rank-based node embedding.

3.1. Rank-based Node Embedding

First, consider irregular traffic patterns. As shown in Fig.1, location 121 (top blue curve) at a highway from dataset PEMS08 demonstrates a regular traffic pattern from the day time high on 08/19 to the deep night low and back to the day time high on 08/20, and so on. These daily (or weekly) traffic patterns can be captured by the temporal embeddings, $E^{tod}$ (time of day) and $E^{dow}$ (day of week), which however are less effective in addressing the irregular patterns that do not have daily or weekly cycles. For example, in Fig.1, although location 44 (middle red curve), also at a highway from dataset PEMS08, demonstrates a daily traffic pattern, it experienced a sharp drop to almost zero at 08/19 15:00 and recovered about 5 hours later. This could be a highway closure or partial block due to reasons such as a car accident. Such irregular events are infrequent in the dataset, which makes it harder for our model to be trained to recognize them. The existing node embedding $E^{v}$ from the prior work cannot change temporally to reflect such changes in the flow rates.

To better capture such irregular traffic patterns, we introduce a rank-based node embedding. Consider an arbitrary time interval $j\in T$ in the input $\mathcal{X}_{M,T}$. We assign a rank value to each location $k\in M$: Sort $\mathcal{X}_{i,j}$, $\forall i\in M$, in ascending order (with ties broken arbitrarily), and the rank of location $k$ at time $j$ is the index number of $\mathcal{X}_{k,j}$’s position in the ordered list. Our first hypothesis is that the new rank-based embedding can help distinguish the irregularities caused by road closure or other rare events, such as the one with location 44 in Fig.1, since the location’s rank during the time of road closure will be probably among the lowest, whereas its rank at normal times would be much higher. In the event of road closure, the ranks of dependent locations over adjacent time periods will likely change, too, deviating from normal patterns. It is easier to tell such irregularities based on location, rank, time-of-the-day, and day-of-the-week, than based on location, time-of-the-day, and day-of-the-week, since the rank value provides additional hint. For spatio-temporal irregularities, the exact flow rates of the affected locations vary greatly at different times in a day or on different days in a week. Yet ranks, which are the indices of those locations’ rates in the ascending list of all locations’ rates, can be considered as normalized, relative flow rates, whose distribution tends to be more stable from time to time than the actual rates, revealing the intrinsic pattern of an irregularity. This property will help the model identify irregular patterns and separate them from normal patterns, with limited training data for irregularities due to their infrequent occurrences.

Our second hypothesis is that the new rank-based embedding can help the model be more robust to noises of a traffic pattern. In Fig. 1, except for the irregularity at 08/19 15:00, location 44 exhibits a normal daily traffic pattern with noises as the traffic fluctuates, which could be normal or sometimes due to inaccuracy sensor reading. Noises can also happen due to inference errors. Refer to the right plot in Fig. 3 for inference. After the first step, we have the estimated $\mathcal{X}_{M^{\prime},T}$, which carries the inference errors from the dynamic adaption module. These errors are noises to the next step. Comparing to the actual flow rates, the ranks are discretized values that tend to smooth out noise fluctuation and be more stable. Especially for partial sensing, the fewer the number of sensed locations is, the more stable the rank-based embedding becomes. The stability of the ranks could also enhance the model’s adaptability from one spatial area (say, with sensor data) to a new area (without sensor data), whereby their actual flow rates can differ greatly but their relative ranks follow stable patterns. In other words, the rank-based embedding is more robust to the distribution shift from the sensed locations to the unsensed locations, and between the training dataset and the test dataset.

We have run extensive experiments on node-based embedding to test the validity of the above hypotheses.

Specifically, at each time interval, we rank the flow rates at all locations. Given the $i$-th rank of the locations, vector $B_{i}^{r}\in\mathbb{R}^{d}$ denotes the rank-based node embedding bank for rank $i$. For input data $\mathcal{X}_{N,T}$ (or $\mathcal{X}_{M,T}$ for the first step), we rank each time interval in $T$ over $n$ locations, yielding the rank feature $E^{r}\in\mathbb{R}^{n\times l\times d}$. A fully connected layer is then applied to the rank-based node embedding to aggregate over the length $l$, resulting in an aggregated rank-based node embedding ${E^{r}}^{\prime}\in\mathbb{R}^{n\times d}$, encapsulating a generalized high-dimensional rank feature for each location over a period.

Ultimately, a Multi-Layer Perceptron (MLP) processes the raw data $\mathcal{X}_{N,T}$ (or $\mathcal{X}_{M,T}$ for the first step) to produce the feature embedding $E^{f}\in\mathbb{R}^{n\times d}$. We then concatenate this with the other four embeddings: time-of-day embedding $E^{tod}$, day-of-week embedding $E^{dow}$, node embedding $E^{v}$, rank-based node embedding ${E^{r}}^{\prime}$, to form an aggregated feature $H\in\mathbb{R}^{n\times 5d}$. This aggregated feature then passes through another MLP to produce a high-dimensional representation $H^{\prime}\in\mathbb{R}^{n\times 5d}$.

3.2. Dynamic Adaption Step

The main objective of this step is to capture the latent correlations between sensed locations and unsensed locations and to transfer the feature embedding from sensed locations to unsensed locations. This is to address the challenge of the shift to an unknown distribution at unsensed locations. In Fig. 3, the dynamic adaption step is represented from $\mathcal{X}_{M,T}$ to $\mathcal{X}_{M^{\prime},T}$ with a red arrow. The input for this step is the historical data from the permanent sensors deployed at the sensed locations, denoted as $\mathcal{X}_{M,T}$. The output is the predicted historical data for the unsensed locations, represented by $\hat{\mathcal{X}}_{M^{\prime},T}$.

3.3. Long-Term Forecasting Step

The primary objective of this step is to enhance the model’s long-term forecasting power and to further refine the parameters established during the initial training step. One challenge is to fully utilize the embeddings from limited spatio-temporal data. With the previous dynamic adaptive step, we obtain the well-trained embeddings with the information of adaptation from sensed locations to unsensed locations. Thus, the forecasting structure in this step could leverage this knowledge to achieve a better outcome.

The long-Term Forecasting step is shown in Fig. 3, from $\mathcal{X}_{M,T}$, $\mathcal{X}_{M^{\prime},T}$ to $\mathcal{X}_{M,T^{\prime}}$ (blue arrows). The input consists of historical data from sensed sensors $\mathcal{X}_{M,T}$ and predicted historical values at unsensed locations $\hat{\mathcal{X}}_{M^{\prime},T}$ (from the dynamic adaption step). The output of the long-term forecasting step is the future data for sensed locations $\hat{\mathcal{X}}_{M,T^{\prime}}$.

To keep our model’s resistance to noise, we first re-rank the flow rates across the sensed data and the predicted historical unsensed data, yielding the rank-based node embedding. As we explained, the noisy prediction could be alleviate by the rank-based node embedding. By incorporating additional ground truth information $\mathcal{X}_{M,T^{\prime}}$, the model’s parameters are further fine-tuned and optimized.

3.4. Aggregation Step

So far, the model has learned how to adapt knowledge from sensed locations to unsensed locations during the dynamic adaptive step (as shown from $\mathcal{X}_{M,T}$ to $\mathcal{X}_{M^{\prime},T}$ in Fig. 3) and how to perform long-term forecasting in the long-term forecasting step (as shown from $\mathcal{X}_{M,T}$, $\mathcal{X}_{M^{\prime},T}$ to $\mathcal{X}_{M,T^{\prime}}$ in Fig. 3). Intuitively, this aggregation step inherits the optimal parameters learned from previous steps and aggregates them together. As Fig. 3 shown, the input comprises three parts, the historical sensed data $\mathcal{X}_{M,T}$, the predicted history unsensed data $\hat{\mathcal{X}}_{M^{\prime},T}$, and the predicted future sensed sensor data $\hat{\mathcal{X}}_{M,T^{\prime}}$. We treat the historical data in all locations ${\mathcal{X}_{N,T}}^{\prime}$ as the concatenation of the first two data. The output is the predicted future data for the unsensed locations $\hat{\mathcal{X}}_{M^{\prime},T^{\prime}}$.

Following the methodology previous steps, the two parts of input first get their embedding ${H_{N,T}}^{\prime}\in\mathbb{R}^{n\times 5d}$ and ${H_{M,T^{\prime}}}^{\prime}\in\mathbb{R}^{m\times 5d}$. Sensed and unsensed node embedding bank $B_{M}^{v}$ and $B_{M^{\prime}}^{v}$, sensed and unsensed rank embedding ${E_{M}^{r}}^{\prime}$ and ${E_{M^{\prime}}^{r}}^{\prime}$, and MLP’ are trained from previous steps. Thus, they can express the valuable knowledge learned from previous steps to get the optimal model parameter and predicted future data for unsensed locations.

4.1. Setting and Datasets

4.2. Traffic Forecast Accuracy

Table 2 compares our method STPS with the baselines on traffic forecast accuracy in terms of average MAE, MAPE, and RMSE over 96 future intervals (i.e., 8 hours). All experiments were conducted using the weighted selection method. The number of unsensed locations is set to 250 for larger datasets including PEMS03, PEMS04 and PEMSBAY, and it is reduced to 150 for PEMS08 and METRLA, which have fewer locations. The percentage of locations that are unsensed ranges from 69% to 88.2%. We will vary the number of unsensed locations and study how it will impact the accuracy shortly. The table shows that our model outperforms all baseline models in traffic forecast accuracy, for example, achieving a $28\%$ improvement in MAPE against the best baseline result over the METRLA dataset.

The non-deep-learning matrix factorization method performs poorly probably because it is unable to capture complex spatial-temporal dependencies. The long-term traffic forecasting models, PatchTST* and iTransformer*, do not sufficiently model spatial correlation patterns, thus resulting in relatively poor performance. Among all the baseline models, STAEFormer* — which is a short-term spatial temporal traffic forecasting model — achieves the best overall performance, benefiting from its sophisticated embedding techniques (e.g., node embedding, time-of-day and day-of-week embedding), coupled with a robust transformer structure. TESTAM* performs close to STAEFormer*, thanks to its informative MOE architecture. STID* also exhibits strong performance by leveraging similar embedding techniques as STAEFormer*. FourierGNN* shows relatively weak performance, likely due to its approach to treat spatio-temporal data purely as a graph, which is inadequate to capture the crucial temporal correlations for long-range forecasting.The spatial extrapolation models, IGNNK and STGNP, were originally designed for extrapolate to a relatively modest extent, such as $30\%$, in contrast to our experimental setting of extrapolation towards 69-88.2% of locations that are unsensed from only 12.8-31% of locations that are sensed. In addition, they use STAEFormer for extrapolating in the temporal dimension from one hour data to eight hours data. Overall, they perform slightly worse than STAEFormer. In comparison, our model STPS performs better than all baselines as expected because this is the first work on the problem of partial sensing long-term traffic forecast with a targeted overall design and particularly, a novel three-steps model as shown in Figure3 and a new rank-based embedding.

4.3. Number of Unsensed Locations

Figure 4 compares our method STPS with the baselines on forecast accuracy in terms of RMSE over dataset PEMS08 with respect to a varying number of unsensed locations from 50 to 100 to 150. The left plot uses the random selection method, and the right plot uses the weighted selection method. In each plot, for each number of unsensed locations on the horizontal axis, a group of bars present the average RMSE values of the Full Sensing Benchmark (leftmost), STID*, …, and our method STPS (rightmost), respectively.

The Full Sensing Benchmark tries to establish some sort of accuracy bound that a partial sensing model such as STPS can possibly achieve. We reason that a partial sensing model without the recent knowledge of unsensed locations, i.e., $\mathcal{X}_{M^{\prime},T}$, should not beat a full sensing model with the knowledge of $\mathcal{X}_{M^{\prime},T}$. This knowledge of unsensed locations is hypothetical, and thus the Full Sensing Benchmark is not implementable, but it gives us an accuracy bound for a partial sensing model. Table 3 shows the forecast accuracy of the full-sensing baselines on dataset PEMS08, assuming the knowledge of $\mathcal{X}_{M^{\prime},T}$, such that they can use $\mathcal{X}_{N,T}$ to infer $\mathcal{X}_{M^{\prime},T^{\prime}}$, where $N=M+M^{\prime}$. Among the full-sensing baselines, PDFormer performs the best in RMSE and thus its results are used as the Full Sensing Benchmark in Figure 4.