
Transferability of Spectral Graph Convolutional Neural Networks
This paper focuses on spectral graph convolutional neural networks (ConvNets), where filters are defined as elementwise multiplication in the frequency domain of a graph. In machine learning settings where the dataset consists of signals defined on many different graphs, the trained ConvNet should generalize to signal on graphs unseen in the training set. It is thus important to transfer filters from one graph to the other. Transferability, which is a certain type of generalization capability, can be loosely defined as follows: if two graphs describe the same phenomenon, then a single filter/ConvNet should have similar repercussions on both graphs. This paper aims at debunking the common misconception that spectral filters are not transferable. We show that if two graphs discretize the same continuous metric space, then a spectral filter/ConvNet has approximately the same repercussion on both graphs. Our analysis is more permissive than the standard analysis. Transferability is typically described as the robustness of the filter to small graph perturbations and reindexing of the vertices. Our analysis accounts also for large graph perturbations. We prove transferability between graphs that can have completely different dimensions and topologies, only requiring that both graphs discretize the same underlying continuous space.
07/30/2019 ∙ by Ron Levie, et al. ∙ 32 ∙ shareread it

A wavelet Plancherel theory with application to sparse continuous wavelet transform
We introduce a framework for calculating sparse approximations to signals based on elements of continuous wavelet systems. The method is based on an extension of the continuous wavelet theory. In the new theory, the signal space is embedded in larger "abstract" signal space, which we call the windowsignal space. There is a canonical extension of the wavelet transform on the windowsignal space, which is an isometric isomorphism from the windowsignal space to a space of functions on phase space. Hence, the new framework is called a waveletPlancherel theory, and the extended wavelet transform is called the waveletPlancherel transform. Since the waveletPlancherel transform is an isometric isomorphism, any operation on phase space can be pulledback to an operation in the windowsignal space. Using this pull back property, it is possible to pull back a search for big wavelet coefficients to the windowsignal space. We can thus avoid inefficient calculations on phase space, performing all calculations entirely in the windowsignal space. We consider in this paper a matching pursuit algorithm based on this coefficient search approach. Our method has lower computational complexity than matching pursuit algorithms based on a naive coefficient search.
12/07/2017 ∙ by Ron Levie, et al. ∙ 0 ∙ shareread it

On the Transferability of Spectral Graph Filters
This paper focuses on spectral filters on graphs, namely filters defined as elementwise multiplication in the frequency domain of a graph. In many graph signal processing settings, it is important to transfer a filter from one graph to another. One example is in graph convolutional neural networks (ConvNets), where the dataset consists of signals defined on many different graphs, and the learned filters should generalize to signals on new graphs, not present in the training set. A necessary condition for transferability (the ability to transfer filters) is stability. Namely, given a graph filter, if we add a small perturbation to the graph, then the filter on the perturbed graph is a small perturbation of the original filter. It is a common misconception that spectral filters are not stable, and this paper aims at debunking this mistake. We introduce a space of filters, called the Cayley smoothness space, that contains the filters of stateoftheart spectral filtering methods, and whose filters can approximate any generic spectral filter. For filters in this space, the perturbation in the filter is bounded by a constant times the perturbation in the graph, and filters in the Cayley smoothness space are thus termed linearly stable. By combining stability with the known property of equivariance, we prove that graph spectral filters are transferable.
01/29/2019 ∙ by Ron Levie, et al. ∙ 0 ∙ shareread it
Ron Levie
is this you? claim profile