The geometric structure of a data domain can be described with a graph. In many applications such as social networks and sensor network, the graph is unknown. The classification of such data is particularly difficult, due to the translation and displacement of signals on the unknown graph.

Haar scattering transform on graphs computes unsupervised 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.

A Haar scattering is calculated by iteratively applying the permutation invariant operator (a,b) -> (a+b,|a-b|). It computes progressively more invariant signal descriptors by cascading this operator at multiple scales in the deep network.

At each layer of the network, it finds an optimal pairing which minimizes the total variation of scattering vectors, averaged over the training set. The pairing optimizations thus generate hierarchical dyadic partitions of the graph vertices.

Several Haar scattering transforms are needed to obtain a complete signal representation. The unsupervised learning computes multiple partitions by optimizing pairings over non-overlapping subsets of the training set.

Paper

• Unsupervised Deep Haar Scattering on Graphs, Chen X., Cheng X., Mallat S., Conference on Neural Information Processing Systems (NIPS), Montreal, Quebec, Canada, Dec. 2014. (PDF)

Software

• HaarScat is a toolbox for computing Haar scattering transforms. Classification framework with feature selection and a Gaussian kernel SVM is provided.