The rise of graph-structured data such as social networks, regulatory networks, citation graphs, and functional brain networks, in combination with resounding success of deep learning in various applications, has brought the interest in generalizing deep learning models to non-Euclidean domains. 
 In this paper, we introduce a new spectral domain convolutional architecture for deep learning on graphs. The core ingredient of our model is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. Our model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely-connected graphs, and can handle different constructions of Laplacian operators. Extensive experimental results show the superior performance of our approach on spectral image classification, community detection, vertex classification and matrix completion tasks. In many domains, one has to deal with large-scale data with underlying non-Euclidean structure. Prominent examples of such data are social networks, genetic regulatory networks, functional networks of the brain, and 3D shapes represented as discrete manifolds. The recent success of deep neural networks and, in particular, convolutional neural networks (CNNs) BID19 have raised the interest in geometric deep learning techniques trying to extend these models to data residing on graphs and manifolds. Geometric deep learning approaches have been successfully applied to computer graphics and vision ; BID3 a) ; BID24 , brain imaging BID18 , and drug design BID10 problems, to mention a few. For a comprehensive presentation of methods and applications of deep learning on graphs and manifolds, we refer the reader to the review paper BID4 .Related work. The earliest neural network formulation on graphs was proposed by BID11 and BID27 , combining random walks with recurrent neural networks (their paper has recently enjoyed renewed interest in BID20 ; BID30 ). The first CNN-type architecture on graphs was proposed by BID5 . One of the key challenges of extending CNNs to graphs is the lack of vector-space structure and shift-invariance making the classical notion of convolution elusive. Bruna et al. formulated convolution-like operations in the spectral domain, using the graph Laplacian eigenbasis as an analogy of the Fourier transform BID29 ). BID13 used smooth parametric spectral filters in order to achieve localization in the spatial domain and keep the number of filter parameters independent of the input size. BID8 proposed an efficient filtering scheme using recurrent Chebyshev polynomials applied on the Laplacian operator. BID17 simplified this architecture using filters operating on 1-hop neighborhoods of the graph. BID0 proposed a Diffusion CNN architecture based on random walks on graphs. BID24 (and later, Hechtlinger et al. (2017) ) proposed a spatial-domain generalization of CNNs to graphs using local patch operators represented as Gaussian mixture models, showing a significant advantage of such models in generalizing across different graphs. In BID25 , spectral graph CNNs were extended to multiple graphs and applied to matrix completion and recommender system problems.Main contribution. In this paper, we construct graph CNNs employing an efficient spectral filtering scheme based on Cayley polynomials that enjoys similar advantages of the Chebyshev filters BID8 ) such as localization and linear complexity. The main advantage of our filters over BID8 is their ability to detect narrow frequency bands of importance during training, and to specialize on them while being well-localized on the graph. We demonstrate experimentally that this affords our method greater flexibility, making it perform better on a broad range of graph learning problems.Notation. We use a, a, and A to denote scalars, vectors, and matrices, respectively.z denotes the conjugate of a complex number, Re{z} its real part, and i is the imaginary unit. diag(a 1 , . . . , a n ) denotes an n×n diagonal matrix with diagonal elements a 1 , . . . , a n . Diag(A) = diag(a 11 , . . . , a nn ) denotes an n × n diagonal matrix obtained by setting to zero the off-diagonal elements of A. Off(A) = A − Diag(A) denotes the matrix containing only the off-diagonal elements of A. I is the identity matrix and A • B denotes the Hadamard (element-wise) product of matrices A and B. Proofs are given in the appendix. In this paper, we introduced a new efficient spectral graph CNN architecture that scales linearly with the dimension of the input data. Our architecture is based on a new class of complex rational Cayley filters that are localized in space, can represent any smooth spectral transfer function, and are highly regular. The key property of our model is its ability to specialize in narrow frequency bands with a small number of filter parameters, while still preserving locality in the spatial domain. We validated these theoretical properties experimentally, demonstrating the superior performance of our model in a broad range of graph learning problems.
A spectral graph convolutional neural network with spectral zoom properties.
{"src": "scitldr-AIC_train", "paper_id": "S1680_1Rb"}