Pruned Graph Scattering Transforms
Authors: Vassilis N. Ioannidis
Siheng Chen
Georgios B. Giannakis
Venue:  (2020)
Keywords: Graph scattering transforms
pruning
graph convolutional networks
stability
deep learning

Abstract: 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.

Published as a conference paper at ICLR 2020
PRUNED GRAPH SCATTERING TRANSFORMS
Vassilis N. Ioannidis
Siheng Chen
Dpt. of Electrical and Computer Engineering Univ. of Minnesota Minneapolis, MN, USA
Mitsubishi Electric Research Laboratories Cambridge, MA, USA schen
ioamn006@ @ umn.edu
Georgios B. Giannakis
Dpt. Electrical and Computer Engineering Univ. of Minnesota
Minneapolis, MN, USA georgios @ udn
ABSTRACT
Graph convolutional networks (GCNs) have achieved remarkable performance in a variety of network science learning tasks. However, theoretical analysis of such approaches is still 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 graph-spectrun-inspired criterion, and retains informative scattering features on-the 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 state-of-the-art GCNs; and iii) Graph data from various domains lead to different scattering patterns, suggesting domain-adaptive PGST network architectures.
INTRODUCTION
The abundance of graph-structured data calls for advanced learning techniques, and complements nicely standard machine learning tools that cannot be directly applied to irregular data domains. Permeating the benefits of deep learning to the graph domain, graph convolutional networks (GCNs)
provide versatile and powerful framework to learn from complex graph data (Bronstein et al.) 2017). GCNs and variants thereof have attained remarkable success in social network analysis, 3D point cloud processing, recommender systems and action recognition. However, researchers have recently reported inconsistent perspectives on the appropriate designs for GCN architectures. For example, experiments in social network analysis have argued that deeper GCNs marginally increase the learning performance (Wu et al. 2019), whereas method for 3D point cloud segmentation achieves state-of- the-art performance with a 56-layer GCN network (Li et al., (011).. These 'controversial" empirical findings motivate theoretical analysis understand the fundamental performance factors and the architecture design choices for GCNs.
Aiming bestow GCNs with theoretical guarantees, one promising research direction is to study graph scattering transforms (GSTs). GSTs are non- non-trainable GCNs comprising a cascade of graph filter banks followed by nonlinear activation functions. The graph filter banks are mathematically designed and are adopted to scatter an input graph signal into multiple channels. GSTs extract scattering features that can be utilized towards graph learning tasks (Gao et al. 2019),, with competitive performance especially when the number of training examples is small. Under certain conditions on the graph filter banks, GSTs are endowed with energy conservation properties (Zou & Lerman
"This work was mainly done while V. N. Ioanndis was working Mitsuhishi Electric Research Laboratories.

---

Published as a conference paper at ICLR 2020
(a) Academic collaboration
(b) Protein Protein-protein network
(c) 3D point cloud
Figure I: Illustration of the same PGST applied to different graph datasets. Notice that for the social network (a) most of GST branches are pruned, suggesting that most information is captured by local interactions.
2019), as well as stability meaning robustness graph topology deformations (Gama al. 2019a). However, GSTs are associated with exponential complexity in space and time that increases with the number of layers. This discourages deployment of GST's when deep architecture is needed. Furthermore, stability should not come at odds with sensitivity. A filter's output should he sensitive to and "detect" perturbations of large magnitude. Lastly, graph data in different domains (social networks, 3D point clouds) have distinct properties, which encourages GSTs with domain-adaptive architectures.
The present paper develops a data-adaptive pruning framework for the GST to systematically retain important features. Specifically, the contribution of this work is threefold.
C1.
We put forth pruning approach to select informative GST features that we naturally term pruned graph scattering transform (pGST). The pruning decisions are guided by criterion promoting alignment (matching) of the input graph spectrum with that of the graph filters. The optimal pruning decisions are provided on-the-fly, and alleviate the exponential complexity of GSTs.
C2. We prove that the PGST is stable perturbations of the input graph signals. Under certain conditions on the energy of the perturbations, the resulting pruning patterns before and after the perturbations are identical and the overall PGST stable.
C3. We showcase with extensive experiments that: the proposed PGST's perform similarly and in certain cases better than the bascline GSTs that use all scattering features, while achieving significant computational savings; ii) The extracted features from PGSTs can be utilized towards graph classification and 3D point cloud recognition. Even without any training on the feature extraction step, the performance comparable to state-of-the aatt-----t---ttte-eeeee--- deep supervised learning approaches, particularly when training data are scarce; and iii) By analyzing the pruning patterns of the PGST, we deduce that graph signals different domains call for different network architectures; see Fig. T
RELATED WORK
GCNs rely on layered processing architecture comprising trainable graph convolution operations to linearly combine features per graph neighborhood. followed by pointwise nonlinear functions applied the linearly transformed features (Bronstein et al., (017). Complex GCNs and their variants have shown remarkable success in graph semi- supi-supe learning (Kipf & Welling, 2017 Veličković et al.) 2018) and graph classification (Ying et al. 2018). To simplify GCNs, (Wu al. 2019) has shown that by employing single-layer lincar GCN the performance in certain social network learning tasks degrades only slightly. On the other hand, (Li et al. 2019) has developed a 56-layer GCN that achieves ofate-of-the-att art performance in 3D point cloud segmentation. Hence, designing GCN architectures guided by properties of the graph data a highly motivated research question.
Towards theoretically explaining the success of GCNs, recent works study the stability properties of GSTs with respect to metric deformations of the domain (Gama et al. 2019b at Zou & Lerman
2019). GST's generalize scattering transforms (Bruna & Mallat 2013 Mallat la 2012 to non-Fuclidean
2

---

Published as a conference paper at ICLR 2020
domains. GSTs are cascade of graph filter banks and nonlinear operations that is organized in tree-structured architecture. The number of extracted scattering features a GST grows exponentially with the number of layers. Theoretical guarantees for GSTs are obtained after fixing the graph filter banks to implement set of graph wavelets. The work in (Zou & Lerman (019) establishes energy conservation properties for GSTss given that certain energy- peergy-preseviing graph wavelets are employed, and also prove that GSTs are stable to graph structure perturbations; see also (Gama et al.] 2019b) that focuses on diffusion wavelets. On the other hand, (Gama et al. (0099) proves stability to relative metric deformations for wide class of graph wavelet families. These contemporary works shed light into the stability and generalization capabilities of GCNs. However, stable transforms are not necessarily informative, and albeit highly desirable, principled approach to selecting informative GST features remains still an uncharted venue.
BACKGROUND
Consider a graph 9 := EV with node set V == {u and edge set E := {ei) Its connectivity is described by the graph shift matrix S E RxN, whose (n, n n')tt entry Sun' is nonzero if (n, n') E 3 or if n = n'. A typical choice for S is the adjacency or the Laplacian matrix. Further, each node can be also associated with few attributes. Collect attributes across all nodes in the matrix [x,,,.,,pp] E xxF, where each column X, E RN is 'graph signal.'
X ==
Graph Fourier transform. A Fourier transform corresponds the expansion of a signal over bases that are invariant to filtering, here, this graph frequeney basis is the eigenbasis of the graph shift matrix S. Henceforth, S assumed normal with S VAV where V E RNNN forms the graph Fourier basis, and A E R is the diagonal matrix of corresponding eigenvalues An ..., AN-1- These eigenvalues represent graph frequencies. The graph Fourier transform (GFT) of x E IR is x V x E R.N, while the inverse transform is x VX. The vector X represents the signal's expansion in the eigenvector basis and describes the graph spectrum of x. The inverse GFT reconstructs the graph signal from its graph spectrum by combining graph frequency components weighted by the coefficients of the signal's graph Fourier transform. GFT is a tool that has been popular for analyzing graph signals in the graph spectral domain.
Graph convolution neural networks. GCNs permeate the benefits of CNNs from processing Euclidean data to modeling graph structured data. GCNs model graph data through succession of layers, each of which consists of a graph convolution operation (graph filter), a pointwise nonlinear function (-), and oftentimes also a pooling operation. Given a graph signal x E RV, the graph convolution operation diffuses each node's ' information to its neighbors according to the graph shift matrix S, as Sx. The with entry [Sx]n En'En, S is weighted average of the one-hop neighboring features. Successive application of S will increase the reception field, spreading the information across the network. Hence, a Kth order graph convolution operation (graph filtering) is
h(S)x Σ S vh(A)*
where the graph filter h(-) is parameterized by the learnable weights {wx )K Ik=o= and the graph filter in the graph spectral domain is ((A)= = Σ A k In the graph vertex domain, the learnable weights reflect the influences from various orders of neighbors; and in the graph spectral domain, those weights adaptively adjust the focus and emphasize certain graph frequency bands. GCNs employ various graph filter banks per layer, and learn the parameters that minimize predefined learning objective, such as classification, or regression.
Graph scattering transforms. GSTs are the nontrainable counterparts of GCNs, where the parame- ters of the graph convolutions are selected based on mathematical designs. GSTs process the input at each layer by sequential application of graph filter banks [h)(
elementwise nonlinear function (-),, and a pooling operator U. At the first layer, the input graph signal x E RRN constitutes the first scattering feature vector (())
Next, Z(o) is processed by the graph filter banks and (-)) to generate { with ž(z) := ( (S)z ). At the second layer, the same operation is repeated per 1. The resulting computation structure is a tree with J branches at each non-leaf node; see also Fig. The éth layer of the tree includes J nodes. Each tree node at layer é in the scattering
transform is indexed by the path (! of the sequence of graph convolutions applied the input
3

---

Published as a conference paper at ICLR 2020
Mo0 X
(S)
fs (9)
hy(3)
h2(S)
(g(
hi1S)
2(2.3)
X(5.2)
Figure 2: Scattering pattern associated with a PGST with and = 3. The dashed lines represent the pruned branches. The example of graph signal and the GFT's of x and the filter banks are included as well. Note that the third filter j = 3 at generates no output, i.c. 2(3) = 0, and hence is pruned.
graph signal x, i.e. pl() (f(), ................................ ((() indexed by (p(o, at layer l + 1 is
The scattering feature vector at the tree node
(p(00. =0 (h,
where the variable p( holds the list of indices of the parent nodes ordered by ancestry, and all path p(9) in the tree with length l are included the path set p(() with |p()]] = 2 The nonlinear transformation function (-) disperses the graph frequency representation through the spectrum, and endows the GST with increased discriminating power (Gama et al. 2019a). By exploiting the sparsity of the graph, the computational complexity of 2 is O)KE), where in g Each scattering feature vector (g)()) is summarized by an aggregation operator U-) to obtain scalar scattering coefficient as (()))) := (z(()))) where U-) is typically an average or sum operator that effects dimensionality reduction of the extracted features. The scattering coefficient at each tree node reflects the activation level at a certain graph frequency band.
[ the number of edges
These scattering coefficients are collected across all tree nodes to form a scattering feature map
T (x) = { ( ( epeo 1é=0
where [x(x) Et J The GST operation resembles a forward pass of a trained GCN. This is why several works study GST stability under perturbations of S in order to understand the working
mechanism of GCNs (Zou & Lerman 2019 Gama et al.) 2019a b).
4 PRUNED GRAPH SCATTERING TRANSFORMS
While the representation power of GST increases with the number of layers, the computational and space complexity of the transform also increase exponentially with the number of layers due to its scattering nature. Hence, even if informative features associated exponential complexity of extracting such features is prohibitive with the existing GST architectures. On the other hand, various input data (social networks, 3D point clouds) may have distinet properties, leading to different GST feature maps. In some cases, only a few tree nodes in deep layers are informative; and in other cases, tree nodes in shallow layers carry significant information; see Fig. I This requires a customized GST to adaptively choose significant tree nodes.
available at deeper GST layers, the
Alleviating GST limitations, we introduce a pruned graph scattering transform (pGST) system- atically retain informative tree nodes without additional complexity. Our novel PGST alleviates the exponential complexity and adapts GST different input data. Furthermore, PGST offer practical mechanism to understand the architecture of GCNs. Based on the pruning patterns, the proposed PGST suggests when deeper GCN is desirable, and when shallow one will suffice. Pruning the wavelet packets has been traditionally employed for compression in image processing
AA tree node is fully specified by its corresponding path.
Any analytical function h(S) can be written as polynomial of S with maximum degree N Horn &
Johnson 2012.
4

---

Published as a conference paper at ICLR 2020
applications (Xiong al. 2002). where the pruning is guided by a rute-distortion optimallity criterion. In this work, we consider a graph spectrum inspired criterion. Intuitively, each tree node the GSTs reflects unique subband in the graph spectrum. When the subband of a tree node does not have sufficient overlap with the the graph spectrum of a graph signal, this tree node cannot capture the property of this graph signal, and should be pruned.
For example, consider a smooth graph signal x, where connected nodes have similar signal values, that has a sparse (low-rank) representation in the graph spectral domain that is, & == V R and [ = for n 2 b. The graph spectrum of the jth graph filtered output is then
hy (S) diag (A)( (15(A1) hy (A2) "h,))) Ng(AN))N)
where An is the with eigenvalue of S and each frequency T, is weighted by the corresponding transformed eigenvalue h (A,).. Hence, if the support of the graph spectrum (h,(A,)), is not included the support of x),, then the jth graph filter output will not capture any information; that is, hy (S)x Ow: see Fig. 2 Thus, identifying such graph filters and pruning the corresponding tree nodes will result to parsimonius and thus computationally efficient GST.
Pruning criterion. Motivated by the aforementioned observation, introduce pruning criterion select the scattering branches per tree node by maximizing the alignment between the graph spectrum of the graph filters and the scattering feature. At the tree node p. the optimization problem
max Uiaa)dj-1
Σ
Σ (h)(An)²-)) |0 fiP.))
(4)
t. f(.) E (0,1), j=1....,!
where (p)) := Vz(p) is the graph spectrum of the scattering feature vector (pp) T is user-specific
threshold; and, f(p.j) stands for the pruning assignment variable indicating whether node (p.j) is active (f(p)) = 1) or it should be pruned (f(p.)) = O). The objective in (4) promotes retaining tree nodes that maximize the alignment of the graph spectrum of (p))) with that of h (A). The threshold
introduces minimum spectral value to locate those tree nodes whose corresponding graph spectral
response is small, i.c. (A,,)) < Note that criterion is evaluated per tree node p, thus allowing for a flexible and scalable design.
The optimization problem in 4 is nonconvex since finJ) is discrete variable. Furthermore, recovering (1)) requires eigendecomposition of the Laplacian matrix that incurs O(N*) complexity. Nevertheless, by exploiting the structure in (4, we develop an efficient pruning algorithm that achieves the maximum of (4) as summarized in the following theorem.
Theorem 1. The optimal pruning assignment variables
{Kinn), of is given as follows
Bip.)) > T, if
fip
. L;=1,...
Binus [| ||
The optimal variables fip.)) are given by comparing the energy of the input ((p) to that the output Z(p.) per graph filter that can be evaluated at low complexity of O(N). Our pruning criterion leads to principled and scalable algorithm to selecting the GST tree nodes to be pruned. The pruning objective is evaluated at each tree node p, and pruning decisions are made on-the-fly. Hence, when fip) = 1, tree node p is active and the graph filter bank will be applied to (p)) expanding the tree to the next layer; otherwise, the GST will not be expanded further at tree node p. which can result to exponential savings in computations. An example of such pruned tree depicted in Fig. 2 Evidently, the hyperparameter 7 controls the input-to-output energy ratio. A large corresponds to an aggressively pruned scattering tree, while small 7 amounts minimally pruned scattering tree. The PGST is then defined as
(x) = (1(p) PET
where T is the set of active nodes T {p E PI lin) =1}.
5

---

Published as a conference paper at ICLR 2020
Our pruning approach provides concise version of GSTs and effects savings in computations well as memory. Although the worst-case complexity of pGST is still exponential, a desirable complexity can be effected by properly selecting As byproduct, the scattering patterns of pGSTs reveal the appropriate depths and widths of the GSTs for different input data; see also Fig. | The pruning approach far is unsupervised one, since no input data labels are assumed available.
STABILITY AND SENSITIVITY OF PGST
In this section, we prove the stability of PGST to perturbations of the input graph signal. To establish the ensuing results, we consider graph wavelets that form frame with frame bounds A and B (Hammond al. 2011). Specifically, for any graph signal x E INN, holds that, A || S Ei= [1)x(()) I 1²||x||? In the graph vertex domain, the scalar frame bounds A and B characterize the numerical stability of recovering a graph signal x from { (S)x); In the graph spectral domain, they reflect the ability of the graph filter bank to amplify x along each graph frequency. Tight frame bounds, satisfying A B², are of particular interest because such wavelets lead to enhanced numerical stability and faster computations (Shuman et al. (0015). The frame property of the graph wavelet plays an instrumental role in proving GST stability to perturbations of the underlying graph structure (Gama et al. 2019a Zou & Lerman 2019).
Consider perturbed graph signal x given by
X =
where 5 TR:N is the perturbation vector. Such an additive model 6 may represent noise in the observed feature adversarial perturbations. We are interested in studying how and under which conditions our PGST is affected by such perturbations. A stable transformation should have a similar output under small input perturbations.
Before establishing that our PGST is stable, we first show that GST stable to small perturbations of the input graph signal?
Lemma 1. Consider the GST (b)) with L layers and J graph filters; and suppose that the graph filter bank forms a frame with bound B, while x and & are related via (6). then holds that
(x) [x)]
((x)112
(B
181l..
Σl J
The squared difference of the GSTs is normalized by the number of scattering features in ++-), that is [x() Ei J The bound in ( relates to the frame bound of the wavelet filter bank. Notice that for tight frames with B 1, then the normalized stability bound is tight. Let T be the structure of the pruned tree for & (X). The following lemma asserts that the PGST offers the same pruned tree for the original and the perturbed inputs.
Lemma 2. Let 7n denote the perturbed scattering feature at the tree node p and 6p == 7pp 3p. If for all p E P and j = I,.... J, it holds that
|1hh
7 || 11 [S,(6)), + +
11
(8)
Then, we obtain
1. The pruming transform will output the same tree treefor T (x) and T (x); With g(x) := [1,,(S)x -
that is, T T= T. and,
[| a necessary condition for is
19(2,)) ) > g(6p)
According to (). Lemma can be interpreted as signal-to-noiss ratio (SNR) condition because under g(5,) > 0. it is possible to write (9) as (g(z))//((8) > 1. Lemma provides a per-layer and
branch condition for PGST to output the same scattering tree for the original the perturbed signal. By combining Lemmas and [
we arrive at the following stability result for the PGST network.
Prior art deals with GST stability to structure perturbations Gama
2019a b Zou & Lerman 2019

---

Published as a conference paper at ICLR 2020
+
THS egw
+ge
FMCS -
PTHS
Clasklicatinn Buliinalnnnn accuracy
0.5
3003
Clociftaiinn
Scanno
0.70
0.4
Austorabap
Pacebock
Authocat.p
Facebook
1.000
1,400
30
60
100
Number of samples
SNB
Authorship
(b) Facebook
Runtime
(d) Feature overlap
Figure 3: Classification accuracy against number of samples in the authorship attribution (a) and SNR in dB for source localization (b). Runtime comparison seconds of the scattering transforms (c).
Theorem 2. Consider the PGST transform (.) with L layers and J graph filters; and suppose that the filter bank forms frame with bound B, while x and & are related via (6). The PGST is stable to bounded perturbations 8, in the sense that
filter
L (x)
(x)122
E FBB2i
|
L (x)
Σl Fe
where Fg : (p(0 UT| is the number of active scattering features at layer l, and [x)] Ei- Fe the number of retained scattering features.
EXPERIMENTS
This section evaluates the performance of our PGST in various graph classification tasks. Graph classification amounts to predicting label yi given x; and S; for the ith graph. Our PGST extracts (x,). which is utilized as a feature vector for predicting yi- During training, the structure of the PGST T is determined, which is kept fixed during validation and testing. The parameter is selected via cross-validation. Our goal is to provide tangible answers to the following research questions.
RQ1 How does the proposed PGST compare to GST?
RQ2 How does PGST compare to state-of-the-an GCN approaches for graph classification?
RQ3 What are the appropriate scattering patterns for various graph data?
Appendix includes additional experiments on ablation studies over the effect of the parameters J, T,
PGST vs. GST. To address RQI, we reproduce the experiments of two tasks in (Gama al. 2019a) authorship attribution and source localization. For the scattering transforms, we consider three implementations of graph filter banks: the diffusion wavelets (DS) in (Gama et al. (201b), the monic cubic wavelets (MCS) in (Hammond et al.) 2011) and the tight Hann wavelets (THS) in (Shuman et al. 2015 The scattering transforms use 5 filters, = layers, and T = 0.01. The extracted features from GSTs subsequently utilized by linear support vector machine (SVM) classifier.
Authorship attribution amounts to determining if a certain text was written by a specific author. Each text is represented by graph with N 244, where words (nodes) connected based their relative positions in the text, and x is a bag-of-words representation the text; see also (Gama et al. 2019b). Fig. (a) reports the classification accuracy for the authorship attribution task as the number of training samples (texts) increases. GSTs utilize Σ 5' 781 scattering coefficients, while PGSTss rely only on IT| = 61 for PDS, |T] 30 for PMCS, and |T| 80 for FTHHS. Evidently, the proposed PGST achieves comparable performance as the bascline GST, whereas PGST uses only subset of features (12.8%, 3.8% and 10.2% respectively). The SVM classifier provides coefficient that weighs each scattering scalar. The magnitude of each coefficient shows the importance of the corresponding scattering feature in the classification. Fig. (d) depicts the percentage of features
*pDS, PMCS, PTHS denote the pruned versions of these transforms.

---

Published as a conference paper at ICLR 2020
Data Set
Method
ENZYMES
COLLAB
... MCS PMCS POINTNET POINTNET++ 3DSHAPENETS VoXNET
Komel
SHORTEST-PATH
42.32
78.86
59.10
76.43
6-36
WL-DA
60.15
79.04
80.74
75.26
PAYCHYNAN
76.27
72.60
75,00
GRAPHSAGE
54.25
75.42
68.
70.48
ECC
53.50
74.10
67.79
72.65
GNNS
SET2SET
78.12
71.75
SORTPOOL
57.12
79.37
73.76
75.54
0.40
DIFFPOOL- DET
58.35
75.47
82.13
75.62
DIYPPOO--NoL
62.67
79.98
75.63
77.42
DIFFPOOL
64.23
81.15
75.50
78.10
Scatering
GSC
53.88
76.57
76.88
74.03
Noworcdpp dpph
Newwet depp
GST
59.84
(a) Tr/ttst: 9843/2468
(b) Tr//tstt 615/11703
PGST (Ours)
60.25
81.27
78:40
78.57
Figure 4: 3D point cloud classification.
Table I: Graph classification accuracy.
after prunning retained in the t most important GST features given by the SVM classifier. observed, that although PGST does take into account the labels, the retained features are indeed informative for classification.
Source localization amounts recovering the source of rumor given diffused signal over Facebook subnetwork with N = 234; see the detailed settings in (Gama et al. 2019b). Fig. (b) shows the classification accuracy of the scattering transforms for increasing SNR dB. In accordance to Lemma 1 and Theorem 2, both pGST and GST are stable for a wide range of SNR. Furthermore, the performance of PGST matches the corresponding GST, while the PGST uses only a subset of
features. Fig. (c) depicts the runtime of the different scattering approaches, where the computational advantage of the pruned methods is evident.
Graph classification. Towards answering RQ2, the proposed pGST is compared with the following sfate-of-the-art approaches The kernel methods shortest-path Weisfeiler-Lehman optimal assignment (WL-OA) (Kriege et al. 2016); the deep learning approaches PatchySan (Niepert et al. (2016), GraphSage (Hamilton et al. 20.1 7). edge-condiiioned filters in CCNs (ECC) (Simonovsky & Komodakis 2017). Set2Set (Vinyals et al. 2015), SortPool (Zhang al. 2018 and DoffPool (Ying et 20.]((01)))) and the geometric scattering classifier (GSC) (Gao et al.
a (Borgwardt & Kriegel 2005). and
2019 Results are presented with protein data sets D&D, Enzymes and Proteins, and the scientific collaboration data set Collab. Detailed description of the datasets is included in the Appendix. We perform 10-fold cross validation and report the classification accuracy averaged over the 10 folds. The gradient boosting classifier is employed for PGST and GST with parameters chosen based on the performance on the validation set. The graph scattering transforms use the MC wavelet with L= 5, J = 5 and r = 0.01. Table [ lists the classification accuracy of the proposed and competing approaches. Even without any training on the feature extraction step, the performance of PGST is comparable to the ofth-offtheeart deep supervised learning approaches across all datasets. GST and PGST outperform also GSC, since the latter uses a linear SVM to classify the scattering features.
Point cloud classification. We further test PGST in classifying 3D point clouds. Given a point cloud, a graph can be created by connecting points (nodes) to their nearest neighbors based on their Euclidian distance. Each node is also associated with 6 scalars denoting its x-y-z coordinates and RGB colors. For this experiment, GSTss are compared against PointNet++ (Qi et al. 2017a| b). 3dShapeNets (Wu et al. 2015) and VoxNet (Maturana & Scherer] 2015). that are state- the deep learning approaches. Fig. F reports the classification accuracy for the ModelNet40 dataset (Wu et al.. 2015) for increasing L. In Fig. 4 (a) 9,843 clouds are used for training and 2,468 for testing using the gradient boosting classifier; whereas, in Fig. 4 (b) only 615 clouds are used for training and the rest for testing using a fully connected neural network classifier with layers. The scattering transforms use an MC wavelet with J = 5 for Fig. (a) and J = 9 for Fig. 4 (b). Fig. Ishowcases that scattering transforms are competitive to -tate-of-the-arr approaches, while PGST outperforms GST. This may be attributed to overfitting effects, since large number of GST features is not informative. Furthermore, the exponential complexity associated with GSTs prevents their application for L = 6. Fig 4 (b) shows that when the training data are scarce, GST and PGST outperform the PointNet++, which requires a large number of training data to optimize over the network parameters.
Forr the competing approaches report the 10-fold cross-validation numbers reported by the original authors; see also (Yigg al. 2018).
8

---

Published as a conference paper at ICLR 2020
Scattering patterns. Towards answering RQ3, depict the scattering structures of pGSTs, with MC wavelet, J and L 5, for the Collab, Proteins, and ModelNet40 datasets in Fig. Evidently, graph data from various domains require adaptive scattering architecture. Specifically, most tree nodes for the academic collaboration dataset are pruned, and hence most informative features are in the shallow layers. This is consistent with the study in (Wu et al.! 2019), which experimentally shows that deeper GCNs do not contribute as much for social network data. These findings are further supported by the small-world phenomenon in social networks, which suggests the diameter of social networks is small (Watts & Strogatz, 1998). On the other hand, the tree nodes for 3D point cloud are minimally pruned, which is in line with the work in (Li al.) (2019) that showcases the advantage of deep GCNs in 3D point clouds classification. For the protein datasets, additional experiments are performed in Appendix A.4 that corroborate the PGST insights regarding the required number of GCN layers.
7 CONCLUSIONS
This paper developed novel approach to pruning the graph scattering transform. The proposed PGST relies on graph-spectruu--asse data-adaptive criterion to prune non-informative features on-the-fly, and effectively reduce the computational complexity of GSTs. Furthermore, when the input signal is perturbed, the stability of PGST is established. Experiments demonstrate that i) the performance gains of PGST's relative GSTs; ii) PGST is competitive in variety of graph classification tasks; and (iii) graph data from different domains exhibit unique pruned scattering patterns, which calls for adaptive network architectures.
Acknowlegdments. This work was supported by Mitsubishi Electric Research Laboratories, the Doctoral Dissertation Fellowship of the University of Minnesota, and the NSF grants 171 141, and 1500713.
REFERENCES
Karsten M Borgwardt and Hans-Peter Kriegel. shortest-path kernels on graphs. In IEEE Insl. Conf. on Data Mining (ICDM), 2005.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Sig. Process. Mag., 34(44:18844) 2017.
Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE Trans. Pattern Anal. Mach. Intel. (888))8881188888888888 2013.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability of graph scattering transforms. In Proc. Advances Neural Inf. Process. Syst. (NeurIPS). 2019a.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms on graphs. In Proc. Intl. Conf. on Learn. Representations (ICLR), 2019b.
Feng Gao, Guy Wolf, and Matthew Hirn. Geometric scattering for graph data analysis. In Proc. Intl. Conf. Mach. Learn. (ICML), pp. 2122-2131, 2019.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): 2011.
Roger A Horn and Charles R Johnson. Matrix Analysis. Cambridge university press, 2012.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
In Proc. Intl. Conf. on Learn. Representations (ICLR), Toulon, France, Apr. 2017.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. In Proc. Advances Neural Inf. Process. Syst. (NeurIPS), 2016.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Can gens go as deep as cnns? In Proc. Int. Conf. Comput. Vis, 2019.

---

Published as a conference paper at ICLR 2020
Stéphane Mallat. Group invariant scattering. Communications Pure and Applied Mathematics, 65 (10):1331-1398, 2012.
Daniel Maturana and Sebastian Scherer. Voxnet: A 3d convolutional neural network for real-time object recognition. In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2015.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In Proc. Intl. Conf. Mach. Learn. (ICML), 2016.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In IEEE Conf. on Comp. Vis. and Pat. Rec., 201 7a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in metric space. In Proc. Advances Neural Inf. Process. Syst. (NeurIPS), 2017b.
David Shuman, Christoph Wiesmeyr, Nicki Holighaus, and Pierre Vandergheynst. Spectrum-adapted tight graph wavelet and vertex-frequency frames. IEEE Trans. Sig. Process., 63(16))4223-4235 2015.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters convolutional neural networks graphs. In IEEE Conf. Comp. Vis. and Pat. Rec., 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proc. Intl. Conf. on Learn. Representations (ICLR), 2018.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. Proc. Intl. Conf. on Learn. Representations (ICLR), 2015.
Duncan Watts and Steven H Strogatz. Collective dynamics 'small-workl networks. Nature, 393 (6684):440, 1998.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In Proc. Intl. Conf. Mach. Learn. (ICML), 2019.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In IEEE Conf. on Comp. Vis. and Put. Rec., 2015.
Zixiang Xiong, Kannan Ramchandran, and Michael T Orchard. wavelet image coding. 2002.
quantization for
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling, In Proc. Advances Neural Inf. Process. Syst. (NeurIPS), 2018
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference Artificial Intelligence, 2018.
Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 2019.
10

---

Published as a conference paper at ICLR 2020
Dataset
Graphs
Features F
Max number of nodes per graph
Collab
5000
492
D&D
1178
89
5748
Enzymes
600
126
Proteins
1113
3
620
Table 2: Dataset characteristics
Chasifiction accuEac)
10a
10"
10
10
10
10
10
100
10
10
10
10
10
(a) Classification accuracy
(b) Number of active features TT]
10-3
10
10
10
10
10
100
(c) Runtime in seconds
Figure Performance of PGSTs for varying 7.
A ADDITIONAL EXPERIMENTS
Dataset characteristics. The characteristics of the Datasets used in Table [ are shown in Table 2 Notice that the nodes in the Collab dataset did not have any features, and hence x was selected as the vector that holds the node degrees.
PTHS
Clasilicaton Lecuney
Classtication soaurayy
0.9
0.8
0.7
0.6
0.6
6
10
Figure 6: Classification accuracy different parameters.
11

---

Published as a conference paper at ICLR 2020
A.1 ABLATION STUDY
Fig. S reports how the PGST is affected by varying the threshold T in the task of source localization, with 6 and 5. Fig. (a) shows the classification accuracy that generally decreases increases since the number of active features [7] decreases; cf. Fig. (b). (b). Fig. (c) reports the rumtime seconds of the approaches. Fig. showcases the classification performance of the pGST with r = 0.01 for varying L with = 3 on the left and for varying J with L = 3 on the right. It is observed, that the classification performance generally increases with L. and
B PROOF OF THEOREM
First, the objective in is rewritten
5 (2,()n)² -) (m)) fj Σ 20) (diag (A)( - -r1) Zin)
(10)
that follows by definition. By introducing the scalars aj == (di(ag (A)) =1) for j 1. ,....,.... can be rewritten as
max f3
Σash
(11)
j=1
S.
(0,1) j j= i
The optimization problem in [II is nonconvex since fj a discrete variable. However, maximizing the sum in (11) amounts to setting ʃj for the positive aj over Such approach leads to the optimal pruning assignment variables as follows
[1 af 0, 0
fj
- I
(12)
af < O.
The rest of the proof focuses rewriting aj as follows
aj -Ztp) (diag (2)) -I)
(13)
=||diag (hy (A) (A)) 112 -1((( 11?
(14)
Furthermore, since V orthogonal matrix holds that follows
|| and
|diag (A,())) 12 -1h,
(15)
=1))(h,(S))z))))
=1|z(,,)11=
(16)
where the second line follows since a--) is applied elementwise and does change the norm.
C PROOF LEMMA
By definition 3 it holds
[ 22
(di (
(17)
p() (P())
Hence, it is well motivated to bound each term of the sum in 17 as follows
(θ(p)))
T (10(Z()))))
U (2
(18)
1 (p(c))
(p(o)) |I
(19)
12

---

Published as a conference paper at ICLR 2020
where 19 follows since the norm is sub- multipliccaiiie operator. Next will show the following recursive bound
12(0000 (pre)
|| (oooo 1:) a(h3ce) (pte bY)l
(20)
s 100llll (S) 11) - h100) (S) (n)z myll
(21)
< 111yc0s (S) - 11(0)) (p(-)))
(22)
51 (S) (pte- - (pte-1)) 1;y1
(23)
where (1 (3 follow since the norm a sub-multiplicative operator and (22 follows since
nonlinearity nonexpansive, i.e. ||((|| < 1. Hence, by applying (23) times the following condition holds
(ip(t)
(p(0)) ll S |1 (S) ( (S)] ... 11ya (S) x|]
(24)
and by further applying the frame bound and (6) follows that
(g(0)) (p(t)) - B" |||
(25)
Combining
25) and the average operator property || = holds that (0())))
(26)
By applying the bound (6) for all entries in the right hand side of (17 it follows that
[x(()) (x))
B 181
(27)
t=0 g
By factoring out ||o]| and observing that the sum in the right side of 27 does not depend on the path index p follows that
L
(x) 2xx)|1 <
Σ
|p(t)
1200)122 1822
11812
(28)
F=
Finally, since the cardinality of the paths at & is |l(od| = Je and (Bo ((B²))4) (BRJ 1) it holds
(B2J)L
[ - +(x)
V
B - ||
(29)
D PROOF OF LEMMA 2
will prove the case for = 0, where 2pr0) = x, since the same proof holds for any First, we adapt & to the following
|1 (S)x| |||x|| |1,(())) +
||
(30)
The proof will examine two cases and will follow by contradiction. For the first case, consider that branch j is pruned in (x) and not pruned in (5)),, i.e. ( E T and (j) & ग. By applying (5) for Z(g) (S)xx)) there exists C 2 such that
(S)
-
(31)
X 2
(S)x <T||x||2
C||x||
(32)
Furthermore, from 5 holds for ž0) = (S)( that
(S)x 1
(33)
13

---

Published as a conference paper at ICLR 2020
By applying (6) to (33) and using the triangular inequality it follows that
[|, 2 +
[1, 2 +|
(34)
Next, by applying 32 holds that
- +|x|2 C||x ||, || |
(35)
7 [[|x||² ||x + | (S)8 -0
(36)
Next, by utilizing (30) and the absolute value property |a| 2 a to upper-bound bound the left side of 36
follows that
[S)x|] - -||x|| >
(37)
Finally, by applying 32 the following is obtained
0 |0|
(38)
which implies that C < O. However, this contradicts since C 2 0. Following symmetric argument we can complete the proof for the other case.
14


Reviews:
[{"review_id": "rJlnxSdzoH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nIt 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.\n\nSome 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklFB48pFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nFirst, 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.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJluIJRpYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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)\n\nPros :\n- Good performances with a simple method. This is a positive aspect of the paper.\n- This is an attempt to scale spectral methods on large graphs.\n- A stability study of the practical impact of this threshold is done.\n\nCons:\n- 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:\n$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$\n- 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?\n- 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. \n- \". 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.\n\n\nminor: \n- \"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\")\n- The notation p^{(l)}\\cup j can be a bit confusing, couldn't this author write (p^{(l)},j) or anything similar?\n- 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.\n- \"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?\"\n- Figures and Tables are too small...\n\npost rebuttal:\nI found the arguments of the authors convincing, they addressed my concern and revised the paper accordingly.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)