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.

2 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. 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.

3 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. 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.]

4 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. 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.

5 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., 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.

6 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. 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.]

7 , 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. We propose a Graph convolution layerin which a self-adaptive adjacency matrix can be learned fromthe data through an end-to-end supervised training.

8 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. Our proposedself-adaptive adjacency matrix is able to uncover unseengraph structures automatically from the data without anyguidance of prior knowledge.

9 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.]

10 , 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.