Unsupervised Deep Haar Scattering on Graphs
The classification of high-dimensional data defined on graphs is particularly difficult when the graph geometry is unknown. We introduce a Haar scattering transform on graphs, which computes invariant signal descriptors. It is implemented with a deep cascade of additions, subtractions and absolute values, which iteratively compute orthogonal Haar wavelet transforms. Multiscale neighborhoods of unknown graphs are estimated by minimizing an average total variation, with a pair matching algorithm of polynomial complexity. Supervised classification with dimension reduction is tested on data bases of scrambled images, and for signals sampled on unknown irregular grids on a sphere.
This paper uses transformations of the form  |W|\pi to build deep networks, where W is a discrete Haar transform, | | is the pointwise absolute value nonlinearity, and \pi is a permutation of the index set of the input vector.    The authors note that the \pi at each layer can be optimized for additive costs of pairs of indices in O(d^3) operations where d is the size of the input.  They  propose  a cost function that maximizes the variance of the output of a layer.  On the MNIST data set and a artificially transformed MNIST problem they use their (unsupervised) feature maps as inputs to an SVM and get strong classification results.This is an interesting paper and should be accepted.  The approach is unusual: they manage to arrange for a tractable combinatorial optimization for feature learning; after the optimization, the fprop is very fast.  I can't think of another work that does this.    On the other hand, the approach is not very well motivated.  The authors use a abs nonlinearity, why?  in their scattering network references, abs nonlinearities are used to introduce invariance to deformations; the choice of abs is well motivated because of its interactions with specially designed complex filters.   Why do we expect an abs nonlinearity to reduce nuisance variation more than variation that we care about generically/unsupervised, and with real haar type filters?  Moreover, the authors justify the cost function they use as the one that limits the contractiveness of their representation.  What stops the reductions in contractiveness from being precisely reintroduction of variance in nuisance dimensions?  The experiments do not give much intuition here: the MNIST data set is very special (it has well defined clusters), and previous works using sparse coding have gotten equally strong (permutation invariant) results (e.g. in the works of Julien Mairal and coauthors; although there the feature learning was supervised).    I would have loved a page or two less about filter banks etc. and more experiments on other data sets, or more analysis of what is happening here.minor details:  citation 11 the authors names are mangled, on line 212 \pi^0 appears twice, 3.1 needs to have a more explicit/clearer  definition of interlacingAll in all, interesting enough that it should really be accepted, but experiments are lacking: a strong result on MNIST is not especially illuminating or noteworthy.