Regularized Graph Structure Learning with Semantic Knowledge for Multi-variates Time-Series Forecasting

1 Introduction

The spatial-temporal graph network [Yu et al., 2018; Cao et al., 2020; Chen et al., 2019; Shang et al., 2021] enhances time-series forecasting by modelling the correlation as well as the relationship between multivariate time-series. It has many applications. For example, the traffic flow forecasting is a basic yet important application in intelligent transportation system, which constructs the spatial dependency graph with road distance. The cloud service flow forecasting is a fundamental task in cloud serving system and e-commerce domain, which builds the relationship graph based on request region or zone information. Existing graph time-series forecasting networks like STGCN [Yu et al., 2018], DCRNN [Li et al., 2018] and ASTGCN [Guo et al., 2019] exploit fixed graph structure constructed with domain expert knowledge to capture the multi-variate time-series relationship. The explicit graph is not always available in every applications or may be incomplete as it is hard for human expert to capture latent or long-range dependence among substantial time-series. Thus how to define accurate dynamic relationship graph becomes a critical task for graph time-series forecasting.

∗ equal contribution, This work was partly done when Hongyuan Yu was intern at Ant Group.

† corresponding author

As the quality of graph structure impacts the performances of graph time-series forecasting greatly, many recent efforts [Lu et al., 2021; Bai et al., 2020; Chen et al., 2021a] have made for Graph Structure Learning (GSL). For instance, GTS [Shang et al., 2021] have been proposed to learn the discrete graph structure simultaneously with GNN. AGCRN in [Bai et al., 2020] is proposed to learn the similarity matrix derived from trainable adaptive node embedding and forecasting in an end-to-end style. DGNN [Lu et al., 2021] is a dynamic graph construction method which learns the timespecific spatial adjacency matrix firstly and then exploits dynamic graph convolution to pass the message. However, these aforementioned methods go to another extreme that they learn the intrinsic/implicit graph structure from time-series patterns directly, while ignoring the possibility to leverage priori timeseries relationships defined from domain expert knowledge.

In this paper, we focus on solving two problems, the first is how to take advantage of combining the explicit time-series relationship with implicit correlations effectively in an endto-end way; the second is how to regularize the learned graph to be sparse which filters out the redundant useless edges thus improves overall performances, and is more valuable to real-world applications. To address these issues, firstly we introduce the Regularized Graph Generation (RGG) module to learn the implicit graph, which adopts the Gumbel Softmax trick to sparsify the dense similarity matrix from node embedding. Second, we introduce the Laplacian Matrix Mixed-up Module (LM3 ) to incorporate the explicit relationship from domain knowledge with the implicit graph from RGG. Figure1 shows the graph structure learned from only explicit relationship in (a), both implicit and explicit relationship without regularization (b), as well as from our proposed RGSL shown in (c). We can observe that RGSL can discover the implicit time-series relationship ignored by naive graph structure learning algorithm(shown in red boxes in Figure1(a)). Besides, compared to Figure 1(b), the regularization module in RGSL which automatically removes the noisy/redundant edges making the learned graph more sparse, as well as more effective than dense graph.

To summarize, our work presents the following contributions.

• We propose a novel and efficient model named RGSL which first exploits both explicit and implicit time-series relationship to assist graph structure learning, and our proposed LM3 module effectively mixes up two kinds of Laplacian matrix collectively.
• Besides, to regularize the learned matrix, we also propose a RGG module which formulates the discrete graph structure as a variable independent matrix and exploits the Gumbel softmax trick to optimize the probabilistic graph distribution parameters.
• Extensive experiments show the proposed model RGSL significantly outperforms benchmarks on three datasets consistently. Moreover, both the LM3 module and RGG module can be easily generalized to different spatiotemporal graph models.

2 Methodology

In this section, we first introduce problem definition and notations, and then describe the detailed implementation of proposed RGSL. The overall pipeline is shown in Figure 2. The RGSL consists of three major modules, and the first is the regularized graph generation module name RGG which learns the discrete graph structure with trainable node embeddings in Section 2.2 with Gumbel softmax trick. The second is the Laplacian matrix mix-up module named LM3 in 2.3 which captures both explicit and implicit time-series correlations between nodes in a convex way. Finally, in 2.4, we utilize recurrent graph network to perform time-series forecasting considering both the spatial correlation and temporal dependency simultaneously.

2.1 Preliminary

The traffic series forecasting is to predict the future time series from historical traffic records. Denote the training data by X0:T = {X0,X1, . . . ,Xt, . . . ,XT}, and Xt = {X0 t ,X1 t , . . . ,XN t }, where the superscript refers to series and subscript refers to time. There are total T timestamps for training and τ timestamps required for traffic forecasting. We denote G(0) as the explicit graph constructed with priori time-series relationship, and G(l) as the implicit graph learned from trainable node embeddings, and the vertex of graph G(l) represents traffic series X, and A ∈ RN×N is the adjacent matrix of the graph G representing the similarity between time-series. Thus, the time-series forecasting with the explicit graph task can be defined as:

where Wθ denotes all the learnable parameters, ˆXT+1:T+τ denotes the ground truth future values, L is the loss function.

2.2 Regularized Graph Generation

Regularization method Dropout [Srivastava et al., 2014] aims at preventing neural networks from overfitting by randomly drop connections during training. However, traditional Dropout equally treats every connection and drop them with the same distribution acquired from cross-validation, which doesn't consider the different significance of different edges. In our Regularized Graph Generation(RGG) module, inspired by [Shang et al., 2021] and works in reinforcement learning, we simply resolve the regularization problem with Gumble Softmax to replace Softmax, which is super convenient to employ, increases the explainability of prediction and shows nice improvements. Another motivation of applying Gumble Softmax trick is to alleviate the density of the learned matrix after training fromGNNs.

Let E ∈ RN×d be the learned node embedding matrix, d is the embedding dimension, θ is the probability matrix then θij ∈ θ represents the probability to preserve the edge of time-series i to j, which is formulated as:

Let σ be activation function and s is the temperature variable, then the sparse adjacency matrix A(l) is defined as:

Equation 3 is the Gumbel softmax implementation of our task where the A(l) ij = 1 with the probability θij and 0 with remaining probability. It can be easily proved that Gumbel Softmax shares the same probability distribution as the normal Softmax, which ensures that the graph forecasting network keeps consistent with the trainable probability matrix generation statistically.

At each iteration, we calculate the adjacent matrix θ as the Equation 2 suggests, Gumbel-Max samples the adjacent matrix to determine which edge to preserve and which to discard, which is similar to Dropout. However, dropout randomly selects edges or neurons with equal probability, while we drop out useful edges with small likelihood and tend to get rid of those redundant edges. As in Figure. 4(a), all the non-diagonal entries are non-zero, but substantial amounts of them are small-value and regarded as useless or even noisy. Another difference from dropout is that in test phase, RGG also utilizes Gumbel Softmax to remove the noise information contained in redundant small values. In this way, we filter out the similarity information between nodes which is beneficial for later traffic predicting, and also inherit the advantages of dropout such as improving the regularization and generalization, and preventing too much co-adapting. From another perspective, RGG also improves the explainability in graph time-series prediction since A(l) is sparse which is more similar to semantic knowledge shown in Figure. 1.

The RGG module regularizes the learnable graph generated with trainable node embeddings, making it more explainable. It is easy to add to graph generation tasks, significantly reducing the computation cost.

2.3 LaplacianMatrixMix-upModule

There are many kinds of attributes in time-series, for example in traffic time-series forecasting task, each node Xi0:T represents flows in a POI, whose properties are affected by multiple complicated factors: location, time of the day, nearby commercial buildings, and so on. We classify the factors into three categories: 1) temporal dependencies; 2) spatial dependencies; 3) external factors. The first two factors are easy to understand, and external factors can be illustrated in this example: although road A and road B are not connected spatially, they are both six-lane avenues and have gas stations on them, thus we assume A and B may share similar patterns. We propose a Laplacian matrix mix-up module named LM3 which carefully fuses both the explicit graph generated from priori relationship and the implicit graph calculated with trainable node embeddings, discovering the above three categories of relationship.

The spatial adjacent information is often provided with datasets themselves, or can be acquired with little effort from urban maps. Let's denote them as explicit graph A(0) , then the spatially adjacent relationship is easily captured by{X0:T j }, s.t. A(0) i,j = 1. Although the explicit graph may not include complete information, it contains spatial correlations and can be set as the training start-point. On the other hand, the A(l) , derived from Eq.3, encodes the inner product of node embeddings, and captures the implicit correlation between multivariate time-series. Let X ∈ RN×H be input matrix, W (0) , W (0) b , W (l) , W (l) b are learnable parameters, then the Chebyshev polynomial expansion form of graph operations for A(l) (Eq.5) and A(0) (Eq.4)

where I ∈ RN×N , D is the degree matrix.

The mix-up operation originally serves as a data augmentation method to better constrain the border of the feature space, and we apply the idea of 'mix-up' here to balance the composition of two kinds of correlations, and constrain the border of Adjacent Matrix. Besides, different from traditional mix-up which samples weighting coefficients from beta distribution, we compute the weights by self-attention module, which dynamically assigns higher weights to the high intrasimilarity between long-distance nodes, and further improves mining the semantic correlations. As the following equation suggests, LM3 mixes up the explicit graph A(0) with learned implicit graph A(l) in a convex dynamic manner.

where fa denotes self-attention network, θa and θb are the parameters of attention network. By utilizing LM3 module, the dynamic convex combination of explicit graph and learned implicit graph, we carefully capture the two kinds of timeseries correlation. And the experiments can demonstrate our assumption in Section 3.4.

2.4 Spatial Temporal Recurrent Convolution Network

As illustrated in Figure2, we first take the learnable nodes embedding E as inputs Eq.3 and output the probability graph A(l) . Then, we apply the Chebyshev polynomial expansion form of graph operations for both A(l) and A(0) and put the encoding graph into LM3 module Eq.6 to get M (m) . In order to further understand the spatial and temporal interdependencies between traffic series, our method takes X0:T and M (m) as input, then put it to Spatial Temporal Recurrent Graph Convolution Module (STRGC) which contains a graph convolution network and a Gate Recurrent Unit (GRU) network to updates hidden states ht collectively as the equations 7. It is worth noting that many sequence and graph architectures can be applied here, we opt for a simple but effective one to model the dynamic and comprehensive spatialtemporal correlations, and finally outputs time series predictions XT+1:T+τ .

where the embedded graph information is sent into reset gate rt and update gate zt, and σ refers to sigmoid function.

The loss function in our method is mean absolute error (MAE) loss formulated as Eq. 8.

3 Experiments

3.1 Datasets

To evaluate the performance of the proposed RGSL, we conduct experiments on two public real-world traffic datasets PeMSD4 and PeMSD8 [Guo et al., 2019; Song et al., 2020a], and a proprietary dataset RPCM.

PeMSD4: The PeMSD4 dataset refers to the traffic flow data in the San Francisco Bay Area and contains 3848 detectors on 29 roads. The time span of this dataset is from January to February in 2018

PeMSD8: The PeMSD8 dataset contains traffic flow information collected from 1979 detectors on 8 roads on the San Bernardino area from 1/Jul/2016 - 31/Aug/2016.

RPCM: The RPCM dataset collects Remote Procedure Call(RPC) data every ten minutes provided by a world leading internet company. The RPC data is a direct reflection of the remote communications and mutual calls between distributed systems. RPCM contains time series from 113 applications deployed in different Logic Data Center(LDC).

3.2 Baselines

To evaluate the overall performance of our work, we compare our model RGSL with traditional methods and deep models as follows.

1) Sequence models which classically focus on capturing temporal relations among series, such as Historical Average (HA) which uses the average of the same historical timestamps as predictions, Vector Auto-Regression (VAR) [Zivot and Wang, 2006], support vector regression (SVR) [Drucker et al., 1997], Auto-Regressive Integrated Moving Average (ARIMA) [Williams and Hoel, 2003] which is a statistics method modelling time dependencies; GRU-ED which is GRU-based encoder-decoder framework; FC-LSTM [Sutskever et al., 2014] uses long shortterm memory (LSTM) and encoder decoder network;Dual Self-attention Network(DSANet) [Huang et al., 2019] using CNN and self-attention mechanism for temporal and spatial correlations respectively;

2) Deep graph models: Diffusion convolutional recurrent neural network(DCRNN) [Li et al., 2018] which adopts a diffusion process on a directed graph to model the traffic flow, utilizes bidirectional random walks, and combines GCN with recurrent models in an encoder-decoder manner; Spatio-temporal graph convolutional network(STGCN) [Yu et al., 2018] exploits spatial convolution and temporal convolution for forecasting; Attention-based spatiotemporal graph convolutional network(ASTGCN) [Guo et al., 2019] which integrates attention mechanisms based on STGCN for capturing dynamic spatial and temporal patterns; Spatial-Temporal Synchronous Graph Convolutional Network(STSGCN) [Song et al., 2020a] which addresses heterogeneities in spatial-temporal data and designs multiple modules for different time periods; Adaptive Graph Convolutional Recurrent Network (AGCRN) [Bai et al., 2020] which learns node-specific and data-adaptive graph to capture fine-grained features; GCNs with a time-aware zigzag topological layer (Z-GCNETs) [Chen et al., 2021b] introduces the concept of zigzag persistence into time-aware GCN.

Evaluation Metrics: In this paper, we use mean absolute error (MAE), mean absolute percentage error (MAPE), and root-mean-square error (RMSE) to measure the performance.

3.3 Results

The overall experimental results, including our RGSL and other baselines are shown in Table 1. We summarize the results in the following three aspects: 1) GCN-based deep methods outperform other methods, which is reasonable since graph pays more attention to spatial correlations; 2) Our method further improves traffic forecasting methods with a significant margin at all metrics. Our RGSL outperforms AGCRN by 3.22% MAE on PeMSD4 and around 2.88% MAE on PeMSD8 mainly result from 2 reasons. The first is that AGCRN totally ignores the explicit graph knowledge. Secondly, AGCRN learns dense and somehow redundant adjacent matrix. We demonstrate the above explanations after add on our module, as shown in table 3. Z-GCNETs performs better than AGCRN (relatively 1% in MAE and MAPE, but inferior about 1% in RMSE). And one of the differences is Z-GCNETs utilizes explicit graph information, demonstrating the significance of prior knowledge. Z-GCNETs processes raw data in part, regards each part as a channel and stacks channel-wise layers, which can capture more detailed features, but it also has graph redundancy problem. 3) The proposed method significantly outperforms other methods by 0.61% - 3.92% relative improvements corroborates that regularization plays an important role in graph networks, and carefully collaborating prior knowledge and learned correlations is promising and worthwhile. Experiments results in Figure5 shows that road 1 and road 2 are not spatially connected and thus not existed in prior explicit graph, but RGSL captures their similarity and is able to model this similarity by learning A(l) . Besides, in Figure3our model also shows superior for all horizons and deteriorate slower than other GCNbased models.

3.4 Ablation Study

Table2 illustrates the effect of removing key components of our method on both PeMSD4 and RPCM dataset. There are two main modules LM3 and RGG, and LM3 takes prior graph and learnable graph as input.

Table2 shows four ablations that removing RGG module results in degradation(relative 1%) due to the lack of regularization. Besides, removing RGG also makes adjacent matrix less explainable, as in Figure4(b), the learned adjacent matrix is filled with small enties. 4(b) and 1(c) are adjacent matrix with LM3 module, it is sparse and accord with our expectation.

Table2 experiment 3,2,1 and Figure 1 shows the effect of LM3 module, while experiment 1 and 2 respectively takes prior knowledge or learned knowledge as the only graph input. The substantial decrease in performance demonstrates the followings: 1)only the explicit graph restricts the sum of learnable parameters and lacks flexibility; 2) learnable-only graph performs far better than priori graph, yet miss plenty of useful knowledge. As shown in 1(a), compared to (c), it lacks some key edges(in red boxes); 3) utilizing both prior and learnable knowledge by simply add them up shows small gain in performances, but is inferior to our carefully designed convex dynamic pattern, since the fixed parameters lacks the ability to weight the importance of the above two matrix according to their distributions. Overall, our modules shows great potential to boost the prediction performance as well as can be easily employed in different graph neural networks.

Model Agnostic Analysis: Besides, RGSL can be generalized to different GNNs. As Tab 3 shows, RGSL added on STGCN also significantly increases the metrics (relative improvements +4.49% MAE, +4.82% RMSE, +4.41%MAPE ). Both the LM3 and RGG modules do not have excrescent requirements for graph or graph-related tasks, and can be easily applied and extended to related tasks.

4 RelatedWork

Multi-variates time-series forecasting has been widely studied, and there are exhaustive surveys and thesis which can be referred to [Yin et al., 2021; Ting, 2021]. Here we focus more on the recent advances of deep neural network. The deep learning methods treat spatio-temporal relations mainly utilizing RNN based [Guo et al., 2020; Pan et al., 2020], GNN

based [Yu et al., 2018; Guo et al., 2019; Song et al., 2020b; Bai et al., 2020; Chen et al., 2021b], and CNN based [Wu et al., 2020] networks, where CNN lacks generalization since the irregularity of input. In detailed RNN based methods, attention mechanism [Jin et al., 2020; Li and Moura, 2020; Zhang et al., 2020a] is frequently applied to model temporal correlation, while the simpler FNN-based approach is used in [Wei et al., 2019; Song et al., 2020a; Cao et al., 2020; Chen et al., 2020; Zhang et al., 2020b] can also show competitive results. However, these RNN, attention or FNN mechanism shows deficiency in performance because of their ability to corelates and interacts spatial and temporal information. Apart from capturing temporal dependency with NN, other techniques that have also been combined with GNNs include autoregression [Lee et al., 2019], and Kalman filters.

In GNN based methods, there are multiple ways to construct adjacent matrix, which can be split into Connection Matrix [Song et al., 2020a], Distance Matrix [Li et al., 2018], Similarity Matrix [Lv et al., 2020] and Dynamic Matrix. However, these methods discard the correlation between prior knowledge and learned re-allocate embeddings. ASTGCN [Guo et al., 2019] utilizes spatial-temporal attention and spatial-temporal convolution to model adjacent spatialtemporal relationship, and the input temporal information is from three different granularity. AGCRN [Bai et al., 2020] captures fine-grained spatial and temporal correlations in traffic series automatically based on the two modules and recurrent networks, but lacks interpretability in visualization. STNorm [Deng et al., 2021] propose temporal and spatial normalization and separately refine the high-frequency component and the local component underlying the raw data.

5 Conclusion

In this paper, we propose a novel model RGSL which contains a laplacian matrix mix-up module to automatically discover implicit time-series pattern and fuse both the explicit graph and implicit graph in a dynamic convex fashion. Furthermore, we argue that graph regularization which improves graph interpretability also helps to capture the complicated correlation more efficiently. Thus we propose a RGG module which is easy to add-on and has similar property to Dropout. Experiments on three real-world flow datasets show our model RGSL enhances the state-of-the-art performances by a large margin. Since the proposed LM3 module and RGG module are general and do not have additional constraints on task, future works and software projects can be apply these two to various graph-based tasks which are not confined to time series forecasting.

Acknowledgments

Yan Huang and Liang Wang were jointly supported by National Key Research and Development Program of China Grant No. 2018AAA0100400, National Natural Science Foundation of China (61721004, U1803261, and 61976132), Beijing Nova Program (Z201100006820079), Key Research Program of Frontier Sciences CAS Grant No. ZDBS-LYJSC032, CAS-AIR.