Graph-structured data such as social networks, functional brain networks, gene regulatory networks, communications networks have brought the interest in generalizing deep learning techniques to graph domains. In this paper, we are interested to design neural networks for graphs with variable length in order to solve learning problems such as vertex classification, graph classification, graph regression, and graph generative tasks. Most existing works have focused on recurrent neural networks (RNNs) to learn meaningful representations of graphs, and more recently new convolutional neural networks (ConvNets) have been introduced. In this work, we want to compare rigorously these two fundamental families of architectures to solve graph learning tasks. We review existing graph RNN and ConvNet architectures, and propose natural extension of LSTM and ConvNet to graphs with arbitrary size. Then, we design a set of analytically controlled experiments on two basic graph problems, i.e. subgraph matching and graph clustering, to test the different architectures.   Numerical results show that the proposed graph ConvNets are 3-17% more accurate and 1.5-4x faster than graph RNNs. Graph ConvNets are also 36% more accurate than variational (non-learning) techniques. Finally, the most effective graph ConvNet architecture uses gated edges and residuality. Residuality plays an essential role to learn multi-layer architectures as they provide a 10% gain of performance. Convolutional neural networks of BID20 and recurrent neural networks of BID17 are deep learning architectures that have been applied with great success to computer vision (CV) and natural language processing (NLP) tasks. Such models require the data domain to be regular, such as 2D or 3D Euclidean grids for CV and 1D line for NLP. Beyond CV and NLP, data does not usually lie on regular domains but on heterogeneous graph domains. Users on social networks, functional time series on brain structures, gene DNA on regulatory networks, IP packets on telecommunication networks are a a few examples to motivate the development of new neural network techniques that can be applied to graphs. One possible classification of these techniques is to consider neural network architectures with fixed length graphs and variable length graphs.In the case of graphs with fixed length, a family of convolutional neural networks has been developed on spectral graph theory by BID6 . The early work of BID5 proposed to formulate graph convolutional operations in the spectral domain with the graph Laplacian, as an analogy of the Euclidean Fourier transform as proposed by BID14 . This work was extended by BID16 to smooth spectral filters for spatial localization. BID9 used Chebyshev polynomials to achieve linear complexity for sparse graphs, BID21 applied Cayley polynomials to focus on narrow-band frequencies, and BID27 dealt with multiple (fixed) graphs. Finally, BID19 simplified the spectral convnets architecture using 1-hop filters to solve the semi-supervised clustering task. For related works, see also the works of , and references therein.For graphs with variable length, a generic formulation was proposed by BID12 ; BID29 based on recurrent neural networks. The authors defined a multilayer perceptron of a vanilla RNN. This work was extended by BID22 using a GRU architecture and a hidden state that captures the average information in local neighborhoods of the graph. The work of BID30 introduced a vanilla graph ConvNet and used this new architecture to solve learning communication tasks. BID25 introduced an edge gating mechanism in graph ConvNets for semantic role labeling. Finally, BID4 designed a network to learn nonlinear approximations of the power of graph Laplacian operators, and applied it to the unsupervised graph clustering problem. Other works for drugs design, computer graphics and vision are presented by BID10 ; BID1 ; BID26 .In this work, we study the two fundamental classes of neural networks, RNNs and ConvNets, in the context of graphs with arbitrary length. Section 2 reviews the existing techniques. Section 3 presents the new graph NN models. Section 4 reports the numerical experiments. This work explores the choice of graph neural network architectures for solving learning tasks with graphs of variable length. We developed analytically controlled experiments for two fundamental graph learning problems, that are subgraph matching and graph clustering. Numerical experiments showed that graph ConvNets had a monotonous increase of accuracy when the network gets deeper, unlike graph RNNs for which performance decreases for a large number of layers. This led us to consider the most generic formulation of gated graph ConvNets, Eq. (11). We also explored the benefit of residuality for graphs, Eq. (12). Without residuality, existing graph neural networks are not able to stack more than a few layers. This makes this property essential for graph neural networks, which receive a 10% boost of accuracy when more than 6 layers were stacked. Future work will focus on solving domain-specific problems in chemistry, physics, and neuroscience.
We compare graph RNNs and graph ConvNets, and we consider the most generic class of graph ConvNets with residuality.
{"src": "scitldr-AIC_train", "paper_id": "HyXBcYg0b"}