Graph Scattering beyond Wavelet Shackles
Authors: Christian Koke
Gitta Kutyniok
Venue: NeurIPS 2022 Accept (2022)
Keywords: Geometric Deep Learning
Graph Convolutional Networks
Scattering
Wavelets
Stability Guarantees
Rigorous Proofs
Quantum Chemistry

Abstract: This work develops a flexible and mathematically sound framework for the design and analysis of graph scattering networks with variable branching ratios and generic functional calculus filters.	Spectrally-agnostic stability guarantees for node- and graph-level perturbations are derived; the vertex-set non-preserving case is treated by utilizing recently developed mathematical-physics based tools. Energy propagation through the network layers is investigated and related to truncation stability. New methods of graph-level feature aggregation are introduced and stability of the resulting composite scattering architectures is established. Finally, scattering transforms are extended to edge- and higher order tensorial input. Theoretical results are complemented by numerical investigations: Suitably chosen scattering networks conforming to the developed theory perform better than traditional graph-wavelet based scattering approaches in social network graph classification tasks and	significantly outperform other graph-based learning approaches to regression of quantum-chemical energies on QM$7$.

Graph Scattering beyond Wavelet Shackles
Christian Koke Technical University Munich & Ludwig Maximilian University Munich christian barristan.kkkeetummm. koke@tum.de
Gitta Kutyniok
Ludwig Maximilian University Munich & University of Tromsø
kutyniok@matal lmu.de
Abstract
This work develops flexible and mathematically sound framework for the design and analysis of graph scattering networks with variable branching ratios and generic functional calculus filters. Spectrally-agnostie stability guarantees for node- and graph-level perturbations are derived; the vertex-set non-preserving case is treated by utilizing recently developed mathematical-phhy -hyysics based tools. Energy propaga- tion through the network layers is investigated and related to truncation stability. New methods graph-level feature aggregation are introduced and stability the resulting composite scattering architectures is established. Finally, scattering transforms are extended to edge- and higher order tensorial input. Theoretical results are complemented by numerical investigations: Suitably chosen scattering networks conforming to the developed theory perform better than traditional graph- wavelet based scattering approaches in social network graph classification tasks and significantly outperform other graph-based learning approaches to regression of quantun-chemical energies QM7.
Introduction
Euclidean wavelet scattering networks [22 4 are deep convolutional architectures where output- features generated in each layer. Employed filters designed rather than learned and derive from a fixed (tight) wavelet frame, resulting in a tree structured network with constant branching ratio. Such networks provide state of the methods in settings with limited data availability and serve as a mathematically tractable model of standard convolutional neural networks (CNNs). Rigorous investigations establishing remarkable invariance- and stability properties of wavelet scattering networks were initially carried out in (22). The extensive mathematical analysis [38] generalized the term 'scattering network include tree structured networks with varying branching rations and frames of convolutional filters, thus significantly narrowing the conceptual gap to general CNNs.
With increasing interest in data graph-structured domains, well performing networks generalizing Euclidean CNNs to this geometric setting emerged [8] 5 If efficiently implemented, such graph convolutional networks (GCNs) replace Fuclidean convolutional filters by functional calculus filters; iee. scalar functions applied to suitably chosen graph-shift-opratoo capturing the geometry of the underlying graph [8 14 9. Almost immediately, proposals aimed extending the success story of
Euclidean scattering networks to the graph convolutional setting began appearing: In (48), the authors utilize dyadic graph wavelets (see e.g. (14) based on the non-normalized graph Laplacian resulting in norm preserving graph wavelet scattering transform. In 10), diffusion wavelets (see e.g. (8) are used construct a graph scattering transform enjoying spectrum-dependent stability guarantees to graph level perturbations. For scattering transforms with N layers and K distinct functional calculus filters, the work [11 derives node-level stability bounds of O N/2) and conducts corresponding numerical experiments choosing diffusion wavelets, monic cubic wavelets (14] and tight Hann wavelets (35) as filters. In [12) the authors, following (8), construct so called geometric wavelets and establish the expressivity of scattering transform based such frame through extensive numerical
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

experiments, A theoretical analysis of this and a closely related wavelet based scattering transform is the main focus of [28]. Additionally, graph-wavelet based scattering transforms have been extended to the spatio-temporal domain 277. utilized to overcome the problem of oversmoothing in GCNs
25 and pruned to deal with their exponential (in network depth) increase needed resources [S]
Common among all these contributions is the focus on graph wavelets, which are generically understood derive a scale-sampling procedure from common wavelet generating kernel function RR - IR satisfying various properties [4]. Established stability or expressivity properties - -especillly to structural perturbations - are then generally linked to the specific choice of the wavelet kernel and utilized graph shift operator [10 28 This severely limits the diversity of available filter banks in the design of scattering networks and draws into question their validity as models for more general GCNs whose filters generically do not derive from wavelet kernel.
A primary foeus of this work is to provide alleviation in this situation: After reviewing the graph signal processing setting in Section we introduce a general framework for the construction of (generalized) graph scattering transforms beyond the wavelet setting Section 3 Section establishes spectrum- agnostic stability guarantees on the node signal level and for the first time also for graph-level perturbations. To handle the vertex-set non-preserving case, new 'distance measure" for operators capturing the geometry of varying graphs is utilized. After providing conditions for energy decay (with the layers) and relating it to truncation stability, we consider graph level feature aggregation and higher order inputs in Sections 5 and respectively. In Section 7 we then provide numerical results indicating that general functional calculus filter based scattering is at least as expressive as standard wavelet based scattering in graph classification tasks and outperforms leading graph neural network approaches to regression of quantum chemical energies on QM7.
2 Graph Signal Processing
Taking signal processing approach, we consider signals on graphs as opposed to graph embeddings:
Node-Signals: Given graph (G, we are primarily interested in node-signals, which are functions from the node-set G to the complex numbers, modelled as elements of ClOI, We equip this space with an inner product according to (f.g) = E TigaP; (with all vertex weights μ4 > 1) and denote the resulting inner product space by (G). We forego considering arbitrary inner products on CIGI solely in the interest of increased readability.
Functional Calculus Filters: Our fundamental objects in investigating node-signals will be func- tional calculus filters based on a normal operator (G) e (G). Prominent examples include the adjacency matrix W, the degree matrix D, normalized (1 D- D or un-normalized (C = D- W) graph Laplacians Writing normalized eigenvalue-eigenneeonn pairs of A as (Ai, $5) the filter obtained from applying g C - C is given by g gA) |Gl (A.)) (dt, D'vev The operator we utilize our numerical investigations of Section is given by L := C/ C/Amax(D) (C). We divide by the largest eigenvalue ensure that the spectrum (L)) is contained in the interval [0, 1]. which aids in the choice of functions from which filters are derived.
Generalized Frames: We are most interested in filters that arise from a collection of functions
adequately covering the spectrum of the operator to which they are applied. To this end we call a collection (9:(-) (-)) ker of functions generalized frame if satisfies the generalized frame condition
A & Eie! (c) 2 < B for any e in for constants A; B O. As proved in Appendix B this condition sufficient guarantee that the associated operators form frame:
Theorem 2.1. Let A
(G)) be normal. If the family (g(()) of bounded functions satisfies A < Eier [2] & B for all e in the spectrum (A)), we have (Vf e (GG))
(G) -
Alfl2a > ElaAA))i & Blff
SEl
Notably, the functions (gifter need not be continuous: In fact, in our numerical implementations, will among other mappings - utilize the function do(-). defined by 6o(0) and dn = 0 for * 0 as well as modified cosine, defined by cos () = O and cos(c) cos(c) for 0.

---

Operator Frames: Beyond these ingredients, the central building block of our scattering architecture is comprised of family of functional calculus filters in each layer. That is, we assume that in each layer, the node signal space (G,) carries a normal operator A, and an associated collection of functions comprised of an output generating function x.(()) as well as a filter bank (.))..))),.,,,, indexed by an index set n.. As the network layer n varies (and in contrast to wavelet-scattering networks) we allow the index set T, as well as the collection The Generalized Graph Scattering Transform
generalized graph scattering transform a non-linear map & based on a tree structured multilayer graph convolutional network with constant branching factor in each layer. For an input signal f (G), outputs are generated in each layer of such a scattering network, and then concatenated to form feature vector in feature space &. The network is built up from three ingredients:
Connecting Operators: To allow intermediate signal representations in the 'hidden' network layers to further processed with functional calculus filters based on varying operators, which might not all be normal for the same choice of node-weights, to live in varying graph signal spaces. In fact, we do not even assume that these signal spaces are based common vertex This is done to allow for modelling of recently proposed networks where input- and pprocessing' graphs are decoupled (see e.g. 1 36)), as well as architectures signal space ( (G,) to each layer n. Connecting operators are then (not necessarily linear) operators Pa (Gn-1) - (G,) connecting the signal spaces of subsequent layers. We assume them be Lipschitz continuous (())()) - P(g)lle & Rt If f 9 (G.))))).) and triviality preserving (P(0) = 0), For our original node-signal space we also write (G) = (Go)
allow these intermediate representations
incorporating graph pooling [20]. Instead, we associate
Non- Lin-aiiees:::es: To each layer, we also associate a (possibly) non-linear function Pr: C C acting poinwise on signals in (G,). Similar to connecting operators, we assume Pn preserves zero and is Lipschitz-contnnee with Lipschitz constant denoted by L This definition allows for the absolute value con-linearity, but also ReI.u or trivially the identity function.
(xx())) Ulg-. (.)),.r,, functions vary. We only demand that in each layer the functions the
filter bank together with the output generating function constitute a generalized frame with frame constants A,, Bn >
We refer to the collection functions Ωy == (pn, sequence and call ØN :- (Pn, A our operator collection. The generalized scattering transform is then constructed iteratively:
as mod-
To our initial signal f e (GG) we first apply the connecting operator Pt, yielding signal rep- resentation (G Subsequently, we apply the pointwise non-linearity P1. Then apply our graph filters (xx(A,)) Ulg (A)))mer to p1 (P(((f)) yielding the output Vi(() as well as the intermedi- ate hidden representations (UIIm](F) obtained in the first
8o (1.)
(4.))
Po(P)())
X:(4,7]
Sea (Ar)
(d,) (P(())
(x(()
9x. (A)))))))))() layer. Here we have introduced the one-step scattering propagator Ua[n]] ((G,-1) (²(G.) mapping ʃ Ir. (A.)).(PP( as well as the output generating operator (²(G.) mapping ʃ to (m. Upon defining the set Xa N IN-1 ... I1 of paths of length (N- - terminating in layer N - (with 1 taken to be the one-element set) and iterating the above procedure, we see that the outputs gener- ated in the / llaer are indexed by paths N terminating in the previous layer.
8. (4,)
x=(
(x((()))
V. (GG,,))
()(A))
PrLFF
x=(As)]
PiGB
((G))
Figure 1: Schematic Scattering Architecture
3

---

Outputs generated in the N layer are thus given by [xye//n-llo...d/n/l1 imam to Jerw-1. Concatenating the features obtained in the various layers of network with depth N, our full feature vectors thus live in the feature space
F - (GGG))
The associated canonical norm is denoted 11.xx. For convenience, brief review of direct sums of spaces, their associated norms and a discussion of corresponding direct sums of maps is provided in Appendix A We denote the hence constructed generalized scattering transform of length N, based on a module sequence f2y and operator collection ØN by &N. In our numerical experiments in Section 7 we consider two particular instantiations of the above general architecture. In both cases the utilized shift-operator is L == L/ E/>xmxx( (f), node weights satisfy H4 1, the branching ratio in each layer chosen as and the depth is set to N 4 as well. The connecting operators are set to the identity and non-linearities are set to the modulus (|-1). The two archi- tectures differ in the utilized filters, which are repeated in each layer and depicted in Fig. 2 Postponing a discussion of other parameter- choices, note here that the filters {sin( (T/ (sin( cos( x/2-)] provide a high and a low pass filter on the spectrum o (L)) = [o, 1]. while (sin( COs(TT)) provides spectral refinement of the former two filters. The inner two elements of the filter bank in Architecture thus separate input signal into high- and low-lying spectral components. The outer two act similarly at higher spectral scale. Additionally Architecture utilizing cos and óg as introduced Section prevents the lowest lying spectral information from propagating. Instead it extracted via ( in each layer. Note that Id arises from applying the constant-1 function to L. Normalizations are chosen to generate frames with upper bounds B $ 1.
costa
S 3 329
Cost $22
sini
sin1 ))
Miir. y
V2 2o
Id Architecture II
Architecture I
Figure 2: Filters of tested Ar- chitectures
4 Stability Guarantees
In order to produce meaningful signal representations, a small change in input signal should produce a small change in the output of our generalized scattering transforms. This property is captured in the result below, which is proved in Appendix C
Theorem 4.1. With the notation of Section we have for all f, e (G):
1/2
N
(f) 1 (h)lll &
1+
max
11. R 11,0)
B₁
If- -lbba
In the case where upper frame bounds B, and Lipschitz constants I and R are all smaller than or equal one, this statement reduces to the much nicer inequality:
o (f) 4 &n < lf -hllee
Below, we always assume R L & as this easily achievable through rescaling. We will keep B,, variable to demonstrate how filter size influences stability results. As for our experimentally tested architectures (cf. Fig. 2). we note for Architecture that B, = 1/2 for all n, so that (2) applies. For Architecture II we have Bn = 3, which yields a stability constant of v + 2- 3 + 2 3 + 2- 33 = 9. Similar to other constants derived in this section, this bound is however not necessarily tight.
Operators capturing graph geometries might only be known approximately in real world tasks; e.g. edge weights are only known to a certain level of precision. Hence it is important that our scattering representation be insensitive to small perturbations in the underlying normal operators in each layer, which is captured by our next result, proved in Appendix D Smallness here is measured in Frobenius norm || F. which for convenience is briefly reviewed Appendix
Theorem 4.2. Let nN and &N be two scattering transforms based on the same module sequence ON and operator sequences NN, EN with the same connecting operators (P,, P.)) in each layer. Assume Rt Lt < 1 and Bn & B for some B and n & N. Assume that the respective normal operators satisfy ||An Ânl[F F & 6 for some 8 > 0. Further assume that the functions

---

(9r En and in each layer are Lipschitz continuous with associated Lipschitz constants satisfying Xm +
Eymeh Zneer 19m & D2 for all n & N and some D > 0. Then we have
[fv PN(f)l & 212 - 1) (m B, 1/2 - (fflee
for all f (G). Bf 1/2, the stability constant improves /2 (
The condition B < is e.g. satisfied by our Architecture but -strictly speaking- we may not apply Theorem 4.2 since not all utilized filters are Lipschitz continuous. Remark D.3 Appendix however shows, that the above stability result remains applicable for this architecture long as demand that and Á are (potentially rescaled) graph Laplacians. For Architecture we note that D = VV 10/2 and thus the stability constant is given by v 12(22-1) v33 TV 10/2 = 45
We are also interested in perturbations that change the vertex set of the graphs in our architecture. This is important for example in the context of social networks, when passing from nodes representing individuals to nodes representing (close knit) groups of individuals. To investigate this setting, we utilize tools originally developed within the mathematical physics community [29]
Definition 4.3. Let H. and H be two finite dimensional Hilbert spaces. Let A and be normal operators on these spaces. Let J H - H and J. H - H be linear maps called identification operators. We call the two spaces mannss--nitarllyequuvalal (with > 0) if for any S E and u E H we have
|Jfl < 2
I(J - (+) 8lflm,
If JJfllne & 8 Iif + <f.l fr. 1 JJull < /v |ul| + (u, | u)
If, for some w E C the resolvent R = (A w)- satisfies [I[RR J f) < 8 fl for all f H. we say that A and A are w-S-close with identification operator J.
Absolute value A and adjoint J* of operators are briefly reviewed in Appendix A While the above definition might seem fairly abstract at first, it is in fact natural setting investigate structural perturbations as Figure 3 exemplifies. In our current setting, the Hilbert spaces
in Definition 4.3 are node-signal spaces H = (G)) H = (()) of different graphs. The notion of w-ô-closeness is then useful, as it allows to compare filters defined on different graphs but obtained from applying the same function the respective graph-operators:
Lemma 4.4. In the setting of Definition 4.3 let A and Á be w-S-
close and satisfy oop | op & K for some K >>> 0. If C ---6 C
holomorphic on the disk (0) of radius (K + 1), there is a
vertex-weight vertex- 2
constant C > 0 so that
(lo( - Jop & CCg. ..
weig- 1/82
with Cy depending on g. w and K.
Figure 3: Prototypical Exam- ple of d-unitar--quuivllnn Node Signal Spaces with (-1)-126-close Laplacians.
An explicit characterization of C2 together with proof of this result is presented in Appendix F Lemma i.4 our main tool in establish-
ing our next result, proved in Appendix G which captures stability under set non- preserving perturbations:
Details in Appendix
Theorem 4.5. Let Nv N be scattering transforms based on common module sequence Gy and differing operator sequences 2N, ØN. Assume Rt Lt & 1 and B,, & for some and n > Assume that there are identification operators Jn (²(G,) - ((G.). ). Jn ((G.) - (G,). (0 & & N) so that the respective signal spaces are d-unitarily equivalent, the respective normal operators A,, Ân are w-d-close as well as bounded (in norm) by > and the connecting operators satisfy PPaja-if - S.PPlllet = O. For the common module sequence f2 assume that the non-linearities satisfy [Jn(f Japa 0 and that the constants Cx, and
5

---

(Cg., Te associated through Lemma 4.4 to the functions of the generalized frames in each layer satisfy Ct. + En.er'y Ca.. & D2 for some D > O. Denote the operator that the family (Jn)n of identification operators induce on FN through concatenation by IN : AN FNN. Then, with KN 122 1)2D2. BN-1 if B > 1/2 and KN V2D2. (1 BN)/(1 B) B 1/2:
(N(( IN IN & KN.6 8- If ef (G).
The stability result persists with slightly altered stability constants, if identification operators only almost commute with non-linearities and/or connecting operators, as Appendix G further elucidates. Theorem 4.5 is not applicable to Architecture where filters are not all holomorphic, but is directly applicable to Architecture II. Stability constants can be calculated in terms of D and B as before.
Beyond these results, stability under truncation of the scattering transform is equally desirable: Given the energy WN := "m.,.....eee [|U[])] [Tw] c ... (f) ( stored in the network at layer N, it is not hard see that after extending & (ff by zero to match dimensions with & 2 (f) we have N (f) - 4 (f)1(f) N+ < ( bound for WN is then given as follows:
BN+1 WN (see Appendix for more details). A
Theorem 4.6. Let ox be generalized graph scattering transform based on a an operator sequence
Le Pn. An)x_ and a module sequence Sh with each p.(()) 3 O. Assume in each layer n > 1 that there is an eigenvector tin of A,, with solely positive entries; denote the smallest entry by m, := minge.. [ and the eigenvalue corresponding to thn by Xn. Quantify the sppctral-gap' opened up at this eigenvalue through neglecting the output-generating function by th- := Ey,er, 19.. (An))
and assume B, 2 The We then have (with C [ max (L, R()
N I
Bn ))
Wx(J) & C
mp
The product in (3) decays if C. - C+ converges and I (n) - 00 diverges as N - oc. The chosen to lie the lowest lying eigenspace of a graph Laplacian or normalized graph Laplacian (irrespective of the connectedness of the underlying graphs). As an example, we note that if extend our Architecture to infinite depth (recall from Section 3 that we are using the same filters, operators, etc. in each layer) we have upon choosing An 0 and Vn to be the constant normalized vector that Mn- 0, CN 1 and m. 1/ 1/v/C], for graph with |G] vertices. On a graph with 16 vertices, we then e.g. have WN & (3/4) Ni | f and thus (( (
the eigenvectors th, can e.g. always be ensured if they
(3/4)* (
As detailed in Appendix H Theorem alloo implies that under the given assumptions the scattering transform has trivial 'kernel' for N c0, mapping only 0 to O.
5 Graph-Level Feature Aggregation
To solve tasks such as graph classification or regression over multiple graphs, we need to represent graphs of varying sizes in a common feature space. Given scattering transform 4x, we thus need to find stability preserving map from the feature space N to some Euclidean space that is independent of any vertex set cardinalities. Since FN is a large direct sum of smaller spaces (cf. (.). we simply construct such maps on each summand independently and then concatenate them.
General non-linear feature aggregation: Our main tool in passing to graph-level features is
non-linear map Nº (G) - R given as
1
N
(4)
V
with Ma := Eieg P4 and |f = (Zier pf Our inspiration to use this map stems from can then be recovered from (f) up to permutation of indices (2]] Hence, employing NG (with p > |G') to aggregate node-information into graph-level information, we lose the minimal necessary information
the standard case where all μ. 1: For p > |G], the vector |s| ((Ihll.....fc
.... [fcl)

---

about node permutation (clearly (f) = No (IIf) for any permutation matrix IT) and beyond that only information about the complex phase (respectively the sign in the real case) in each entry of f.
Given scattering transform DN mapping from ( to the feature space FN D (e.))) '1
we ob- tain a corresponding map VN mapping from ((G) to RN = + (RP*)) "1-- by concatenating the feature map 4N with the operator that the family of non-linear maps {Ner, In_ induces on FN by concatenation. Simi-
(P(())
Sey (Ar)
larly we obtain the map N (G)) - LNN by concatenat-
(A1)
pa
1r"-1 with
(4g)
ing the map NN= (G)) - DN (e(Gn))
(2(
the operator induced by the family ( 1. G. In=1- The feature space 2N is completely determined by path-sets 1 and used maximal p-norm indices Pn. It no longer depends on cardinalities of vertex sets of any graphs, allowing to compare (signals on) varying graphs with each other. Most of the results of the previous sections then readily transfer the graph-leved level-featurrr setting (c.f. Appendix
(G,)
((G)
No
RP)
RP
Figure 4: Graph Level Scattering
Low-pass feature aggregation: The spectrum-free aggregation scheme of the previous paragraph is especially adapted to settings where there are no high-level spectral properties remaining constant under graph perturbations. However, many commonly utilized operators, such as normalized and un-normalized graph Laplacians, have a somewhat 'stable' spectral theory: Eigenvalues are always real, non-negative, the lowest-lying eigenvalue equals zero and simple (if the graph is connected). In this section we shall thus assume that each mentioned normal operator A,, (Án) has these spectral properties. We denote the lowest lying normalized eigenvector (which is generically determined up to complex phase) by t'a.. and denote by M (G,,) - C the map given by Ma (f) Kr'..: (Wa..:Je(G... ())G))) The absolute value around the inner product is introduced absorb the phase- ambiguity in the choice of v's.. Given a scattering transform n mapping from (²( to the feature
space NN. we obtain a corresponding map y < mapping from (G) to EN = "N,CC"""" by MoRh
N
1=1 induces on Fy by concatenation. As detailed in Appendix 1.2] this map inherits stability properties in complete analogy to the discussion of Section
concatenating the feature map n with the operator that the family of maps {M J
6 Higher Order Scattering
Node signals capture information about nodes in isolation. However, one might be interested in binary, ternary or even higher order relations between nodes such distances or angles in graphs representing molecules. In this section we focus on binary relations - i.e. edge level input as this is the instantiation we also test in our regression experiment in Section [ Appendix J.2 provides more details and extends these considerations beyond the binary setting. We equip the space of edge inputs with an inner product according to (f.g) = = Jyg9ifHii and denote the resulting inner-produce space by ((E) with E' G G the set of edges. Setting e.g. node-weights μ4 and edge weights pid to one, the adjacency matrix W as well as normalized or un-normalized graph Laplacians constitute self- adjoint operators on (2E)) where they act by matrix multiplication. Replacing the Gn of Section by En, we can then follow the recipe laid out there in constructing 2nd scattering transforms; all that we need are a module sequence Q2 and an operator sequence 23 := (P? AW) where now P2 e (En-1) - {2(E,, (E,,) and A (E,) - f² (E,). We denote the resulting feature map by $3 and write $7 for the corresponding feature space. The map N introduced in 44) can also be adapted aggregate hidher-order features into graph level features: With ||/ll == Cijea ( 1/4 and Σ Gl E Uij. we define NZ (J) (lllle VIE, [[] II [lll ([)))=))))) \/VP.
33 with feature space Rh @ (Ex) 1I"
Given feature map
we obtain a corresponding
7

---

(R.)) (R%))I--11 by concatenating & with the map that the family of non-linear maps (NN J==1 induces on & n by concatenation. The stability results of the preceding sections then readily translate to &3 and V (c.f. Appendix J
map 3 mapping from to
BN -
7 Experimental Results
We showcase that even upon selecting the fairly simple Architectures I and II introduced in Section (c.f. also Fig. 2) our generalized graph scattering networks are able to outperform both wavelet- based scattering transforms and leading graph-networks under different circumstances. To aid visual clarity when comparing results, we colour-code the best-performing method in green, the second-best performing in yellow and the third-best performing method in orange respectively.
Social Network Graph Classification: To facilitate contact between our generalized graph scat- tering networks, and the wider literature, we combine a network conforming to our general theory namely Architecture I Fig. 2 (as discussed in Section 3 with depth N 4, identity as connect- with the low pass aggregation scheme of Section 5 and Euclidean support vector machine with RBF-kernel (GGSN+EK). The choice N was made to keep computation-tine palatable, while aggregation scheme and non non-linearities were chosen to facilitate comparison with standard saateer-scattering approaches. For this hybrid architecture (GGSN+EK), classification accuracies under the standard choice of 10-fold cross validation on five common social network graph datasets are compared with performances of popular graph kernel approaches, leading deep learning methods as well as geometric wavelet scattering (GS-SVM) [12] More details are provided in Appendix K As evident from Table [ our network consistently achieves higher accuracies than the geometric wavelet scattering transform of [12., with the performance gap becoming significant on the more complex REDDIT datasets, reaching a relative mean performance increase of more than 10% REDDIT- This indicates the liberating power of transcending the graph wavelet setting. While on comparatively smaller and somewhat simpler datasets there is performance gap between static architecture and fully trainable networks, this gap closes more complex datasets: While P-Poinc e.g. outperforms our method on IMDB datasets, the roles reversed REDDIT datasets. On REDDIT-B our approach trails only GIN; with difference in accuracies insignificant. On REDDIT-5K our method comes in third, with the gap to the second best generate state of the art results.
ing operators and --non-lineeritin
method (GIN) being statistically insignificant. On REDDIT-12K
Table 1: Classification Accuracies on Social Network Datasets
Method
Classification Accuracies
COLLAB
IMDB-
IMDB-M
REDDIT-B
REDDIT-SK
REDDIT-12K
WL 33
47.8241.45
7..60
N/A
78.52=2.0
50.77 + 2.02
34.37 = 1.32
Graphle
73.42+2.43
5..90
N/A
27.26=2.34
39.75 + 1.36
25.98 = 1.29
DGK 42
03.00=10.20
66.90
0..50-1.500
78.00=0.30
41.20 + 0.10
32.20
0 0.10
DGCNN 46
03.76+00.4
70.03++0.86
4.883-0.85
N/A
48.70 +: 4.54
N/A
PSCN 26
72.60+22.15
71.00 20
2.824
86.30 1.58
49.10 + 0.70
41.32 = 0.42
P-Prine 19
N/A
81.86 4,26
57.31 1.27
79.78
51.71
+: 3.01
42.16 = 3.41
S2S-N2N.PP
01.75+0..80
0.77
01.19
86.50=
52.28
+ 0.50
42.47 0.10
GSN-c 3
85.5 1.2
77.8 3.3
54.3 = 3.3
N/A
N/A
N/A
WKPL-KC 47
N/A
75.1 +: 1.1
49.5 d: 0.4
N/A
59.5 0.6
48.4 + 0.5
GIN [1
1..20=
7..10+5.10
52.30 80
92. 2..50
57.50 + 1.50
N/A
GS-SVM [2]
19.94+1.61
71.20
48.7342.32
89 89.65+1.94
53.33 + 1.37
45.23
1.25
GOSN+EK [OURS]
80.34 10.3441..68
73.70
2.227
91.60+ 1.97
56.89 4: 2.24
49.03
1.58
Regression of Quantum Chemical Energies: In order showcase the prowess of both our higher order scattering scheme and our spentrum-agnostic aggregation method of Section 5] we combine these building blocks into hybrid architecture which we then apply in combination with kernel methods (2GGST + EK) to the task of atomization energy regression on QM7. This is a comparatively small dataset of 7165 molecular graphs, taken from the 970 million strong molecular database GDB- 13 (2). Each graph in QM7 represents an organic molecule, with nodes corresponding to individual atoms. Beyond the node-level information of atomie charge, there is also edge level information characterising interaction strengths between individual nodes/atoms available. This is encoded into so called Coulomb matrices (see e.g. 3D or Appendix K) of molecular graphs, which for us serve dual purpose: On the one hand we consider Coulomb matrix edge-level input signal on given graph.
8

---

On the other hand, we also treat it as an adjacency matrix from which we build up graph Laplacian L. Our normal operator then chosen as L C/ Em/r ()) again. Connecting operators are set to the identity, while non-linearities are fixed to pr)a(()) = 1. Filters are chosen as (sin(x/2 L), cos(1/ x /2- )in(s )), cOS(TT 2)) acting through matrix multiplication. Output generating functions are set to the identity and depth is N 4, so that we essentially recover Architecture II of Fig.
2 now applied to edge-level input. Graph level features are aggregated via the map No of Section 6 We chose p (and not p >> 5) for Ne to avoid overfitting. Generated feature vectors are combined with node level scattering features obtained from applying Architecture II of Fig. 2 to the in- put signal of atomic charge into composite feature vectors; plotted in Figure 5 As is visually evident, even when reduced to the low-dimensional subspace of their first three principal components, the generated scatter- ing features are able to aptly resolve the atom- ization energy of the molecules. This aptitude is also reflected in Table comparing our approach with leading graph-based learning methods trained with ten-fold cross validation on node and (depending on the model) edge level information. Our method is the best performing. We significantly outperform the next best model (DTNN), producing less than half of its mean absolute error (MAE). Errors of other methods are at least one sometimes two orders of magnitude greater. In part, this performance discrepancy might be explained by the hightened suitability of our scattering transform for environ- ments with somewhat limited training-data availability. Here speculate that the additional performance gap might be ex- plained by the fact that our graph shift operator A carries the same information as the Coulomb matrix (a proven molecular graph descriptor in itself (31). Additionally, our filters being infinite series" in powers of the underlying normal operator
lood /mall
-100
20 Bol Sooe
-200
100
-200
300
600
-100
Figure 5: Atomization Energy as Function of pri- mary Principal Components of Scattering Features
Table Comparison of Methods
Method
MAE [kcal/mol]
AttentiveFP [40
66.2 2.8
DMPNN 44
105.8 1 13.2
DTNN 39
8.2 = 3.9
GraphCony 18
118.9 + 20,2
GROVER (base)
30
72.5 + 3.9
MPNN 13
113.0 + 17.2
N-GRAM
125.6 +
PAGTN (global) 6
47.8 3.0
PhysChem 45
59.6 2.3
SchNet 52]
74.2 6.0
Weave 17
59.6 2.3
allows for rapid dispersion of information across underlying molecular graphs, as opposed to e.g. the filters in GraphConv or SchNet, which do not incorporate such higher powers. To quantify the effect of including second order scattering coefficients, we also include the result of performing kernel-regression solely on first order features generated through Architecture II of Fig. (GGTT + EK). While results are still better than those of all but one leading approach, incorporating higher order scattering improves performance significantly.
GGST+EK [OURS]
11.3 + 0.6
2GGST+EK [OURS]
3.4 = 0.3
8 Discussion
Leaving behind the traditional reliance on graph wavelets, we developed a theoretically well founded framework for the design and analysis of (generalized) graph scattering networks; allowing for varying branching rations, non-linearities and filter banks. We provided spectrum independent stability guarantees, covering changes in input signals and for the first time also arbitrary normal perturbations in the underlying graph-shift-opperaton vertex-set non- non-preserving changes in graph domains, we obtained guarantees for this setting too. We provided conditions for energy decay and discussed implications for truncation stability. Then we introduced a new method of graph-level feature aggregation and extended scattering networks to higher order input data. Our numerical experiments showed that a simple scattering transform conforming to our framework is able to outperform the traditional graph-ward wavelet based approach to graph scattering in social network graph classification tasks. On complex datasets our method also competitive with current fully trainable methods, ouperforming all competitors on REDDIT-122 outperform current leading graph-based learning methods in predicting atomization energies on QM7. A reasonable critique of scattering networks tractable models for general graph convolutional
After introducing a new framework to quantify stability
Additionally, higher order graph scattering transforms significantly

---

networks is their inability to emulate non con-tree-structuree network topologies. While transcending the wavelet setting has arguably diminished the conceptual gup between the two architectures, this structural difference persists. Additionally we note that despite provided promising example, it is not yet clear whether the newly introduced graph-perturbation framework can aptly provide stability guarantees to all reasonable coarse-graining procedures. Exploring this question is the subject of ongoing work.
Broader Impact
We caution against an over-interpretation of established mathematical guarantees: Such guarantees do not negate biases that may be inherent to utilized datasets.
Disclosure of Funding
Christian Koke acknowledges support from the German Research Foundation through the MIMO Il-project (DFG SPP 1798, KU 1446/21-2). Gitta Kutyniok acknowledges support from the ONE Munich Strategy Forum (LMU Munich, TU Munich, and the Bavarian Ministery for Science and Art), the Konrad Zuse School of Excellence in Reliable AI (DAAD), the Munich Center for Machine Learning (BMBF) well the German Research Foundation under Grants DFG-SPP-2298, KU 1446/31-1 and KU 1446/32-1 and under Grant DFG-SFB/TR 109, Project C09 and the Federal Ministry of Education and Research under Grant MaGriDoo
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. International Conference on Learning Representations, 2021.
[2] L. C. Blum and J.-L. Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database GDB-13. J. Am. Chem. Soc., 131:8732, 2009.
[3] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[4] Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE Trans. Pattern Anal. Mach. Intell., 35(8):1872-1886, 2013.
[5] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally connected networks on graphs. International Conference on Learning Representations (ICLR2014), CBLS, April 2014, 2014.
[6] Benson Chen, Regina Barzilay, and Tommi Jaakkola. Path-augmented graph transformer network, 2019.
[7] Paul Civin, Nelson Dunford, and Jacob T. Schwartz. Linear operators, part i: General theory. American Mathematical Monthly, 67:199, 1960.
[8] Ronald R. Coifman and Mauro Maggioni. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21(1):53-94, 2006. Special Issue: Diffusion Maps and Wavelets.
[9] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[10] Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms graphs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LAA USA. May 6-9, 2019. OpenReview.net, 2019.
10

---

[11] Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph scattering transforms. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox. and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 4036-8046, 2019.
[12] Feng Gao, Guy Wolf, and Matthew J. Hirn. Geometric scattering for graph data analysis. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2122-2131. PMLR, 2019.
[13] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[14] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): 2011.
[15] Vassilis N. Ioannidis, Siheng Chen, and Georgios B. Giannakis. Pruned graph scattering transforms. In International Conference on Learning Representations, 2020.
[16] Yu Jin and Joseph F. JáJá. Learning graph-level representations with gated recurrent neural networks. CoRR, abs/1 805607683, 2018.
[17] Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of compuler-aided molecular design, 30(8):595 608, 2016.
[18] Thomas N. Kipf and Max Welling. Semi- suprrvspe classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[19] Panagiotis Kyriakis, Iordanis Fostiropoulos, and Paul Bogdan. Learning hyperbolic repre- sentations of topological features. In International Conference on Learning Representations, 2021.
[20] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3734- 3743. PMLR, 09-15 Jun 2019.
[21] Shengchao Liu, Mehmet F Demirel, and Yingyu Liang. N-gram graph: Simple unsupervised representation for graphs, with applications to molecules. Advances in neural information processing systems, 32, 2019.
[22] Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331-1393 2012.
[23] Hana Melánová, Bernd Sturnfels, and Rosa Winter. Recovery from power sums. Experimental Mathematics, 000):1-10, 2022.
[24] Barry Simon Michael Reed. Methods of modern mathematical physics, Volume 1. Academic Press, 1981.
[25] Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. Advances in Neural Information Processing Systems, 33:14498- 14508, 2020.
[26] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In Maria Florina Balcan and Kilian Q Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pages 2014-2023, New York, New York, USA, 20-22 Jun 2016. PMLR.
[27] Chao Pan, Siheng Chen, and Antonio Ortega. Spatio-temporal graph scattering transform, 2020.

---

[28] Michael Perlmutter, Feng Gao, Guy Wolf, and Matthew Hirn. Understanding graph neural networks with asymmetric geometric scattering transforms, 2019.
[29] Olaf. Post. Spectral Analysis Graph-like Spaces by Olaf Post. Lecture Notes in Mathematics, 2039. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st ed. 2012. edition, 2012.
[30] Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems, 33: 13:12559-12571 2020.
[31] M. Rupp, A. Tkatchenko, K.-R. Müller, and O. A. von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning. Physical Review Letters, 108:058301, 2012.
[32] Kristof Schütt, Pieter-Jan Kindermans, Huziel Enoc Sauceda Felix, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Robert Müller. Schnet: A continuous-filte convolutional neural network for modeling quantum interactions. Advances in neural information processing systems, 30, 2017.
[33] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77):559-2561, 2011.
[34] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In David van Dyk and Max Welling, editors, Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pages 488 495, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 16-18 Apr 2009. PMLR.
[35] David Shuman, Christoph Wiesmeyr, Nicki Holighaus, and Pierre Vandergheynst. Spectrum- adapted tight graph wavelet and vertex- freeue-fr frames. IEEE Transactions on Signal Pro- cessing, 63(16))4223-4233 2015.
[36] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature, 2021.
[37] Wihler T.P. On the hölder continuity of matrix functions for normal matrices. Journal of inequalities pure and applied mathematics, 10(4), Dec 2009.
[38] Thomas Wiatowski and Helmut Böleskei. A mathematical theory of deep convolutional neural networks for feature extraction. IEEE Transactions on Information Theory, 64:1845-1866, 2018.
[39] Zhenqin WU, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay S. Pande. Moleculenet: a benchmark for molecular machine learningt felectronic supplementary information (esi) available. see doi: 10.1039/c7sc02664. Chemical Science, 9:513 530, 2018.
[40] Zhaoping Xiong, Dingyan Wang. Xiaohong Liu, Feisheng Zhong, Xiaozhe Wan, Xutong Li, Zhaojun Li, Xiaomin Luo, Kaixian Chen, Hualiang Jiang, and Mingyue Zheng. Pushing the boundaries of molecular representation for drug discovery with the graph attention mechanism. Journal of Medicinal Chemistry, 63(16)88749 076774979777,,, 2020. PMID: 31408336.
[41] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[42] Pinar Yanardag and S.V.N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, page 1365-1374, New York, NY, USA, 2015, Association for Computing Machinery.
12

---

[43] Pinar Yanardag and S.V.N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, page 1365-1374, New York, NY, USA, 2015. Association for Computing Machinery.
[44] Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Guzman-Perez, Timothy Hopper, Brian Kelley, Miriam Mathea, Andrew Palmer, Volker Settels, Tommi Jaakkola, Klavs Jensen, and Regina Barzilay. Analyzing learned molecular representa- tions for property prediction. Journal of Chemical Information and Modeling, 59(8):3370-3388) 2019. PMID: 31361484.
[45] Shuwen Yang, Ziyao Li, Guojie Song, and Lingsheng Cai. Deep molecular representation learning via fusing physical and chemical information. Advances in Neural Information Processing Systems, 34, 2021.
[46] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty- -Scco- AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4438 4445. AAAI Press, 2018.
[47] Qi Zhao and Yusu Wang. Learning metrics for persistence- based summaries and applications for graph classification. Advances in Neural Information Processing Systems, 32, 2019.
[48] Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 1963):1046-1074, nov 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] A discussion of how and in which order the main claims made in Abstract and Introduction were substantiated within the paper is a main focus of Section g
(b) Did you describe the limitations of your work? [Yes] This is second focus of Section g
(c) Did you discuss any potential negative societal impacts of your work? [Yes] This is part of Section g
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] Every Theorem and Lemma is stated in mathematically precise way, with all underlying assumptions included. Additionally, Appendix [ briefly reviews some terminology that might not be immediately present in every readers mind, but is utilized in order to be able to state theoretical results in a precise and concise manner.
(b) Did you include complete proofs of all thcoretical results? [Yes] This is the Focus of Appendices B statements and corresponding proofs are in complete analogy (in fact almost verbatim the same) to previously discussed statements and proofs.
H and [ Results in Appendix P are merely stated, as
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Yes; please see the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] This is the main focus of Appendix
13

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Errors for results of conducted experiments are included in Table and Table 2 respectively.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] This is described at the beginning of Appendix K
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] All utilized datasets
were matched to the papers that introduced them (cf. Section K Additionally,
partially built on code corresponding to [12 which we mentioned in Appendix K
(b) Did you mention the license of the assets? [Yes] We mentioned in Appendix K that the
code corresponding to [12] is freely available under an Apache License.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
Please supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes] For the utilized social network datasets, we mention in Appendix K that neither personally identifyable data content that might be considered offensive is utilised.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "m0PxVrT73Ok", "reviewer": "Reviewer_697M", "summary": "In this paper, the authors focus on the design and analysis of graph scattering networks with variable branching ratios and generic functional calculus filters. Spectrally-agnostic stability guarantees for node- and graph-level perturbations are established.\n\n", "questions": "1. The authors should add comments on the optimality of the upper bounds established in Section 4.\n\n2. More background and details are needed for the section on higher order scattering.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThis paper is well-organized. The theoretical results on stability guarantees and the experimental results on quantum chemical energies are interesting.\n\nWeaknesses:\n1. The authors present several upper bounds in Section 4 for stability guarantees. However, it is unknown the optimality of these bounds.\n\n2. The section on higher order scattering needs more background knowledge to follow for readers.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OM4UnIjUQIM", "reviewer": "Reviewer_5wnJ", "summary": "The paper proposes a generalization of graph scattering networks that goes beyond the graph wavelets setting. The authors provide stability guarantees for their generalized scattering transform, as well as layer-wise energy decay bounds. The authors propose a simple feature aggregation method to transform graphs into Euclidean space and briefly discussed taking into account higher-order scattering. The authors conducted experiments of their methods on a graph classification task and a graph regression task. ", "questions": "Questions on the quality front: \n\n1. The lipschitz-type bounds in theorems 4.1 and 4.2 appear to be just iterative applications of a layer-wise lipschitz type condition. While this is certainly a valid bound, the constants in the upper-bound involves a product of N terms/terms raised to the Nth power (this exponential term also appears in theorem 4.5). I would argue that on a practical level, these exponential terms render the bounds rather impractical, unless matching lower bounds/some sharpness result can be shown. In particular, say N is 10. Then if I perturb say the input by some small constant, the output could have a order C^10 change to it, which can be astronomical. \n\n2. In the expressivity/energy section, the analysis was conducted in the limit of infinite network depth. The idea is quite neat, but it raises several important questions that the authors have to address:\n\n-  the authors make the assumption that one can always choose an eigenvector of strictly positive entries. This of course follows from results in spectral graph theory. However, for the connected graph case, which I argue is probably the most important case, it is my understanding that the only eigenvector that satisfies this will be the eigenvector corresponding to the smallest eigenvalue, in which case the eigenvector has constant entries (they are all the same), and the corresponding eigenvalue is just 0, in which case the notation of defining m_n as the minimum and lambda_n etc becomes somewhat redundant. On the other hand, if the graph is disconnected, then the eigenvector that you pick will, to the best of my knowledge, have positive entries in one component and 0's in some other component, which would violate the strictly positive entry assumption. in either case, I think some change/clarification has to be made here. \n\n- While I think the energy bounds are interesting, it is unclear to me how useful/related this is to link to the expressivity of the network. The fact that the mapping only maps 0 to 0, when N goes to infinity, seems like a property that is only marginally related to expressivity in some bare-minimum way. One can probably come up with some kind of invertible linear-type transformation that also only maps 0 to 0. This property to me at first sight seems to just mean that the mapping is not contracting, but going from \"no contraction\" to \"expressivity\" seems a bit of a stretch claim to me. I think the authors could modify the wording of their conclusion here. \n\nIn terms of the clarity of exposition, I think the general ML audience will find this paper difficult to read and apply, for the following reasons: \n\n1. There is too much material for a 9 page conference paper. Important aspects of the paper are delegated to the appendix, and there is not enough room for the authors to give the necessary treatment for background knowledge and definitions. As a result, only those that already have very substantial backgrounds in graph wavelets/graph networks and spectral graph theory will be able to understand it. \n\n2. The authors have the style of defining things in the broadest, most abstract and general version first, and then in the experimental section just make some very specific choices in their model that conform to their general theoretical results, but without justifying those experimental choices at all. I understand that this is a theoretical paper, but I think having one or two tables of pseudocodes on particular instantiations of your architecture, and providing more justification for why certain parameter or modeling choices are made (such as cross-validation etc) would help the users understand and adopt their method much more readily. In particular, the experimental results for the regression application is great, but for the classification is not very good. I wonder if the performance on the classification task could be improved with an alternative instantiation of their model, such as using other functions than sines and cosines, or changing the layer parameter, or using a different operator than the Laplacian etc. \n\n", "limitations": "Main limitations are outlined in section above. \nNo negative societal impact. \n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: the idea, methods etc are original. The novelty/originality of the paper definitely meets the bar for publication at NeurIPS.\n- Quality: the background and tools used are somewhat technical and motivated quite abstractly. The quality of the mathematics/derivations, even though I didn't check proofs line by line, are, to the best of my knowledge, sound.  \n- Clarity: the organization and exposition of the article leaves much room for improvement. Details are given below. \n- Significance: Nowadays it is certainly interesting and significant to consider problems involving GCNs and graph networks. The topic of this paper is of sufficient significance to meet the bar for publication at NeurIPS. \n\nOverall, I think the originality, significance and mathematical soundness of the paper are fine, whereas the clarity of the paper leaves room for improvement, which I will detail in sections below. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7AAdlmclehi", "reviewer": "Reviewer_oeim", "summary": "In this paper, the authors define a very general notion of scattering transform, with an application on graphs. They (re)define each building blocks of the scattering transform: spectral filters, output (low-pass) functions, non-linearities, etc., as well as proper projection operators when the domain changes between layers. Under appropriate assumption of Lipschitzness of each of these elements, they show stability of the resulting transform, as well as energy preservation, generalizing the classical Euclidean results. Some variants on graphs are presented: an aggregation strategy for graph classification and higher-order scattering. Experiments on real data show the effectiveness of the approach.", "questions": "-The approach is interesting, but I would suggest either to reformulate the title and/or abstract to be less specialized on graphs, or on the contrary focusing far more the description of the architecture on graphs by giving minimal examples satifying all the formulated hypothesis along the way.\n\n- if the higher-order architecture used in the regression experiment ? It is not clear.\n\n- is the constant \"$2$\" in definition 4.3 arbitrary ?\n\n- in theorem 4.2 (and related results), could the proximity of the normal operators be expressed in terms of spectral norm rather than Frobenius ? This is more often satisfied (eg by random graphs, or spectral graph coarsening, etc)", "limitations": "The authors are quite honest about the limitations in their first experiment, where they are often not state-of-the-art.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- a general approach, than can take into account many variants, domain changes, etc.\n- all classical theoretical results on scattering hold\n- a very complete supplementary material\n- the experiments are convincing, especially for graph regression\n\nWeaknesses:\n\n- a bit paradoxically, the approach suffers from too much generality. The authors define very abstract operators and elements, and in fact nothing in particular is about graphs at all, until the discussions of sections 6 and 7 which are not the core of the approach. Furthermore, the actual choice of the filters, some combination of sin and cos, is quite hidden within the experiment section, and may seem a tad arbitrary. As a result, the reader is somewhat left wondering all along the paper what the actual architecture is, if this is just an abstract formulation of previous architecture or if there is something fundamentally new here. Examples of implementation on graphs along the abstract description could really help the understanding of the approach.\n- many variants are described but, it seems, not tested in experiments (changing graphs, higher-order tensors...)\n- the theorems are valid under many assumptions, but a minimal examples satisfying all of them is not given", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept