Graph WaveNet for Deep Spatial-Temporal Graph Modeling - …

1 Graph WaveNet for Deep Spatial-Temporal Graph ModelingZonghan Wu1,Shirui Pan2 ,Guodong Long1,Jing Jiang1,Chengqi Zhang11 Centre for Artificial Intelligence, FEIT, University of Technology Sydney, Australia2 Faculty of Information Technology, Monash University, , Graph Modeling is an importanttask to analyze the spatial relations and temporaltrends of components in a system. Existing ap-proaches mostly capture the spatial dependency ona fixed Graph structure, assuming that the under-lying relation between entities is , the explicit Graph structure (relation)does not necessarily reflect the true dependency andgenuine relation may be missing due to the incom-plete connections in the data. Furthermore, ex-isting methods are ineffective to capture the tem-poral trends as the RNNs or CNNs employed inthese methods cannot capture long-range tempo-ral sequences.

2 To overcome these limitations, wepropose in this paper a novel Graph neural networkarchitecture, Graph WaveNet , for spatial-temporalgraph Modeling . By developing a novel adaptivedependency matrix and learn it through node em-bedding, our model can precisely capture the hid-den spatial dependency in the data. With a stackeddilated 1D convolution component whose recep-tive field grows exponentially as the number oflayers increases, Graph WaveNet is able to handlevery long sequences. These two components areintegrated seamlessly in a unified framework andthe whole framework is learned in an end-to-endmanner. Experimental results on two public traf-fic network datasets, METR-LA and PEMS-BAY,demonstrate the superior performance of our IntroductionSpatial-temporal Graph Modeling has received increasing at-tention with the advance of Graph neural networks.

3 It aimsto model the dynamic node-level inputs by assuming inter-dependency between connected nodes, as demonstrated byFigure 1. Spatial-Temporal Graph Modeling has wide appli-cations in solving complex system problems such as traf-fic speed forecasting[Liet al., 2018b], taxi demand pre-diction[Yaoet al., 2018], human action recognition[Yan Corresponding 1: Spatial-Temporal Graph Modeling . In a spatial-temporalgraph, each node has dynamic input features. The aim is to modeleach node s dynamic features given the Graph al., 2018], and driver maneuver anticipation[Jainet al.,2016]. For a concrete example, in traffic speed forecasting,speed sensors on roads of a city form a Graph where the edgeweights are judged by two nodes Euclidean distance.

4 As thetraffic congestion on one road could cause lower traffic speedon its incoming roads, it is natural to consider the underlyinggraph structure of the traffic system as the prior knowledge ofinter-dependency relationships among nodes when modelingtime series data of the traffic speed on each basic assumption behind Spatial-Temporal Graph model-ing is that a node s future information is conditioned on itshistorical information as well as its neighbors historical in-formation. Therefore how to capture spatial and temporal de-pendencies simultaneously becomes a primary challenge. Re-cent studies on Spatial-Temporal Graph Modeling mainly fol-low two directions. They either integrate Graph convolutionnetworks (GCN) into recurrent neural networks (RNN)[Seoet al.]

5 , 2018; Liet al., 2018b]or into convolution neural net-works (CNN)[Yuet al., 2018; Yanet al., 2018]. While hav-ing shown the effectiveness of introducing the Graph structureof data into a model, these approaches face two major , these studies assume the Graph structure of data re-flects the genuine dependency relationships among , there are circumstances when a connection does notentail the inter-dependency relationship between two nodesand when the inter-dependency relationship between twonodes exists but a connection is missing. To give each circum-stance an example, let us consider a recommendation the first case, two users are connected, but they may havedistinct preferences over products. In the second case, [ ] 31 May 2019users may share a similar preference, but they are not linkedtogether.

6 Zhanget al.[2018]used attention mechanisms toaddress the first circumstance by adjusting the dependencyweight between two connected nodes, but they failed to con-sider the second , current studies for Spatial-Temporal Graph mod-eling are ineffective to learn temporal dependencies. RNN-based approaches suffer from time-consuming iterative prop-agation and gradient explosion/vanishing for capturing long-range sequences[Seoet al., 2018; Liet al., 2018b; Zhanget al., 2018]. On the contrary, CNN-based approaches en-joy the advantages of parallel computing, stable gradients andlow memory requirement[Yuet al., 2018; Yanet al., 2018].However, these works need to use many layers in order tocapture very long sequences because they adopt standard 1 Dconvolution whose receptive field size grows linearly with anincrease in the number of hidden this work, we present a CNN-based method namedGraph WaveNet , which addresses the two shortcomings wehave aforementioned.

7 We propose a Graph convolution layerin which a self-adaptive adjacency matrix can be learned fromthe data through an end-to-end supervised training. In thisway, the self-adaptive adjacency matrix preserves hidden spa-tial dependencies. Motivated by WaveNet [Oordet al., 2016],we adopt stacked dilated casual convolutions to capture tem-poral dependencies. The receptive field size of stacked di-lated casual convolution networks grows exponentially withan increase in the number of hidden layers. With the sup-port of stacked dilated casual convolutions, Graph WaveNetis able to handle Spatial-Temporal Graph data with long-rangetemporal sequences efficiently and effectively. The main con-tributions of this work are as follows: We construct a self-adaptive adjacency matrix whichpreserves hidden spatial dependencies.

8 Our proposedself-adaptive adjacency matrix is able to uncover unseengraph structures automatically from the data without anyguidance of prior knowledge. Experiments validate thatour method improves the results when spatial dependen-cies are known to exist but are not provided. We present an effective and efficient framework to cap-ture Spatial-Temporal dependencies simultaneously. Thecore idea is to assemble our proposed Graph convolutionwith dilated casual convolution in a way that each graphconvolution layer tackles spatial dependencies of nodes information extracted by dilated casual convolution lay-ers at different granular levels. We evaluate our proposed model on traffic datasetsand achieve state-of-the-art results with low compu-tation source codes of Graph WaveNetare publicly available Related Graph Convolution NetworksGraph convolution networks are building blocks for learninggraph-structured data[Wuet al.]

9 , 2019]. They are widely ap-plied in domains such as node embedding[Panet al., 2018],node classification[Kipf and Welling, 2017], Graph classifi-cation[Yinget al., 2018], link prediction[Zhang and Chen,2018]and node clustering[Wanget al., 2017]. There aretwo mainstreams of Graph convolution networks, the spectral-based approaches and the spatial-based approaches. Spectral-based approaches smooth a node s input signals using graphspectral filters[Brunaet al., 2014; Defferrardet al., 2016;Kipf and Welling, 2017]. Spatial-based approaches extracta node s high-level representation by aggregating feature in-formation from neighborhoods[Atwood and Towsley, 2016;Gilmeret al., 2017; Hamiltonet al., 2017]. In these ap-proaches, the adjacency matrix is considered as prior knowl-edge and is fixed throughout training.

10 Montiet al.[2017]learned the weight of a node s neighbor through Gaussiankernels. Velickovicet al.[2017]updated the weight of anode s neighbor via attention mechanisms. Liuet al.[2019]proposed an adaptive path layer to explore the breadth anddepth of a node s neighborhood. Although these methods as-sume the contribution of each neighbor to the central nodeis different and need to be learned, they still rely on a pre-defined Graph structure. Liet al.[2018a]adopted distancemetrics to adaptively learn a Graph s adjacency matrix forgraph classification problems. This generated adjacency ma-trix is conditioned on nodes inputs. As inputs of a Spatial-Temporal Graph are dynamic, their method is unstable forspatial-temporal Graph Spatial-Temporal Graph NetworksThe majority of Spatial-Temporal Graph Networks followstwo directions, namely, RNN-based and CNN-based ap-proaches.