summaries: This paper proposes a clustering attention-based approach to handle the problem of unsmoothness while modeling spatio-temporal data, which may be divided into several regions with unsmooth boundaries. With the help of a graph attention mechanism between vertices (which correspond to different regions), the CGT model is able to model the (originally unsmooth) cross-region interactions just like how Transformers are applied in NLP tasks (where words are discrete). Experiments seem to suggest a big improvement when compared to baselines. In this paper, the authors developed a neural network architecture to address the spacial and temporal unsmoothness problem, which was claimed to be neglected by existing works. The proposed model, CGT, has an encoder-decoder structure, and is characterized by clustering modules for spacial regions based on their temporal patterns. To handle temporal unsmoothness, additivity-preserved multi-view position encoding was proposed to characterize different temporal relationships. The experimental results on real ride-hailing datasets demonstrate the effectiveness of the proposed method to some extent.
abstractText: Deep learning based approaches have been widely used in various urban spatiotemporal forecasting problems, but most of them fail to account for the unsmoothness issue of urban data in their architecture design, which significantly deteriorates their prediction performance. The aim of this paper is to develop a novel clustered graph transformer framework that integrates both graph attention network and transformer under an encoder-decoder architecture to address such unsmoothness issue. Specifically, we propose two novel structural components to refine the architectures of those existing deep learning models. In spatial domain, we propose a gradient-based clustering method to distribute different feature extractors to regions in different contexts. In temporal domain, we propose to use multi-view position encoding to address the periodicity and closeness of urban time series data. Experiments on real datasets obtained from a ride-hailing business show that our method can achieve 10%-25% improvement than many stateof-the-art baselines.
references.authors: James Atwood Don Towsley
references.title: Diffusion-convolutional neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Dzmitry Bahdanau Kyunghyun Cho Yoshua Bengio
references.title: Neural machine translation by jointly learning to align and translate
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Antoni Buades Bartomeu Coll J-M Morel
references.title: A non-local algorithm for image denoising
references.venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05),
references.authors: Rewon Child Scott Gray Alec Radford Ilya Sutskever
references.title: Generating long sequences with sparse transformers
references.venue: CoRR, abs/1904.10509,
references.authors: Daizong Ding Mi Zhang Xudong Pan Min Yang Xiangnan He
references.title: Modeling extreme events in time series prediction
references.venue: In Advances in Neural Information Processing Systems,
references.authors: David K Duvenaud Dougal Maclaurin Jorge Iparraguirre Rafael Bombarell Timothy Hirzel Alán Aspuru-Guzik Ryan P Adams
references.title: Convolutional networks on graphs for learning molecular fingerprints
references.venue: In Advances in neural information processing systems,
references.authors: Xu Geng Yaguang Li Leye Wang Lingyu Zhang Qiang Yang Jieping Ye Yan Liu
references.title: Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Shengnan Guo Youfang Lin Ning Feng Chao Song Huaiyu Wan
references.title: Attention based spatialtemporal graph convolutional networks for traffic flow forecasting
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Will Hamilton Zhitao Ying Jure Leskovec
references.title: Inductive representation learning on large graphs
references.venue: In Advances in Neural Information Processing Systems,
references.authors: David K Hammond Pierre Vandergheynst Rémi Gribonval
references.title: Wavelets on graphs via spectral graph theory
references.venue: Applied and Computational Harmonic Analysis,
references.authors: Guolin Ke Qi Meng Thomas Finley Taifeng Wang Wei Chen Weidong Ma Qiwei Ye TieYan Liu
references.title: Lightgbm: A highly efficient gradient boosting decision tree
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Qimai Li Zhichao Han Xiao-Ming Wu
references.title: Deeper insights into graph convolutional networks for semi-supervised learning
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Yaguang Li Rose Yu Cyrus Shahabi Yan Liu
references.title: Diffusion convolutional recurrent neural network: Data-driven traffic forecasting
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Yexin Li Yu Zheng
references.title: Citywide bike usage prediction in a bike-sharing system
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Yujia Li Daniel Tarlow Marc Brockschmidt Richard Zemel
references.title: Gated graph sequence neural networks
references.venue: arXiv preprint arXiv:1511.05493,
references.authors: Yuxuan Liang Songyu Ke Junbo Zhang Xiuwen Yi Yu Zheng
references.title: Geoman: Multi-level attention networks for geo-sensory time series prediction
references.venue: In IJCAI,
references.authors: Binbing Liao Jingqing Zhang Ming Cai Siliang Tang Yifan Gao Chao Wu Shengwen Yang Wenwu Zhu Yike Guo Fei Wu
references.title: Dest-resnet: A deep spatiotemporal residual network for hotspot traffic speed prediction
references.venue: ACM Multimedia Conference on Multimedia Conference,
references.authors: Lei Lin Zhengbing He Srinivas Peeta
references.title: Predicting station-level hourly demand in a large-scale bike-sharing network: A graph convolutional neural network approach
references.venue: Transportation Research Part C: Emerging Technologies,
references.authors: Ding Liu Bihan Wen Yuchen Fan Chen Change Loy Thomas S Huang
references.title: Non-local recurrent network for image restoration
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Zheyi Pan Yuxuan Liang Weifeng Wang Yong Yu Yu Zheng Junbo Zhang
references.title: Urban traffic prediction from spatio-temporal data using deep meta learning
references.venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga Adam Lerer
references.title: Automatic differentiation in pytorch
references.authors: Filipe Rodrigues Ioulia Markou Francisco C Pereira
references.title: Combining time-series and textual data for taxi demand prediction in event areas: A deep learning approach
references.venue: Information Fusion,
references.authors: Pavel Senin
references.title: Dynamic time warping algorithm review
references.venue: Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA,
references.authors: Hongzhi Shi Quanming Yao Qi Guo Yaguang Li Lingyu Zhang Jieping Ye Yong Li Yan Liu
references.title: Predicting origin-destination flow via multi-perspective graph convolutional network
references.venue: IEEE 36th International Conference on Data Engineering (ICDE),
references.authors: Xingjian Shi Dit-Yan Yeung
references.title: Machine learning for spatiotemporal sequence forecasting: A survey
references.venue: arXiv preprint arXiv:1808.06865,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In Advances in neural information processing systems,
references.authors: Dong Wang Wei Cao Jian Li Jieping Ye
references.title: Deepsd: supply-demand prediction for online carhailing services using deep neural networks
references.venue: IEEE 33rd International Conference on Data Engineering (ICDE),
references.authors: Menglin Wang Baisheng Lai Zhongming Jin Xiaojin Gong Jianqiang Huang Xiansheng Hua
references.title: Dynamic spatio-temporal graph-based cnns for traffic prediction
references.venue: arXiv preprint arXiv:1812.02019,
references.authors: Senzhang Wang Jiannong Cao Philip S Yu
references.title: Deep learning for spatio-temporal data mining: A survey
references.venue: arXiv preprint arXiv:1906.04928,
references.authors: Xiaolong Wang Ross Girshick Abhinav Gupta Kaiming He
references.title: Non-local neural networks
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Ying Xu Dongsheng Li
references.title: Incorporating graph attention and recurrent architectures for city-wide taxi demand prediction
references.venue: ISPRS International Journal of Geo-Information,
references.authors: Huaxiu Yao Fei Wu Jintao Ke Xianfeng Tang Yitian Jia Siyu Lu Pinghua Gong Jieping Ye Zhenhui Li
references.title: Deep multi-view spatial-temporal network for taxi demand prediction
references.venue: In ThirtySecond AAAI Conference on Artificial Intelligence,
references.authors: Zhitao Ying Jiaxuan You Christopher Morris Xiang Ren Will Hamilton Jure Leskovec
references.title: Hierarchical graph representation learning with differentiable pooling
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Junbo Zhang Yu Zheng Dekang Qi Ruiyuan Li Xiuwen Yi
references.title: Dnn-based prediction model for spatio-temporal data
references.venue: In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,
references.authors: Junbo Zhang Yu Zheng Dekang Qi
references.title: Deep spatio-temporal residual networks for citywide crowd flows prediction
references.venue: In Thirty-First AAAI Conference on Artificial Intelligence,
references.authors: Lingyu Zhang Wei Ai Chuan Yuan Yuhui Zhang Jieping Ye
references.title: Taxi or hitchhiking: Predicting passenger’s preferred service on ride sharing platforms
references.venue: In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval,
references.authors: Yu Zheng Licia Capra Ouri Wolfson Hai Yang
references.title: Urban computing: concepts, methodologies, and applications
references.venue: ACM Transactions on Intelligent Systems and Technology (TIST),
references.authors: Jie Zhou Ganqu Cui Zhengyan Zhang Cheng Yang Zhiyuan Liu Lifeng Wang Changcheng Li Maosong Sun
references.title: Graph neural networks: A review of methods and applications, 2018
sections.heading: 1 INTRODUCTION
sections.text: The aim of this paper is to use urban data to study spatio-temporal prediction problems, whose goal is to forecast region-based spatial distribution in the future (Shi & Yeung, 2018; Wang et al., 2019). Recently, region-based spatio-temporal forecasting has been extensively studied with various applications in traffic (Li et al., 2018b), ride-hailing services (Zhang et al., 2018; Li & Zheng, 2019), environment (Liang et al., 2018), resources (Li & Zheng, 2019), and human flows (Wang et al., 2019; Shi et al., 2020), among others. Such spatio-temporal forecasting is crucial for various tasks, such as dispatching and pricing, in urban computing (Zheng et al., 2014). Accurate spatiotemporal forecasting methods may not only lower the barrier for decision making, but also improve the quality of various services including traffic management, transportation, and air quality management. However, achieving accurate prediction represents major challenges for many existing methods due to some difficulties in urban data, such as unsmoothness.
  As an illustration, we will show throughout the paper that urban spatio-temporal prediction task suffers from not appropriately handing spatial and temporal unsmoothness. Unsmoothness is a common phenomenon in many spatial and/or temporal data sets. The observations in some locations/time-steps differ substantially from the observations in their neighboring locations/time-steps. For example, rush-hour traffic surge is temporally unsmoothed, while it occurs in many regions in a city. Figure 1 shows potential spatial unsmoothness due to different points of interest. Specifically, S1, S2 and S3 denote business, residential, and recreational areas, respectively, whereas U1, U2, and U3 are their boundaries. Traffic observations in the interior areas of S1, S2 and S3 may be quite close to each other, whereas observations along U1, U2, and U3 may have much larger variations. Figure 2 shows 24-hour temporal patterns in the spatial neighborhood of a selected smooth
  region (2a) and a selected unsmooth region (2b). The temporal patterns for the smooth region are
  close to those of most of their closest neighbors except the region with yellow color 1 in terms of shape and magnitude. The temporal patterns of the unsmooth region differ more significantly from those in all his closest neighbors. Moreover, we also discover some sharp surge and drop patterns in the unsmooth region. For more quantitative metrics for measuring unsmoothness, please refer to Appendix A for details.
  However, the attempt to handling unsmoothness is quite limited both at model and feature levels. Many existing prediction methods share their spatial and temporal feature extractors universally across all time-steps and/or all regions. Thus, it greatly limits the expressiveness of those prediction methods, since they are greatly vulnerable to the presence of unsmoothness in urban data.
  In this paper, we develop a novel Clustered Graph Transformer (CGT) framework by integrating Graph Attention Network (GAT) (Veličković et al., 2018) with Transformer (Vaswani et al., 2017) based on a unified attention encoder-decoder architecture (Bahdanau et al., 2015). The GAT and Transformer are effective methods for spatial and temporal feature extraction based on attention mechanism. To handle spatial unsmoothness, we develop a novel Clustered Graph Attention Network (CGAT) by leveraging different graph attention kernels on different regions. The CGAT learns clustering assignments for each region according to their temporal patterns so that regions with different temporal patterns are assigned with different spatial feature extractors. To handle temporal unsmoothness, we propose additivity-preserved multi-view position encoding (MVPE) by characterizing different kinds of temporal relationship including weekly or daily periodicity and temporal closeness (Zhang et al., 2017). In summary, our major contributions are summarized as follows:
  • To the best of our knowledge, CGT is the first of its kind in using graph attention network with a transformer under an encoder-decoder architecture for long sequence spatiotemporal forecasting.
  • We propose to improve the expressiveness of spatial feature extraction using the clustering technique. We also handle the temporal unsmoothness by using MVPE, which is a tailored position encoding for urban computing.
  • Compared with most existing baseline models, CGT achieves improvement ranging from 10% to 25% in spatiotemporal prediction on various tasks, datasets and cities. Error reduction on unsmooth areas dominates this improvement.
  1Except region 1. Details are in section 4.3
sections.heading: 2 METHODOLOGY
sections.text: We formalize the learning problem of urban spatiotemporal forecasting and introduce the CGT framework to capture the spatial and temporal dependencies and unsmoothness of urban data.
sections.heading: 2.1 URBAN SPATIOTEMPORAL FORECASTING
sections.text: We consider urban spatiotemporal forecasting problems in a city. Suppose that the city can be divided into V disjoint regions and we observe temporal information across T time intervals within each region. Our spatio-temporal data is represented as a |V | × T matrix. As an example, we consider taxi demand forecasting problem and each entry in the matrix represents the total number of taxi orders inside a region within a specific time interval. Our prediction problem is formulated as f : R|V |×Tx → R|V |×Ty such that we use the historical data within time period Tx to predict the future trend in time period Ty , that is,
  Xt−Tx+1:t = [X t−Tx+1, . . . , Xt] f(·)−−→ Xt+1:t+Ty = [Xt+1, . . . , Xt+Ty ]. (1) Problem (1) is a one-step prediction problem as Ty = 1 and a multi-step prediction problem as Ty > 1. We regard the whole city as a graph with V regions (or vertices), each of which has both demand and supply numbers across T time intervals.
sections.heading: 2.2 FRAMEWORK OVERVIEW
sections.text: Figure 3 shows the overview of the CGT framework. The CGT is an encoder-decoder based architecture. The clustered graph attention layers (CGAT) and temporal attention layers are stacked alternately in the encoder and decoder. For prediction problem (1), the input tensor to encoder is Xt−Tx+1:t. In the training phase, the whole target sequence Xt:t+Ty is input to the decoder and the masked attention controls the visibility of target sequence in each step of decoding. The Xt is used to initialize the decoder state at the initial decoding step. In the testing phase, at step Ts (Ts ≤ Ty), the decoder input tensor is [Xt, X̂t+1:t+Ts ], where X̂ represents predicted values from previous steps. The multi-view position encoding (MVPE) is added to input tensors in both encoder and decoder.
  Our key novel contribution in CGT lies in the design and use of CGAT and MVPE. On spatial mode, CGAT integrates self-clustering and a set of graph attention kernels (GAT), which are used for region clustering and spatial feature extraction, respectively. CGATs firstly generate soft clustering assignment scores for regions according to their temporal pattern in the sampled period. The cluster scores are used as the weights to apply different GATs to each region. On temporal mode,
  we use multi-view position encoding (MVPE) to manually inject ordering information, periodicity information, and closeness information to the model.
sections.heading: 2.3 MULTI-VIEW POSITION ENCODING
sections.text: We design a multi-view position encoding mechanism (MVPE) for urban computing. The position encoding consists of five channels as follows. There are two channels for weekly periodicity given by
  PE1(x) = (1 + sin(2πx/7))/2 and PE2(x) = (1 + cos(2πx/7))/2.
  There are two channels for daily periodicity given by
  PE3(x) = (1 + sin(2πx))/2 and PE4(x) = (1 + cos(2πx))/2.
  There is one channel for closeness given by
  PE5(x) = exp(−ax2),
  where x represents the temporal difference between a fixed timestep (e.g. the time t+1 in formulation (1)) and a specific timestep in inputs or outputs.
  The MVPE mechanism injects ordering information and relevance information to the temporal modeling. First, MVPE provides unique identifiers for all time-steps in temporal sequences, which is critical for non-recurrent to model sequences. Second, according to Zhang et al. (2016), the weekly and daily periodicity, as well as closeness are considered to be highly important in modeling urban time series. The periodicity channels provide constant crest/trough values for timesteps spanned by an integer number of periods. The closeness channel provides a surging value for the nearby timesteps. The model will be trained to make predictions according to different temporal relevance to avoid making over-smoothing ones.
sections.heading: 2.4 CLUSTERED GRAPH ATTENTION
sections.text: We propose the clustered graph attention layer (CGAT) for spatial feature extraction. It learns different graph attention kernels for different regions based on a gradient-based self-clustering assignment such that different regions are treated differently in spatial dependency modeling.
  First, a vertex-level soft-assignment to K clusters is learnt from the temporal pattern of each vertex:
  C = σs(σr(XfWf )tWt), (2)
  where C is the cluster assignment score for each vertex to K clusters. Wf and Wt are parameters for linear layers on the feature mode and temporal mode, respectively, and σr and σs represent the relu and softmax activation functions. The feature dimension of input tensor Xf is first squeezed to 1 using Wf , in order to provide summarized temporal pattern at each vertex. The Wt is further applied to the temporal pattern to calculate a K−dimensional cluster assignment score. Second, we use cxi,k to denote the assignment score of C for assigning vertex xi to cluster k. Then, C is used to re-weight the latent output by using K GATs as follows:
  hxi = K∑ k=0 G(xi)cxi,k, (3)
  where hxi is the summed output for a CGAT layer at vertex xi and Gθk(xi) is the output for each GAT at vertex xi. We use the GAT defined by Veličković et al. (2018). The attention between two vertex xi and xj is calculated as:
  αi,j = exp(σ(aT [Wxi||Wxj ]))∑
  xm∈Nxi exp(σ(aT [Wxi||Wxm]))
  , (4)
  where W and aT are network parameters, Nxi represents the neighborhood of region xi, [·||·] is the concatenation operation, and σ(·) is the Leakyrelu activation function. The aggregation function for GAT is given by G(xi) = σ( ∑ xj∈Ni αi,jWxj).
sections.heading: 2.5 TEMPORAL ATTENTION AND TRANSFORMER
sections.text: The temporal features are extracted by adapting the multi-head attention model to the temporal mode of spatio-temporal tensor (Vaswani et al., 2017). Detailed information is included in Appendix C.
sections.heading: 2.6 OPTIMIZATION OBJECTIVE
sections.text: The optimization objective of CGT consists of two major components. The first component is the prediction error given by Lpred = ||y − ŷ||2, (5) where || · ||2 the standard L2 norm and ŷ and y are, respectively, the tensor of predicted values and that of true values.
  The second component consists of three constraints for obtaining a good vertex cluster schema C. Let the clustering result C = (Cb,l,v,k) be a tensor of order (B,L, V,K), where B is the batch size, L is the number of all CGAT layers, V is the number of vertices, and K is the cluster number. Thus, Cb1,l1,·,· denotes a V × K matrix and Cb,l,v,· is a K × 1 vector. The three constraints including consistency, purity, and diversity are summarized below.
  • Consistency: The clustering assignment is generated through the temporal pattern of each vertex such that C should be temporally (batch) invariant and layer invariant. The loss function for ensuring consistency is defined as
  Lc = 4 BL(B − 1)(L− 1)V 2 B−1∑ b1=1 B∑ b2=b1+1 L−1∑ l1=1 L∑ l2=l1+1 ||Cb1,l1,·,· − Cb2,l2,·,·||22. (6)
  • Purity: Ideally, each vertex should be only assigned to one cluster. The loss function for encouraging purity is given by
  Lp = 1
  BLV B∑ b=1 L∑ l=1 V∑ v=1 (1− ||Cb,l,v,·||22). (7)
  • Diversity: To balance the cluster size, we define the loss function for ensuring diversity as follows:
  Ld = 1
  BLV 2 B∑ b=1 L∑ l=1 || V∑ v=1 Cb,l,v,·||22. (8)
  The overall minimization goal is to minimize the following object function
  L = Lpred + α(Lc + Lp + Ld), (9) where α is a tuning parameter. It is worth noting that each batch consists of training snippets within a continuous short period of time (e.g., several hours). Keeping the clusters stable by using above regularizations allows to capture the short-term stability of urban time series data, while it does not violate the daily or long-term variability. We verify this short-term stability feature in Appendix B.
sections.heading: 2.7 APPLICATION-LEVEL ADAPTATIONS
sections.text: Several state-of-the-art techniques need to be considered for improving our implementation and evaluation on real-world applications. First, we construct a set of graphs G = {G1, G2, G3} as the graph adjacency matrix, each of which represents region-wise distance, region-wise functional similarity and region-wise road connectivity, respectively. It follows the idea of Geng et al. (2019) in order to encode multiple region-wise relationships as multi-graphs for the better utilization of auxiliary data. Second, following Child et al. (2019), we implement spatial atrous attention to reduce the extra large spatial dimension in order to reduce the computational cost for CGATs.
  Denoting atrous stride and atrous offset as s and a, the atrous version of eq.(4) is revised to be:
  αi,j,g,s,a = exp(σ(aTg [Wgxi||Wgxj ]))Is,a(j)∑
  xm∈Nxi exp(σ(aTg [Wgxi||Wgxm]))Is,a(m)
  , (10)
  where aTg and Wg denote the feature transformation operation for graph g. Is,a(·) is a masking function for atrous attention:
  Is,a(j) = { 1 if j mod s = a; 0 otherwise.
  To cover all the regions, atrous-GAT needs to traverse a = 0, · · · , s − 1 by in-layer aggregation. The aggregated atrous-GAT output under single graph g ∈ G is calculated as:
  Gg(xi) = σ( s−1∑ a=0 ∑ xj∈Ni αi,j,g,s,aWxj). (11)
  Each GAT outputs an aggregated output over multi-graph given by G(xi) = ∑ g∈G Gg(xi)/|G|. The regularizers in eq.(6)-(8) are calculated separately for multi-graph and finally averaged for calculating the loss.
sections.heading: 3 RELATED WORK
sections.heading: 3.1 SPATIOTEMPORAL DEEP LEARNING
sections.text: There have been various ways to model the spatial and temporal dependencies with deep neural networks. The combination of CNN and RNN is the most intuitive one (Yao et al., 2018; Zhang et al., 2017; Wang et al., 2017; Liao et al., 2018; Rodrigues et al., 2019). However, CNN-based architectures are unable to handle non-Euclidean region-wise relationships. The STMGCN (Geng et al., 2019), DCRNN (Li et al., 2018b) and GCNN-DDGF (Lin et al., 2018) use ChebNet (Kipf & Welling, 2017) and diffusion convolution to extract spatial features based on rather complex graph representations. The graph attention network (Veličković et al., 2018) is the third generation of spatial modeling, which has more complex structures for discovering region-wise relationships. The ST-MetaNet (Pan et al., 2019) is a representative work of GAT with application in urban computing. In temporal feature extraction, attention-based methods outperform RNNs in terms of both accuracy and efficiency. The ASTGCN (Guo et al., 2019) is an attention-based model on both spatial and temporal domains. The GeoMAN (Liang et al., 2018) further adapts the attention-based model to encoder-decoder architecture for long sequence prediction. However, all existing methods neglect the unsmoothness problem of urban data.
sections.heading: 3.2 GRAPH NEURAL NETWORKS
sections.text: The research works on graph neural networks could be summarized in several categories (Zhou et al., 2018). Spectral graph convolution (Hammond et al., 2011; Kipf & Welling, 2017) defines convolution operator by the eigen-decomposition of the graph laplacian, based on the graph spectral theorem. Non-spectral graph convolution (Duvenaud et al., 2015; Atwood & Towsley, 2016; Hamilton et al., 2017) directly operates the spatial domain by defining a set of neighborhood aggregation and updating rules on vertex-level. Moreover, the gated GNN (Li et al., 2015) leverages the gating technique from LSTM, which provides more complex operations for neighborhood aggregation. GAT (Veličković et al., 2018) is using attention mechanism to discover the vertex-wise similarities in a graph. In urban computing, the intuition is confident that regions are strongly correlated. The GAT might help to discover this intrinsic structure in the region-based spatial distribution.
sections.heading: 3.3 VERTEX CLUSTERING AND GRAPH POOLING
sections.text: Vertex clustering is a frequently used method for graph pooling (Ying et al., 2018), which is a common technique migrated from computer vision. However, the intuition for graph pooling and vertex clustering proposed in this work is different. Graph pooling is to reduce the number of vertices such that vertices in each cluster are regarded sampled into one in the next layer. Downscaling the graph layer would improve model generality and reduce computational cost. The vertex clustering in our approach is to discover a set of vertices sharing similar patterns, which is used for better feature extraction.
sections.heading: 3.4 HANDLING UNSMOOTHNESS IN MACHINE LEARNING
sections.text: Non-local mean methods are proposed for image denoising and restoration by investigating the pixel-level self-similarity in images. Buades et al. (2005) proposed to calculate pixel pair-wise similarity within a large search window. The densities for noisy pixels are interpolated by those similar pixels. Wang et al. (2018b),Liu et al. (2018) designed non-local neural networks to incorporate the similar idea in deep learning. However, these non-local mean methods are applied to fix part of the spatial distribution at corrupted areas, which is different from our problem formulation. In time series prediction, Ding et al. (2018) proposed a extreme-value loss (EVL) for extreme event prediction in time series data. Compared with our method, EVL has no model-level effort to extract unsmooth features from data, which totally relies on the success of optimization algorithm.
sections.heading: 4 EXPERIMENTS
sections.text: We conduct experiments on a demand/supply dataset for ride-hailing services in two cities A and B 2 from Jun 2017 to Jun 2019. The demand data is the number of ride-hailing orders in each region within each time interval. The supply data is the summation of online duration for all ridehailing drivers. The spatial and temporal distribution is sampled and aggregated into 1km×1km map gridding and 30 minutes temporal sampling interval3. For both datasets, we cut off the long tail on the 95th quantile and normalize them by min-max normalization. The duration of the dataset is two years, where first 70% is used for training, 10% for validation, and remaining 20% for test. The multi-graph G involves region-wise relationships including neighborhood, functional similarity, and road connectivity, which are identical to those used in (Geng et al., 2019). The functional similarity graph is binarized on 0.9 so that three graphs have almost equal graph sparsity4.
sections.heading: 4.1 OVERALL PERFORMANCE
sections.text: In this section, the encoder and decoder both stack 3 CABs and TABs alternately, with 16 hidden states each. The default clustering number is 3, with atrous stride being equal to 2. The number of heads in TAB multi-head attention is set to be 3. The network is optimized by using scheduled Adam on PyTorch (Paszke et al., 2017).
  We conduct both one-step prediction and multi-step prediction experiments. To avoid the long sequence problem, which may exhaust computational resource, we sampled 10 input time-steps for each output time-step Tk. The input time-steps include 3 closest time-steps (Tk−1, Tk−2, Tk−3), 2 from daily periodicity (Tk−48, Tk−96) and 1 from weekly periodicity (Tk−48∗7). For multi-step prediction, the default output length is 8, the encoder input length is 27.
  2Anonymous for blind review. 3Designed according to industrial practices 4In city A, it is roughly 12000 edges for 1296 vertices.
  Baselines are built based on following research works. For the sake of information fairness, all deep learning models are slightly revised to take in multiple graphs.
  • HA, LR and XGBoost: Historical average, linear regression and XGBoost. The model parameters for LR and XGBoost are shared across space and time. XGBoost is implemented using LightGBM (Ke et al., 2017).
  • DMVST (Yao et al., 2018): a CNN-RNN based model. Region-wise relationships are encoded as external inputs.
  • DCRNN (Li et al., 2018b) and ST-MGCN (Geng et al., 2019): Both are GCN-RNN based model for spatiotemporal feature extraction. DCRNN is based on encoder-decoder architecture for multi-step traffic prediction.
  • GeoMAN (Liang et al., 2018): The spatial and temporal features are extracted by spatial attention and RNN. It is based on the encoder-decoder architecture.
  • ASTGCN (Guo et al., 2019): an attention-based model on spatial and temporal domain. Spatiotemporal features are extracted using GCN and convolution. ASTGCN don’t have position encoding.
  • DST-GCNN 5(Wang et al., 2018a): A two stream framework for traffic prediction. The first stream constructs dynamic affinity graph. The second stream use the graph and spatiotemporal convolution for feature extraction.
  • GAT+RNN 5(Xu & Li, 2019): a GAT+RNN structure for traffic forecasting.
  Table 1 summarizes the RMSEs and MAPEs of CGT and state-of-the-art baselines. There are few observations from above experiment results. First, the proposed CGT model outperforms all baselines in all prediction tasks by a large margin. Second, all encoder-decoder based models, including m-DCRNN, m-GeoMAN and CGT, perform well in all multi-step prediction tasks.
sections.heading: 4.2 ABLATION STUDY AND PARAMETER TEST
sections.text: In this section, we show the experiment results of CGT on the one-step demand prediction problem in city A with varying model configurations to show the parameter effect. As shown by figure 4, the optimal result is achieved when α = 0.1 and k = 3. Table 2 shows the model performance when specific component is removed from CGT. The ablation study shows the significance of our novel contribution.
  5Made-up experiment according to reviewer’s comments. Unfinished due to time limit.
sections.heading: 4.3 MODEL INTERPRETATION
sections.text: We claim that the prediction error is reduced due to more accurate predictions in spatial and temporal unsmooth areas. To validate this, we explore the relationship between the unsmoothness and the error reduction from a baseline model. The baseline model is designed by removing clustering and MVPE from CGT. Figure 5 shows a positive relationship between unsmoothness and error reduction. Table 3 shows the error reduction from the baseline model on different quantiles of spatial and temporal unsmooth areas. Conclusions could be drawn that CGT could improve the prediction performance, especially in spatial and temporal unsmooth areas by significant margins.
  Above improvements on spatial mode may be caused by the effective clustering technique, which applies different spatial kernels to regions with different patterns. Referring back to Figure 2, the neighbor 1 (yellow line) in Figure 2a is an unsmooth point in the neighborhood. It is assigned to the same cluster with the target region (blue line) in Figure 2b, which is also an unsmooth region. The remaining regions in Figure 2a stay in the same cluster. According to above case study, the temporal pattern for inner-cluster regions are similar, while the temporal pattern for intra-cluster regions are diverse. It is sensible to apply a shared operator to target regions in a single cluster, since the relationship between target regions and their neighbors are more stable within a cluster. However, applying one smoothing operator to different clusters does not work very well, since it may introduce some artifacts. In conclusion, discriminating smooth and unsmooth patterns may greatly improve the local spatial feature extraction.
sections.heading: 5 CONCLUSION AND FUTURE WORK
sections.text: In this paper, we proposed Clustered Graph-Transformer for spatiotemporal prediction problems in urban computing. To handle the spatial and temporal unsmoothness problem, we use a gradientbased clustering technique in GAT to construct spatial feature extractor. We use MVPE and attention to handle temporal unsmoothness by providing a urban-specific temporal encoding to the temporal mode. The experiment has shown the effectiveness of the proposed model. In the future, we plan to explore long seq2seq problem using atrous transformer (Child et al., 2019) as well as explore the explanation for the attention and clustering assignments.
sections.heading: A PRELIMINARY ANALYSIS
sections.text: In this section, we conduct a preliminary error analysis for a baseline GNN+RNN based model on spatial and temporal unsmooth areas in order to prove our assumptions and motivate our design methodology.
  For input spatial temporal signal X , denote Xs and Xt as its spatial and temporal modes, respectively, and L as the graph laplacian matrix for spatial distribution. The L is the loss metric. The spatial and temporal unsmoothnesses could be represented by the difference between a convoluted value and its true value. We define the spatial convolution kernel as αL, which is a linear combination of the features from all neighboring locations. The temporal convolution kernel is defined as Wt∗, which is a 1d convolution along temporal mode. The spatial and temporal unsmoothnesses are calculated as φs = L(X,αLXs) and φt = L(X,Wt ∗ Xt), respectively. The α and Wt are optimized using the same training set as the baseline model. Spatial and temporal areas with larger unsmoothness means that they are hard to be represented by using
  a linear combination of observations in neighboring locations.
  (a) Positive relationship between spatial unsmoothness (X) and prediction error (Y) for the baseline model. (b) Positive relationship between temporal unsmoothness (X) and prediction error (Y) for the baseline model.
  Figure 7: Baseline prediction error and unsmoothness
  Figure 7 shows the positive relationship between baseline prediction error and spatial/temporal unsmoothness. There are several reasons for this. First, the expressiveness of GNNs are limited. Using
  ChebNet as an example, it treats all neighbors in one convolution kernel homogeneously and shares its weighted transformation on feature dimension to all neighboring vertices. Thus, ChebNet lacks discriminativity within the neighborhood. Li et al. (2018a) also proves that the usage of laplacian smoothing will cause serious problem in deep-stacked GCN models. Second, spatial feature extractors are shared among all regions, that is, it is assumed that spatial feature extraction rule is universally applied to the whole city. In Figure 6, we clustered the regions in the city into 5 clusters according to their similarities by using DTW (Senin, 2008) of temporal pattern in a short snippet and print averaged 24 hour temporal pattern for them. The clustering result shows that the magnitudes for regions from different clusters are different with high confidence. The overall temporal patterns for different clusters are quite diverse.
sections.heading: B LOCAL STABILITY ON THE TEMPORAL MODE
sections.text: In this section, we prove in details that the temporal patterns are stable within each batch, compared with its large variation across the whole dataset. The average value for batch-level standard deviation on temporal mode is 658.57. The standard-deviation on temporal mode for the whole dataset is 1074.84, which is significantly larger. The batch-size is the same with our experiment setting.
sections.heading: C CALCULATION FOR TEMPORAL ATTENTION IN TRANSFORMER
sections.text: The temporal attention is calculated as follows:
  Attn(Q,K, V ) = softmax( QKT√ dk )V,
  where QKT is a self-attention to represent relationships among different time-steps. Such relationship is further applied on V by transforming its temporal mode.
  The feed forward layer is a linear transformation on the feature mode as follows:
  Hffn(X) = σr(XfWf ).
  In encoder, the self-attention is used to discover temporal dependencies in the latent feature vector h such that the attention is defined as
  Q = hWq,K = hWk, and V = hWv. (12)
  In decoder, the self-attention performs similarly, but a mask is applied on the input sequence so that the feature extraction at time t could not view the temporal features later than it. The mask is implemented by an upper triangular matrix. The encoder-decoder attention transforms the temporal mode of decoder latent feature based on temporal dependencies from the encoder as follows:
  Q = hencWq,K = hencWk, and V = hWv, (13)
  where h is the decoder latent feature vector from previous decoder layers and henc is the encoder feature vector which denotes the encoder state. In this application, the initial state for the decoder input sequence (target sequence) is copied from the last time-step of the input sequence.
  D VISUALIZATION FOR PERFORMANCE ON TEMPORAL UNSMOOTHNESS
  Figure 8 shows the comparison between ground truth and machine learning models based on 24- hour ride-hailing demand values in selected regions. According to the visualization, CGT model is more close to ground truth, especially in those temporal unsmoothed areas.