Make Graph Neural Networks Great Again: A Generic Integration Paradigm of Topology-Free Patterns for Traffic Speed Prediction

1 Introduction

Traffic speed prediction, a fundamental task in the development of Intelligent Transportation System (ITS), has gained significant attention in the research community. In recent years, methods based on Graph Neural Networks (GNNs) have demonstrated exceptional performance in this area.

* Corresponding author.

Their effectiveness stems from the capability to model spatial correlations and temporal dependencies through information aggregation across various graph topologies [Dong et al., 2023; Hu et al., 2023] , such as road networks [Yu et al., 2017; Wang et al., 2023], road segment-segment distance graphs [Li et al., 2017], variable correlation graphs [Wu et al., 2020; Zhang et al., 2024; Wang et al., 2020], etc.

Despite their promising performance, GNN-based methods are inherently limited by their reliance on topologyregularized patterns. During node message propagation, GNNs primarily capture information constrained by the graph topology, leading to the limited scope of data representation. This limitation restricts GNNs from recognizing topology-free patterns, referring to latent or indirect relationships beyond the immediate graph structure, which are crucial for traffic speed prediction performances. To address the challenge, recent approaches have started to incorporate topology-free patterns. Notably, attention-based models have been employed to discern the intricate, non-topological relationships between nodes, such as GMAN [Zheng et al., 2020], ASTGCN [Guo et al., 2019], etc.

These advancements highlight a trend towards a more sophisticated comprehension of traffic speed dynamics, combining both topology-regularized and topology-free patterns to improve the predictive accuracy. However, to achieve the goal, three unique challenges arise:

1) Topology-free patterns vary across different scales. Topology-free patterns exhibit different characteristics at different scales. Figure 1 shows an example of a traffic speed system in the city. Note that R1 is an arterial road near the business area in the new city district, while R2 is an arterial road near the residential area in the old city district. At the finest spatial scale, both R1 and R2 are considered arterial roads in the city, sharing similar functions. Consequently, their overall traffic speed patterns exhibit similarity over long periods. However, when considering a larger spatial scale, the contextual differences of R1 and R2 remain significant. R1, being in the new city district, benefits from more lanes, resulting in an overall higher speed. In contrast, R2, located in the old city district, has fewer lanes, leading to slower speeds. This characteristic is not captured at the finest spatial scale. Therefore, this phenomenon emphasizes that "topology-free patterns" vary across different scales.

2) Topology-free patterns are dynamically changing. Here, we still taking Figure 1 as an example. During non-peak hours, the traffic speed patterns of R1 and R2 are generally similar, since they share similar arterial road characteristics. However, when considering R1 is located in a business area, while R2 is in a residential area, the speed of R2 decreases first during the morning peak hours, followed by a decrease in the speed of R1. This is because residents in the residential area commute to the business area during the morning peak hours. When the traffic volume in the residential area increases, it will take several minutes (a delay) to affect the traffic conditions in the business area. Similarly, during the evening peak hours, people located in the business area will return to the residential area, thus, a similar time delay phenomenon will occur, but the order has changed. Such difference between R1 and R2 would occur periodically every day, resulting in short-term divergence of the traffic speed patterns. Furthermore, as intelligent traffic light controllers are developed to optimize waiting time adaptively[Wei et al., 2018], the dynamics of topology-free patterns become more complicated. Therefore, how to capture the dynamics of topology-free patterns is still challenging.

3) The integration of topology-regularized and topologyfree patterns lacks a unified schema. Topology-regularized patterns are typically modeled using GNN-based approaches. However, the field of GNNs is characterized by a multitude of variants, each with its unique architecture and method of processing graph-structured data in handling node and edge features [Zhang et al., 2020; Wang et al., 2019a], varying mechanisms of aggregating neighborhood information [Zhao et al., 2019; Wang et al., 2018], and distinct strategies for capturing the hierarchical and complex patterns within graphs [Wang et al., 2019b]. As a result, each GNN variant offers a different perspective on how to interpret and utilize the topologyregularized patterns in a dataset. Developing a unified schema that can blend these two types of patterns would enable a more robust and complete analysis of graph-structured data. Such an integration is pivotal, especially in complex systems analysis, where both explicit graph structures and implicit, non-structural relationships play crucial roles in shaping the overall dynamics of the system.

Therefore, to tackle the above challenges, we propose a generic framework for boosting current GNN-based traffic speed prediction models by flexibly integrating cross-scale topology-free patterns. Specifically, the proposed framework is structured as a two-stage architecture: (1) Stage I: Topology-free pattern preservation, where we develop a Dual Cross-Scale Transformer(DCST) by modeling topology-free patterns and dynamics via hierarchical attention interactions across scales in both the spatial and temporal domains; (2) Stage II: Topology-regularized/-free patterns integration, where we devise a distillation-style integration paradigm that injects topology-regularized into topology-free patterns by regarding the original GNN-base methods as the teacher model and DCST as the student model. The proposed integration paradigm is model-agnostic and can serve as a wrapper to apply to any GNN-based model.

In summary, our contributions can be listed as follows:

• We identify existing GNN-based methods' limitations and introduce the cross-scale and dynamics of topologyfree patterns to the traffic speed prediction task.
• We further propose DCST to effectively capture topology-free patterns.
• We devise a distillation-style learning framework to flexibly integrate topology-regularized/-free patterns without bothering to revise the GNN-based models.
• We conduct extensive experiments on three real-world datasets to validate the effectiveness of our proposed framework.

2 ProblemFormulation

In this work, we focus on the multi-step traffic speed prediction task that integrates the topology-regularized and topology-free patterns.

Formally, let G = (V, E) denote the road network, where V = {v1, v2, . . . vN} represents the road segment set with N segments (recorded by sensors) 1 , and E is the edge set to demonstrate the adjacency relationship between road segments. Each road segment vi is associated with a T-step traffic speed series xi = {xi1 , xi2 , · · · , xit , · · · , xiT }, where xit stands for the traffic speed value of i-th road segment at tth time step. Then, the traffic speed records X of the entire road network G can be regarded as a multi-variate time series: X = {x1 , x2 , · · · , xN } ∈ RN×T .

Following the classic setting in auto-regressive time series forecasting, given the historical observations Xt-T:t =

1 In this work, we interchangeably use road segments, nodes, and sensors.

{x1t-T:t , x2t-T:t , · · · , xNt-T:t } of a certain time period T, we aim to predict future traffic speed in a period of time period H, denoted by Xt:t+H = {x1t:t+H , x2t:t+H , · · · , xNt:t+H }. Then, the traffic speed prediction problem with the integration of topology-regularized and topology-free patterns can be formulated as:

where g1 is a learnable function to capture the topologyregularized patterns by considering the road network topology, g2 is a learnable function to automatically preserve the topology-free patterns without any prior geographical knowledge, and f is a learnable integration function for prediction.

Noted that since we aim to provide a flexible and generic framework for boosting current GNN-based methods, and current GNN-based methods have already been working well in capturing topology-regularized patterns, we directly adopt the current GNN-based methods as g1, and study how to design the topology-free patterns function g2 and the integration function f. Moreover, the current GNN-based methods (g1) have inherently captured the temporal dependencies [Dong et al., 2024], we will not additionally introduce how to model the temporal dependencies to avoid redundancy.

3 Methodology

In this section, we introduce our proposed framework for boosting traffic speed prediction tasks. We start with an overview and present each component in detail.

3.1 Framework Overview

Our framework aims to provide a generic wrapper-style solution to enhance the current GNN-based methods by integrating cross-scale topology-free patterns. The proposed framework includes two stages: (1) preserving topology-free patterns, and (2) integrating topology-regularized/-free patterns. Specifically, in Stage I, we design a Dual Cross-Scale Transformer(DCST) to capture cross-scale topology-free patterns and corresponding dynamics (as shown in Figure 2). In Stage II, a teacher-student learning framework (as shown in Figure 3) is proposed to integrate topology-regularized/-free patterns, in which the current GNN-based methods are taken as the teacher model, and DCST as the student model. The learning framework extracts the knowledge of the topologyregularized spatial correlations from the current GNN-based methods and then passes it into the DCST for integration. Then, the well-trained DCST learned through the teacherstudent framework will generate predictions by taking into account both the topology-regularized and topology-free patterns. In the following content, we will introduce the DCST and the integration procedure in detail.

3.2 Dual Cross-Scale Transformer for Topology-Free Patterns

Transformer networks [Vaswani et al., 2017] have emerged as a predominant paradigm in the realms of natural language processing and computer vision. The core idea of Transformer is to exploit the self-attention mechanism to automatically explore the correlations and dependencies among the input tokens. As discussed, the topology-free patterns indicate the complex interactions among nodes that are beyond the graph topology modeled by GNN-based methods. Therefore, we develop a new Dual Cross-Scale Transformer (DCST) to preserve topology-free patterns and corresponding dynamics.

Next, we introduce how to divide data into different scales at the spatial and temporal dimensions. And then, we present the design of the proposed DCST.

Spatial-Temporal Scale Generation

Spatial Scale. We split the geospace into grids based on a pre-defined standard (i.e., width and length). Different standards lead to different scales. Nodes (road segments) are distributed in the grids. Let hit-T:t ∈ RT×D denote the Ddimensional representation of the i-th node, then the representation matrix can be represented as

where Ht-T:t ∈ RN×T×D . Then, we represent the grid representation by aggregating the associated nodes. Formally, given the m-th grid of the ls-th spatial scale, the representation Zmls can be represented as

where Zmls ∈ RT×D , and LN denotes layer normalization, and Wi ls ∈ RD×D and bils ∈ RD denote the weight and bias terms, respectively. Then, we denote the representation matrix for the ls-th spatial scale as Zls .

Temporal Scale. To capture the dynamics of topology-free patterns, we construct temporal scales by splitting the observations in terms of different unit time lengths. The larger the length, the coarser the scale. Let ξlt denote the unit time length for the lt-th temporal scale, then the constructed temporal scales can be represented as

where Sij,l ∈ Rξlt ×D is the j-th segment of node vi on the lt-th temporal scale. For convenience, we set ξlt divisible by T . Then, the representation of the j-th segment of node vi on the lt-th temporal scale Pij,lt can be represented as

where Pij,lt ∈ RD , Sij,lt is reshaped as R1×(D×ξlt ) , and Wj,lt ∈ R(D×ξlt )×D and bj,lt ∈ RD denote weight and bias terms, respectively. Then, the representation matrix of the lt-th temporal scale can be denoted as Plt . To reduce the complexity, all nodes at the same segment of a given temporal scale share the same parameters.

By adjusting the unit length of ξlt , we can obtain temporal segments with different scales, which are used to capture the dynamics of cross-scale topology-free patterns.

Traffic Speed Records

Figure 3: An illustration of the integration process of topologyregularized/-free patterns. The integration process follows the teacher-student paradigm, where the GNN-based model is taken as the teacher model (topology-regularized patterns), and the Dual Cross-Scale Transformer is taken as the student model (topologyfree patterns). During the process, the GNN-based model has been pre-trained and kept fixed. The integration is conducted by jointly optimizing "Soft Loss" and "Hard Loss".

Dual Cross-Scale Transformer

The proposed Dual Cross-Scale Transformer (DCST) is composed of an embedding layer (denoted as FC), a temporal Transformer, a spatial Transformer, and a prediction layer. Specifically, the embedding layer is a fully connected layer that transforms the original data into D-dimensional representations, represented as

Then, the Temporal Transformer takes the representation Ht-T:t as input to capture the dynamics of the topology-free patterns by investigating attention between nodes across temporal segments in different scales. Then, the updated node representations are further fed into the Spatial Transformer to capture the cross-scale characteristics of the topology-free patterns by exploring the relationship between nodes and affiliated grids. The Spatial and Temporal Transformers follow the same architecture. Each layer of the Transformers corresponds to one spatial or temporal scale, respectively. For a general description, we utilize "∗" to represent s (spatial) or t (temporal), and ignore the time subscript "t -T : t" to denote the learned node representation by the l∗-th layer as Hl∗ . Then, the updating process of the node representation on the l∗-th layer can be represented as

(7) where Φ denotes Zls for the Spatial Transformer, and Plt for the Temporal Transformer, respectively; WQ l∗ , WK l∗ , and WV l∗ are learnable parameters; MSA(Q,K, V ) is multi-head self-attention block and Q,K, V serves as queries, keys and values [Vaswani et al., 2017]; MLP represents a multi-layer feedforward block [Liu et al., 2021]. Suppose there are Ls spatial scales and Lt temporal scales, then, the output of the Temporal Transformer can be denoted as HLt . The Spatial Transformer takes HLt as input, and the output can be denoted as HLs . In the process of aggregating cross-scale topology-free patterns, DCST aggregates Φ features from fine-grained to coarse-grained. This means that in the Temporal Transformer, the length of ξlt becomes longer as the number of layers increases, and in the Spatial Transformer the size of the grid changes from small to large.

The prediction layer is a fully connected layer, which takes the learned representation HLs as input and then generates prediction Y .

3.3 Integration of Topology-regularized and Cross-Scale Topology-free Patterns

The proposed Dual Cross-Scale Transformer has deeply explored the cross-scale topology-free patterns in traffic speed prediction tasks. However, we still have another research question: can we further integrate the topology-regularized patterns with the topology-free patterns to boost traffic speed prediction performances of GNN-based methods? To this end, we propose a novel teacher-student framework to conduct the integration through knowledge distillation. Specifically, we take the current GNN-based methods as the teacher model and the proposed DCST as the Student model. Intuitively, since the GNN-based methods are graph-based models that leverage the topology of the graph to describe the relationships between sensors and GNNs to capture correlations, they can effectively capture topology-regularized patterns. Through knowledge distillation, the topologyregularized patterns are learned and then passed to the DCST for integration. Formally, let YGNN, YDCST, and Y denote the predictions of the GNN-based methods (the teacher model), DCST (the student model), and the ground truth of the traffic speed. We first pre-train the GNN-based methods to fit the ground truth. Then, we fix the GNN-based methods and conduct the integration process by optimizing DCST with the help of GNN-based methods. Specifically, the integration has two objectives: (1) accepting the knowledge from the GNNbased methods, and (2) predicting as accurately as possible. Therefore, following the convention of the teacher-student paradigm, the training loss can be represented as:

where MAE denotes Mean Square Error, and α and β are hyperparameters for Soft Loss and Hard Loss, respectively. Specifically, the "Soft Loss" is to set the prediction results of the GNN-based methods YGNN as the target, and push the prediction of DCST YDCST as close as to the GNN-based methods. Along this line, the learned topology-regularized patterns will be integrated into the DCST. On the other hand, the "Hard Loss" aims to make the DCST generate precise prediction results, which can provide the correct optimization direction for the integration. The integration is conducted automatically by minimizing L in Equation (9).

4 Experiment

In this work, we conduct extensive experiments on three realworld datasets to evaluate the performance of our proposed methods in traffic prediction tasks. Particularly, our experiments aim to answer the following research questions:

• RQ1: How well does our framework perform in traffic prediction tasks? Can our proposed framework boost current GNN-based methods?
• RQ2: How much can topology-regularized and crossscale topology-free patterns contribute to traffic speed prediction, respectively?
• RQ3: How do the key components of the Dual CrossScale Transformer architecture contribute to the results?

4.1 Experiment Setting

Datasets. We evaluate our proposed framework on three traffic speed datasets [Jiang et al., 2021], including: "METR-LA"(Los Angeles), "PEMS-BAY"(San Francisco), and "PEMSD7(M)"(California). In the experiment, we split the datasets into three non-overlapping sets, where the earliest 70% of the data is the training set, the following 20% are validation set, and the remaining 10% of the data are test set.

Comparsion Setup. Since our proposed framework is a generic wrapper for boosting current GNN-based models, we evaluate the performance following an ablation study manner. Specifically, we take five widely-used GNN-based models as the base models and compare their performance with/without our proposed framework. The selected five base models are STGCN [Yu et al., 2017], DCRNN[Li et al., 2017], GWNet[Wu et al., 2019], MTGNN[Wu et al., 2020] and AGCRN[Bai et al., 2020]. We also compare non-GNNbased models for a broader analysis, including two linear models: HA and LSTNet[Lai et al., 2018], and four models that solely capture topology-free patterns: GMAN, ASTGCN, STAEformer (based on attention) [Liu et al., 2023], and STID (based on MLP) [Shao et al., 2022].

When applying our proposed framework, we take the GNN-based model as the teacher model, and the proposed DCST as the student model. We denote the GNN-based model powered by our framework as "∗-KD", where ∗ refers to the GNN-based model, such as STGCN-KD, DCRNN-KD, GWNet-KD, MTGNN-KD, and AGCRN-KD, respectively.

Evaluation Metrics. We select three widely used metrics for traffic speed prediction tasks, including Mean Absolute Error (MAE), Root Mean Squared Error (RMSE), and Mean Absolute Percentage Error (MAPE). We use historical 12 time steps to predict future average 12 time steps.

4.2 RQ1: Overall Comparison

Table 1 summarizes the overall experimental results. The bold results are the best. Based on Table 1, we can make the following observations and analysis: (1) When our framework combines different GNN-based models, the performance can exceed models that only capture topology-free patterns. This reflects the importance of considering both topology-regularized and cross-scale topology-free patterns. (2) All the enhanced "*-KD" versions consistently outperform the base versions in terms of all metrics over all datasets, these results can validate our motivation that the cross-scale topology-free patterns are essential for boosting traffic speed prediction. Such wrapper-style design benefits the current SOTA GNN-based models without modifying the original architecture but only needs to pass the learned topologyregularized patterns for integration.

4.3 RQ2: Analysis of Topology Regularized/-Free Patterns

In this work, we integrate the topology-regularized and topology-free patterns for boosting the performance of traffic speed prediction. One interesting question may arise: what is the optimal extent of topology-regularized patterns to be accepted for the DCST to achieve the best performance? To answer the question, we study the effects of the trade-off parameters α and β in Equation (9). The trade-off parameters decide whether the prediction results rely on more topologyfree or topology-regularized patterns.

Specifically, we set α + β = 1, and select five pair of values, i.e., {(α = 0.1, β = 0.9), (α = 0.3, β = 0.7), (α =

0.5, β = 0.5), (α = 0.7, β = 0.3), (α = 0.9, β = 0.1)}, to investigate the corresponding performances. The larger α is, the more the prediction relies on the topology-regularized patterns from the GNN-based methods. We present the MAPE for each pair of trade-off parameters in Figure 4.

An important observation is that there is not a universally optimal setting for the parameters α and β applicable to all Graph Neural Network (GNN)-based methods. It has been noted that different GNN-based methods attain their peak performance with various combinations of topology-regularized and topology-free patterns. This variance can be attributed to the fact that the balance between topology-regularized and topology-free patterns is influenced by the specific characteristics of each GNN-based method. These characteristics include distinct architectural designs and diverse strategies for graph construction and learning topology-regularized patterns. For instance, STGCN, which is the least effective among the GNN models evaluated, demonstrates an increased need for topology-free patterns to enhance its performance.

4.4 RQ3: Ablation Study of DCST

In this experiment, we aim to study the necessity of crossscale consideration, the dynamics of topology-free patterns. We construct multiple variants of DCST for the analysis. For clarity, we name these variants as (1) w/o ST: variants that remove Spatial Transformer; (2) w/o TT: variants that remove Temporal Transformer; (3) w/o CS: variants that only use one specific scale in the Spatial Transformer and Temporal Transformer; (4) DCST: a complete version that includes all components. We present the experimental results on the METRLA dataset in Figure 5.

We can conclude the following findings: (1) The performance of w/o ST decreases the most. A possible explanation is that inter-node spatial interactions contribute more to topology-free patterns compared to intra-node temporal relationships. (2) The performance of w/o TT also decreases. Such a result validates the necessity and effectiveness of preserving the dynamics of topology-free patterns. (3) Although the effect of w/o CS is better than that of w/o ST and w/o TT, it is still not as good as DCST, which reflects noncomprehensive consideration of cross scales in space and time, leading to incomplete information preservation.

5 RelatedWork

5.1 Traffic Prediction

Traffic prediction is initially treated as a time series prediction problem. Traditional time series models such as ARMA [Benjamin et al., 2003] and ARIMA [Box and Pierce, 1970] are not capable of modeling the nonlinear and stochastic features due to the linear nature. Then, Graph Neural Networks(GNNs)-besed models are widely used for traffic prediction, this kind of method leverages the topology of the graph to describe the relationships between time series and GNNs to capture correlations. Earlier GNN-based methods treat traffic networks as a pre-defined graph which aggregates patterns from neighboring connected road segments [Yu et al., 2017; Li et al., 2017]. Then, GWNet[Wu et al., 2019] first constructs a self-adaptive graph through two learnable embedding matrices. AGCRN[Bai et al., 2020] introduces a node-specific module to construct graph. Our work distinguishes itself from these methods by overcoming the limitations of graph topology structure with Dual Cross-Scale Transformer and further integrating the topology-regularized pattern through distillation-style learning framework.

5.2 Knowledge Distillation

The term "knowledge distillation" proposed by[Hinton et al., 2015] refers to a process in which a well-trained teacher model transfers its knowledge to a student model. One crucial role of knowledge distillation is performance enhancement. Given the prior knowledge from the teacher models, the student models may have better performance than the teacher models. Then few samples are illustrated. [Ahn et al., 2019] propose a creative framework that develops knowledge transfer by maximizing the information betwixt the teacher network and the student network. [Ahn et al., 2019] introduced this teacher-student mechanism to the transformer model to deal with image issues.

6 Conclusion Remarks

In this work, we study the problem of traffic speed prediction. The current GNN-based methods exploit topologyregularized patterns with graph topology while neglecting topology-free patterns beyond the graph structure. To overcome the limitation, we developed a generic wrapper-style framework to boost current GNN-based methods by integrating topology-free patterns. Specifically, we devise a Dual Cross-Scale Transformer architecture with a Spatial Transformer for learning cross-scale topology-free patterns and a Temporal Transformer for capturing the dynamics. The topology-regularized patterns are integrated into topologyfree patterns with a teacher-student learning framework. The proposed framework is flexible and can be applied to any current GNN-based methods without any modification. The empirical evaluation validates the necessity of cross-scale topology-free patterns and their dynamics, and the effectiveness of our proposed framework for learning such patterns.

Acknowledgments

This research is funded by the Science and Technology Development Fund (FDCT), Macau SAR (File No. 0123/2023/RIA2, 001/2024/SKL, 0047/2022/A1), the Natural Science Foundation of China under Grant No. 61836013, the National Science Foundation (NSF) (Grant No. 2040950, 2006889, 2045567), the State Key Laboratory of Internet of Things for Smart City (University of Macau) Open Research Project No. SKL-IOTSC(UM)-2024-2026/ORP/GA02/202, and the University of Macau (SRG2021-00017-IOTSC, MYRG2022-00048-IOTSC).

Contribution Statement

In this work, Yicheng Zhou and Pengfei Wang have an equal contribution, specifically, they led the project, provided theoretical support, and were responsible for the overall model design, code implementation, experimental design and paper writing. Denghui Zhang, Dingqi Yang, and Yanjie Fu provided guidance in solving complex problems and helped with paper writing. Pengyang Wang provided valuable feedback on the paper drafts. All authors reviewed and approved the final manuscript.