  Deep Learning's recent successes have mostly relied on Convolutional
Networks, which exploit fundamental statistical properties of images, sounds
and video data: the local stationarity and multi-scale compositional structure,
that allows expressing long range interactions in terms of shorter, localized
interactions. However, there exist other important examples, such as text
documents or bioinformatic data, that may lack some or all of these strong
statistical regularities.
  In this paper we consider the general question of how to construct deep
architectures with small learning complexity on general non-Euclidean domains,
which are typically unknown and need to be estimated from the data. In
particular, we develop an extension of Spectral Networks which incorporates a
Graph Estimation procedure, that we test on large-scale classification
problems, matching or improving over Dropout Networks with far less parameters
to estimate.
