An End-to-End Deep Learning Architecture for Graph ...

1 An End-to-End deep LearningArchitecture for Graph ClassificationMuhan Zhang, Zhicheng Cui, Marion Neumann, Yixin ChenDepartment of Computer Science and Engineering, Washington University in St. Louis{muhan, , networks are typically designed to deal with data intensor forms. In this paper, we propose a novel neural networkarchitecture accepting graphs of arbitrary structure. Given adataset containing graphs in the form of(G, y)whereGis agraph andyis its class, we aim to develop neural networksthat read the graphs directly and learn a classification are two main challenges: 1) how to extract useful fea-tures characterizing the rich information encoded in a graphfor classification purpose, and 2) how to sequentially read agraph in a meaningful and consistent order. To address the firstchallenge, we design a localized Graph convolution model andshow its connection with two Graph kernels.}

2 To address thesecond challenge, we design a novel SortPooling layer whichsorts Graph vertices in a consistent order so that traditionalneural networks can be trained on the graphs. Experimentson benchmark Graph classification datasets demonstrate thatthe proposed Architecture achieves highly competitive per-formance with state-of-the-art Graph kernels and other graphneural network methods. Moreover, the Architecture allowsend-to-end gradient-based training with original graphs, with-out the need to first transform graphs into IntroductionThe past few years have seen the growing prevalence ofneural networks on application domains such as image classi-fication (Alex, Sutskever, and Hinton 2012), natural languageprocessing (Mikolov et ), reinforcement Learning (Mnih et ), and time series analysis (Cui, Chen, andChen 2016). The connection structure between layers makesneural networks suitable for processing signals in tensorforms where the tensor elements are arranged in a mean-ingful order.

3 This fixed input order is a cornerstone for neuralnetworks to extract higher-level features. For example, if werandomly shuffle the pixels of an image shown in Figure 1,then state-of-the-art convolutional neural networks (CNN)fail to recognize it as an images and many other types of data are natu-rally presented with order, there is another major category ofstructured data, namely graphs, which usually lack a tensorrepresentation with fixed ordering. Examples include molecu-lar structures, knowledge graphs, biological networks, socialCopyrightc 2018, Association for the Advancement of ArtificialIntelligence ( ). All rights reserved. Figure 1: A consistent input ordering is crucial for , and text documents with dependencies. The lackof ordered tensor representations limits the applicability ofneural networks on graphs. In this paper, we aim at designingnovel neural network structures that can accept graphs andlearn predictive , there is a growing interest in generalizing neuralnetworks to graphs.

4 (Bruna et ) generalized convo-lutional networks to graphs in the spectral domain, wherefilters are applied on a Graph s frequency modes computedby Graph fourier transform. This transformation involvesexpensive multiplications with the eigenvector matrix of thegraph Laplacian. To reduce the computation burden, (Def-ferrard, Bresson, and Vandergheynst 2016) parameterizedthe spectral filters as chebyshev polynomials of eigenvalues,and achieved efficient and localized filters. One limitation ofthe above spectral formulations is that they rely on the fixedspectrum of the Graph Laplacian, and thus are suitable onlyfor graphs with a single structure (and varying signals on ver-tices). Spatial formulations, on the contrary, are not restrictedto a fixed Graph structure. To extract local features, severalworks independently proposed to propagate features betweenneighboring vertices.

5 (Duvenaud et ) proposed differ-entiable Neural Graph Fingerprints, which propagate featuresbetween 1-hop neighbors to simulate the traditional circularfingerprint. (Atwood and Towsley 2016) proposed Diffusion-CNN, which propagates neighbors with different hops to thecenter using different weights. Later, (Kipf and Welling 2016)developed a first-order approximation of the spectral convolu-tion in (Defferrard, Bresson, and Vandergheynst 2016) whichalso resulted in propagation between neighboring vertices.(Niepert, Ahmed, and Kutzkov 2016) proposed another wayof spatial Graph convolution by extracting fixed-sized localpatches from nodes neighborhoods and linearizing theseThe Thirty-Second AAAI Conferenceon Artificial Intelligence (AAAI-18)4438patches with Graph labeling methods and Graph canonizationtools. The resulting algorithm is called spatial methods do not require a single Graph struc-ture, they can be applied to both node classification andgraph classification tasks.

6 Although achieving state-of-the-art node classification results (Atwood and Towsley 2016;Kipf and Welling 2016), most previous works have relativelyworse performance on Graph classification tasks. One rea-son for this is that after extracting localized vertex features,these features are directly summed up as a Graph -level fea-ture used for Graph classification (Duvenaud et ;Defferrard, Bresson, and Vandergheynst 2016).In this paper, we propose a new Architecture that can keepmuch more vertex information and learn from the globalgraph topology. A key innovation is a newSortPooling layer,which takes as input a Graph s unordered vertex features fromspatial Graph convolutions. Instead of summing up thesevertex features, SortPooling arranges them in a consistentorder, and outputs a sorted Graph representation with a fixedsize, so that traditional convolutional neural networks canread vertices in a consistent order and be trained on thisrepresentation.

7 As a bridge between Graph convolution layersand traditional neural network layers, the SortPooling layercan backpropagate loss gradients through it, integrating graphrepresentation and Learning into one End-to-End contributions in this paper are as follows. 1) We pro-pose a novel End-to-End deep Learning Architecture for graphclassification. It directly accepts graphs as input without theneed of any preprocessing. 2) We propose a novel spatialgraph convolution layer to extract multi-scale vertex features,and draw analogies with popular Graph kernels to explain whyit works. 3) We develop a novel SortPooling layer to sort thevertex features instead of summing them up, which can keepmuch more information and allows us to learn from the globalgraph topology. 4) Experimental results on benchmark graphclassification datasets show that ourDeep Graph Convolu-tional Neural Network(DGCNN) is highly competitive withstate-of-the-art Graph kernels, and significantly outperformsmany other deep Learning methods for Graph deep Graph Convolutional NeuralNetwork (DGCNN)DGCNNhas three sequential stages: 1) Graph convolutionlayersextract vertices local substructure features and definea consistent vertex ordering; 2) aSortPooling layersorts thevertex features under the previously defined order and unifiesinput sizes; 3) traditional convolutional and dense layers readthe sorted Graph representations and make predictions.

8 Weshow the DGCNN Architecture in Figure useAto denote the adjacency matrix of a Graph , andnthe number of vertices. We consider only simple graphs inthis paper, ,Ais a symmetric 0/1 matrix, and the graphhas no self-loops. Suppose each vertex has ac-dimensionalfeature vector, we useX Rn cto denote the Graph s nodeinformation matrix with each row representing a vertex. Forgraphs with vertex labels or attributes,Xcan be the one-hotencoding matrix of the vertex labels or the matrix of multi-dimensional vertex attributes. For graphs without vertexlabels,Xcan be defined as a column vector of normalizednode degrees. We call a column inXafeature channelofthe Graph , thus the Graph hascinitial channels. In the rest ofthe paper, we usePito denote theithrow of any matrixP,andPijto denote the entry(i, j)ofP. For a vertexv,weuse (v)to denote the set ofv s neighboring Graph convolution layersProposed formGiven a graphAand its node informationmatrixX Rn c, our Graph convolution layer takes thefollowing form:Z=f( D 1 AXW),(1)where A=A+Iis the adjacency matrix of the graphwith added self-loops, Dis its diagonal degree matrix with Dii= j Aij,W Rc c is a matrix of trainable graphconvolution parameters,fis a nonlinear activation function,andZ Rn c is the output activation Graph convolution can be separated into four , a linear feature transformation is applied to the nodeinformation matrix byXW, mapping thecfeature channelstoc channels in the next layer.

9 The filter weightsWareshared among all vertices. The second step, AYwhereY:=XWpropagates node information to neighboringvertices as well as the node itself. To see this, we notice that( AY)i= j AijYj=Yi+ j (i)Yj, , theithrowof the resulting matrix is the summation ofYiitself andYjfromi s neighboring nodes. The third step normalizes eachrowiby multiplying D 1ii, in order to keep a fixed featurescale after Graph convolution. The last step applies a point-wise nonlinear activation functionfand outputs the graphconvolution Graph convolution aggregates node information inlocal neighborhoods to extract local substructure extract multi-scale substructure features, we stack multiplegraph convolution layers (1) as followsZt+1=f( D 1 AZtWt),(2)whereZ0=X,Zt Rn ctis the output of thetthgraphconvolution layer,ctis the number of output channels oflayert, andWt Rct ct+1mapsctchannels toct+1chan-nels.

10 After multiple Graph convolution layers, we add a layerto concatenate the outputZt,t=1,..,hhorizontally toform a concatenated output, written asZ1:h:= [Z1,..,Zh],wherehis the number of Graph convolution layers andZ1:h Rn h1ct. In the concatenated outputZ1:h, eachrow can be regarded as a feature descriptor of a vertex,encoding its multi-scale local substructure that our Graph convolution form is similar to thespectral filter proposed in (Kipf and Welling 2016) it alsopropagates neighboring nodes to center except for using adifferent propagation matrix. In fact, our Graph convolutionform (1) also has a spectral formulation. We will discusstheir relations and differences in detail in the supplemen-tary material and show that our Graph convolution form is atheoretically closer approximation to the Weisfeiler-Lehmanalgorithm (Weisfeiler and Lehman 1968).