Spectral Networks and Locally Connected Networks on Graphs
Authors: Joan Bruna, Wojciech Zaremba, Arthur Szlam, Yann LeCun
ICLR 2014

Abstract: Convolutional Neural Networks are extremely efficient architectures in image and audio recognition tasks, thanks to their ability to exploit the local translational invariance of signal classes over their domain. In this paper we consider possible generalizations of CNNs to signals defined on more general domains without the action of a translation group. In particular, we propose two constructions, one based upon a hierarchical clustering of the domain, and another based on the spectrum of the graph Laplacian. We show through experiments that for low-dimensional graphs it is possible to learn convolutional layers with $O(1)$ parameters, resulting in efficient deep architectures.


Peer review:
[Review]:
> - A brief summary of the paper's contributions, in the context of prior work.

Exploiting the grid structure of different types of data (e.g., images) with convolutional neural networks has been essential to the recent breakthrough results in various pattern recognition tasks. This paper explores generalizing convolutional neural networks from grids to weighted graphs.

The reviewer finds weighted graph inputs best motivated by two datasets constructed at the end of the paper in order to test the proposed techniques. Both datasets are MNIST derivatives. The first subsamples the MNIST pixels in a disorganized manner, destroying the grid structure. The second projects MNIST onto a sphere, giving the input a more complicated manifold structure. Both of these are interpreted as weighted graphs in the natural manner. (A couple real-world examples of such structures occur to the reviewer: geo-spatial data and surfaces in 3D graphics.)

If we are persuaded that weighted graphs are an interesting type of input for a neural net, how can we generalize convolutional neural networks to them? The paper introduces two broad approaches. The first approach is to use a metric on the graph to define neighborhoods and build a locally-connected network.

The second, 'spectral,' approach is a bit more complicated. This can be understood as similar to how one can look at convolutional neural networks in terms of the Fourier Transform. A regular convolution can be thought of as pointwise multiplication in the Fourier domain. Drawing on the harmonic analysis of graphs, the paper uses the eigenvectors of the Laplacian, which have similar properties. Functions on the graph can be decomposed into coefficients of these eigenvectors and pointwise multiplied to achieve a convolution-like effect.

As mentioned previously, the authors test their techniques on two constructed datasets. For the subsampled MNIST, they are able to beat a fully-connected network with a locally-connected one, but only tie it with the spectral approach (though the spectral approach uses almost two orders of magnitude fewer parameters). For MNIST on a sphere, both approaches achieve slightly worse results than the fully-connected network (but, again, use fewer parameters).

> - An assessment of novelty and quality.

The reviewer is not familiar with this area but believes this work to be novel.

The ideas in this paper seem quite deep, and the experiments performed are interesting. In fact, the constructed datasets alone are interesting.

The exposition of the paper could be a bit stronger. This seems somewhat more sensitive because most people in the neural networks community will not have the mathematical background the paper presently requires.  A little more motivation and hand-holding could make the paper more accessible. That said, this doesn't seem like something that should be a barrier to publication.

> - A list of pros and cons (reasons to accept/reject)

Pros:
* Generalizing convolutional neural networks to graphs seems like a valuable enterprise.
* Explores some very intriguing ideas. In particular, the spectral generalization of convolutional networks feels quite deep.
* Constructs cute datasets to test the ideas on.

Cons:
* Paper could be more accessible (see above).