We present graph wavelet neural network (GWNN), a novel graph convolutional neural network (CNN), leveraging graph wavelet transform to address the shortcomings of previous spectral graph CNN methods that depend on graph Fourier transform. Different from graph Fourier transform, graph wavelet transform can be obtained via a fast algorithm without requiring matrix eigendecomposition with high computational cost. Moreover, graph wavelets are sparse and localized in vertex domain, offering high efficiency and good interpretability for graph convolution. The proposed GWNN significantly outperforms previous spectral graph CNNs in the task of graph-based semi-supervised classification on three benchmark datasets: Cora, Citeseer and Pubmed. Convolutional neural networks (CNNs) BID15 have been successfully used in many machine learning problems, such as image classification BID10 and speech recognition BID11 , where there is an underlying Euclidean structure. The success of CNNs lies in their ability to leverage the statistical properties of Euclidean data, e.g., translation invariance. However, in many research areas, data are naturally located in a non-Euclidean space, with graph or network being one typical case. The non-Euclidean nature of graph is the main obstacle or challenge when we attempt to generalize CNNs to graph. For example, convolution is not well defined in graph, due to that the size of neighborhood for each node varies dramatically .Existing methods attempting to generalize CNNs to graph data fall into two categories, spatial methods and spectral methods, according to the way that convolution is defined. Spatial methods define convolution directly on the vertex domain, following the practice of the conventional CNN. For each vertex, convolution is defined as a weighted average function over all vertices located in its neighborhood, with the weighting function characterizing the influence exerting to the target vertex by its neighbors . The main challenge is to define a convolution operator that can handle neighborhood with different sizes and maintain the weight sharing property of CNN. Although spatial methods gain some initial success and offer us a flexible framework to generalize CNNs to graph, it is still elusive to determine appropriate neighborhood.Spectral methods define convolution via graph Fourier transform and convolution theorem. Spectral methods leverage graph Fourier transform to convert signals defined in vertex domain into spectral domain, e.g., the space spanned by the eigenvectors of the graph Laplacian matrix, and then filter is defined in spectral domain, maintaining the weight sharing property of CNN. As the pioneering work of spectral methods, spectral CNN BID3 exploited graph data with the graph Fourier transform to implement convolution operator using convolution theorem. Some subsequent works make spectral methods spectrum-free BID4 BID14 BID12 , achieving locality in spatial domain and avoiding high computational cost of the eigendecomposition of Laplacian matrix.In this paper, we present graph wavelet neural network to implement efficient convolution on graph data. We take graph wavelets instead of the eigenvectors of graph Laplacian as a set of bases, and define the convolution operator via wavelet transform and convolution theorem. Graph wavelet neural network distinguishes itself from spectral CNN by its three desirable properties: (1) Graph wavelets can be obtained via a fast algorithm without requiring the eigendecomposition of Laplacian matrix, and thus is efficient; (2) Graph wavelets are sparse, while eigenvectors of Laplacian matrix are dense. As a result, graph wavelet transform is much more efficient than graph Fourier transform; (3) Graph wavelets are localized in vertex domain, reflecting the information diffusion centered at each node BID27 . This property eases the understanding of graph convolution defined by graph wavelets.We develop an efficient implementation of the proposed graph wavelet neural network. Convolution in conventional CNN learns an individual convolution kernel for each pair of input feature and output feature, causing a huge number of parameters especially when the number of features is high. We detach the feature transformation from convolution and learn a sole convolution kernel among all features, substantially reducing the number of parameters. Finally, we validate the effectiveness of the proposed graph wavelet neural network by applying it to graph-based semi-supervised classification. Experimental results demonstrate that our method consistently outperforms previous spectral CNNs on three benchmark datasets, i.e., Cora, Citeseer, and Pubmed.2 OUR METHOD 2.1 PRELIMINARY Let G = {V, E, A} be an undirected graph, where V is the set of nodes with |V| = n, E is the set of edges, and A is adjacency matrix with A i,j = A j,i to define the connection between node i and node j. The graph Laplacian matrix L is defined as L = D −A where D is a diagonal degree matrix with D i,i = j A i,j , and the normalized Laplacian matrix is L = I n − D −1/2 AD −1/2 where I n is the identity matrix. Since L is a real symmetric matrix, it has a complete set of orthonormal eigenvectors U = (u 1 , u 2 , ..., u n ), known as Laplacian eigenvectors. These eigenvectors have associated real, non-negative eigenvalues {λ l } n l=1 , identified as the frequencies of graph. Eigenvectors associated with smaller eigenvalues carry slow varying signals, indicating that connected nodes share similar values. In contrast, eigenvectors associated with larger eigenvalues carry faster varying signals across connected nodes. Replacing graph Fourier transform with graph wavelet transform, we proposed GWNN. Graph wavelet transform has three desirable properties: (1) Graph wavelets are local and sparse; (2) Graph wavelet transform is computationally efficient; (3) Convolution is localized in vertex domain. These advantages make the whole learning process interpretable and efficient. Moreover, to reduce the number of parameters and the dependence on huge training data, we detached the feature transformation from convolution. This practice makes GWNN applicable to large graphs, with remarkable performance improvement on graph-based semi-supervised learning.
We present graph wavelet neural network (GWNN), a novel graph convolutional neural network (CNN), leveraging graph wavelet transform to address the shortcoming of previous spectral graph CNN methods that depend on graph Fourier transform.
{"src": "scitldr-AIC_train", "paper_id": "H1ewdiR5tQ"}