{'fraction_non_alphanumeric': 0.034703528555838484, 'fraction_numerical': 0.007821025827573663, 'mean_word_length': 5.002401746724891, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ODformer: Spatial-Temporal Transformers for Long Sequence Origin-Destination Matrix Forecasting Against Cross Application Scenario

Origin-Destination (OD) matrices record directional flow data between pairs of OD regions. The intricate spatiotemporal dependency in the matrices makes the OD matrix forecasting (ODMF) problem not only intractable but also non-trivial. However, most of the related methods are designed for very short sequence time series forecasting in specific application scenarios, which cannot meet the requirements of the variation in scenarios and forecasting length of practical applications. To address these issues, we propose a Transformer-like model named ODformer, with two salient characteristics: (i) the novel OD Attention mechanism, which captures special spatial dependencies between OD pairs of the same origin (destination), greatly improves the ability of the model to predict cross-application scenarios after combining with 2D-GCN that captures spatial dependencies between OD regions. (ii) a PeriodSparse Self-attention that effectively forecasts long sequence OD matrix series while adapting to the periodic differences in different scenarios. Generous experiments in three application backgrounds (i.e., transportation traffic, IP backbone network traffic, crowd flow) show our method outperforms the state-of-the-art methods.


Introduction
Origin-Destination (OD) matrices are widely used to provide location-based services (LBSs) or to aid in data mining and discovery in various scenarios related to geographic information. Specifically, OD matrices help to estimate travel expense [1] and schedule trips, so Google Maps provide OD matrices for better developing LBSs. From a broader perspective, OD matrices support various data analysis tasks by introducing geographic information. For instance, the COVID-19 spread in a country could be forecasted according to the human movements OD matrix [2]. Moreover, internet traffic OD matrices show the potential to support IP backbone network management [3], and internet resource allocation [4]. In a word, the specific meaning of data stream is diverse between different application backgrounds, but we can still unify them into one cross-scenario application. Generally speaking, OD matrices record every traffic flow from origin regions to destination regions which are geographically divided. The regions of OD matrices could be city spans, country spans, or even entire continents spans. Each element (i, j) in OD matrices is an OD pair that represents a certain traffic flow from region i to region j against a diverse background, as illustrated in Figure 1.
Here, we consider the Origin-Destination matrix forecasting problem (ODMF) in which the elements represent traffic data for different application backgrounds (e.g., transportation traffic, IP backbone network traffic). There are many application scenarios for ODMF results. For example, in the field of transportation, it can be used to plan the itinerary in advance, the allocation of traffic resources, and in the field of IP network, it can be used to help efficiently complete tasks such as network planning or operation and maintenance.
Existing methods are designed against exceedingly fixed application backgrounds and under limited problem settings. On the one hand, those methods are specific to a single application [5,2,6], thus, all the algorithm details intend to achieve the best performance on a single application scenario which leads to poor portability. Further, they are invalid for revealing the intrinsic spatial-temporal features in OD matrix-type data across different application scenarios. On the other hand, many methods [7,8,9] design the experiment setting just to fulfill literally excellent results but ignore the actual demands of ODMF, such as long sequence time-series forecasting (LSTF). As the sampling interval is around 5 to 20 minutes in most OD matrix datasets, existing methods only predict the next several or even one timestep, which means predicting the next several minute's OD matrices. For resource allocation or another downstream task, this kind of prediction goes for nothing in a realistic application. Therefore, we focus on the long sequence ODMF problem, which could be defined as follows: in multiple scenarios, based on OD matrices at several historical timesteps, we predict OD matrices at longer future timesteps, illustrated in Figure 2. To address the above problems, we present a spatial-temporal transformer (ODformer) for long sequence OD matrices forecasting. To the best of our knowledge, it is the first time to introduce the transformer to the ODMF problem, meanwhile with targeted improvements to accommodate the problem. We propose a more general spatial dependency module that consists of the OD Attention mechanism and the 2D graph neural network, which captures spatial dependencies in multiple scenarios. Further, we redesign the self-attention mechanism of the transformer named as PeriodSparse Self-attention to reduce the computational complexity of the long-sequence prediction tasks, while adapting to time series with diverse features from different scenarios. The contribution of this paper are summarized as follows: • ODformer is the first Transformer-like model for the ODMF problem. Meanwhile, for the first time, it crosses multiple scenarios in ODMF, covering three real-world application scenarios: transportation traffic, crowd flow, and IP backbone network traffic.
• We propose OD Attention mechanism to mine the specialized spatial dependency between OD pairs of the same origin (destination), which is dramatically different from existing ODMF methods (i.e., merely considering the topological correlation between OD regions). Based on this, we achieve significant improvement in capturing spatialtemporal dependency in various application scenarios.
• To support long sequence forecasting, we propose Peri-odSparse Self-attention mechanism to capture long-range temporal correlation by achieving sparse attention with O(L ln L) time complexity and adapting to periodicity in different scenarios.
In the transportation traffic forecasting scenario, the data reveal the highest relationships with the geographic factors. Thus the point is how to capture spatial dependency. The direct idea is to transfer the 2D convolution to the spatial domain, and extract the spatial dependency in a way similar to processing pictures. For instance, STGCN [8] formulates the traffic spatialtemporal prediction task on graph structures. MDL [17] designs two sophisticated models for predicting node flow and edge flow, respectively, based on fully convolutional networks to integrate transportation geographic factors. Despite convolutional neural networks(CNNs) could capture simple adjacent dependency between regions, the depth topological relationship between geographical regions is different from that in Euclidean space extracted by CNN. With the proposal of Graph Neural Network (GCN) [18], some graph-based models [8,5], capture the topological information to forecast vehicle traffic flow between regions by employing GCNs that work in a noneuclidean space. In summary, the existing methods in the background of transportation traffic mainly focus on capturing spatial dependency by extracting the topological adjacent information.
In the crowd flow forecasting scenario, the available data reveal different features of transportation background. The crowd data [13] is usually collected from smart devices carried by humans that provide GPS information. In this case, the crowd data is more fine-grained and shows less relevance to road traffic structure. Due to the more complex spatial dependency, merely depending on geographic adjacency is far from enough, OD-CRN [2] proposes the Dynamic Graph Constructor to capture highly temporal-dependent relationships between OD regions.
In the IP backbone network traffic forecasting scenario, the spatial dependency varies from the aforementioned. As the topology structures of IP networks consist of artificially set network nodes, the spatial dependency is comparatively irrelevant to natural geographic factors. Most existing methods [14,16,7] treat the network traffic volumes between IP nodes as grid-like data, thus applying convolution neural networks to extract spatial patterns. MSTNN [15] simply transfers the graph-based method to the IP network data to try to capture the spatial dependency, just like in geography determined scenario, which ignores the particularity of artificial IP network nodes.

Long Sequence Time-series Forecasting
In the time-series forecasting problem, the ability to capture precise long-term dependency [19,20] between historical sequence and predicted sequence determines the availability degree against the real-world application. Long sequence time-series forecasting (LSTF) advocates a longer predicted sequence than historical [21].
The traditional sequence-to-sequence LSTF models mostly apply recurrent neural networks (RNNs) [22] such as LSTM [23] or GRU [24] to capture temporal patterns. The multilayered LSTM [23] maps the variable length input sequence to a vector of fixed dimensionality, then decodes the relatively long target sequence from the vector. And the RNN Encoder-Decoder [21] proposes a gated recursive convolutional neural network to avoid the model degrading extremely rapidly when dealing with relatively long sequences. But the above RNN methods perform ineffectiveness when the prediction sequence becomes longer, which is probably due to the intrinsic limitations of recurrent neural network architectures [25].
Inducement of attention mechanism to time series forecasting problem brings a chance to process long sequence. Dual-Stage Attention-Based Recurrent Neural Network [25,19] adaptively extracts relevant input features at each time step by referring to the previous encoder hidden state, then selects relevant encoder hidden states across all time steps. With the amelioration of canonical Transformer architecture [26] against localityagnostics and memory bottleneck [27], addressing the LSTF problem by transformers became possible. Autoformer [20] adopts the sparse versions of point-wise self-attention for long series efficiency, meanwhile settling down the information utilization bottleneck. Informer [28] designed a ProbSparse Selfattention mechanism, which achieves O(LlogL) in time complexity and memory usage.

Problem Definition
At first, we define several data forms that are crucial in the long sequence ODMF problem while trying our best to preserve generality.
As we consider the ODMF problem against diverse application scenarios, the raw data varies in forms which mostly consist of two types: traffic trajectories and traffic matrices. Definition 1. (Origin-Destination Pair and Origin-Destination Matrix): Typically, a trajectory(e.g. taxi trajectory, bus trajectory, human trajectory) is a time sequence while each timeslot contains a longitude-latitude coordinate that is denoted as: where each location l is represented by a longitude-latitude coordinate and t is the timestep. To obtain OD pairs, we segment each trajectory as follows: (1) where the trajectory is segmented to n OP pairs. o,d represent the origin and destination regions. For improving generality, we take the departure timeslot of each trajectory segment as the t n of the OD pairs, the approximation mainly due to (i) mostly, the trajectory segment time interval is less than the interval between OD matrices' timeslot. (ii) some trajectory data are the trip forms [5], which means the trajectory contains only one departure time and one arrival time.
In some cases, the raw data is in the form of a traffic matrix (i.e. a set of OD pairs [7,6]), which is even easier. After the division of the area into regions (i.e., districts in cities, provinces in countries, IP internet nodes), we could assign each OD pair to the elements in the OD matrix at timeslot T : The OD matrix is defined as M (T ) ∈ R N×N ×F , where the first two dimensions range over the origin and destination regions (i.e. OR, DR). The last dimension is denoted as the feature of each OP pair that in most cases is a single scalar, but for the sake of particular cases (e.g. multiple features [5]), we reserve that dimension.
Definition 2. (long sequence ODMF): After the above process, we have the input (e.i. the historical sequence at length I): The definitions of "long sequence" differ in different long sequence time-series forecasting methods. The "long sequence" in this paper has two meanings: (i) O is significantly longer than I as primary LSTF methods [23,28,20] encourage. (ii) I is relatively longer than most settings in other methods [2,8,7].

Overall Architecture
As shown in Figure 3, we capture the spatial dependency before applying the attention mechanism in the temporal dimension. In each spatial dependency module, we apply the 2D-GNN and OD Attention mechanism separately to capture spatial dependency upon different aspect (i.e., the adjacent relationships between regions and intrinsic dependency among the OD pairs which shares the same origin or destination). The output of the spatial dependency module is the aggregated results of the above two by the spatial share coefficient α, which varies according to different datasets. To complete sparse sampling for the two sparse attention mechanisms (i.e., OD Attention and PeriodSparse Self-attention), Periodicity Extractor dynamically compute the period sets with k periods based on the output of the spatial dependency module. In this way, the output of the encoder contains both the spatial and temporal dependency of the OD matrix sequence, and finally, we complete the cross attention calculation together with the decoder.

Spatial Dependency
The spatial dependencies in different scenarios are quite different. For example, in transportation traffic, the spatial dependency is strongly correlated with geographic information, while in the IP network, the spatial dependencies are more manifested in the relationship between OD pairs. Based on this, we propose a spatial dependency module that combines two spatial dependencies mechanisms (i.e, OD Attention for dependencies between OD pairs and 2D-GCN for geographic dependencies between OD regions) to meet the needs of the model across scenarios: are the output of 2D-GCN and OD Attention. The shares of the two spatial dependencies are dynamically adjusted by the spatial share coefficient α according to different application scenarios.

Origin-Destination (OD) Attention Mechanism:
Previous works [5,2,6,15] capture the spatial correlation between origin regions or destination regions, but they roughly take all the OD pairs from the same origin or destination as the same while ignoring the dependency between OD pairs from the same regions. Inspired by the spatial attention mechanism [29], we propose the OD Attention mechanism to capture the dependencies between OD pairs of the same origin (destination). At timestep T , the OD matrix: M T ∈ R N×N ×F could be denoted as the origin vector: To avoid the quadratic time complexity on the region's number of the canonical self-attention [30], which significantly restrains the capability in LSTF, here we propose a spatial sparse self-attention mechanism.
(1) Sparse Self-attention:. The brief strategy is to select the dominant query vector that contributes the most information. We apply the Shannon Entropy [31] to select the one with the smallest value (e.g. the Shannon Entropy of uniform distribution is the highest, and the more unlike the query vector and uniform distribution, the better. Since the uniform distribution is to assign the even importance to each element, which is meaningless). Take the origin attention as an example, the i-th query's attention to all the keys is defined in a probability form: p k j | q i = e k(q i ,k j ) / N j=1 e k(q i ,k j ) , where k q i , k j is the exponential kernel: exp each query i is defined below: According to the I(q i ), we choose the top u smallest query vectors as the dominant vector to attend the attention computation and fill other elements with zeros. To limit time consumption, we update the dominant query vector every P max (the largest P k from the period sets that will be illustrated next section) timesteps. Meanwhile, set u = ln N, thus the total time complexity of OD Attention is O (N ln N). The sparse query vectors from X T , Y T is denoted as : X T W, Y T W.
(2) Origin Attention:. We perform the self-attention within the origin vectors to capture the dependencies between OD pairs derived from the same destination regions, the origin attention coefficients computes at below: where W 1 , W 2 , W 3 ∈ R N×N×N are learnable parameter matrices, σ is the activation function. Equation 6 is meant to normalize the origin attention coefficient within each region. The element Ω i,i in the attention matrix reveals the relevance level between origin region i to another origin region i .
(3) Destination Attention:. In the almost same process, we symmetric compute the destination attention coefficient on top of Y T and Y T : At last, we apply the origin attention and destination attention matrix to the OD matrix: M A T = Ω T M T ∆ T . Therefore, each element in the OD matrices is dynamically given the impact of the elements from the same origin or destination regions as illustrated in Figure 4b.

2D Graph Convolution Network:
Besides the intrinsic dependency between OD pairs, the topological relationship among diverse OD regions still plays a large or small role according to the different application scenarios. In ODMF problems, graph convolution neural networks (GCNs) have wildly used to study the connectivity and globality based on topology graphs of regions.
Here, we adopt MGCNN [32] to capture the above relationships, which is an extended two-dimensional transformation of the GCN [33] with Chebyshev polynomial approximation.
where L origin or L destination is the Laplacian matrix obtained from L = I − D −1/2 AD −1/2 , D is the degree matrix, I is the identity matrix. is the hidden state of layer l while H (0) is the OD matrix. After the 2D-GCN operation, we get the OD matrices: M G T in Which the neighbor information propagates K hops between origin regions or destination regions.

Temporal Dependency
Long sequence forecasting of OD matrices mainly faces two challenges: (i) the intricate temporal pattern across the OD matrices. (ii) computation efficiency, which is even more matter due to the data scale of the OD matrices. Thus, we propose the Period Sparse Self-attention, which targets the above issue that captures intrinsic temporal dependency and reduces computation consumption at the same time. However, the periodicity in the differences scenario dataset differs a lot (e.g. the sampling interval is 15mins in the GÉANT dataset while 1 day in the Japan Human Trajectory dataset). For generality against different scenarios and to capture deep temporal dependency, we propose the Periodicity Extractor to adaptively give the period set: P = {P 1 , · · · , P k } of the inputs sequence.

Periodicity Extractor:
For the purpose of adaptively extracting the period length of different datasets properly, inspired by STL [34], we filter the tendency component. Given an OD matrix sequence that has gone trough the spatial dependency module: we apply centered moving average (window size is MovAvr win )to get the tendency component, the remainder component is omitted for simplicity. For each sequence of length L: S T (T is the last timeslot ), we adopt the Auto-Correlation Mechanism [20] to evaluate the chance of periodicity being P based on it's periodicity component:Ŝ T .
where RŜ T (P) is the time-delay similarity betweenŜ T and its P lag seriesŜ T −P that could be calculated by Fast Fourier Transforms (FFT) [35]. Topk(·) meant to get the periods of top k time-delay similarity.

PeriodSparse Self-attention:
Unlike the canonical self-attention mechanism (Figure 5a) with O(L 2 ) time complexity or previous sparse attention that neglect different data time interval (Figure 5b), we propose the Pe-riodSparse Self-attention mechanism (Figure 5c) to adaptively choose the sparse scheme according to different data. Here we define the connectivity pattern I = {I 1 , . . . , I n }, where I i is the set of the input vector indices which attends the ith output vector. Unlike the full self-attention that allows every element to attend to all positions, the PeriodSparse Self-attention is determined by the subsets of Based on the extracted period sets P = {P 1 , · · · , P k }: Notice that we set the number of attention heads according to k (i.e., the indices of periods) so that we capture the spatial dependency at different periodicity by different attention heads. For every single head, we compute the output vector at each position: where K A i = W k S j j∈A i , V A i = W v S j j∈A i and W q , W k , W v are to transform an input S to query, key, or value while d is the inner dimension of the queries and keys. We set k = c · max{(k | K i L P i } ≤ ln L)}, which makes the layer memory usage of Pe-riodSparse Self-attention maintains O(L ln L), c is the sparsity control factor.

Data
We perform experiments on five datasets in three application scenarios (i.e., IP backbone network traffic, crowd flow, transportation traffic) to evaluate the predictive ability of the proposed model across scenarios. IP backbone network traffic: In this scenario, we apply two datasets: the GÉANT 1 dataset and the Abilene 2 dataset. The former is collected from the Abilene network, including 11 nodes (regions) and 48,097 time intervals that differ by five minutes, and the latter is collected from the pan-European research and  One of the most common recurrent neural networks. (6) ARIMA [37]: Classic benchmark model that captures seasonality adequately. (7) N-BEAT [38], (8) DeepAR [39]: Standard time series methods. (9) Informer [28]: One of the most advanced long sequence prediction models based on ProbSparse Self-attention mechanism. (10) Autoformer [20]: An advanced long sequence prediction model with Auto-Correlation mechanism.  1 We replace the PeriodSparse Self-attention in ODformer with full self-attention. 2 The "-" indicates the out-of-memory.

Setting:
We use a threshold of 98% to clip overly large data to remove outliers. Then, fill in the missing values based on topological neighbors of the OD regions: where AGGREGATE is the aggregator function [40] that aggregates information from one-hop neighbors, N(v) denoted the immediate neighborhood of vertex v. To normalize the data, we take natural logarithm of the elements in the original OD matrices. The training/validation/test dataset split ratio is: 6:2:2. The initial learning rate is set to 10 −4 , using the ADAM [41] optimizer. The batch size is set to 16. The training process is early stopped within 8 epochs. All experiments are repeated five times, implemented in PyTorch [42], and conducted on a single NVIDIA GeForce RTX 3090 GPU. At last, we evaluate the overall performance of models on the long sequence ODMF by two metrics: MSE (Mean Square Error), MAE (Mean Absolute Error).

5.3.
Results and Analysis 5.3.1. Overall performance: Table 1 compares the overall performance between the baselines and proposed ODformer on the long sequence ODMF task in data of three scenarios (The input length is on the right side of the dataset). We gradually prolong the prediction length O to verify the long sequence prediction ability of the model. The length setting depends on the specific scale of OD matrices so that long sequence ODMF is tractable on one single GPU for every method. Optimal and suboptimal results are shown in red and purple, respectively. For Table 1, we summarize as follows : (1) In the setting with the smallest prediction length, ODformer greatly improves the inference performance for vast majority scenarios, which illustrates the success of capturing spatial dependencies across scenarios. (2) The prediction error of ODformer rises smoothly and slowly over the growing prediction length O, further outperforming the rest of the models as the O grows. This demonstrates ODformer's success in improving the predictive power towards long sequence OD matrices. (3) The sub-optimal models in different scenarios are different, but our models can all perform optimally, which shows that ODformer successfully solves the problem of the ODMF cross scenario. (4) On the first set of Chengdu data, the performance of ODformer is slightly weaker than that of GEML, which may duo to the spatial relationships in this dataset all depending on the adjacency information between regions.

Ablation study:
To demonstrate the effectiveness of our innovative modules, we performed ablation experiments as follows.
(1) Removal of PeriodSparse Self-attention: The experiment was performed on the Abilene dataset. In Table 2, PeriodSparse Self-attention outperforms the full attention mechanism under various O − I settings. At the same time, it also significantly outperforms full attention in memory consumption. (2) Removal of OD Attention mechanism: As shown in Table  3, ODformer with the full spatial dependency module performs the best on all datasets. However, we can find that the contribution of OD Attention is more dominant in IP backbone network traffic and crowd flow scenarios, while in the scenarios with more relevant geographic information, 2D-GCN contributes more.

Parameter sensitivity:
We perform parameter sensitivity analysis on the spatial dependency and temporal dependency modules of the ODformer model, as shown in Figure 6.
(1) Spatial share coefficient: We conduct prediction experiments with the shortest I − O setting on each of the five datasets to analyze the spatial share coefficient α. To better represent the trend, we use Min-Max Normalization to process the raw MSE values. We find that the α at the lowest MSE is different on different datasets. On more geographically related datasets, the smaller α, the smaller the MSE. Therefore, in the end, we choose the appropriate α according to different application scenarios. When α approaches extreme values, MSE will rise sharply, which shows the necessity of introducing two different spatial dependencies.
(2) Sparsity control factor: We set the input sequence length to 192 on the Abilene dataset, and the sparsity control factors were taken from {0.25, 0.5, 1, 2, 4, 8} for experiments. It can be observed that when the control factor is too large, the overall MSE is lower, which proves the necessity of introducing sparse attention for long sequence prediction. In practical applications, we set the control factor to 2.

Efficiency analysis
We  Figure 7 shows the superiority of ODformer in terms of time and memory consumption.

Conclusion
In this paper, we study the long sequence OD matrix forecasting problem and propose ODformer to forecast long OD matrix series. Specifically, we design the OD Attention mechanism and PeriodSparse Self-attention to deal with the challenges of the variability of spatial-temporal dependencies in various application scenarios and LSTF of OD matrices. Experiments on real-world data in diverse scenarios demonstrate the effectiveness of ODformer in improving the capability of long sequence OD matrix forecasting problems.