Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Graph scattering networks are an established way of encoding the structure of graphs. One of their drawbacks is that, due to having to consider all scattering paths (all possible combination of wavelets coming from each layer) their space complexity scales exponentially with the depth of the network.

The paper proposes a simple scheme for pruning the contributing wavelets so as to retain only those that are best aligned with the input signal of the given layer. The experiments show that this leads to scattering networks that perform about equally well, but are much sparser.

It is not entirely clear why alignment with the input signal should be a good proxy for how informative a given wavelet is. Depending on what downstream algorithm the scattering network's output is fed into, sometimes small coefficients could be important too. It might be unfair to only use an SVM in the experiments, since for SVMs larger magnitude features are important more likely to be relevant.

Some stability results are presented, but they are not terribly deep, and do not address the fact that the optimization is problem is highly nonlinear and therefore even after relatively small perturbations drastically different sets of wavelets may be selected. Nonetheless, this is an interesting contribution to the field of graph scattering networks.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors developed graph scattering transforms (GST) with a pruning algorithm, with the aim to reduce the running time and space cost, improve robustness to perturbations on input graph signal, and encourage flexibility for domain adaption. To this end, pruned graph scattering transform (pGST) was proposed based on the alignment between graph spectrum of the graph filters and the scattering feature. The intuition is to consider tree nodes as subbands in the graph spectrum and prune tree nodes that do not have sufficient overlap with the graph spectrum of a graph signal. The pruning problem was formulated as an optimization problem, and a solution was developed with theoretical analysis. Moreover, the analysis on the stability and sensitivity to perturbations were provided. Overall, the algorithm development is solid. The experimental results demonstrate the proposed pGST can outperform GST on graph classification task with less running time. Comparing with some supervised GNN methods, the proposed pGST can still achieve comparable results on several datasets.

First, it is good to see sufficient theoretical analysis on the optimization algorithm and algorithmic stability. However, one concern here is on the time complexity analysis. As mentioned in this work, the goal is to reduce running time and space cost, but the authors are aware that the worst case time complexity of pGST is the same as GST. Intuitively, with proper pruning, the efficiency can be improved, but it seems to be unknown on when will pGST achieve reasonable efficiency. More analysis, for example, on the impact of tau, may be helpful. In the experiments, it is better to see more insights on scattering pattern analysis, such as on the reasons behind the difference between using shallow GCN for social graphs and using deep GCN for SD point clouds. The current analysis only confirms previous results which didn't use pGST. Thus it is interesting to see what's more can be provided by using pGST to confirm these results. As a minor suggestion, the statistics of the graph data of authorship and facebook can be provided of better understanding of the results.

review_title: Official Blind Review #3

Meta-review: Main content: Authors developed graph scattering transforms (GST) with a pruning algorithm, with the aim to reduce the running time and space cost, improve robustness to perturbations on input graph signal, and encourage flexibility for domain adaption. 
Discussion:
reviewer 1: likes the idea, considers it to be elegant and work well. some questions regarding the proofs in the paper but it sounds like authors have addressed concerns.
reviewer 2: solid paper and results, has questons on stability results, like reviewer 2.
reviewer 3: likes the idea, including good sufficient theoretical analysis and algorthmic stability. concern is around complexity analysis but sounds like the authors have addressed the concerns.
Recommendation: Well written solid paper with good proofs. Authors addressed any reviewer concerns and all 3 reviewres vote weak accept. This is good for poster.
Decision: Accept (Poster)