Graph convolutional networks (GCNs) have achieved remarkable performance in a variety of network science learning tasks. However, theoretical analysis of such approaches is still at its infancy. Graph scattering transforms (GSTs) are non-trainable deep GCN models that are amenable to generalization and stability analyses. The present work addresses some limitations of GSTs by introducing a novel so-termed pruned (p)GST approach. The resultant pruning algorithm is guided by a graph-spectrum-inspired criterion, and retains informative scattering features on-the-fly while bypassing the exponential complexity associated with GSTs. It is further established that pGSTs are stable to perturbations of the input graph signals with bounded energy. Experiments showcase that i) pGST performs comparably to the baseline GST that uses all scattering features, while achieving significant computational savings; ii) pGST achieves comparable performance to state-of-the-art GCNs; and iii) Graph data from various domains lead to different scattering patterns, suggesting domain-adaptive pGST network architectures.
A scattering transform on graphs consists in the cascade of wavelets, modulus non-linearity and a low-pass filter. The wavelets and the low-pass are designed in the spectral domain, which is computationally extensive. Instead to compute any cascades of wavelets, this paper proposes to prune scattering paths which have the lowest energy. This is simple, and numerically efficient.
I find this idea elegant because it is simple, and it seems to work well(and even improve standard GST). Yet, I would have liked to see more explanations concerning the threshold selection: indeed, a naive simple grid search to find the best threshold could be less efficient than doing no pruning.(at least at training, but also for testing: maybe some guarantees that the test accuracy won't be lower under reasonable assumptions)
Pros :
- Good performances with a simple method. This is a positive aspect of the paper.
- This is an attempt to scale spectral methods on large graphs.
- A stability study of the practical impact of this threshold is done.
Cons:
- The bound in lemma 1 sounds pretty un-optimal. Indeed, the frame bound is B, thus the corresponding operator is B-lipschitz, and the modulus operator is 1-lipscthiz. Thus, shouldn't the lipschitz constant be simply $\sim B^{L+1}$? I don't understand why it does depend on the number of filters. Also, if B>1, then the lipschitz constant can be arbitrary high. This sounds to me like a big issue, because high lipschitz constant would indicate an unstability. For instance if $B\geq 1$, for order 1:
$B^4\Vert x\Vert^2\geq B^2\Vert Hx\Vert^2 + B^2\Vert Ux\Vert^2\geq \Vert |H||H|x\Vert^2+\Vert U|H|x\Vert^2+B^2\Vert Ux\Vert^2\geq \Vert \Phi x\Vert^2$
- How is the threshold selected? It is obvious that the normalisation of the filters play an extremely important role(if the frame was tight, I wouldn't complain). This should be well documented and this is currently not the case. I find this is critical. Maybe a parallel with the bias of soft-thresholding operators could be drawn to find an optimal value?
- I also believe the threshold shouldn't take in account the low-pass filter contribution. Indeed, as for equation (5), the energy of z_(p) is the sum of the energy of the high frequencies of z_p and the low frequency energy. It would not add any compute time(because this quantity is computed anyway) to measure the relative energy w.r.t. the high frequencies without the low-pass filter. It would write then: ||z_(puj)||^2/(||z_p||^2-||U(z_p)||^2) . Indeed, in classical signal processing (e.g., images, spectrogram), the low pass filter contains much more energy than other frequencies, which are however informative. In the current setting, discriminative scattering path could be discarded simply because the wavelet combined with a modulus did a good job at demodulating the signal to the low frequency domain. 
- ". Furthermore, stable features are not necessary useful for learning. For example, an all-zero scattering feature at a certain output channel of the GST is non-informative albeit stable to any deformation" > I find this statement pretty obvious, could the authors think of a better example? In my opinion, stability to deformation at not extra-cost is always desirable because it helps creating a linear invariants.
minor: 
- "Under certain conditions on graph filter banks, GSTs are endowed with energy conservation properties, as well as stability meaning robustness to graph topology deformations (Gama et al., 2019a)." > I think the citation about (Zou&Lerman) should be added here. (next to "conservation property")
- The notation p^{(l)}\cup j can be a bit confusing, couldn't this author write (p^{(l)},j) or anything similar?
- Top equation of page 5: $V^Th_j(S)x=diag(h_j)$. Shouldn't there be a \hat on diag(h_j)? Indeed, the current notation is a bit confusing... I guess it would be nice to introduce the convolution operator, in Fourier.
- "if the graph spectrum {hj (λn)}n is not aligned with [xb]n" . I'm not sure to understand the term "align" in this context, in particular because it seems to be used in different contexts in the paper. Could you simplify to "if the support of h_j is included in the support of \hat x?"
- Figures and Tables are too small...
post rebuttal:
I found the arguments of the authors convincing, they addressed my concern and revised the paper accordingly.