Efficient Large-Scale Urban Parking Prediction: Graph Coarsening Based on Real-Time Parking Service Capability

spatiotemporal GCNs [30] have emerged as a powerful and prevalent approach within the realm of traffic prediction, adept at navigating the intricacies of traffic graphs by integrating both spatial and temporal dependencies. Unlike relying solely on GCNs or RNNs, spatiotemporal GCNs excel at dissecting time-series data embedded in graph structures [31], thereby yielding more precise prediction. For instance, Zhao et al. [32] introduced the T-GCN model, ingeniously combining GCN with GRU to understand the intricate topology of traffic networks and the dynamic shifts in traffic data, enhancing the capture of spatiotemporal characteristics more effectively. In a similar vein, Sun et al. [33] unveiled DDSTGCN, leveraging TCN to track variations in traffic states alongside GCN for topology learning, markedly boosting traffic prediction accuracy. In recent years, scholars have suggested employing attention mechanisms to bolster the extraction of spatiotemporal features, thereby extending the model’s interpretability. Furthermore, Li et al. [34] developed AST-GAT, incorporating multi-head graph attention and attention-based LSTM modules to intricately map the spatiotemporal interdependencies among road segments, aiming to refine the precision of traffic prediction.

Due to the inherent structural and functional similarities between urban transportation networks and urban parking networks, both involve complex spatial relationships and dynamically changing temporal characteristics. Leveraging advanced spatiotemporal graph convolutional models from the field of traffic prediction, we believe can effectively enhance the accuracy of parking prediction. However, in the domain of parking prediction, the industrial sector continues to prioritize concerns regarding time costs and resource consumption, with a current lack of effective solutions. These challenges will limit the feasibility and effectiveness of the aforementioned spatiotemporal graph convolutional models in practical industrial applications.

As the scale of graphs continues to expand, finding a universal method that can simplify the structure while preserving key attributes becomes increasingly important. Simplified graph representations not only facilitate storage but also offer efficiency in approximate algorithms [19]. There are mainly two methods for simplifying graphs: The first method, known as graph sparsification [35], approximates the maintenance of distance relationships between node pairs by removing edges from the graph. However, for highly structured parking graphs, this method might lose the original graph’s connectivity. An improved method is the K-neighbors Sparsifier [36], which performs local sparsification on each node by setting a threshold, but still introduces high computational complexity. With the growing popularity of deep learning, Wu et al. [37] proposed GSGAN, which generates new graphs through GANs to preserve the community structure of the original graph, but it introduces edges that do not exist in the original graph and contradicts reality.

The second approach is known as graph coarsening [38], which aims to reduce the number of nodes to a subset of the original nodes while maintaining the original graph properties. The key to graph coarsening [20] lies in the ability to accurately measure the variations before and after coarsening. The GraClus [39] technique, and the MCCA [40] algorithm all employ the idea of greediness by constantly compacting the connected regions of the original graph. However, these approaches lack guarantees for global optimization. Recently, spectral graph theory [21] proved that graphs with similar spectra are usually considered to have similar topologies. Therefore, the idea of minimizing the spectral distance can be introduced into the coarsening process, using the eigenvalues of the graphs to measure the structural similarity and ensuring that the generated coarsened graphs can maintain the properties of the original graphs.

However, we have observed that current graph coarsening methods primarily focus on reducing the complexity of the graph structure while often neglecting the dimensionality of node features. This approach does not effectively reduce the actual volume of parking data in large-scale urban parking prediction tasks. Although the parking network structure has been somewhat simplified through graph coarsening techniques, the training overhead for downstream parking prediction models has not decreased as significantly as anticipated.

AEs have demonstrated remarkable proficiency in managing intricate spatiotemporal data relevant to transportation systems [41]. Typically employing symmetrically structured encoders and decoders for unsupervised learning, these AEs are adept not only at distilling input data into compact representations of potential vectors [26], but also at restoring the data to its original dimensions. They achieve this by optimizing the reconstruction of the data’s objective, thereby minimizing loss [28]. For instance, the TGAE introduced by Wang et al. [41] adeptly captures the underlying patterns of traffic flow through a spatiotemporal AE, facilitating the prediction of future traffic information. Similarly, the TCN-AE devised by Mo et al. [42] leverages TCNs within its encoding module to extract features from temporal data, subsequently utilizing the decoding module to map latent representations back to the original data space, thus enabling anomaly detection.

Inspired by the capabilities of AEs in dimensionality reduction and key feature extraction of spatiotemporal data, we propose the integration of AEs into large-scale urban parking prediction tasks, aiming to address the limitations of traditional coarsening methods in handling parking lot node features. Additionally, by leveraging the advantages of TCN in processing complex temporal data, AEs can more accurately capture and analyze the parking patterns within different parking lots, thereby significantly enhancing the performance and depth of understanding of downstream parking prediction models.

In this paper, our goal is to effectively reduce the time and resource costs of parking prediction models by achieving a unified reduction in the dimensions of the structure and feature data of urban parking graphs, while ensuring the accuracy of parking prediction tasks. The urban parking graph can be represented as $G=(V,E,A)$, where $V$ denotes the set of parking nodes, $E$ denotes the set of edges, and $A\in\mathbb{R}^{N\times N}$ denotes the directed adjacency matrix, $N=|V|$.

The parking prediction problem [11] can be interpreted as: given a parking graph $G$ and historical parking data $X_{(t-T+1):t}$ for $T$ time slices before time $t$, learning a function $F$ to predict future parking data $\hat{Y}_{(t+1):(t+T^{\prime})}$ for $T^{\prime}$ time slices after time $t$, as shown in Equation 1.

where the parking data $X=\{x_{1},x_{2},\ldots,x_{T}\}\in\mathbb{R}^{T\times N\times F}$ represents the parking flow information observed at $T$ time slices for all parking lots. Each $x_{t}$ corresponds to a time slice and includes $N$ parking lot nodes, each with $F$ dimensional features, including the longitude, latitude, openness to the public, charging situation, and real-time occupancy rate of the parking lot.

Given the complexity of the parking data $X$ directly inputting the high-dimensional data $x_{t}$ into GAT would lead to considerable computational redundancy, thereby increasing the model’s time cost. To address this, we adopt a dimensionality reduction strategy that involves extracting and abstracting certain features of the parking lots. This effectively reduces the computational burden and enhances the model’s computational efficiency.

The ParkingRank algorithm [24] is an algorithm to quantitatively assess the service capability of different parking lots. By integrating complex parking information such as the total number of parking spaces in the parking lot, the degree of openness to the public, and the price of parking, it can help drivers to understand the actual situation of the parking lot in a more comprehensive way, so that they can make informed choices in the parking decision-making process. Specifically, the algorithm primarily focuses on three aspects to describe the real-time service capacity of parking lots, as shown in Equation 2:

• •

  Parking lot service range: This aspect considers which types of vehicles are allowed to park in the parking lot. For example, parking lots at shopping centers may be open to all vehicles, while those in residential areas may only serve residents. Therefore, parking lots with a broader service scope generally have stronger service capabilities.

• •

  Total number of parking spaces: The more internal parking spaces a parking lot has, the stronger its service capacity usually is.

• •

  Price of parking: Higher parking prices may reduce the number of vehicles able to afford parking fees. Thus, expensive prices may lower the service capacity of the parking lot.

where $PR_{i}$ represents the service capacity of each parking lot; $s_{i}\in[0,1]$ denotes the service range, which is used to measure the degree of openness of the parking lot, from the public parking lot ($s_{i}=1$) to the private parking lot ($s_{i}=0$); $y_{i}$ and $z_{i}$ represent the total number of parking spaces and the price of parking, respectively. $\|y\|$ and $\|z\|$ are the first-order paradigms for the $y$- and $z$-column vectors.

We believe that the process of quantifying the service capability of a parking lot is essentially a process of extracting the redundant parts of the parking lot features $x_{t}$, and the low-dimensional evaluation results can be used as new abstract features to replace the original high-dimensional parking data $x_{t}$, providing a more concise and information-rich feature input for subsequent graph modeling.

Graph coarsening, as the current mainstream graph dimensionality reduction technique, aims to overcome the huge computational obstacles faced by large-scale graph data when processing, extracting and analyzing. Typically, the input for graph coarsening is the graph adjacency matrix [20]. When dealing with complex structures such as urban parking graphs, the traditional adjacency matrix constructed from topological relationships is obviously difficult to adequately capture the complexity and diversity of the real parking landscape. In fact, drivers do not only consider the proximity of parking lots in the region when making parking decisions, but also comprehensively compare the distance of regional parking lots, real-time space occupancy rate, openness to the public, and charging situation, and other factors. Therefore, before performing the task of urban parking graph coarsening, we need a high-quality parking graph that can truly reflect the preference of parking behavior and adapt to the dynamic change of parking demand.

GAT [43] are an advanced spatial-based graph neural network methodology, with the core advantage of redefining the aggregation of node features. Unlike GCN, GAT introduces an attention mechanism, allowing the model to dynamically allocate different weights based on the importance of each neighboring node. In contrast, GCN typically assigns equal weights to all neighboring nodes for information aggregation. This strategy enables GAT to more effectively capture spatial correlations within road networks and selectively emphasize nodes that are more critical to the current task. This feature of GAT is particularly important in the application of urban parking network prediction. However, since GAT often uses MLP or cosine similarity to calculate the degree of association between nodes, conventional methods lack interpretability when applied to nodes such as parking lots, which have specific attributes. These methods often fail to provide an intuitive understanding of the interactions between parking lots.

To mitigate the black-box issue encountered by GATs in analyzing parking graphs, we integrate the parking spatiotemporal transfer matrix [2] into the computation of attention coefficients within GATs. This matrix meticulously accounts for the spatiotemporal evolution of parking lot features, encompassing real-time occupancy rates, service capabilities, and spatial connections, thereby facilitating a dynamic representation of parking cruising behavior. This nuanced incorporation allows for a richer, more detailed understanding of parking dynamics, effectively translating the raw data into actionable insights. The formulation of this transfer matrix $A_{trf}$ is presented in Equation 3.

where each element $\alpha_{i,j}^{\text{trf}}$ of $A_{\text{trf}}\in\mathbb{R}^{N\times N}$ represents the probability of a vehicle heading to another parking lot $j$ when it finds parking lot $i$ is full. $q_{i}$ represents the real-time occupancy rate of parking lot $i$, which also indicates the probability of a vehicle choosing to stay in parking lot i based on the parking situation. $w_{i,j}$ is the reciprocal of the normalized distance $A_{i,j}$ between parking lot i and parking lot j. $PR_{i}$ is the normalized service capacity of parking lot $i$.

By introducing the parking spatiotemporal transfer matrix, the GAT model can dynamically consider multiple factors, including the spatial relationships between parking lots, real-time occupancy rates, service capacities, and other relevant factors, when assigning attention weights. This mechanism enables the model to more accurately capture the spatiotemporal dependencies of nodes in complex parking networks and respond in real-time to fluctuations in parking demand. Through this approach, the model not only identifies the most critical nodes for the current prediction task but also flexibly adjusts its focus on different parking lots, optimizing the model’s representation of the parking network’s complexity and enhancing its performance in downstream prediction tasks. We believe that the improved graph attention mechanism will help construct a parking network that fully reflects the complex spatiotemporal correlations of parking lots. The overall framework of our proposed PRGAT is shown in Fig. 1:

In this paper, the input to PRGAT consists of the original adjacency matrix $A$ based on Euclidean distance and the new parking data $X^{\text{low}}\in\mathbb{R}^{T\times N\times F^{\text{low}}}$, which is composed of the service capacity $PR_{i}$, the real-time occupancy rate $q_{i}$, and latitude and longitude coordinates. The output is the updated parking data $X^{\text{re}}\in\mathbb{R}^{T\times N\times F^{\text{re}}}$. Here, $F^{\text{low}}$ represents the new feature dimensions after quantification and extraction, while $F^{\text{re}}$ denotes the new feature dimensions relearned by PRGAT.

The algorithm initially applies a linear transformation to each parking lot node’s features $x_{t}^{\text{low}}(i)$ using a learnable weight matrix $W\in\mathbb{R}^{F^{\text{re}}\times F^{\text{low}}}$ to enhance the node’s expressive capability. Subsequently, it employs an attention mechanism $\mathcal{T}$ on the set of nodes to compute the attention coefficient $e_{i,j}$ between node $i$ and node $j$. This procedure can be encapsulated by Formula 4, wherein the attention mechanism might be a function that signifies the correlation between two objects, like cosine similarity or a Multilayer Perceptron (MLP), and $\|$ represents the vector concatenation operation.

To capture local topological information and enhance computational efficiency, a masking mechanism and normalization operation have been introduced. The attention coefficients $e_{i,j}$ are confined within the first-order neighborhood of the nodes, enabling each node to concentrate solely on its directly connected neighboring nodes and disregard the other nodes in the graph, ultimately yielding the attention matrix $A_{\text{attn}}\in\mathbb{R}^{N\times N}$. See Formula 5 for details, where LeakyReLU represents the activation function.

Moreover, the masking mechanism ingeniously reflects the factors influencing the parking decision-making process. Drivers, when choosing a parking lot, tend to compare a specific parking lot with its adjacent ones, rather than conducting pairwise comparisons among all parking lots. Such a masking mechanism not only enhances the model’s sensitivity to local associations but also aligns more closely with the behavioral patterns in the actual parking decision-making process.

We input both the parking spatiotemporal transfer matrix $A_{\text{trf}}$ and the aforementioned attention matrix $A_{\text{attn}}$ into the softmax activation function simultaneously to derive the ParkingRank attention matrix $A_{\text{combined}}\in\mathbb{R}^{N\times N}$, as indicated in Equation 6.

This ParkingRank attention matrix not only reflects the dynamic characteristics of the parking graph, capturing the flow trajectories and behavioral patterns of vehicles in urban parking scenarios, but also overcomes the shortcomings of insufficient interpretability of the parking lot relevance matrix computed by traditional graph attention methods.

After obtaining the normalized ParkingRank attention coefficients $\alpha_{i,j}^{\text{combined}}$, GAT conducts a weighted aggregation of the features of each node $i$ with its neighbors $N_{i}$, thereby producing the final output for each node. This procedure is depicted in Formula 7, where $\sigma$ denotes the sigmoid activation function.

The PRGAT we designed is fundamentally a pre-trained model, its primary purpose being to serve as a front-end graph construction module within the overall framework for urban parking prediction. Its loss function is described in Formula 8, and the pseudocode for the graph is provided in Algorithm 1.

Define the coarsened parking graph $G_{c}=(V_{c},E_{c},A_{c})$ is the result of coarsening the original adjacency matrix $A$, which is a smaller weighted graph. $V_{c}$ denotes a set of disjoint hypernodes, which covers all nodes in the original graph V, where each hypernode is formed by the aggregation of some of the nodes in the original graph, i.e., $v_{i}^{c}=\{v_{1},v_{2},\ldots,v_{n}\}\in\mathbb{R}^{N}$. $A_{c}\in\mathbb{R}^{N_{c}\times N_{c}}$ is the adjacency matrix of the coarsened graph, $N_{c}=|V_{c}|$.

This document employs the SGC algorithm[21], which utilizes spectral distance (SD) to demonstrate that the coarsened network retains spatial features similar to those of the original network. This concept is illustrated in the equation below:

where the vectors $\lambda$ and $\lambda_{c}$ represent the eigenvalues of the Laplacian matrices of the original graph $G$ and the coarsened graph $G_{c}$, respectively. The spectral distance $SD(G,G_{c})$ is considered sufficiently small if it is less than $\delta$ (where $\delta$ is a very small number). Only when this condition is met do the eigenvalues and eigenvectors of the two graphs exhibit similarity in the spectral domain. The calculated spectral distance can then substantiate that the coarsened graph significantly preserves the attributes of the original graph during the coarsening process. Thus, it can be inferred that the spatial structure of the coarsened network remains similar to that of the original network. The key steps of the SGC algorithm are introduced below.

The algorithm initiates by inputting the ParkingRank attention matrix $A_{\text{combined}}$ and the coarsening ratio $n=\frac{N_{c}}{N}$. It computes the Laplacian matrix $\mathcal{L}$ and, through matrix decomposition, obtains the first $N_{c}$ and the last $N-N_{c}+1$ Laplacian eigenvalues $\lambda$ and Laplacian eigenvectors $u$, for capturing both the local and global information of the parking graph. This procedure is illustrated in Formulas 10 and 11 , wherein $\mathcal{L}$ signifies the normalized Laplacian matrix, with $I_{N}$ and $D$ being the identity matrix and the degree matrix, respectively.

Then, the algorithm starts to iterate different eigenvalues intervals, performs parking clustering on the internal eigenvectors $u$ respectively, divides the parking lots with similar features into a parking hypernode, and generates a preliminary coarsened graph $G_{c}$ based on the clustering results, the clustering principle is shown in Equation 12.

The Laplacian eigenvectors $u$ computed from the ParkingRank attention matrix $A_{combined}$ has rich parking graph topology information as well as parking lot node feature information, which can provide more accurate and intuitive parking lot node characterization for the coarsening process.

The process continuously calculates the distance $SD$ between the Laplacian eigenvectors of the coarsened graph $G_{c}$ and those of the original graph, opting for the coarsening outcome with the minimum error. Finally, the coarsened graph $G_{c}=(V_{c},E_{c},A_{c})$ along with the corresponding index matrix $index$ are returned. This procedure is depicted in Formula 13, with the coarsening specifics provided in Algorithm 2.

Since the coarsening process of the parking graph described above does not downscale the parking lot node features, the feature data corresponding to the parking hypernodes $X^{\text{combined}}\in\mathbb{R}^{T\times N\times F^{\text{low}}}$remains a splicing operation between the merged parking lot data, which is formalized as follows:

If it is simply used as the feature input for the parking prediction models, it will not significantly improve the overall framework training efficiency, and even lose the intrinsic connection between the nodes. In this regard, we consider adopting the symmetric TCN-AE, which is because:

• •

  TCN is able to mine the intrinsic laws behind the parking time-series data itself [42], such as the tidal characteristics, which helps in the compression and reconstruction of the parking data.

• •

  The encoder is able to embed the high-dimensional sparse parking data into the low-dimensional dense tensor form, which reduces the computational overhead of the training model.

• •

  The decoder is able to achieve an approximate lossless reduction and can reconstruct the spatial structure of the original parking graph.

To maintain the consistency of the prediction results between the coarsened and the original parking graphs, we train a set of symmetric TCN-based AEs for each parking hypernode, utilizing the index matrix generated by the graph coarsening module. TCNs typically consist of multiple layers of dilated causal convolution, with each layer performing one-dimensional convolution. Moreover, to enhance the network’s expressive capacity, residual connections are often added following multiple convolutional layers, organizing these layers into several residual blocks. Each residual block primarily includes two dilated causal convolution layers, interspersed with normalization, activation, and dropout operations, before the output is added to the input of the next residual block. This design not only optimizes the flow of information but also enhances the model’s ability to capture features of parking data effectively.

The procedure is detailed as follows: As depicted in Fig. 2, firstly, the parking data $X^{\text{low}}\in\mathbb{R}^{T\times N\times F^{\text{low}}}$ undergoes encoding with the residual blocks within the encoder[40], as indicated in Formula 15. Owing to the reduction in the number of features as the quantity of residual blocks increases, it allows the feature data $X^{c}\in\mathbb{R}^{T\times N_{c}\times F^{\text{low}}}$ corresponding to the coarsened graph to be represented within a low-dimensional feature space.

where $\sum_{j=0}^{k-1}f(j)$ denotes the filter $f$ of length $k$ and $*$ denotes the convolution operation. This formula ensures that only information prior to the current time step is considered and future information is not computed.

Next, we input the adjacency matrix $A_{c}$ of coarsened graph and feature matrix $X^{c}$ into a spatiotemporal graph convolutional model. This paper takes T-GCN[30] as an example, as shown in Fig. 3, which captures the spatiotemporal dependencies of the parking coarsened graph through 2 layers of GCN and 1 layer of GRU, finally obtaining the coarsened graph’s predicted results $Y_{c}\in\mathbb{R}^{T\times N_{c}\times F^{\text{low}}}$ through a linear transformation, as seen in Formulas 16, 17, 18, 19, and 20, where $W$ and $b$ represent the weights and biases of T-GCN, respectively, and $u_{t}$, $r_{t}$, $c_{t}$, $h_{t}$ denote the reset gate, update gate, candidate hidden state, and current hidden state at time $t$,respectively. $gc\left(\cdot\right)$ denotes the graph convolution operation, and tanh is the activation function.

Due to the fact that the dimensions of the coarsened graph’s predicted results $Y_{c}$ do not align with the size of the original parking graph, these results are not inherently interpretable. To address this, decoding is necessary. Based on the prediction length, we opt for a particular pre-trained decoder, inputting the prediction of each hypernode to reconstruct the original parking graph’s prediction results $\hat{Y}\in\mathbb{R}^{T\times N\times F^{\text{low}}}$, thereby fulfilling the prediction task for the entire urban parking graph. The decoding procedure is depicted in Formula 21. $f^{-1}$ denotes the filters within the decoder, distinct from the encoding phase, as the feature count in the decoder’s residual blocks grows with the increase in residual blocks, aiming to reconstruct parking data within a high-dimensional feature space.

The loss functions for the pre-trained TCN-AE and the parking prediction model utilize Mean Squared Error (MSE) and Huber Loss, respectively, as detailed in Formulas 22 and 23. In this context, $\hat{X}\in\mathbb{R}^{T\times N\times F^{\text{low}}}$ represents the outcome post-reconstruction by the autoencoder, $Y$ signifies the real observed data, and $\theta$ represents the threshold parameter that controls MSE.

The overall parking prediction framework of this paper is shown in Fig. 4.

This paper selected 9000 parking lots within five districts including Bao’an and Luohu in Shenzhen as research subjects. The parking data recorded for six months starting from June 1, 2016, was sampled at 15-minute intervals. These datasets encompassed key information such as the geographic coordinates, open status, pricing details, and real-time occupancy of each parking lot. To ensure data quality, we conducted deduplication and visualization-based outlier detection operations on the raw parking data. Additionally, to maintain consistency in data processing, all datasets underwent normalization before analysis. Finally, we partitioned the dataset chronologically into training set (70%), validation set (20%), and test set (10%) to ensure the validity and reliability of the experiments. Specifically, the distribution of parking lots in Bao’an District was visually presented through Fig. 5, and specific details of the parking lot data are referred to in Table \@slowromancapi@.

To evaluate the performance of our method, we selected several commonly used evaluation metrics in regression tasks: MAE , RMSE, and MAPE. The expressions for these metrics are as follows:

where $\hat{y}_{t}^{i}$ and $y_{t}^{i}$ respectively represent the predicted result and the ground truth for the $i$-th parking lot at time $t$. $T$ denotes the length of the time sample, and $N$ is the total number of parking lot nodes.

In the experimental parameter design, we use data from the past 12 time steps to predict data for the next 1, 2, and 4 steps, which corresponds to using the past 3 hours of parking traffic to predict the parking traffic for the next 15 minutes, 30 minutes, and 60 minutes, respectively. Additionally, to evaluate the performance of our proposed urban parking prediction framework, we selected several widely-used baseline models in the field of parking prediction, as well as some recent popular graph reduction methods for comparison:

• •

  T-GCN[32]: A classical model for traffic flow prediction that combines Graph Convolutional Networks (GCNs) and Gated Recurrent Units (GRU) to capture the spatiotemporal correlations in traffic data, effectively modeling both spatial dependencies between traffic nodes and temporal patterns within the traffic time series.

• •

  STGCN[44]: Utilizes multiple ST-Conv blocks that integrate temporal and spatial convolutions to model multi-scale traffic networks, proven to effectively capture comprehensive spatiotemporal correlations.

• •

  STSGCN[45]: By stacking multiple STSGCL blocks for synchronous spatiotemporal modeling, it can effectively capture complex local spatiotemporal traffic correlations.

• •

  SparRL[35]: A universal and effective graph sparsification framework implemented through deep reinforcement learning, capable of flexibly adapting to various sparsification objectives.

For the training of different models, we used a V100 GPU for development and incorporated early stopping and dynamic learning rate adjustment strategies to optimize training performance. To ensure completeness and transparency, all model configurations and training-related hyperparameter settings are detailed in Table \@slowromancapii@. In these configurations, the structural parameters of each model were kept at their default settings, while other hyperparameters, such as learning rate and weight decay, were selected using grid search.

To demonstrate the graph construction process of the PRGAT method, we conducted an experiment using real parking lot data from Bao’an District in Shenzhen. In Bao’an District, the number of parking lots exceeds 1,000, leading to the number of reachable edges between parking lots reaching the order of millions. Therefore, to simplify the analysis while ensuring the practicality of the results, we selected a more central CBD area within the district as the study area, which contains over 600 parking lots. Additionally, we set a spatial distance threshold of 500 meters; distances between any parking lots exceeding this threshold were considered unreachable to align with real parking scenarios.

Shown in Fig. 6 is a visualization of the parking graph constructed using the PRGAT model for the Baoan core area around evening during the week, where the different sizes of circles represent the service capacity of the parking lots, with larger circles implying stronger service capacity and more popularity among drivers. Unlike the traditional spatial adjacency matrix, the dynamic adjacency matrix generated by PRGAT can intuitively reflect the real-time importance of each parking lot, which helps the downstream prediction model to accurately determine the key parking lots in each time period, thus effectively identifying the places with strong or weak parking demand. Meanwhile, the graph composed of these parking lots with strong service capacity essentially depicts the parking backbone network of the city in different time periods, and this dynamic parking backbone network reflects the core areas and hotspots of the city’s parking demand, which provides an important perspective for understanding the city’s parking behavior pattern.

Fig. 7 depicts the distribution of parking lots in the core area of Bao’an under different coarsening ratio (coarsened vertices/original graph vertices). By adjusting the coarsening ratio, we can clearly see significant changes in the structure and density of the parking graph: parking lots with stronger service capacities gradually absorb those with weaker capacities, thus forming larger parking hypernodes with enhanced comprehensive service capabilities. As the ratio of coarsening is progressively reduced, the backbone of the urban parking graph also becomes clearer. However, this coarsening process also poses certain challenges: a simplified parking graph means the loss of some important parking information, which could affect the downstream model’s ability to capture details, especially in areas highly sensitive to parking demand or where demand changes rapidly.

Considering the dual role of the coarsening ratio in the speed of model convergence and model prediction accuracy, we set up control experiments with coarsening ratio of 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, and without coarsening (coarsening ratio of 1), to study the impact of different coarsening ratio on the prediction of parking occupation rate during the evening rush hour. The prediction results are shown in the Figure 8, where dashed and solid lines respectively represent the impact of different coarsening ratio on model prediction accuracy and convergence speed.

As shown in Fig. 8, when the coarsening ratio decreases from 1 to 0.6, the error growth rate of the model predictions remains relatively stable. This indicates that within this range, key features are effectively preserved, and the model primarily loses redundant and secondary parking information, whose absence has limited impact on overall prediction accuracy. However, as the coarsening ratio is further reduced, prediction error rises sharply. For instance, at a coarsening ratio of 0.2, calculation errors of 77.2%, 64.2%, and 61.8% are introduced across different model configurations. This suggests that crucial parking information, including the highly variable characteristics of certain parking lots, has been stripped away during the coarsening process, which significantly degrades model performance.

It’s noteworthy that the curve of model training duration presents a different trend. Initially, as the coarsening ratio reduces, training time decreases rapidly, demonstrating that coarsening can effectively alleviate the model’s computational burden. However, once the coarsening ratio reaches 0.6, the reduction in training time becomes more gradual, suggesting that further coarsening does not yield significant efficiency gains. This shift indicates that the coarsening process has started merging nodes of parking lots with distinct characteristics, resulting in the loss of critical detail information that was previously observable. Under these conditions, the model’s ability to differentiate between variations in parking lot service capacities gradually deteriorates, making it less efficient in learning the complex features of urban parking networks in a lower-information setting. This, in turn, impacts its prediction accuracy and generalization performance.

The two sets of experiments indicate that the ideal coarsening ratio should be within the range of 0.5 to 0.6. Coarsening within this interval manages to strike a balance between simplifying model complexity and retaining key feature information, which is particularly crucial when dealing with large-scale urban parking graphs, as these often contain a vast number of parking lot nodes and edges. Moreover, this phenomenon mirrors the real-world situation where approximately 50%-60% of parking lots make the primary contribution to urban parking demand. These parking lots are typically the ones with the highest usage frequency, optimal locations, and best service capabilities. However, it should be noted that the coarsening rate range we provide is merely idealized. The specific choice of coarsening rate must be dynamically adjusted based on the structure of the urban parking network and characteristics of parking data (such as parking frequency, peak periods) using adaptive deep learning models.

To explore the predictive performance of the urban parking prediction framework we proposed, we conducted predictions on the future 15 minutes, 30 minutes, and 60 minutes parking occupancy rates of various parking lots in Bao’an District during weekday evening rush hours using three baseline models, with the coarsening ratio set to 0.6. The corresponding prediction results are presented in Table \@slowromancapiii@.

Our experimental results demonstrate that, whether for short-term or long-term predictions, models using PRGAT as a pre-construction unit for graphs almost always outperform traditional parking prediction methods across all metrics. Specifically, taking TGCN as an example, compared to the default adjacency matrix, the ParkingRank attention matrix created by PRGAT achieves an average reduction of about 46.8% in MAE. Furthermore, compared to the traditional GAT mechanism, it also reduces RMSE by about 20.5%. This significant improvement in performance is attributed to the comprehensive considerations PRGAT takes in constructing dynamic parking graphs. Unlike traditional methods that focus solely on the spatial relationships between parking lots or on a single feature like available parking spaces, PRGAT also incorporates other critical information including real-time service capabilities such as the available capacity, level of accessibility, and cost of parking lots. This approach results in a graph that is not just a simple representation of spatial proximity but a richer, more accurate depiction of actual parking behavior patterns, greatly enhancing the model’s understanding and predictive ability in complex parking scenarios.

In terms of enhancing model training efficiency, compared to baseline methods, our framework achieves an average improvement of approximately 30.5%, further confirming the efficiency of our framework in handling complex parking prediction tasks. Furthermore, in the choice of graph dimensionality reduction techniques, graph coarsening outperforms graph sparsification in reducing model training duration. Graph sparsification primarily reduces the scale of the graph by decreasing the number of edges, but since the dimensionality of node features remains unchanged, its impact on training efficiency is not significant. Additionally, the loss of crucial connectivity information between parking lots can severely affect the predictive accuracy of downstream models. In contrast, graph coarsening, by merging nodes, not only reduces the scale of the parking network but also simplifies the model’s computational complexity while preserving key structural information, thereby aiding in maintaining the accuracy of the model’s predictions.

Notably, we optimized the AE by incorporating TCN to improve the processing of parking time series data, achieving near-lossless compression and restoration of large-scale parking data. Compared to previous work [46], this approach effectively keeps the MAPE within 12.6%, further increasing the accuracy of predictions.

It is important to recognize that although the application of coarsening techniques can improve model training efficiency, it inevitably introduces some level of error. Hence, our aim is to maximize training efficiency while striving to preserve prediction accuracy as much as possible. As the graph scale expands, our framework not only demonstrates a distinct advantage in prediction accuracy but also reveals increasingly significant differences in efficiency. This is especially evident when handling large-scale, dynamically changing complex urban parking graphs, showcasing the exceptional performance and practical value of our framework.

To verify whether our proposed framework can adapt to parking graphs of different scales, we simulate the expansion of the parking graph scale by gradually increasing the number of parking lots. In the experiments, the coarsening ratio is set to 0.6, with the prediction of parking occupancy rates for the next 15 minutes during the evening rush hour as the evaluation task. This approach allows us to observe changes in the model’s prediction accuracy and convergence speed on parking graphs of various sizes. Synthesizing Fig. 9(a) and 9(b), it can be observed that when the scale of the parking graph is small, our framework shows relatively conservative improvements in terms of accuracy and efficiency, with an average accuracy improvement of about 11.1% and a training efficiency improvement of about 23.7%. Importantly, as the scale of the graph expands, the performance advantages of our prediction framework become particularly pronounced. Unlike the baseline models, which exhibit a higher error growth rate and exponential increase in iteration costs, our framework demonstrates a stable growth trend, significantly surpassing traditional methods in terms of error control and training efficiency.

This performance advantage is mainly attributed to the efficient algorithms and model structures adopted within our framework, such as the PRGAT and TCN-AE . The former effectively captures key features of parking data, while the use of the latter significantly enhances the model’s capability to extract and analyze parking lot features. This ensures that the prediction framework can retain critical information from the original parking graph to a great extent, even after coarsening processing. In contrast, traditional parking prediction techniques, even when combined with graph sparsification, still face issues with suboptimal prediction performance and training speeds. This is due to graph sparsification often losing significant parking detail information as the network scale increases, severely impacting predictive performance. Additionally, since this technique does not involve dimension reduction of node features, the growth in training efficiency is similar to baseline models that do not employ any graph dimension reduction techniques.

In addressing the challenges of large-scale urban parking prediction, our framework optimizes data flow and information processing, effectively managing complex and voluminous parking data. This not only ensures high accuracy in model predictions but also significantly reduces training times, thereby meeting the needs for timeliness and accuracy. Such capabilities enable our framework to quickly and accurately respond to dynamic changes in urban parking, providing real-time predictive results.

To validate the robustness of our framework under different parking patterns and regional layouts, we further refined the experimental dataset and conducted robustness analysis on the subdivided datasets. Specifically, using the parking data of Bao’an District as the base, we divided the dataset into three smaller subsets based on differences in parking lot service coverage. These subsets correspond to regions primarily dominated by shopping centers, office complexes, and areas with a relatively balanced distribution of parking lot types. Each subset contains approximately 200 parking lots, as detailed in Table \@slowromancapiv@. In the experimental setup, we set the prediction step to 1, the coarsening rate to 0.6, and used MAE and MAPE as the main evaluation metrics.

As shown in Table \@slowromancapv@, the prediction results for different types of parking datasets demonstrate that our framework achieves higher prediction accuracy on datasets with distinct regional characteristics compared to parking networks with evenly distributed parking lot types. Specifically, in parking networks dominated by commercial area parking lots, our framework improves prediction accuracy by 11.59% in terms of MAE. Similarly, for parking networks dominated by office area parking lots, the MAE prediction error is reduced by an average of 13.18%. In terms of MAPE, our framework achieves an average improvement of 15.06% in prediction performance on these two types of parking networks with highly concentrated service characteristics.

The performance improvement is primarily attributed to the fact that parking networks with distinct regional characteristics often exhibit clearer parking demand and behavior patterns. For example, the demand fluctuations for commercial area parking lots are mainly concentrated on weekends, while the peak demand for office area parking lots typically occurs during morning and evening rush hours. Such parking networks with well-defined overall trends provide a solid foundation for the optimization of the PRGAT module in our framework. Specifically, the characteristics of these networks enable the PRGAT module to accurately identify and enhance the feature representation of critical nodes while weakening the influence of secondary and redundant nodes on model performance. This allows the construction of an adjacency matrix that better reflects actual parking behavior patterns. The adjacency matrix, in turn, provides the downstream spatiotemporal graph convolutional model with clearer learning objectives, thereby improving the model’s prediction performance.

In contrast, for parking networks with evenly distributed types and less pronounced demand characteristics, the correlations between nodes are relatively uniform, which limits the effectiveness of the PRGAT module in constructing the adjacency matrix and results in a smaller improvement in the framework’s predictive performance.Through these experimental validations, our framework is better suited for parking networks with distinct regional characteristics, whereas the overall performance improvement is relatively limited for networks with more evenly distributed parking types.

To further validate the rationality of each component within the framework, we conducted an ablation study based on the task of predicting the occupancy rate of parking lots in the Bao’an District for the next 15 minutes during the evening rush hour. The ablation experiments were divided into two parts, separately assessing the impact of PRGAT and TCN-AE on three sets of baseline models, with the coarsening ratio set to 0.6 in the experiments.

Fig. 10(a) shows the experimental results of parking predictions using various types of adjacency matrices. Clearly, among all baseline methods, the ParkingRank attention matrix constructed by PRGAT exhibits the best performance, achieving an average reduction in relative error of about 38.3%. PRGAT, by integrating the attention coefficient matrix with the parking spatiotemporal transition matrix, delves deep into the feature and spatial dependencies between parking lots, effectively restoring real parking demand scenarios. In contrast, traditional static adjacency matrices, built solely on spatial location information, overlook the intrinsic characteristics of parking lots and their interactions with the surrounding environment. Often, they fail to fully capture the complex interactions and dynamic changes between parking lots, limiting the authenticity and dynamism of the scenarios captured by the model, and thus performing poorly in downstream prediction tasks. Moreover, compared to the traditional GAT mechanism, another advantage of PRGAT is that it not only offers a more detailed and dynamic method to represent parking graphs, but it also intuitively reflects which parking lots have stronger comprehensive service capabilities at specific moments, thus becoming a key basis for making parking decisions.

However, a limitation of the PRGAT is that it aggregates node feature information considering only the 2nd-order neighborhood, neglecting the potential connections between distant nodes. This may lead to inadequate capturing of the interactions between remote parking lots during holidays or major events. Therefore, future research exploring and implementing graph convolutional networks that include higher-order neighborhood information will be crucial. This will enable the model to capture a broader range of node interactions, thereby enhancing the accuracy and practicality of the predictions.

Fig. 10(b) illustrates the effect of the AE on the prediction framework. From the figure, it can be found that not adding the AE leads to an average decrease in prediction accuracy of about 30.1%. This is because the coarsened parking graph changes its original spatial relationship, and simply splicing a set of vertex features corresponding to each hypernode will lead to redundancy of hypernode information and dimensionality inflation, thus limiting the model’s generalization ability. In addition, the loss of the intrinsic connection between nodes will also lead to the model’s inability to fully exploit the spatial dependency of the coarsened graph. On the contrary, the approach using autoencoder can selectively extract and reconstruct the key features inside the hypernodes, thus effectively adapting to the spatial changes inside the hypernodes. Meanwhile, we additionally introduce TCN in the encoding-decoding process, which enhances the model’s ability to learn the laws behind the dynamic changes of the parking lot view from the time-series data, and is more helpful for the compression and reconstruction of the parking data, which achieves an average 20% accuracy improvement.

To further validate the contribution of the ParkingRank Graph Attention Module to the accuracy of parking prediction tasks, we conducted a node error comparison experiment. Specifically, we used the original adjacency matrix and the attention matrix generated by the pre-trained ParkingRank Graph Attention Module as inputs to the spatiotemporal graph convolution model and recorded the average prediction error of each parking lot node during training to evaluate the impact of different adjacency matrices on model performance. The experiment utilized data from 100 parking lots in Bao’an District, with T-GCN as the parking prediction model and a prediction step set to 1.

Fig. 11(a) shows the heatmap visualization of the original adjacency matrix, where each cell represents the spatial relationships between different parking lots. From the figure, it can be observed that the weight distribution is relatively uniform, lacking evident traffic patterns and presenting a certain level of noise. Fig. 11(b) illustrates the prediction error distribution of different parking lot nodes during the training process when the original adjacency matrix is used as input for the spatiotemporal graph convolution model. It is evident that the prediction errors for all parking lot nodes are generally high, indicating that the model struggles to effectively capture the spatiotemporal relationships between parking lots. For certain important parking lots in the area (e.g., those near densely packed commercial zones or office buildings, highlighted in deep red in the figure), the prediction errors are particularly pronounced. This phenomenon further demonstrates that the original adjacency matrix fails to effectively reflect the underlying traffic patterns and spatial features of the parking network, thereby limiting the model’s prediction performance.

Fig. 11(c) presents the heatmap visualization of the ParkingRank Attention Adjacency Matrix constructed by the ParkingRank Graph Attention Module. Compared to Fig. 11(a), the weight distribution in Fig. 11(c) is more heterogeneous and structured. Specifically, the distribution characteristics of important parking lots are more evident in Fig. 11(c), as reflected by larger weight accumulations in the corresponding rows or columns, with overall darker colors. This feature indicates that certain parking lots are likely located in commercial centers or other areas with high parking demand, showing stronger associations with nearby parking lots. As a result, distinct cluster-like structures are formed in the corresponding rows or columns of the adjacency matrix. These cluster structures reflect the local correlations between parking lots, effectively revealing the actual characteristics of the parking network and its spatiotemporal interaction patterns.

Fig. 11(d) illustrates the prediction error distribution of different parking lot nodes during the training process when the ParkingRank Attention Matrix is used as input. Compared to Fig. 11(b), where the original adjacency matrix is used, the error levels of all parking lot nodes are significantly reduced. In particular, for nodes at the center of cluster structures (i.e., parking lot nodes with darker colors in Fig. 11(b)), the model effectively reduces the average prediction error by 45.1% during each training epoch. This result demonstrates that the ParkingRank Attention Matrix enables the spatiotemporal graph convolution model to achieve higher learning efficiency and lower error levels in regions with distinct features. Specifically, the ParkingRank Attention Matrix optimizes the weight distribution of the original adjacency matrix, more accurately reflecting the relationships between important parking lots and their surrounding lots. This refined weight allocation not only strengthens the relational representation of key nodes but also reduces the influence of minor and redundant nodes, allowing the model to learn more realistic parking behavior patterns in high-demand areas, thereby improving the prediction accuracy for these parking lot nodes. In contrast, the original adjacency matrix, with its uniform and unstructured weight distribution, results in concentrated errors in important parking lot areas during training, further hindering the model’s overall prediction performance.

To gain a deeper understanding of the time and space complexity of our framework when training on large-scale urban parking networks, we conducted a quantification experiment on computational cost (FLOPs) and memory usage (MU). In the evaluation process, we selected STSGCN as the baseline and set the graph coarsening rate to 0.6. The specific computational complexity comparison results are shown in Table \@slowromancapvi@.

As shown in Table \@slowromancapvi@, in terms of time complexity, our framework reduces the computational cost of each forward and backward pass by an average of 33.2% when training on large-scale parking networks. This optimization is primarily attributed to the graph coarsening technique, which compresses the original parking network into a smaller graph while preserving the main structure and spatiotemporal dependencies of the original graph. As a result, the model only needs to compute fewer nodes and edges during each forward and backward pass. In contrast, traditional parking prediction models typically rely on full-graph computation, where each node aggregates information from all its neighboring nodes in each layer. As the graph size increases, this approach leads to a significant increase in computational cost, which severely impacts training efficiency.It is worth noting that, while we introduce the PRGAT, Graph Coarsening, and TCN-AE modules into our framework, which inevitably add extra computation, the impact of these additional computations on the overall training time is negligible and can be considered almost insignificant when compared to traditional models that perform spatiotemporal graph convolution directly on the original parking network scale.

Specifically, the computational cost of the PRGAT module is proportional to the graph size, but through the selective weighting mechanism, the model does not perform equal computations for all neighboring nodes. Instead, it focuses on the neighbors most relevant to the current node, thereby reducing redundant calculations and avoiding unnecessary overhead. The Graph Coarsening module’s computational cost mainly comes from node merging and adjacency matrix updates, but compared to the downstream spatiotemporal GCNs, its impact on the overall computational cost is minimal. Finally, the TCN-AE module’s computational cost does not increase exponentially with the graph size but remains relatively stable, meaning it will not become a computational bottleneck during training.

In terms of space complexity, our framework does not show significant improvement in memory usage when processing large-scale parking networks. In fact, it even leads to an average increase of 22% in memory consumption. This increase mainly comes from the following two factors: 1. Graph Coarsening, the increased memory consumption in this module is primarily due to the need to store multiple intermediate results. For example, it requires maintaining the mapping between the original and coarsened graphs, storing clustering labels and cluster centers during the clustering process, and storing intermediate results such as adjacency matrices and Laplacian matrices for each layer of multi-level graph coarsening. 2. TCN-AE, this module requires storing a large amount of intermediate activation values and hidden states during feature compression and reconstruction. Particularly when handling long time-series data, AE needs to store the hidden states and corresponding activation values for each time step, which results in significant memory consumption.

This experiment indicates that while our framework effectively reduces computational costs, it inevitably increases memory consumption due to the introduction of techniques such as graph coarsening. However, we consider this additional memory overhead acceptable, as it is necessary for optimizing computational performance and improving the model’s prediction accuracy. Current parking prediction tasks generally have low requirements for memory storage, especially when handling large-scale spatiotemporal data, where memory usage typically does not become a bottleneck. In contrast, time efficiency has a more significant impact on parking prediction performance, as increased computation time often significantly affects model deployment and real-time prediction capabilities. Therefore, we adopted a ”trading space for time” optimization strategy, leveraging moderate memory costs to achieve more efficient computational performance. This approach enables the framework to effectively address large-scale urban parking prediction tasks, enhancing training efficiency and prediction accuracy while maintaining high precision.