Year: 2021

Abstract:
Traffic forecasting is a challenging problem due to complex road networks and sudden speed changes caused by various events on roads. Several models have been proposed to solve this challenging problem, with a focus on learning the spatio-temporal dependencies of roads. In this work, we propose a new perspective for converting the forecasting problem into a pattern-matching task, assuming that large traffic data can be represented by a set of patterns. To evaluate the validity of this new perspective, we design a novel traffic forecasting model called Pattern-Matching Memory Networks (PM-MemNet), which learns to match input data to representative patterns with a key-value memory structure. We first extract and cluster representative traffic patterns that serve as keys in the memory. Then, by matching the extracted keys and inputs, PM-MemNet acquires the necessary information on existing traffic patterns from the memory and uses it for forecasting. To model the spatio-temporal correlation of traffic, we proposed a novel memory architecture, GCMem, which integrates attention and graph convolution. The experimental results indicate that PM-MemNet is more accurate than state-of-the-art models, such as Graph WaveNet, with higher responsiveness. We also present a qualitative analysis describing how PM-MemNet works and achieves higher accuracy when road speed changes rapidly.

heading: 1 INTRODUCTION
text: Traffic forecasting is a challenging problem due to complex road networks, varying patterns in the data, and intertwined dependencies among models. This implies that prediction methods should not only find intrinsic spatio-temporal dependencies among many roads, but also quickly respond to irregular congestion and various traffic patterns (Lee et al., 2020) caused by external factors, such as accidents or weather conditions (Vlahogianni et al., 2014; Li & Shahabi, 2018; Xie et al., 2020; Jiang & Luo, 2021). To resolve these challenges and successfully predict traffic conditions, many deep learning models have been proposed. Examples include the models with graph convolutional neural networks (GCNs) (Bruna et al., 2014) and recurrent neural networks (RNNs) (Siegelmann & Sontag, 1991), which outperform conventional statistical methods such as autoregressive integrated moving average (ARIMA) (Vlahogianni et al., 2014; Li et al., 2018). Attention-based models, such as GMAN (Zheng et al., 2020), have also been explored to better handle complex spatio-temporal dependency of traffic data. Graph WaveNet (Wu et al., 2019) adopts a diffusion process with a self-learning adjacency matrix and dilated convolutional neural networks (CNNs), achieving stateof-the-art performance. Although effective, existing models have a weakness in that they do not accurately forecast when conditions are abruptly changed (e.g., rush hours and accidents).
In this work, we aim to design a novel method for modeling the spatio-temporal dependencies of roads and to improve forecasting performance. To achieve this goal, we first extract representative traffic patterns from historical traffic data, as we find that there are similar traffic patterns among roads, and a set of traffic patterns can be generalized for roads with similar spatio-temporal features. Figure 1 shows the example speed patterns (left, 90-minute window) that we extract from many different roads and a representative traffic pattern (right time series). With the representative patterns, we transform the conventional forecasting problem into a pattern-matching task to find out which pattern would be the best match for the given spatio-temporal features to predict future traffic
conditions. With insights from the huge success of neural memory networks in natural language processing and machine translation (Weston et al., 2015; Sukhbaatar et al., 2015; Kaiser et al., 2017; Madotto et al., 2018), we design graph convolutional memory networks called GCMem to manage representative patterns in spatio-temporal perspective. Lastly, we design PM-MemNet, which utilizes representative patterns from GCMem for traffic forecasting. PM-MemNet consists of an encoder and a decoder. The encoder consists of temporal embedding with stacked GCMem, which generates meaningful representations via memorization, and the decoder is composed of a gated recurrent unit (GRU) with GCMem. We compare PM-MemNet to existing state-of-the-art models and find that PM-MemNet outperforms existing models. We also present a qualitative analysis in which we further investigate the strengths of PM-MemNet in managing a traffic pattern where high responsiveness of a model to abrupt speed changes is desired for accurate forecasting.
The experimental results indicate that PM-MemNet achieves state-of-the-art performance, especially in long-term prediction, compared to existing deep learning models. To further investigate the characteristics of PM-MemNet, we conduct an ablation study with various decoder architectures and find that PM-MemNet demonstrates the best performance. We also investigate how the number of representative patterns affects model performance. Finally, we discuss the limitations of this work and future directions for neural memory networks in the traffic forecasting domain.
The contributions of this work include: (1) computing representative traffic patterns of roads, (2) design of GCMem to manage the representative patterns, (3) design of PM-MemNet that matches and uses the most appropriate patterns from GCMem for traffic forecasting, (4) evaluation of PMMemNet compared to state-of-the-art models, (5) qualitative analysis to identify the strengths of PM-MemNet, and (6) discussion of limitations and future research directions.

heading: 2 RELATED WORK

heading: 2.1 TRAFFIC FORECASTING
text: Deep learning models achieve huge success by effectively capturing spatio-temporal features in traffic forecasting tasks. Past studies ahve shown that RNN-based models outperform conventional temporal modeling approaches, such as ARIMA and support vector regression (SVR) (Vlahogianni et al., 2014; Li et al., 2018). More recently, many studies have demonstrated that attention-based models (Zheng et al., 2020; Park et al., 2020) and CNNs (Yu et al., 2018; Wu et al., 2019) record better performance in long-term period prediction tasks, compared to RNN-based models. In terms of spatial modeling, Zhang et al. (2016) propose a CNN-based spatial modeling method for Euclidean space. Another line of modeling methods, such as GCNs, using graph structures for managing complex road networks also become popular. However, there are difficulties in using GCNs in
the modeling process, such as the need to build an adjacency matrix and the dependence of GCNs on invariant connectivity in the adjacency matrix. To overcome these difficulties, a set of approaches, such as graph attention models (GATs), have been proposed to dynamically calculate edge importance (Park et al., 2020). GWNet (Wu et al., 2019) adopts a self-adaptive adjacency matrix to capture hidden spatial dependencies in training. Although effective, forecasting models still suffer from inaccurate predictions due to abruptly changing road speeds and instability, with lagging patterns in long-term periods. To address these challenges, we build, save, and retrieve representative traffic patterns for predicting speed rather than directly forecasting with an input sequence.

heading: 2.2 NEURAL MEMORY NETWORKS
text: neural memory networks are widely used for sequence-to-sequence modeling in the natural language processing and machine translation domains. Memory networks are first proposed by Weston et al. (2015) to answer a query more precisely even for large datasets with long-term memory. Memory networks perform read and write operations for given input queries. Sukhbaatar et al. (2015) introduce end-to-end memory networks that can update memory in an end-to-end manner. Through the end-to-end memory learning, models can be easily applied to realistic settings. Furthermore, by using adjacent weight tying, they can achieve recurrent characteristics that can enhance generalization. Kaiser et al. (2017) propose novel memory networks that can be utilized in various domains where life-long one-shot learning is needed. Madotto et al. (2018) also introduce Mem2Seq, which integrates the multi-hop attention mechanism with memory networks. In our work, we utilize memory networks for traffic pattern modeling due to the similarity of the tasks and develop novel graph convolutional memory networks called GCMem to better model the spatio-temporal correlation of the given traffic patterns.

heading: 3 PROPOSED APPROACH
text: In this section, we define the traffic forecasting problem, describe how we extract key patterns in the traffic data that serve as keys, and introduce our model, PM-MemNet.

heading: 3.1 PROBLEM SETTING
text: To handle the spatial relationships of roads, we utilize a road network graph. We define a road network graph as G = (V, E ,A), where V is a set of all different nodes with |V| = N , E is a set of edges representing the connectivity between nodes, andA ∈ RN×N is a weighted adjacency matrix that contains the connectivity and edge weight information. An edge weight is calculated based on the distance and direction of the edge between two connected nodes. As used in the previous approaches (Li et al., 2018; Wu et al., 2019; Zheng et al., 2020; Park et al., 2020), we calculate
edge weights via the Gaussian kernel as follows: Ai,j = exp ( − dist 2 ij
σ2
) , where distij is the distance
between node i and node j and σ is the standard deviation of the distances.
Prior research has formulated a traffic forecasting problem as a simple spatio-temporal data prediction problem (Li et al., 2018; Wu et al., 2019; Zheng et al., 2020; Park et al., 2020) aiming to predict values in the next T time steps using previous T ′ historical traffic data and an adjacency matrix. Traffic data at time t is represented by a graph signal matrix, XtG ∈ RN×din , where din is the number of features, such as speed, flow, and time of the day. In summary, the goal of the previous work is to learn a mapping function f(·) to directly predict future T graph signals from T ′ historical input graph signals: [
XG (t−T ′+1), · · · , XG(t) ] f(·)−−→ [XG(t+1), · · · , XG(t+T )] The goal of this study is different from previous work in that we aim to predict future traffic speeds from patterned data, instead of utilizing input XG directly. We denote P ⊂ RT ′ as a set of representative traffic patterns, p ∈ P as one traffic pattern in P, and d : X × P → [0,∞) as a distance function for pattern matching. Detailed information about traffic pattern extraction will be discussed in the next subsection. Our problem is to train the mapping function f(·) as follows:[
XG (t−T ′+1), · · · , XG(t) ] d(·),k−NN−−−−−−−→ [P t1 , . . . , P tN] f(·)−−→ [XG(t+1), · · · , XG(t+T )],
where P ti = {p1, . . . , pk} is a set of k-nearest neighboring traffic patterns of node i in time t, with a distance function d. Note that pj is the j-th nearest neighbor pattern.

heading: 3.2 KEY EXTRACTION FROM TRAFFIC PATTERNS
text: Analyzing the traffic data, we find that the data has repeating patterns. In traffic data, the leading and trailing patterns have a high correlation, even during short-term periods. To take advantage of these findings, in our model, we build a representative pattern set, P. First, from historical data, we compute an average daily pattern, which consists of 288 speed data points (total 24 hours with 5- minute intervals) for each vertex v ∈ V . We then extract pattern p by slicing the daily patterns with a given window size T ′, as shown in Figure 2 (a). At this stage, |P| = N ×b 288T ′ c. After we collect the patterns, we investigate similarity distribution of the extracted pattern set, P, via cosine similarity (Figure 2 (b)) and find that the pattern set P has a biased distribution with too many similar patterns (i.e., class imbalance). Since such class imbalance causes memory ineffectiveness in accurate memory retrieval and gives biased training results, we use clustering-based undersampling (Lin et al., 2017) with cosine similarity. For example, if pattern p and pattern p′ have a cosine similarity larger than δ, they are in same cluster. We utilize the center of each cluster as a representative pattern of that cluster. After undersampling by clustering, we have a balanced and representative pattern set, P, as shown in Figure 2 (c), which we use as keys for memory access. Table 2 presents the effect of different δ and |P| on forecasting performance.

heading: 3.3 NEURAL MEMORY ARCHITECTURE
text: Conventionally, memory networks have used the attention mechanism for memory units to enhance memory reference performance, but this attention-only approach cannot effectively capture spatial dependencies among roads. To address this issue, we design a new memory architecture, GCMem (Figure 3 (b)), which integrates multi-layer memory with the attention mechanism (Madotto et al., 2018) and graph convolution (Bruna et al., 2014). By using GCMem, a model can capture both pattern-level attention and graph-aware information sharing via GCNs.
To effectively handle representative patterns from a spatio-temporal perspective, we utilize several techniques. First, we use a modified version of the adjacent weight tying technique in MemNN (Sukhbaatar et al., 2015; Madotto et al., 2018), which has been widely used for sentence memorization and connection searches between query and memorized sentences. Sukhbaatar et al. (2015); Madotto et al. (2018) propose the technique to capture information from memorized sentences by making use of sentence-level attention. However, their methodology only learns pattern similarity and cannot handle spatial dependency. Using the same method in traffic forecasting is insufficient since handling a graph structure is essential for building spatial dependencies of roads. In order to consider the graph structure while maintaining the original sentence-level attention score, we use an adjacency matrix, a learnable adaptive matrix, and attention scores for the GCNs. By maintaining pattern-level attention, the model takes advantage of both pattern-level information sharing
and adjacent weight tying (Madotto et al., 2018). As a result, adjacent memory cells can effectively retain attention mechanisms while considering a graph structure.
Figure 3 (a) and (b) shows PM-MemNet and our proposed graph convolution memory architecture. The memories for the GCMem are embedding matrices M = {M1, . . . ,ML+1}, where Ml ∈ R|P|×dh . For memory reference, we utilize pattern set P, which contains the extracted traffic patterns (in Section 3.2) and k-Nearest Neighbor (k-NN) with distance function, d(·). For each input traffic data Xi ∈ RT
′×din in node i, based on k-nearest patterns and the distance function, we build a representative memory M li as follows:
M li = k∑ j=1 Softmax(−dj)mlj , (1)
where mlj = M l(pj) is the memory context for pj and layer l, dj = g(Xi, pj), and Softmax(zi) = ezi/ ∑ j e zj . We summarize our representative memory selection process in Figure 3 (c).
After calculating representative memory, GCMem calculates hidden state hl ∈ RN×dh with previous hidden state hl−1 and representative memory M l and M l+1 (Figure 3 (b)). For each representative memory M lj , PM-MemNet calculates pattern-level attention scores, α l i,j as follows:
αli,j = Softmax( hl−1i (M l j) >
√ dh
), (2)
where hl−1i ∈ Rdh is the previous hidden state of node i. We denote an attention matrix as Cl ∈ RN×N , where αli,j is the entry in the i-th row and j-th column of Cl. Then, given memory unit M l+1 ∈ RN×dh for the next layer l + 1, we calculate output feature, ol with graph convolution as shown below:
ol = h∑ i ( W lA,iM l+1A+W l Ã,i M l+1Ã+W lC,iM l+1Cl ) , (3)
where A ∈ RN×N is an adjacency matrix and Ã = Softmax(ReLU(E1E>2 )) is a learnable matrix, which captures hidden spatio-temporal connections (Wu et al., 2019; Shi et al., 2019). E1, E2 ∈ RN×dh are learnable node embedding vectors and W ∈ Rdh is a learnable matrix. We use ReLU as an activation function. Then, we update hidden states by hl = hl−1 + ol. Before we update the hidden states, we apply batch normalization on ol.

heading: 3.4 ENCODER ARCHITECTURE
text: The left side of Figure 3 (a) shows the proposed encoder architecture. PM-MemNet handles traffic patterns and their corresponding memories. Although the patterns in the memory provide enough
information for training, there are other types of data that can also be used for prediction. For example, different roads have their own patterns that may not be captured in advance (e.g., the unique periodicity of roads around an industry complex (Lee et al., 2020)). In addition, there would be some noise and anomalous patterns due to various events (e.g., accidents), which are not encoded when patterns are grouped. As such, we provide embedding for the time (i.e., emb) and noise (i.e., Ni) that the encoder uses to generate input query h0 for GCMem. Specifically, for the time series T = [t−T ′+1, . . . , t] and noiseNi = Xi−p1, we calculate its representation, h0i as shown below:
h0i = emb(T ) +WnNi, (4)
where emb and Wn represent a learnable embedding for the time of day and a learnable matrix, respectively. Note that emb(T ) ∈ Rdh and Wn ∈ Rdh×T PM-MemNet updates h0i using L-layer GCMem. We use the output of the encoder hL ∈ RN×dh as an initial hidden state in the decoder.

heading: 3.5 DECODER ARCHITECTURE
text: As shown in Figure 3 (a), we build our decoder architecture using single layer GRU, followed by the L-stacked GCMem. For each t step, the decoder predicts the value at time step t using the previous prediction ŷt−1 and GRU hidden state h̃t−1. Initially, ŷ0 is zero matrix and h̃0 is encoder hidden state hL. The hidden states from the GRU will be an input for the L-stacked GCMem. Similar to our encoder architecture, GCMem updates hidden states with attention and GCNs. Instead of using updated hidden states for prediction directly, we utilize layer-level self-attention in the decoder. Specifically, for each GCMem layer l and node i, we calculate energy, ei,l using the previous hidden state hl−1i and memory context M l i as shown below:
ei,l = (hl−1i )(M l iW l)>√ dh , (5)
where dh is the hidden size and W l ∈ mathbbRdh×dh is learnable matrix. Then, with the output feature oli of each layer l and node i, we can predict ŷ t i as:
ŷti = L∑ l αi,lo l iWproj , (6)
where Wproj ∈ Rdh×dout is a projection layer and αi,l = Softmax(ei,l). Note that h0 is equivalent to a hidden state of a GRU cell, h̃t. Using layer-level attention, PM-MemNet utilizes information from each layer more effectively.

heading: 4 EVALUATION
text: In this section, we explain the experiments conducted to compare PM-MemNet to existing models in terms of accuracy. We use two datasets for the experiment–METR-LA and NAVER-Seoul. METR-LA contains 4-month speed data from 207 sensors of Los Angeles highways (Li et al., 2018). NAVER-Seoul has 3-month speed data collected from 774 links in Seoul, Korea. As NAVER-Seoul data covered the main arterial roads in Seoul, it can be considered a more difficult dataset with many abruptly changing speed patterns compared to METR-LA data. Both datasets have five-minute interval speeds and timestamps. Before training the PM-MemNet, we have filled out missing values using historical data and applied z-score normalization. We use 70% of the data for training, 10% for validation, and the rest for evaluation, as Li et al. (2018); Wu et al. (2019); Zheng et al. (2020) have done in their work.

heading: 4.1 EXPERIMENTAL SETUP
text: In our experiment, we use 18 sequence data points as a model input (T ′ = 18, one and a half hours) and predict the next 18 sequences. For the k-NN, we utilize the cosine similarity function for the similarity measurement and set k = 3. To extract P, we utilize the training dataset and initialize parameters and embedding using Xavier initialization. After performing a greedy search among dh = [16, 32, 64, 128], L = [1, 2, 3, 4], and various |P| values, we set dh as 128, L as 3, and
|P| ≈ 100 with δ = 0.7 and 0.9 for NAVER-Seoul and METR-LA, respectively. Table 2 presents the experimental results with different memory and pattern sizes (i.e., |P|) We apply the Adam optimizer with a learning rate of 0.001 and use the mean absolute error (MAE) as a loss function.
We compare PM-MemNet to the following baseline models: (1) multilayer perceptron (MLP); (2) STGCN (Yu et al., 2018), which forecasts one future step using graph convolution and CNNs; (3) Graph Convolution Recurrent Neural Network (GCRNN); (4) DCRNN (Li et al., 2018), a sequenceto-sequence model that combines diffusion convolution in the gated recurrent unit; (5) ASTGCN (Guo et al., 2019), which integrates GCN, CNN, and spatial and temporal attention; (6) GraphWaveNet (GWNet) (Wu et al., 2019), which forecasts multiple steps at once by integrating graph convolution and dilated convolution; and (7) Graph Multi-Attention Network (GMAN) (Zheng et al., 2020) which integrates spatial and temporal attention with gated fusion mechanism. GMAN also predicts multiple steps at once. To allow detailed comparisons, we train the baseline models to forecast the next 90 minutes of speeds at 5-minute intervals, given the past 18 5-minute interval speed data points. We train the baseline models in an equivalent environment with PyTorch1 using the public source codes and settings provided by the authors. Detailed settings, including the hyperparameters, are available in Appendix A.1. To ease the performance comparison with previous work, we provide additional experimental results with a commonly used setting, where T ′ = T = 12, in Table 6 in Appendix. We also present a qualitative analysis of our method for NAVER-Seoul dataset in Appendix A.4

heading: 4.2 EXPERIMENTAL RESULTS
text: Table 1 displays the experimental results for NAVER-Seoul and METR-LA for the next 15 minutes, 30 minutes, 60 minutes, and 90 minutes using mean absolute error (MAE), mean absolute percentage error (MAPE), and root mean square error (RMSE). Note that Table 3 and Figure 5 in Appendix show more detailed experimental results and error information. As Table 1 shows, PM-MemNet achieves state-of-the-art performance for both datasets. Specifically, PM-MemNet yields the best performance in all intervals with NAVER-Seoul data, while it outperforms other models in the longterm prediction (i.e., 60 and 90 minutes) with METR-LA data.
In both datasets, we find interesting observations. First, RNN-based models perform better than other models for short term periods (i.e., 15 minutes), but they show a weakness for long-term periods. This problem occurs in sequence-to-sequence RNNs due to error accumulation caused by its auto-regressive property. Compared to the RNN-based models, PM-MemNet shows a lesser performance decrease, although it had decoder based on RNN architecture. This is because of GCMem
1https://pytorch.org
and pattern data, which make representations for traffic forecasting more robust than other methods. In the case of NAVER-Seoul, we observe that all models suffer from decreased accuracy due to more complicated urban traffic patterns and road networks than those in METR-LA. In spite of these difficulties, PM-MemNet proves its efficiency with representative traffic patterns and the memorization technique. This result strengthens our hypothesis that the traffic data used for traffic forecasting can be generalized with a small number of pattern even when the traffic data are complex and hard to forecast.
4.3 ABLATION STUDY
We further evaluate our approach by conducting ablation studies (Table 2, Table 5 in Appendix). First, we check whether GCMem can effectively model spatiotemporal relationships among road networks. To this end, we compare the performance of PM-MemNet to that of SimpleMem, a simplified version of PMMemNet in which the memory layer depends only on pattern-level attention and does not consider any graphbased relationship. By comparing PM-MemNet and SimpleMem, we observe that SimpleMem shows nearly 10% decrease in performance, which shows the importance of a graph structure in modeling traffic data. In the same context, according to Table 1 and Table 2, SimpleMem has lower accuracy than previous models, such as DCRNN, which considers a graph structure.
Next, we combine GCMem with various decoder architectures to investigate how the performance of GCMem changes with different decoder combinations. The results indicate that all decoder combinations achieve state-of-the-art performance for both NAVERSeoul and METR-LA datasets. This result implies that GCMem effectively learns representations, even with a
simple decoder architecture, such as single layer RNN. Also, from the perspective of error accumulation, we notice that PM-MemNet outperforms the CNN decoder even for the 90-minute prediction. In contrast, the one-layered RNN decoder shows a lower performance than the CNN decoder. However, when comparing the RNN decoder to existing RNN-based models, RNN decoder can predict more precisely for the long-term prediction. These results also show that GCMem is a robust solution for long-term dependency modeling. Modifying the GCMem layer depth, we discover that PM-
MemNet generates sufficiently accurate predictions with a single memory layer (i.e., PM-MemNet w/L=1). Although PM-MemNet needs a three-layered GCMem to achieve the highest accuracy, we can still consider deploying the model with a lightweight version while ensuring its state-of-the-art performance.
Next we analyze how different memory sizes (i.e., different pattern numbers) affect the performance. In this experiment, we set |P| as 3, 100, 2000, and 3000. Note that we set |P| as 3 to simulate an extreme case, where PM-MemNet has very rare memory space. Figure 4 shows the experimental results. We can observe that PM-MemNet records the best performance with 100 traffic patterns; attaching large |P| to a model does not always allow the best forecasting performance. We provide the time consumption of the models in Table 4 in Appendix.

heading: 5 LIMITATIONS, DISCUSSION, AND FUTURE DIRECTIONS
text: This work is the first attempt to design neural memory networks for traffic forecasting. Although effective, as shown in the evaluation results, there are limitations to this approach. First, we extract traffic patterns to memorize them in advance; however, it is possible that the extracted patterns are redundant, even after strict filtering. As such, there is need to find important patterns and optimize the number of memory slots. For example, a future study could investigate how to learn and extend the key space during the training phase (Kaiser et al., 2017). Second, the learning of embedding matrices in PM-MemNet proceeds only based on referred patterns. Because there are no further losses to optimize memory itself, patterns not referred to are not trained. This training imbalance among memories is of interest, as the model cannot generate meaningful representations from rare patterns. A future study may research not only how such a representation imbalance affects performance, but also design a loss function to reduce the representation gap between rare and frequent events. Third, we use cosine similarity in this work, but it may not be an optimal solution, since it causes mismatching with noisy traffic data. Also, the optimal window size for pattern matching remains to be addressed. A future study may focus on approaches to effectively compute the similarity of traffic patterns. Designing a learnable function for the distance measurement is one possible direction. Finally, we show that the model can effectively forecast traffic data with a small group of patterns. This implies a new research direction for comparing results and learning methods that work with sparse data, such as meta learning and few or zero shot learning (Kaiser et al., 2017).

heading: 6 CONCLUSION
text: In this work, we propose PM-MemNet, a novel traffic forecasting model with a graph convolutional memory architecture, called GCMem. By integrating GCNs and neural memory architectures, PMMemNet effectively captures both spatial and temporal dependency. By extracting and computing representative traffic patterns, we reduce the data space to a small group of patterns. The experimental results for METR-LA and NAVER-Seoul indicate that PM-MemNet outperforms state-of-theart models. It proves our hypothesis “accurate traffic forecasting can be achieved with a small set of representative patterns” is reasonable. We also demonstrate that PM-MemNet quickly responds to abruptly changing traffic patterns and achieves higher accuracy compared to the other models. Lastly, we discuss the limitations of this work and future research directions with the application of neural memory networks and a small set of patterns for traffic forecasting. In future work, we plan to conduct further experiments using PM-MemNet for different spatio-temporal domains and datasets to investigate whether the insights and lessons from this work can be generalized to other domains.

heading: A APPENDIX
text: A.1 DETAILED EXPERIMENTAL SETUP
MLP Multi-layer perceptron with two hidden layers; each layer contains 64 units and rectified linear unit (ReLU) activation.
STGCN Spatio-Temporal Graph Convolutional Networks (Yu et al., 2018). STGCN models spatial features using spectral-based graph convolution with Chebyshev polynomial approximation and temporal features using gated CNNs. In our experiment, like the original paper, we set STGCN with a graph convolution kernel sizeK = 3, temporal convolution kernel size ofKt = 3, and three layers with 64, 16, and 64 hidden units, respectively.
DCRNN Diffusion Convolutional Recurrent Neural Networks (Li et al., 2018). DCRNN is the model that integrates diffusion convolution with RNNs, especially the GRU. In our experiment, both encoder and decoder contain two recurrent layers with 64 hidden units and maximum steps of random walks set as 3 (i.e., K = 3).
GCRNN Graph Convolutional Recurrent Neural Networks. GCRNN is a variant of DCRNN that integrates simple bidirectional graph convolution and sequence-to-sequence architecture. Both encoder and decoder contain two recurrent layers with 64 hidden units and maximum steps of random walks set as 3 (i.e., K = 3).
ASTGCN Attention based Spatio-Temporal Graph Convolutional Networks (Guo et al., 2019). ASTGCN models spatio-temporal features by attention, GCNs, and CNNs. For the GCNs, ASTGCN utilizes spectral-based graph convolution with Chebyshev polynomials K = 3 and kernel size of CNNs Kt = 3. Furthermore, all layers have the same hidden unit size of 64.
GWNet Graph WaveNet (Wu et al., 2019). GWNet combines graph convolution and dilated causal convolution. In our experiment, to cover the input sequence length, we utilize 12 layers with dilation factors of 1, 2, 1, 2, . . . , 1, 2. Also, following original paper, we set the diffusion step K = 3 and E1, E2 ∈ RN×10. GMAN Graph Multi-Attention Network (Zheng et al., 2020). GMAN handles both spatial and temporal features using attention and pretrained node embedding. In our experiment, we utilize the same setting as the original paper, that is, three layers for both encoder and decoder with eight attention heads and 64 hidden units (8 hidden units per attention head).
PM-MemNet Pattern Matching Memory Networks. Both encoder and decoder have three GCMem layers with 128 hidden units and |P| ≈ 100. Note that the decoder also has one GRU cell before GCMem with 128 hidden units. For the k-NN, we utilize k = 3 and cosine similarity. Also, for the graph convolution, we set the diffusion step as K = 2.
In the experiment, we utilize the MAE loss function and Adam optimizer with a learning rate of 1e−3 for training. The learning rate reduces to 110 for every 10 epochs, starting at 30 epochs, until it reaches 1e−6. For each model, we trained 100 epochs, with an early termination by monitoring the validation error.
A.2 DETAILED RESULTS WITH 18-STEP INPUT AND OUTPUT SEQUENCES
A.3 DETAILED ABLATION STUDY RESULTS
A.4 QUALITATIVE EVALUATION
We present a qualitative analysis using the NAVER-Seoul dataset, which contains a complex road network and the dynamic traffic conditions of urban areas. In this analysis, we evaluate whether our approach effectively patterned traffic data for the traffic forecasting problem. If the approach is valid, we expect PM-MemNet to be more accurate in predicting difficult trailing patterns due to the high correlation between leading and trailing patterns. To verify our expectations, we visualize the long-term traffic prediction results, as shown in Figure 6 (top), where PM-MemNet predicts the end of congestion at 12:00 PM (B) more accurately. Also, in 7:00 AM (A), PM-MemNet quickly catches up on the unexpected peak speed (this continues for about 30 minutes, and PM-MemNet efficiently catches up within 15 minutes). From Figure 6 (bottom), we can see that PM-MemNet predicts a speed drop and its recovery more accurately compared to the other models. For example, GMAN and GWNet predict the speed drop earlier than the actual speed drop, and DCRNN predicts the speed drop later than the real speed drop, as shown in 6 (C). However, PM-MemNet predicts the occurrence of slowdowns on time, even for long-term traffic prediction (D). Overall, with representative traffic patterns and memorization, PM-MemNet effectively handles abruptly changing traffic conditions, even for long-term predictions.
Next, we analyze how PM-MemNet effectively matches input patterns with memorized patterns. Figure 7 presents three examples, each of which has two time-series lines. The red line denotes the current time step t. Before the current time step t, The blue and orange line means input and corresponding matched pattern, respectively. After the current time step t, The blue and orange line means ground truth and prediction results, respectively. In each example, we find that the model effectively retrieves a memorized pattern that matched the input sequence well for prediction. Note that all examples show how PM-MemNet operates for difficult roads and time with rapid speed drops.
A.5 EXPERIMENT WITH 12 SEQUENCE SETTING

Review summaries:
This paper studies the traffic forecasting problem and proposes to conduct prediction by pattern matching. Authors first extract key patterns from the historical data in an offline manner and then fetch the patterns for each time series with a distance function (e.g., cosine similarity). Then, the patterns of different nodes are interacted with GCN to get node representation.

This paper explores a new direction of model design in traffic forecasting tasks. It proposes a neural memory module to model the spatio-temporal traffic data and designs a new traffic forecasting model based on the memory module. Experiments on a few public datasets demonstrate the effectiveness of the proposed scheme.