DIFFUSION SCATTERING TRANSFORMS ON GRAPHS
Stability is a key aspect of data analysis. In many applications, the natural notion of stability is geometric, as illustrated for example in computer vision. Scattering transforms construct deep convolutional representations which are certified stable to input deformations. This stability to deformations can be interpreted as stability with respect to changes in the metric structure of the domain. In this work, we show that scattering transforms can be generalized to nonEuclidean domains using diffusion wavelets, while preserving a notion of stability with respect to metric changes in the domain, measured with diffusion maps. The resulting representation is stable to metric perturbations of the domain while being able to capture "high-frequency" information, akin to the Euclidean Scattering.
The paper introduces an adaptation of the Scattering transform to signals defined on graphs
by relying on multi-scale diffusion wavelets, and studies a notion of stability of this representation
with respect to changes in the graph structure with an appropriate diffusion metric.
The notion of stability in convolutional networks is an important one, and the proposed notion of stability
with respect to diffusion distances seems like an interesting and relevant way to extend this to signals on graphs.
With this goal in mind, the authors introduce a scattering transform on graphs by relying on diffusion wavelets,
and provide an appropriate study of stability, which seems to highlight relevant properties of the graphs.
The proposed representation seems to provide benefits compared to the previous work of Zou & Lerman,
particularly regarding computational efficiency, as well as stability with respect to a metric that is perhaps more
useful, though there is a dependence on the graph topology through the spectral gaps.
In addition, the experiments on author attribution and source localization suggest that the
resulting representation remains discriminative, in addition to providing stability to changes in graph structure.
I find that these contributions provide an interesting advance in theoretical understanding of graph convolutional networks
from a stability perspective, in addition to introducing a useful non-learned representation,
and am thus in favor of acceptance.
Nevertheless, some parts of paper would benefit from further discussions and more clarity:
- other than empirically, one aspect that's missing compared to the original study of the scattering transform is energy preservation. The authors could at least provide a discussion of whether such a property can be obtained here as well (does it depend on the spectral gap through C(beta)?)
- what is the role of the spectral gap in the stability bounds? is this a drawback of the diffusion metric / choice of wavelets?
- Section 3.2 suggests that metric stability is a good way to characterize stability, by seeing deformations in Euclidian domains as a change to the ground metric. Yet, in Euclidian scattering, the same representation is applied to a deformed signal and the original signal, and stability is measured with the Euclidian metric.
Can the link be made more precise, by explaining what a deformation of a signal would be on a graph, or by applying arguments from the proposed construction to the Euclidian case?
- the paper is heavy on terminology from wavelets and harmonic analysis, a more detailed presentation of diffusion wavelets and related concepts such as localization would be beneficial. Also, it seems like the chosen wavelets in the construction favor spatial over frequential localization - is this due to a trade-off? if so, can it be avoided?
Some more detailed comments:
- Section 2, 'generally far weaker': what is meant by 'weaker'?
- Section 3.3:
  * 'calculus on T': T is used before being defined
  * clarify what norm is used (I assume operator norm?)
  * 'defines a distance', 'stronger than .. GH': this should probably be justified
- Section 4:
  * 'optimal spatial localization', 'temporal difference', 'favoring spatial over frequential localization': these could be clarified
  * 'amplify the signal': what does this mean?
  * the sentence about the choice of the appropriate J is not clear and should be further clarified
- Section 5.1:
  * the sentence about the choice pi/pi* = 1 should be clarified. Also, where is this assumption used?
  * epsilon_psi, epsilon_U should be defined
  * 'given that [..] by definition': this doesn't seem to be defined elsewhere
  * (16): isn't a factor m missing in the first term?