  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.
