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]:
This paper investigates the construction of convolutional[-like] neural networks (CNNs) on data with a graph structure that is not a simple grid like 2D images. Two types of constructions are proposed to generalize CNNs: one in the spectral domain (of the graph Laplacian) and one in the spatial domain (based on a multi-scale clustering of the graph). Experiments on variants of the MNIST dataset show that such constructions can lead to networks much smaller than fully connected networks, with similar or better generalization abilities.

Of the 4 papers I reviewed, this is definitely the one I spent the most time on, but also the one I understand the least. It is a very dense paper, with lots of interesting ideas and observations, but without detailed enough explanations in my opinion, thus making it pretty difficult to follow. I need to mention, though, that my knowledge of CNNs is limited to seeing a few times figures of LeNetX architectures, and hopefully people more familiar with CNNs will be able to better grasp the ideas presented here.

My first suggestion would be to start with the spatial construction (2.2) rather than the spectral one, as it is probably easier to visualize. And speaking of visualization, a picture showing the neighborhoods and how the various scales are used would be very helpful (I believe I understand what is being done here, but to be honest I think I need a picture to be sure).

On the spectral construction, if there is a way to put eq. 2.2/2.3 in pictures, it would be great as well. Something unclear about these equations is that we seem to keep only a given number of components at each step, but the definition of y_k does not show that. The main point I failed to understand here is what it means for the group structure to 'interact correctly with the Laplacian'. Unfortunately the example in 2.1.1 is not clear enough for me: instead of saying it recovers a 'standard convolutional net', could you describe the exact net structure, in particular in terms of weight sharing, pooling and subsampling layers? For 2.1.2 I do not really have any specific comment/question -- I was quite lost at this point -- except you could say what is a cubic spline kernel and why it makes sense to use it.

For experiments, please first say in intro of section 4 that the full description of the projected dataset will be given in 4.2. I read the intro of section 4 several times, trying to understand what it meant (it did not help that I understood 'the 2d unit sphere' as 'the unit sphere in 2d', ie a circle)... before finally giving up (I think I got the idea now after reading 4.2 and looking at the pictures, but the description is still confusing: what are e1, e2 and e3 and what is the motivation in the choice of their norms?).

Some other comments on experiments:
- I find the color maps hard to read. Would they look better in grey scale? (Fig. 4 (a)(b): how are we supposed to see it is the same feature?)
- Codenames for models in the results tables do not seem to be documented.
- In Fig. 2 is (a) really the finest? It looks like the coarsest.

Overall, I do believe it is a paper worth publishing. Taking advantage of the inner (unknown) structure of input variables is definitely a direction that could bring substantial improvements, the early experiments presented here are encouraging, and it brings some new ideas to the able. I hope, however, that the authors can increase the readability of the paper by adding more figures and explanations for those less familiar with CNNs.

A few more small remarks:
- The O(1) used in the intro could be a bit misleading, I think it is more O(kd) with k the local neighborhood size and d the number of layers? (or O(d log d) if k decreases exponentially with d)
- 'just an in the case of the grid': typo
- In 2.1.1 I am wondering how important is the assumption of equal variance, and if you coul use the correlation instead
- 'Suppose have a real valued nonlinearity': typo
- 'by a dropping a set number of coefficients': typo
- 'The upshot is that the the construction': typo
- 'navie choice': typo
- w_k-1 under eq. 2.4 should be W_k-1?
- 'gauranteed': typo
- 'the property that the subsampling the Fourier functions on the grid to a coarser grid': typo?
- Figure references in section 4 are messed up (all are Fig. 4.1)
- You could mention 'Learning the 2D topology of images' in the related work section