One of the most notable contributions of deep learning is the application of convolutional neural networks (ConvNets) to structured signal classification, and in particular image classification. Beyond their impressive performances in supervised learning, the structure of such networks inspired the development of deep filter banks referred to as scattering transforms. These transforms apply a cascade of wavelet transforms and complex modulus operators to extract features that are invariant to group operations and stable to deformations. Furthermore, ConvNets inspired recent advances in geometric deep learning, which aim to generalize these networks to graph data by applying notions from graph signal processing to learn deep graph filter cascades. We further advance these lines of research by proposing a geometric scattering transform using graph wavelets defined in terms of random walks on the graph. We demonstrate the utility of features extracted with this designed deep filter bank in graph classification of biochemistry and social network data (incl. state of the art results in the latter case), and in data exploration, where they enable inference of EC exchange preferences in enzyme evolution.
# Summary of the paper
Inspired by the success of deep filter banks, this paper presents a designed deep filter bank for graphs that is based on random walks.  More precisely, the technique uses lazy random walks, expressed in terms of the graph Laplacian, and re-frames this in terms of graph signal processing. Similarly to wavelets, graph node features are calculated at different scales and subsequently summed in order to remain invariant under permutations. Several experiments on graph data sets demonstrate the performance of the new technique.
# Review
This paper is written very well and explains its method with high clarity. The principal issues I see are as follows:
- The originality of the contributions is not clear
- Missing theoretical discussion
- The experimental setup is terse and slightly confusing
Concerning the originality of the paper, the differences to Gama et al., 'Diffusion Scattering Transforms on Graphs' are not made clear. Cursory reading of this publication shows a large degree of similarity. Both of the papers make use of diffusion geometry, but Gama et al. _also_ define a multi-scale filter bank, similar to Eq. 4 and 5. The paper needs to position itself more clearly vis-à-vis this other publication. Is the present approach to be seen more as an application of the theory that was developed in the paper by Gama et al.? What are the key similarities and differences? In terms of space, this could be added to Section 3.2, which could be rephrased as a generic 'Differences to other methods' section and has to be slightly condensed in any case (see my suggestions below). Another publication by Zou & Lerman, 'Graph Convolutional Neural Networks via Scattering', is also cited as an inspiration, but here the differences are larger in my understanding and do not necessitate further justification. Last, the publication 'Graph Capsule Convolutional Neural Networks' by Verma & Zhang is also cited for the definition of 'scattering capsules'. Again, cursory reading of the publication shows that this approach is similar to the presented one; the only difference being which features are used for the definition of capsules. I recommend referring to the invariants as 'capsules' and link it back to Verma & Zhang so that the provenance of the terminology is clear.
Concerning the theoretical part of the paper, I miss a discussion of the complexity of the approach. Such a discussion does not have to be long, but in particular since the paper mentions that the applicability of scattering transforms for transfer learning (and also remarks about the universality of them in Section 4), some space should be devoted to theoretical considerations (memory complexity, runtime complexity). This would strengthen the paper a lot, in particular in light of the complexity of other approaches! Furthermore, an additional experiment about the stability of scattering transforms appears warranted. While I applaud the experimental description in the paper (number of scales, how the maximum scale is chosen, ...), an additional proof or experiment in the appendix should deal with the stability. Let's assume that for extremely large graphs, I am content with 'almost-but-not-quite-as-good' classification performance. Is it possible to achieve this by limiting the number of scales? How much to the results depend on the 'right' choice here?
Concerning the experimental setup, I think that the way (average) accuracies are reported at present is slightly misleading. The paper even remarks about this in footnote 2. While I understand the need of demonstrating the universality of these features, I think that the current setup is not optimal for this. I would recommend (in addition to reporting accuracies) a transfer learning setup rather in which the beneficial properties of the new method can be better explored. More precisely, the claim from Section 4, 4th paragraph ('Since the scattering transform...') needs to be further explored. This appears to be a unique feature of the new method. The current experimental setup does not exploit it. As a side-note, I realize that this might sound like a standard request for 'show more experiments', but I think the paper would be more impactful if it contained one scenario in which its benefits over other approaches are clear.
# Suggestions for improvement
The paper flows extremely well and it is clear that care has been taken to ensure that everything can be understood. I liked the discussion of invariance properties in particular. There are only a few minor things that can be improved:
- 'covariant' and 'equivariant', while common in (graph) signal processing, could be briefly explained to increase accessibility and impact
- 'order' and 'layer' are not used consistently: in the caption of Figure 2a, the term 'order' is used, but for Eq. 4 and 5, for example, the term 'layer' is employed. Since 'layer' is more reminiscent of a DNN, I would suggest to use 'order' throughout the paper, because it meshes better with the way the scattering invariants are defined.
- the notation $Sx$ is slightly overloaded; in Figure 2a, for example, it is not clear at first that the individual cascades are supposed to form a *set*; this is only explained at the end of Section 3.1; to make matters more consistent, the figure should be updated and the combination of individual cascades should be made clear
- In Eq. 5, the bars of the absolute value are not set correctly; the absolute value should cover $\psi_j x(v_i)$ and not $(v_i)$ itself.
- minor 'gripe': $\psi^{(J)}$ is defined as a set in Eq. 2, but it is treated as a matrix or an operator (and also referred to as such); this should be more consistent
- The discussion of the aggregation of multiple statistics in Section 3.2 appears to be somewhat redundant in light of the discussion for Eq. 4 and Eq. 5 in the preceding section
- in the appendix, more details about the training of the FCN should be added; all other parts of the experiments are described in sufficient detail, but the training process requires additional information about learning rates etc.