Understanding Graph Neural Networks with Asymmetric Geometric Scattering Transforms

  • 2019-11-14 17:23:06
  • Michael Perlmutter, Feng Gao, Guy Wolf, Matthew Hirn
  • 2


The scattering transform is a multilayered wavelet-based deep learningarchitecture that acts as a model of convolutional neural networks. Recently,several works have introduced generalizations of the scattering transform fornon-Euclidean settings such as graphs. Our work builds upon these constructionsby introducing windowed and non-windowed graph scattering transforms based upona very general class of asymmetric wavelets. We show that these asymmetricgraph scattering transforms have many of the same theoretical guarantees astheir symmetric counterparts. This work helps bridge the gap between scatteringand other graph neural networks by introducing a large family of networks withprovable stability and invariance guarantees. This lays the groundwork forfuture deep learning architectures for graph-structured data that have learnedfilters and also provably have desirable theoretical properties.


Quick Read (beta)

Understanding Graph Neural Networks with Asymmetric Geometric Scattering Transforms

Michael Perlmutter Department of Computational Mathematics, Science & Engineering, Michigan State University, East Lansing, Michigan, USA Feng Gao Department of Genetics, Yale University, New Haven, Connecticut, USA Guy Wolf Matthew Hirn
November 30, 2019

The scattering transform is a multilayered wavelet-based deep learning architecture that acts as a model of convolutional neural networks. Recently, several works have introduced generalizations of the scattering transform for non-Euclidean settings such as graphs. Our work builds upon these constructions by introducing windowed and non-windowed graph scattering transforms based upon a very general class of asymmetric wavelets. We show that these asymmetric graph scattering transforms have many of the same theoretical guarantees as their symmetric counterparts. This work helps bridge the gap between scattering and other graph neural networks by introducing a large family of networks with provable stability and invariance guarantees. This lays the groundwork for future deep learning architectures for graph-structured data that have learned filters and also provably have desirable theoretical properties.

1 Introduction

The scattering transform is a wavelet-based model of convolutional neural networks (CNNs), introduced for signals defined on โ„n by S. Mallat in [11]. Like the front end of a CNN, the scattering transform produces a representation of an inputted signal through an alternating cascade of filter convolutions and pointwise nonlinearities. It differs from CNNs in two respects: i) it uses predesigned, wavelet filters rather than filters learned through training data, and ii) it uses the complex modulus |โ‹…| as its nonlinear activation function rather than more common choices such as the rectified linear unit (ReLU). These differences lead to a network which provably has desirable mathematical properties. In particular, the Euclidean scattering transform is: i) nonexpansive on ๐‹2โข(โ„n), ii) invariant to translations up to a certain scale parameter, and iii) stable to certain diffeomorphisms. In addition to these theoretical properties, the scattering transform has also been used to achieve very good numerical results in fields such as audio processing [1], medical signal processing [4], computer vision [12], and quantum chemistryย [10].

While CNNs have proven tremendously effective for a wide variety of machine learning tasks, they typically assume that inputted data has a Euclidean structure. For instance, an image is naturally modeled as a function on โ„2. However, many data sets of interest such as social networks, molecules, or surfaces have an intrinsically non-Euclidean structure and are naturally modeled as graphs or manifolds. This has motivated the rise of geometric deep learning, a field which aims to generalize deep learning methods to non-Euclidean settings. In particular, a number of papers have produced versions of the scattering transform for graph [7, 8, 9, 17] and manifold [13] structured data. These constructions seek to provide a mathematical model of geometric deep learning architectures such as graph neural networks in a manner analogous the way that Euclidean scattering transform models CNNs.

In this paper, we will construct two new families of wavelet transforms on a graph G from asymmetric matrices ๐Š and provide a theoretical analysis of both of these wavelet transforms as well as the windowed and non-windowed scattering transforms constructed from them. Because the matrices ๐Š are in general not symmetric, our wavelet transforms will not be nonexpansive frame analysis operators on the standard inner product space ๐‹2โข(G). Instead, they will be nonexpansive on a certain weighted inner product space ๐‹2โข(G,๐Œ), where ๐Œ is an invertible matrix. In important special cases, our matrix ๐Š will be either the lazy random walk matrix ๐, its transpose ๐T, or its symmetric counterpart given by ๐“=๐ƒ-1/2โข๐๐ƒ1/2. In these cases, ๐‹2โข(G,๐Œ) is a weighted ๐‹2 space with weights depending on the geometry of G. We will use these wavelets to construct windowed and non-windowed versions of the scattering transform on G. The windowed scattering transform inputs a signal ๐ฑโˆˆ๐‹2โข(G,๐Œ) and outputs a sequence of functions which we refer to as the scattering coefficients. The non-windowed scattering transform replaces the low-pass matrix used in the definition of the windowed scattering transform with an averaging operator ๐ and instead outputs a sequence of scalar-valued coefficients. It can be viewed as the limit of the windowed scattering transform as the scale of the low-pass tends to infinity (evaluated at some fixed coordinate 0โ‰คiโ‰คn-1).

Analogously to the Euclidean scattering transform, we will show that the windowed graph scattering transform is: i) nonexpansive on ๐‹2โข(G,๐Œ), ii) invariant to permutations of the vertices, up to a factor depending on the scale of the low-pass (for certain choices of ๐Š), and iii) stable to graph perturbations. Similarly, we will show that the non-windowed scattering transform is i) Lipschitz continuous on ๐‹2โข(G,๐Œ), ii) fully invariant to permutations, and iii) stable to graph perturbations.

1.1 Notation and Preliminaries

Let G=(V,E,W) be a weighted, connected graph consisting of vertices V, edges E, and weights W, with |V|=n the number of vertices. If ๐ฑ=(๐ฑโข(0),โ€ฆ,๐ฑโข(n-1))T is a signal in ๐‹2โข(G), we will identify ๐ฑ with the corresponding point in โ„n, so that if ๐ is an nร—n matrix, the multiplication ๐๐ฑ is well defined. Let ๐€ denote the weighted adjacency matrix of G, let ๐=(๐โข(0),โ€ฆ,๐โข(n-1))T be the corresponding weighted degree vector, and let ๐ƒ=diagโข(๐). We will let


be the normalized graph Laplacian, let 0โ‰คฯ‰0โ‰คฯ‰1โ‰คโ€ฆโ‰คฯ‰n-1โ‰ค2 denote the eigenvalues of ๐, and let ๐ฏ0,โ€ฆ,๐ฏn-1 be an orthonormal eigenbasis for ๐‹2โข(G), ๐๐ฏi=ฯ‰iโข๐ฏi. ๐ may be factored as


where ฮฉ=diagโข(ฯ‰0,โ€ฆ,ฯ‰n-1), and ๐• is the unitary matrix whose i-th column is ๐ฏi. One may check that ฯ‰0=0 and that we may choose ๐ฏ0=๐1/2โˆฅ๐1/2โˆฅ2, where ๐1/2=(๐โข(0)1/2,โ€ฆ,๐โข(n-1)1/2)T. We note that since we assume G is connected, it has a positive spectral gap, i.e.

0=ฯ‰0<ฯ‰1. (1)

Our wavelet transforms will be constructed from the matrix ๐“g defined by


where g:[0,2]โ†’[0,1] is some strictly decreasing spectral function such that gโข(0)=1 and gโข(2)=0, and


We note that 1=ฮป0>ฮป1โ‰ฅโ€ฆโขฮปn-1โ‰ฅ0, where the fact that ฮป1<ฮป0=1 follows from (1). When there is no potential for confusion, we will supress dependence of g and write ๐“ and ฮ› in place of ๐“g and ฮ›g. As our main example, we will choose gโข(t)โ‰”gโ‹†โข(t)โ‰”1-t2, in which case


In [8], Gama et al. constructed a graph scattering transform using wavelets which are polynomials in ๐“gโ‹†, and in [9], Gao et al. defined a different, but closely related, graph scattering transform from polynomials of the lazy random walk matrix


In order to unify and generalize these frameworks we will let ๐Œ be an invertible matrix and let ๐Š be the matrix defined by


Note that ๐Š depends on the choice of both g and ๐Œ, and thus includes a very large family of matrices. As important special cases, we note that we may obtain ๐Š=๐“ by setting ๐Œ=๐ˆ, and we obtain ๐ and ๐T by setting gโข(t)=gโ‹†โข(t) and letting ๐Œ=๐ƒ-1/2 and ๐Œ=๐ƒ1/2, respectively.

In Section 2, we will construct two wavelet transforms ๐’ฒ(1) and ๐’ฒ(2) from functions of ๐Š and show that these wavelet transforms are non-expansive frame analysis operators on the appropriate Hilbert space. When ๐Œ=๐ˆ (and therefore ๐Š=๐“), this Hilbert space will simply be the standard inner product space ๐‹2โข(G). However, for general ๐Œ, the matrix ๐Š will not be self-adjoint on ๐‹2โข(G). This motivates us to introduce the Hilbert space ๐‹2โข(G,๐Œ), of signals defined on G with inner product defined by


where โŸจโ‹…,โ‹…โŸฉ2 denotes the standard ๐‹2โข(G) inner product. We note that the norms โˆฅ๐ฑโˆฅ๐Œ2โ‰”โŸจ๐ฑ,๐ฑโŸฉ๐Œ, and โˆฅ๐ฑโˆฅ22=โŸจ๐ฑ,๐ฑโŸฉ2 are equivalent and that


where for any nร—n matrix ๐, we shall let โˆฅ๐โˆฅ2 and โˆฅ๐โˆฅ๐Œ denote its operator norms on ๐‹2โข(G) and ๐‹2โข(G,๐Œ) respectively. The following lemma, which shows that ๐Š is self-adjoint on ๐‹2โข(G,๐Œ), will be useful in studying the frame bounds of the wavelet transforms constructed from ๐Š.

Lemma 1.

๐Š is self-adjoint on L2โข(G,M).


By construction, ๐“ is self-adjoint with respect to the standard inner product. Therefore, for all ๐ฑ and ๐ฒ we have

โŸจ๐Š๐ฑ,๐ฒโŸฉ๐Œ =โŸจ๐Œโข(๐Œ-1โข๐“๐Œ)โข๐ฑ,๐Œ๐ฒโŸฉ2


It will frequently be useful to consider the eigenvector decompositions of ๐“ and ๐Š. By definition, we have

๐“=๐•โขฮ›โข๐•T (2)

where ฮ›=gโข(ฮฉ) and {๐ฏ0,โ€ฆ,๐ฏn-1} is an orthonormal eigenbasis for ๐‹2โข(G) wih ๐“๐ฏi=ฮปiโข๐ฏi. Since the matrices ๐“ and ๐Š are similar with ๐Š=๐Œ-1โข๐“๐Œ, one may use the definition of โŸจโ‹…,โ‹…โŸฉ๐Œ to verify that the vectors {๐ฎ0,โ€ฆ,๐ฎn-1} defined by


form an orthonormal eigenbasis for ๐‹2โข(G,๐Œ), with ๐Š๐ฎi=ฮปiโข๐ฎi. One may also verify that


is a left-eigenvector of ๐Š and ๐ฐiTโข๐Š=ฮปiโข๐ฐiT for all 0โ‰คiโ‰คn-1.

In the following section, we will construct wavelets from polynomials of pโข(๐Š). For a polynomial,
pโข(t)=akโขtk+โ€ฆ+a1โขt+a0 and a matrix ๐, we define pโข(๐) by


The following lemma uses (2) to derive a formula for computing polynomials of ๐Š and ๐“ and relates the operator norms of polynomials of ๐Š to polynomials of ๐“. It will be useful for studying the wavelet transforms introduced in the following section.

Lemma 2.

For any polynomial p, we have

pโข(๐“)=๐•โขpโข(ฮ›)โข๐•Tโ€ƒ๐‘Ž๐‘›๐‘‘โ€ƒpโข(๐Š)=๐Œ-1โขpโข(๐“)โข๐Œ=๐Œ-1โข๐•โขpโข(ฮ›)โข๐•Tโข๐Œ. (3)

Consequently, for all xโˆˆL2โข(G,M)

โˆฅpโข(๐Š)โข๐ฑโˆฅ๐Œ=โˆฅpโข(๐“)โข๐Œ๐ฑโˆฅ2. (4)

Since ๐• is unitary, ๐•-1=๐•T, and so it follows from (2) that


for all rโ‰ฅ0. Moreover, since ๐Š=๐Œ-1โข๐“๐Œ


Linearity now implies (3). (4) follows by recalling that โˆฅ๐ฑโˆฅ๐Œ=โˆฅ๐Œ๐ฑโˆฅ2, and noting therefore that for all ๐ฑ,



In light of Lemma 2, for any polynomial p, we may define pโข(๐“)1/2 and pโข(๐Š)1/2 by

pโข(๐“)1/2โ‰”๐•Tโขpโข(ฮ›)1/2โข๐•Tโ€ƒandโ€ƒpโข(๐Š)1/2=๐Œ-1โข๐•Tโขpโข(ฮ›)1/2โข๐•Tโข๐Œ, (5)

where the square root of the diagaonal matrix pโข(ฮ›) is defined entrywise. We may readily verify that


1.2 Related Work

Graph scattering transforms have previously been introduced by Gama, Ribeiro, and Bruna. in [7] and [8], by Gao, Wolf, and Hirn in [9], and by Zou and Lerman in [17]. In [17], the authors construct a family of wavelet convolutions using the spectral decomposition of the unnormalized graph Laplacian and define a windowed scattering transform as an iterative series of wavelet convolutions and nonlinearities. They then prove results analogous to Theorems 1, 3, and 6 of this this paper for their windowed scattering transform. They also introduce a notion of stability to graph perturbations. However, their notion of graph perturbations is significantly different than the one we consider in Section 4.

In [8], the authors construct a family of wavelets from polynomials of ๐“, in the case where gโข(t)=gโ‹†โข(t)=1-t2, and showed that the resulting non-windowed scattering transform was stable to graph perturbations. These results were then generalized in [7], where the authors introduced a more general class of graph convolutions, constructed from a class of symmetric matrices known as โ€œgraph shift operators.โ€ The wavelet transform considered in [8] is nearly identical to the ๐’ฒ(2) introduced in Section 2, in the special case where gโข(t)=gโ‹†โข(t) and ๐Œ=๐ˆ, with the only difference being that our wavelet transform includes a low-pass filter. In [9], wavelets were constructed from the lazy random walk matrix ๐=๐ƒ1/2โข๐“๐ƒ-1/2. These wavelets are essentially the same as the ๐’ฒ(2) in the case where gโข(t)=gโ‹†โข(t) and ๐Œ=๐ƒ-1/2, although similarly to [8], the wavelets in [9] do not use a low-pass filter. In all of these previous works, the authors carry out substantial numerical experiments and demonstrate that scattering transforms are effective for a variety of graph deep learning tasks.

Our work here is meant to unify and generalize the theory of these previous constructions. Our introduction of the matrix ๐Œ allows us to obtain wavelets very similar to either [8] or [9] as special cases. Moreover, the introduction of the tight wavelet frame ๐’ฒ(1) allows us to produce a network with provable conservation of energy and nonexpansive properties analogous to [17]. To highlight the generality of our setup, we introduce both windowed and non-windowed versions of the scattering transform using general (wavelet) frames and provide a detailed theoretical analysis of both. In the case where ๐Œ=๐ˆ (and therefore ๐Š=๐“) much of this analysis is quite similar to [8]. However, for general ๐Œ, this matrix ๐Š is asymmetric which introduces substantial challenges. While [9] demonstrated that asymmetric wavelets are numerically effective in the case ๐Š=๐, this work is the first to produce a theoretical analysis of graph scattering transforms constructed with asymmetric wavelets.

We believe that the generality of our setup introduces a couple of exciting new avenues for future research. In particular, we have introduced a large class of scattering transforms with provable stability and invariance guarantees. In the future, one might attempt to learn the matrix ๐Œ or the spectral function g based off of data for improved numerical performance on specific tasks. This could be an important step towards bridging the gap between scattering transforms, which act as a model of neural networks, and other deep learning architectures. We also note that a key difference between our work and [18] is that we use the normalized graph Laplacian whereas they use the unnormalized Laplacian. It is quite likely that asymmetric wavelet transforms similar to ours can be constructed from the spectral decomposition of the unnormalized Laplacian. However, we leave that to future work.

2 The Graph Wavelet Transform

In this section, we will construct two graph wavelet transforms based off of the matrix ๐Š=๐Œ-1โข๐“๐Œ introduced in Section 1.1. In the following sections, we will provide a theoretical analysis of the scattering transforms constructed from each of these wavelet transforms and of their stability properties.

Let Jโ‰ฅ0, and for 0โ‰คjโ‰คJ+1, let pj be the polynomial defined by

pjโข(t)={1-tifย โขj=0t2j-1-t2jifย โข1โ‰คjโ‰คJt2Jifย โขj=J+1,

and let qjโข(t)=pjโข(t)1/2. We note that by construction

โˆ‘j=0J+1pjโข(t)=โˆ‘j=0J+1qjโข(t)2=1โขย for allย โข0โ‰คtโ‰ค1. (6)

Using these functions we define two wavelet transforms by




and the qjโข(๐Š) are defined as in (5). The next two propositions show ๐’ฒJ(1) is an isometry and ๐’ฒJ(2) is a nonexpansive frame analysis operator on ๐‹2โข(G,๐Œ).

Proposition 1.

๐’ฒJ(1) is an isometry from L2โข(G,M) to โ„“2โข(L2โข(G,M)). That is, for all xโˆˆL2โข(G,M),


Proposition 1 shows ๐Š is self-adjoint on ๐‹2โข(G,๐Œ). By Lemma 2 and by (5) we have


for 0โ‰คjโ‰คJ, and


Thus, ฮจ0(1),โ€ฆ,ฮจJ(1), and ฮฆJ(1) are all self-adjoint on ๐‹2โข(G,๐Œ) and are diagonalized in the same basis. Therefore, lower and upper the frame bounds of ๐’ฒ(1) are given by computing


where Qโข(t)โ‰”โˆ‘j=0J+1qjโข(t)2. The proof follows from recalling that by (6), we have that Qโข(t)=1 uniformly on 0โ‰คtโ‰ค1, and therefore, ๐’ฒ(1) is an isometry. โˆŽ

Proposition 2.

๐’ฒJ(2) is a nonexpansive frame analysis operator from L2โข(G,M) to โ„“2โข(L2โข(G,M)). That is, there exists a constant CJ>0 which depends only on J, such that for all xโˆˆL2โข(G,M),


We note in particular, that CJ does not depend on M or on the eignenvalues of T.

Remark 1.

If we restrict attention to x such that โŸจx,u0โŸฉ=0, then we may use an argument similar to Proposition 4.1 of [8] to get a lower frame bounds for W(2) which does not depend on J, but does depend on the ฮป1.


By the same reasoning as in the proof of Proposition 1, the frame bounds of ๐’ฒ(2) are given by computing


where Pโข(t)=โˆ‘j=0J+1pjโข(t)2. Since 0โ‰คฮปiโ‰ค1 for all i, we have


with the middle inequality following from the fact that pjโข(t)โ‰ฅ0 for all tโˆˆ[0,1], and the last equality following from (6). For the lower bound, we note that



3 The Scattering Transform

In this section, we will construct the scattering transform as a multilayered architecture built off of a frame ๐’ฒ such as the wavelet transforms ๐’ฒJ(1) and ๐’ฒJ(2) introduced in Section 2. We shall see the scattering transform constructed is a continuous operator on ๐‹2โข(G,๐Œ) whenever ๐’ฒ is nonexpansive. We shall also see that it has desirable conservation of energy bounds when ๐’ฒ=๐’ฒ(1) due to the fact that ๐’ฒ(1) is an isometry. On the other hand, we shall see in the following section that the scattering transform has much stronger stability guarantees when ๐’ฒ=๐’ฒJ(2).

3.1 Definitions

Let G=(V,E,W) be a connected weighted graph with |V|=n, let ๐Œ be an invertible matrix, and let ๐’ฅ be some indexing set. Assume that


is a frame on ๐‹2โข(G,๐Œ) such that

Aโขโˆฅ๐ฑโˆฅ๐Œ2โ‰คโˆฅ๐’ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2โ‰”โˆ‘jโˆˆ๐’ฅโˆฅฮจjโข๐ฑโˆฅ๐Œ2+โˆฅฮฆโข๐ฑโˆฅ๐Œ2โ‰คBโขโˆฅ๐ฑโˆฅ๐Œ2, (7)

for some 0<A<B<โˆž. In this paper, we are primarily interested in the case where ๐’ฅ={0,โ€ฆ,J} and ๐’ฒ is either ๐’ฒJ(1) or ๐’ฒJ(2). Therefore, we will think of the matrices ฮจj as wavelets, and ฮฆ as a low-pass filter. However, we will define the scattering transform for generic frames in order to highlight the relationship between properties of the scattering transform and of the underlying frame.

Letting M:๐‹2โข(G,๐Œ)โ†’๐‹2โข(G,๐Œ) be the pointwise modulus function Mโข๐ฑ=(|๐ฑโข(0)|,โ€ฆ,|๐ฑโข(n-1)|), we define ๐”:๐‹2โข(G,๐Œ)โ†’โ„“2โข(๐‹2โข(G,๐Œ)) by


Here, ๐’ฅm is the m-fold Cartesian product of ๐’ฅ with itself, the ๐”โข[๐ฃ]โข๐ฑ are defined by


for mโ‰ฅ1, and we declare that ๐”โข[๐ฃ๐ž]โข๐ฑ=๐ฑ when m=0 and ๐ฃ๐ž is the โ€œempty index.โ€ We then define the windowed and non-windowed scattering transforms, ๐’:๐‹2โข(G,๐Œ)โ†’โ„“2โข(๐‹2โข(G,๐Œ)) and ๐’ยฏ:๐‹2โข(G,๐Œ)โ†’โ„“2 by


where the scattering coefficients ๐’โข[๐ฃ] and ๐’ยฏโข[๐ฃ] are defined by


for some weighting vector ๐โˆˆ๐‹2โข(G,๐Œ). One natural choice is ๐=(๐ŒTโข๐Œ)-1โข๐Ÿ, where ๐Ÿ is the vector of all ones. In this case, one may verify that ๐’ยฏโข[๐ฃ]โข๐ฑ=โˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ1, and we recover a setup similar to [9]. Another natural choice is ๐=๐ฎ0, in which case we recover a setup similar to [8] if we set ๐Œ=๐ˆ.

In practice, one only uses finitely many scattering coefficients. This motivates us to consider the partial scattering transforms defined for 0โ‰คโ„“โ‰คLโ‰คโˆž by




3.2 Continuity and Conservation of Energy Properties

The following theorem shows that the windowed scattering transform ๐’ is nonexpansive and the non-windowed scattering transform ๐’ยฏ is Lipschitz continuous when ๐’ฒ is either ๐’ฒJ(1) or ๐’ฒJ(2) or, more generally, whenever ๐’ฒ is nonexpansive.

Theorem 1.

If Bโ‰ค1 in (7), then the windowed scattering transform S is a nonexpansive operator from L2โข(G,M) to โ„“2โข(L2โข(G,M)), and the non-windowed scattering transform Sยฏ is a Lipschitz continuous operator from L2โข(G,M) to โ„“2. Specifically, for all x,yโˆˆL2โข(G,M),

โˆฅ๐’๐ฑ-๐’๐ฒโˆฅโ„“2โข(๐‹2โข(G,๐Œ))โ‰คโˆฅ๐ฑ-๐ฒโˆฅ๐Œ, (8)


โˆฅ๐’ยฏโข๐ฑ-๐’ยฏโข๐ฒโˆฅโ„“2โ‰คโˆฅ๐โˆฅ๐Œโขโˆฅ๐šฝ-1โˆฅ๐Œโขโˆฅ๐ฑ-๐ฒโˆฅ๐Œ. (9)

The proof of (8) is very similar to analogous results in e.g., [11] and [17]. The proof of (9) uses the relationship ๐”๐ฑ=ฮฆ-1โข๐’โขx to show


Full details are provided in Appendix B.

The next theorem shows that if ๐’ฒ is either of the wavelet transforms constructed in Section 2, then ๐” experiences rapid energy decay. Our arguments use ideas similar to the proof of Proposition 3.3 of [17], with minor modifications to account for the fact that our wavelet constructions are different. Please see Appendix C for a complete proof.

Theorem 2.

Let Jโ‰ฅ0, let Jโ‰”{0,โ€ฆ,J}, and let W={ฮจj,ฮฆ}jโˆˆJ be either of the wavelet transforms, WJ(1) or WJ(2), constructed in Section 2. Then for all xโˆˆL2โข(G,M) and all mโ‰ฅ1

โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2โ‰ค(1-๐minโˆฅ๐โˆฅ1)โขโˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2. (10)

Therefore, for all mโ‰ฅ0,

โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2โ‰ค(1-๐minโˆฅ๐โˆฅ1)mโขโˆฅ๐ฑโˆฅ๐Œ2. (11)

The next theorem shows that if ๐’ฒ=๐’ฒJ(1), then the windowed graph scattering transform conserves energy on ๐‹2โข(G,๐Œ). Its proof, which relies on Proposition 1, Theorem 2, and Lemma 5, is nearly identical to the proof of Theorem 3.1 in [17]. We give a proof in Appendix D for the sake of completeness.

Theorem 3.

Let Jโ‰ฅ0, let Jโ‰”{0,โ€ฆ,J}, and let W=WJ(1). Then the non-windowed scattering transform is energy preserving, i.e., for all xโˆˆL2โข(G,M),


3.3 Permutation Invariance and Equivariance

In this section, we will show that both ๐” and the windowed graph scattering transform are permutation equivariant. As a consequence, we will be able to show that the non-windowed scattering transform is permutation invariant and that under certain assumptions the windowed-scattering transform is permutation invariant up to a factor depending on the scale of the low-pass filter.

Let Sn denote the permutation group on n elements, and, for ฮ โˆˆSn, let Gโ€ฒ=ฮ โข(G) be the graph obtained by permuting the vertices of G. We define ๐Œโ€ฒ, which we view as the analog of ๐Œ associated to Gโ€ฒ, by

๐Œโ€ฒ=ฮ โข๐Œโขฮ T.

To motivate this definition, we note that if ๐Œ is the identity, then ๐Œโ€ฒ is also the identity, and if ๐Œ=๐ƒ1/2, the square-root degree matrix, then the square-root degree matrix on Gโ€ฒ is given by

ฮ โข๐ƒ1/2โขฮ T,

with a similar formula holding when ๐Œ=๐ƒ-1/2. We define ๐’ฒโ€ฒ and ๐โ€ฒ, to be the frame and the weighting vector on Gโ€ฒ, corresponding to ๐’ฒ and ๐, by

๐’ฒโ€ฒโ‰”ฮ โข๐’ฒโขฮ Tโ‰”{ฮ โขฮจjโขฮ T,ฮ โขฮฆโขฮ T}jโˆˆ๐’ฅโ€ƒandโ€ƒ๐โ€ฒ=ฮ โข๐, (12)

and we let ๐’โ€ฒ and ๐’ยฏโ€ฒ denote the corresponding windowed and non-windowed scattering transforms on Gโ€ฒ.

To understand ๐’ฒโ€ฒ, we note that the natural analog of ๐“ on Gโ€ฒ is given by

๐“โ€ฒ=ฮ โข๐“โขฮ T.

Therefore, Lemma 2 implies that for any for any polynomial p,

pโข((๐Œโ€ฒ)-1โข๐“๐Œโ€ฒ) =(๐Œโ€ฒ)-1โขpโข(๐“โ€ฒ)โข๐Œโ€ฒ
=(ฮ โข๐Œโขฮ T)-1โขpโข(ฮ โข๐“โขฮ T)โข(ฮ โข๐Œโขฮ T)
=(ฮ โข๐Œ-1โขฮ T)โขฮ โขpโข(๐“)โขฮ Tโข(ฮ โข๐Œโขฮ T)
=ฮ โข๐Œ-1โขpโข(๐“)โข๐Œโขฮ T
=ฮ โขpโข(๐Œ-1โข๐“๐Œ)โขฮ T.

with a similar formula holding qโ‰”p1/2. Therefore, if ๐’ฒ is either of the wavelet transforms ๐’ฒJ(1) or ๐’ฒJ(2), then ๐’ฒโ€ฒ is analogous wavelet transform constructed from ๐Šโ€ฒโ‰”(๐Œโ€ฒ)-1โข๐“โ€ฒโข๐Œโ€ฒ.

Theorem 4.

Both U and the windowed scattering transform S are equivariant to permutations. That is, if ฮ โˆˆSn is any permutation and Wโ€ฒ is defined as in (12), then for all xโˆˆL2โข(G,M)

๐”โ€ฒโขฮ โข๐ฑ=ฮ โข๐”๐ฑโ€ƒ๐‘Ž๐‘›๐‘‘โ€ƒ๐’โ€ฒโขฮ โข๐ฑ=ฮ โข๐’๐ฑ.

Let ฮ  be a permutation. Since ฮ โข(Mโข๐ฑ)=Mโข(ฮ โข๐ฑ) and ฮ T=ฮ -1, it follows that for all jโˆˆ๐’ฅ

๐”โ€ฒโข[j]โขฮ โข๐ฑ=Mโขฮจjโ€ฒโขฮ โข๐ฑ=Mโขฮ โขฮจjโขฮ Tโขฮ โข๐ฑ=Mโขฮ โขฮจjโข๐ฑ=ฮ โขMโขฮจjโข๐ฑ=ฮ โข๐”โข[j]โข๐ฑ.

For ๐ฃ=(j1,โ€ฆ,jm), we have ๐”โข[๐ฃ]=๐”โข[j1]โขโ€ฆโข๐”โข[jm]. Therefore, it follows inductively that ๐” is equivariant to permutations. Since ๐’=ฮฆโข๐”, we have that

๐’โ€ฒโขฮ โข๐ฑ=ฮฆโ€ฒโข๐”โ€ฒโขฮ โข๐ฑ=ฮ โขฮฆโขฮ Tโขฮ โข๐”๐ฑ=ฮ โข๐’๐ฑ.

Thus, the windowed scattering transform is permutation equivariant as well. โˆŽ

Theorem 5.

The non-windowed scattering transform Sยฏ is fully permutation invariant, i.e., for all permutations ฮ  and all xโˆˆL2โข(G,M)

๐’ยฏโ€ฒโขฮ โข๐ฑ=๐’ยฏโข๐ฑ.

Since ๐” is permutation equivariant by Theorem 4 and ๐โ€ฒ=ฮ โข๐, we may use the fact that ๐Œโ€ฒ=ฮ โข๐Œโขฮ T and that ฮ T=ฮ -1 to see that for any ๐ฑ and any ๐ฃ,

๐’ยฏโ€ฒโข[๐ฃ]โขฮ โข๐ฑ=โŸจ๐โ€ฒ,๐”โ€ฒโข[๐ฃ]โขฮ โข๐ฑโŸฉ๐Œโ€ฒ=โŸจ๐Œโ€ฒโขฮ โข๐,๐Œโ€ฒโขฮ โข๐”โข[๐ฃ]โข๐ฑโŸฉ2=โŸจฮ โข๐Œโข๐,ฮ โข๐Œ๐”โข[๐ฃ]โข๐ฑโŸฉ2=โŸจ๐Œโข๐,๐Œ๐”โข[๐ฃ]โข๐ฑโŸฉ2=๐’ยฏโข[๐ฃ]โข๐ฑ.


Next, we will use Theorem 4 to show that if ๐’ฒ is either ๐’ฒJ(1) or ๐’ฒJ(2) and ๐Œ=๐ƒ1/2, then the windowed scattering transform is invariant on ๐‹2โข(G,๐Œ) up to a factor depending on the scale of the low-pass filter. We note that 0<ฮป1<1. Therefore, ฮป1t decays exponentially fast as tโ†’โˆž, and so if J is large, the right hand side of (13) will be nearly zero. We also recall that if our spectral function is given by gโข(t)=gโ‹†โข(t) then this choice of ๐Œ will imply that ๐Š=๐T.

Theorem 6.

Let M=D1/2, and let W be either WJ(1) or WJ(2). Then the windowed-scattering transform is permutation invariant up to a factor depending on J. Specifically, for all ฮ โˆˆSn and for all xโˆˆL2โข(G,M),

โˆฅ๐’โ€ฒโขฮ โข๐ฑ-๐’๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))โ‰คฮป1tโขโˆฅฮ -๐ˆโˆฅ๐Œโข(1+nโขโˆฅ๐โˆฅโˆž๐min)1/2โขโˆฅ๐ฑโˆฅ๐Œ, (13)

where t=2J-1 if W=W(1) and t=2J if W=W(2).


By Theorem 4, and the fact that ๐’=ฮฆโข๐” we see that

โˆฅ๐’โ€ฒโขฮ โข๐ฑ-๐’๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ)) =โˆฅฮ โข๐’๐ฑ-๐’๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))
=โˆฅฮ โขฮฆโข๐”๐ฑ-ฮฆโข๐”๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))
โ‰คโˆฅฮ โขฮฆ-ฮฆโˆฅ๐Œโขโˆฅ๐”๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ)). (14)

Let t=2J-1 if ๐’ฒ=๐’ฒ(1), and let t=2J if ๐’ฒ=๐’ฒ(2) so that in either case ฮฆ=๐“t. Let ๐ฑโˆˆ๐‹2โข(G,๐Œ), (3) implies that for any ๐ฒโˆˆ๐‹2โข(G,๐Œ)


Therefore, by Lemma 2 and the relationship ๐ฎi=๐Œ-1โข๐ฏi, we have


Since ๐ฏ0=๐1/2โˆฅ๐1/2โˆฅ2, and ๐ฎi=๐Œ-1โข๐ฏi, the assumption that ๐Œ=๐ƒ1/2 implies that ๐ฎ0=1โˆฅ๐1/2โˆฅ2โข๐Ÿ. Therefore, ฮ โข๐ฎ0=๐ฎ0, and so

ฮ โข๐Štโข๐ฑ-๐Štโข๐ฑ=โˆ‘i=0n-1ฮปitโขโŸจ๐ฏi,๐Œ๐ฑโŸฉ2โข(ฮ โข๐ฎi-๐ฎi)=โˆ‘i=1n-1ฮปitโขโŸจ๐ฏi,๐Œ๐ฑโŸฉ2โข(ฮ โข๐ฎi-๐ฎi)=(ฮ -๐ˆ)โข(โˆ‘i=1n-1ฮปitโขโŸจ๐ฏi,๐Œ๐ฑโŸฉ2โข๐ฎi).

Therefore, since {๐ฎ0,โ€ฆ,๐ฎn-1} forms an orthonormal basis for ๐‹2โข(G,๐Œ), we have that by Parsevalโ€™s identity

โˆฅฮ โข๐Štโข๐ฑ-๐Štโข๐ฑโˆฅ๐Œ2 โ‰คโˆฅฮ -๐ˆโˆฅ๐Œ2โขโˆฅโˆ‘i=1n-1ฮปitโขโŸจ๐ฏi,๐Œ๐ฑโŸฉ2โข๐ฎiโˆฅ๐Œ
=โˆฅฮ -๐ˆโˆฅ๐Œ2โขโˆ‘i=1n-1ฮปi2โขtโข|โŸจ๐ฏi,๐Œ๐ฑโŸฉ2|2
โ‰คโˆฅฮ -๐ˆโˆฅ๐Œ2โขฮป12โขtโขโˆ‘i=1n-1|โŸจ๐ฏi,๐Œ๐ฑโŸฉ2|2
โ‰คโˆฅฮ -๐ˆโˆฅ๐Œ2โขฮป12โขtโขโˆฅ๐Œ๐ฑโˆฅ22
=โˆฅฮ -๐ˆโˆฅ๐Œ2โขฮป12โขtโขโˆฅ๐ฑโˆฅ๐Œ2. (15)

To bound โˆฅ๐”๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ)), we note that by Theorem 2,

โˆฅ๐”๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2 =โˆฅ๐ฑโˆฅ๐Œ2+(โˆ‘m=1โˆžโˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2)

where the last inequality uses the fact that the modulus operator is nonexpansive and that Bโ‰ค1 in (7). Combining this with (14) and (15) completes the proof.


4 Stability to Graph Perturbations

Let G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) be weighted graphs with |V|=|Vโ€ฒ|=n, and let ๐Œ and ๐Œโ€ฒ be invertible matrices. Throughout this section, for any object X associated to G, we will let Xโ€ฒ denote the analogous object on Gโ€ฒ, so e.g., ๐ƒโ€ฒ is the degree matrix of Gโ€ฒ. Recall that two important examples of our asymmetric matrix ๐Š are when gโข(t)=gโ‹†โข(t)=1-t2 and ๐Œ=๐ƒยฑ1/2, in which case ๐Š is either the lazy random walk matrix ๐ or its transpose ๐T. In these cases, the matrix ๐Œ encodes important geometric information about G, which motivates us to let


and consider the quantity


as a measure of how poorly aligned the degree vectors of G and Gโ€ฒ are. In the general case, ฮบโข(G,Gโ€ฒ) measures how different the โˆฅโ‹…โˆฅ๐Œ and โˆฅโ‹…โˆฅ๐Œโ€ฒ norms are. It will also be useful to consider


We note that by construction we have 1โ‰คRโข(G,G)โ‰คฮบโข(G,Gโ€ฒ)+1. Thus, if the norms โˆฅโ‹…โˆฅ๐Œ and โˆฅโ‹…โˆฅ๐Œโ€ฒ are well-aligned, we will have ฮบโข(G,Gโ€ฒ)โ‰ˆ0 and consequently Rโข(G,Gโ€ฒ)โ‰ˆ1. We note that we will have ฮบโข(G,Gโ€ฒ)=0 and Rโข(G,Gโ€ฒ)=1, if either ๐Œ=๐ˆ (so that ๐Š=๐“) or if ๐Œ=๐ƒยฑ1/2 and the graphs G and Gโ€ฒ have the same degree vector. The latter situation occurs if e.g. G is a regular graph and Gโ€ฒ is obtained by permuting the vertices of G. We also note that if ๐Œ is diagonal, e.g. if ๐Œ=๐ƒยฑ1/2, then ๐‘1=๐‘2.

We may also measure how far apart two graphs are via their spectral properties. In particular, if we let ๐• be the unitary matrix whose i-th column is given by ๐ฏi, an eigenvector or ๐“ with eigenvalue ฮปi, we see that two natural quantificationโ€™s of how poorly aligned the spectral properties of G and Gโ€ฒ are given by


Motivated by e.g., [8], we also consider the โ€œdiffusion distancesโ€ given by


4.1 Stability of the Wavelet Transforms

In this section, we analyze the stability of the wavelet transforms ๐’ฒJ(1) and ๐’ฒJ(2) constructed in Section 2. Our first two results provide a stability bounds for ๐’ฒJ(1) and ๐’ฒJ(2) in the case where ๐Š=๐“. These results will be extended to the general case by Theorem 9.

Theorem 7.

Suppose G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two graphs such that |V|=|Vโ€ฒ|=n, and let ฮป1*=maxโก{ฮป1,ฮป1โ€ฒ}. Let M=I so that K=T, let W be the wavelets W(1) constructed from T in Section 2, and let Wโ€ฒ be the corresponding wavelets constructed from Tโ€ฒ. Then there exists a constant Cฮป1*, depending only on ฮป1* such that


where as in (2)


By (5) and the fact that qjโข(t)=pjโข(t)1/2, we have that for all 0โ‰คjโ‰คJ+1,

qjโข(๐“)-qjโข(๐“โ€ฒ) =๐•โขqjโข(ฮ›)โข๐•T-๐•โ€ฒโขqjโข(ฮ›โ€ฒ)โข(๐•โ€ฒ)T

Therefore, since ๐• and ๐•โ€ฒ are unitary, we have that for all ๐ฑโˆˆ๐‹2โข(G)


and so summing over J yields


For any sequence of diagonal matrices ๐0,โ€ฆ,๐J+1 one has that for any ๐ฒโˆˆ๐‹2โข(G)


Therefore, by (6),




Now, since โˆฅ๐ฑโˆฅ2=1 and ฮป0=ฮป0โ€ฒ=1,

โˆ‘j=0J+1โˆฅ(qjโข(ฮ›)-qjโข(ฮ›โ€ฒ))โข๐ฑโˆฅ22 โ‰คsup0โ‰คiโ‰คn-1โกโˆ‘j=0J+1|qjโข(ฮปi)-qjโข(ฮปiโ€ฒ)|22

When j=0, we have

|q0โ€ฒโข(t)|=|ddโขtโข1-t|=12โข11-tโ‰คCฮป1*โ€ƒfor allย โข0โ‰คtโ‰คฮป1*.

Likewise, for j=J+1, we have

|qJ+1โ€ฒโข(t)|=|ddโขtโขt2J-1|โ‰ค2J-1โ€ƒfor allย โข0โ‰คtโ‰คฮป1*.

For 1โ‰คjโ‰คJ, we may write qjโข(t)=q1โข(ujโข(t)), where ujโข(t)=t2j-1, and use the fact that |ujโข(t)|โ‰ค1 for all 0โ‰คtโ‰ค1 to compute

|qjโ€ฒโข(t)| =|q1โ€ฒโข(ujโข(t))โขujโ€ฒโข(t)|

for all 0โ‰คtโ‰คฮป1*. Therefore,



Our next result provides stability bounds for ๐’ฒJ(2) in the case where ๐Œ=๐ˆ (i.e. when ๐Š=๐“). We note that while ๐’ฒ(1) has the advantage of being a tight frame, ๐’ฒ(2) has stronger stability guarantees, which in particular are independent of J. Our proof, which is closely modeled after the proofs of Lemmas 5.1 and 5.2 in [8], is given in Appendix E. Due to a small improvement in the derivation, our result appears in a slightly different form than the result stated there.

Theorem 8.

Suppose G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two graphs such that |V|=|Vโ€ฒ|=n, and let ฮป1*=maxโก{ฮป1,ฮป1โ€ฒ}. Let M=I so that K=T, let W be the wavelets W(2) constructed from T in Section 2, and let Wโ€ฒ be the corresponding wavelets constructed from Tโ€ฒ. Then


Theorems 7 and 8 show that the wavelets ๐’ฒ(1) and ๐’ฒ(2) are stable on ๐‹2โข(G) in the special case that ๐Œ=๐ˆ. Our next theorem extends this analysis to general ๐Œ. More generally, it can be applied to any situation where {riโข(๐“)}iโˆˆโ„ and {riโข(๐“โ€ฒ)}iโˆˆโ„ form frames on ๐‹2โข(G) and ๐‹2โข(Gโ€ฒ), โ„ is some indexing set, and each of the ri are polynomials or square roots of polynomials.

Theorem 9.

Suppose G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two graphs such that |V|=|Vโ€ฒ|=n, and let M and Mโ€ฒ be invertible matrices. Let I be an indexing set, and for iโˆˆI, let riโข(โ‹…) be either a polynomial or the square root of a polynomial. Suppose that WT={riโข(T)}iโˆˆI forms a frame analysis operator on L2โข(G) and that WTโ€ฒ={riโข(Tโ€ฒ)}jโˆˆJ forms a frame analysis operator on L2โข(Gโ€ฒ), and assume Bโ‰ค1 in (7) for both WT and WTโ€ฒ. Let K=M-1โขTM and let WK and WKโ€ฒ be the frames defined by {riโข(K)}iโˆˆI and {riโข(Kโ€ฒ)}iโˆˆI. Then,


Let โˆฅ๐ฑโˆฅ๐Œ=1, and let ๐ฒ=๐Œ๐ฑ. Note that โˆฅ๐ฒโˆฅ2=โˆฅ๐Œ๐ฑโˆฅ2=โˆฅ๐ฑโˆฅ๐Œ=1. By Lemma 2 and by (5) we have that for all iโˆˆโ„



โˆฅ(riโข(๐Š)-riโข(๐Šโ€ฒ))โข๐ฑโˆฅ๐Œ =โˆฅ๐Œโข(๐Œ-1โขriโข(๐“)โข๐Œ-(๐Œโ€ฒ)-1โขriโข(๐“โ€ฒ)โข๐Œโ€ฒ)โข๐ฑโˆฅ2

Therefore, squaring both sides, summing over j, and using the nonexpansiveness of ๐’ฒ๐“ and the fact that โˆฅ๐ฒโˆฅ2=1, we have

โ‰ค 3โข(โˆ‘iโˆˆโ„โˆฅ(riโข(๐“)-riโข(๐“โ€ฒ))โข๐ฒโˆฅ22+ฮบโข(G,Gโ€ฒ)2โขโˆ‘iโˆˆโ„โˆฅriโข(๐“โ€ฒ)โข๐ฒโˆฅ22+Rโข(G,Gโ€ฒ)2โขโˆ‘iโˆˆโ„โˆฅriโข(๐“โ€ฒ)โข(๐ˆ-๐‘2)โข๐ฒโˆฅ22)
โ‰ค 3โข(โˆฅ๐’ฒ๐Š-๐’ฒ๐Šโ€ฒโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2+ฮบโข(G,Gโ€ฒ)2+Rโข(G,G)2โขโˆฅ(๐ˆ-๐‘2)โข๐ฒโˆฅ22)
โ‰ค 3โข(โˆฅ๐’ฒ๐Š-๐’ฒ๐Šโ€ฒโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2+ฮบโข(G,Gโ€ฒ)2+Rโข(G,G)2โขฮบโข(G,Gโ€ฒ)2)
โ‰ค 6โข(โˆฅ๐’ฒ๐Š-๐’ฒ๐Šโ€ฒโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2+ฮบโข(G,Gโ€ฒ)2โข(ฮบโข(G,Gโ€ฒ)+1)2)

where the last inequality uses the fact that Rโข(G,Gโ€ฒ)โ‰ค(ฮบโข(G,Gโ€ฒ)+1). โˆŽ

The following corollaries are immediate consequences of Theorem 9 and of Theorems 7 and 8.

Corollary 1.

Suppose G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two graphs such that |V|=|Vโ€ฒ|=n, let M and Mโ€ฒ be invertible matrices, and let ฮป1*=maxโก{ฮป1,ฮป1โ€ฒ}. Let Jโ‰ฅ0, let W be the wavelet transform W(1) constructed from K in Section 2, and let Wโ€ฒ be the corresponding wavelet transform constructed from Kโ€ฒ. Then,

โˆฅ๐’ฒ-๐’ฒโ€ฒโˆฅโ„“2โข(๐‹2โข(G))2 โ‰คCฮป1*โข(2Jโขsup1โ‰คiโ‰คn-1โก|ฮปi-ฮปiโ€ฒ|2+โˆฅ๐•-๐•โ€ฒโˆฅ22+ฮบโข(G,Gโ€ฒ)2โข(ฮบโข(G,Gโ€ฒ)+1)2).
Corollary 2.

Suppose G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two graphs such that |V|=|Vโ€ฒ|=n, let M and Mโ€ฒ be invertible matrices, and let ฮป1*=maxโก{ฮป1,ฮป1โ€ฒ}. Let Jโ‰ฅ0, let W be the wavelet transform WJ(2) constructed from K in Section 2 and let Wโ€ฒ be the corresponding wavelet transform constructed from Kโ€ฒ. Then,

โˆฅ๐’ฒ-๐’ฒโ€ฒโˆฅโ„“2โข(๐‹2โข(G))2 โ‰คCฮป1*โข(โˆฅ๐“-๐“โ€ฒโˆฅ22+โˆฅ๐“-๐“โ€ฒโˆฅ2+ฮบโข(G,Gโ€ฒ)2โข(ฮบโข(G,Gโ€ฒ)+1)2).

One might also wish to replace Corollaries 1 and 2 with inequalities written in terms of โˆฅ๐Š-๐Šโ€ฒโˆฅ๐Œ rather than โˆฅ๐“-๐“โ€ฒโˆฅ2. This can be done by the following proposition. Recall that we think of the two Hilbert spaces ๐‹2โข(G,๐Œ) and ๐‹2โข(G,๐Œโ€ฒ) as being well-aligned if ฮบโข(G,Gโ€ฒ)โ‰ˆ0 and Rโข(G,Gโ€ฒ)โ‰ˆ1. In this case, the right-hand side of (16) is approximately โˆฅ๐Š-๐Šโ€ฒโˆฅ๐Œ.

Proposition 3.
โˆฅ๐“-๐“โ€ฒโˆฅ2โ‰คฮบโข(G,Gโ€ฒ)โข(1+Rโข(G,Gโ€ฒ)3)+Rโข(G,G)โขโˆฅ๐Š-๐Šโ€ฒโˆฅ๐Œ. (16)

Let โˆฅ๐ฑโˆฅ2=1. Then, since ๐“=๐Œ๐Š๐Œ-1

โˆฅ(๐“-๐“โ€ฒ)โข๐ฑโˆฅ2 =โˆฅ๐Œ๐Š๐Œ-1โข๐ฑ-๐Œโ€ฒโข๐Šโ€ฒโข(๐Œโ€ฒ)-1โข๐ฑโˆฅ2
=โˆฅ๐Š-๐‘1-1โข๐Šโ€ฒโข๐‘1โˆฅ๐Œ, (17)

since โˆฅ๐Œ-1โข๐ฑโˆฅ๐Œ=โˆฅ๐ฑโˆฅ2=1. By the triangle inequality,

โˆฅ๐Š-๐‘1-1โข๐Šโ€ฒโข๐‘1โˆฅ๐Œ โ‰คโˆฅ๐Š-๐‘1-1โข๐Šโˆฅ๐Œ+โˆฅ๐‘1-1โข๐Š-๐‘1-1โข๐Šโ€ฒโข๐‘1โˆฅ๐Œ

where we used the facts that โˆฅ๐ˆ-๐‘1ยฑ1โˆฅ๐Œโ‰คฮบโข(G,Gโ€ฒ), โˆฅ๐‘1ยฑ1โˆฅโ‰คRโข(G,Gโ€ฒ), โˆฅ๐Šโˆฅ๐Œ=1, and โˆฅ๐Šโ€ฒโˆฅ๐Œโ‰คโˆฅ๐‘1โˆฅ2โขโˆฅ๐‘-1โˆฅ2โ‰คRโข(G,Gโ€ฒ)2. โˆŽ

Our next theorem shows that if G and Gโ€ฒ are well-aligned, then the upper frame bound for ๐’ฒ can be used to produce an upper frame bound for ๐’ฒโ€ฒ on ๐‹2โข(G,๐Œ). This result will play a key role in proving the stability of the scattering transform.

Theorem 10.

Suppose G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two graphs such that |V|=|Vโ€ฒ|=n, and let M and Mโ€ฒ be invertible nร—n matrices. Let Jโ‰”{0,โ€ฆ,J} for some Jโ‰ฅ0, let


be either of the wavelet transforms, W(1) or W(2), constructed in Section 2, and let Wโ€ฒ be the corresponding wavelet transform constructed from Kโ€ฒ. Then Wโ€ฒ is a bounded operator on L2โข(G,M) and


By Lemma 2, we have that if r is either a polynomial, or the square root of a polynomial, then


Therefore, again applying Lemma 2, we have

โˆฅrโข(๐Šโ€ฒ)โข๐ฑโˆฅ๐Œ =โˆฅ๐Œ((๐Œโ€ฒ)-1r(๐“โ€ฒ)๐Œโ€ฒ)(๐Œ-1๐Œ))๐ฑโˆฅ2

Since ฮฆJ and each of the ฮจj are either a polynomial in ๐Š or the square root of polynomial in ๐Šโ€ฒ, the proof follows by observing

โˆ‘jโˆˆ๐’ฅโˆฅฮจjโ€ฒโข๐ฑโˆฅ๐Œ2+โˆฅฮฆJโ€ฒโข๐ฑโˆฅ๐Œ2 โ‰คRโข(G,G)4โข(โˆ‘jโˆˆ๐’ฅโˆฅฮจjโข๐ฑโˆฅ๐Œ2+โˆฅฮฆJโข๐ฑโˆฅ๐Œ2)

with the last inequality following from the fact that B=1 in (7) by Propositions 1 and 2.โˆŽ

4.2 Stability of the Scattering Transform

In this section, we will prove a stability result for the scattering transform. We will state and prove our result in a great degree of generality in order both to emphasize that the stability of the scattering transform is a consequence of the stability of the underlying frame and so that our result can be applied to other graph wavelet constructions. Towards this end, we will assume that G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) are two-weighted graphs such that |V|=|Vโ€ฒ|=n, let ๐Œ and ๐Œโ€ฒ be nร—n invertible matrices, and assume that ๐’ฒ={ฮจj,ฮฆ}jโˆˆ๐’ฅ and ๐’ฒโ€ฒ={ฮจjโ€ฒ,ฮฆโ€ฒ}jโˆˆ๐’ฅ are frames on ๐‹2โข(G,๐Œ) and ๐‹2โข(Gโ€ฒ,๐Œโ€ฒ) such that Bโ‰ค1 in (7). If ฮ  is a permutation, we will let ๐’ฒโ€ฒโ€ฒโ‰”ฮ โข๐’ฒโ€ฒโขฮ T={ฮ โขฮจjโ€ฒโขฮ T,ฮ โขฮฆโ€ฒโขฮ T}jโˆˆ๐’ฅ denote the corresponding permuted wavelet frame on Gโ€ฒโ€ฒโ‰”ฮ โขGโ€ฒ.

Our stability bound for the scattering transform will depend on choosing the optimal permutation ฮ  such that ๐’ฒโ€ฒโ€ฒ=ฮ โข๐’ฒโ€ฒโขฮ T is well-aligned with ๐’ฒ and has an upper frame bound on ๐‹2โข(G,๐Œ) that is not too large. For ฮ โˆˆSn, we let

๐’œฮ โข(G,Gโ€ฒ)โ‰”supโˆฅ๐ฑโˆฅ๐Œ=1โกโˆฅ๐’ฒโข๐ฑ-ฮ โข๐’ฒโ€ฒโขฮ Tโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2


๐’žฮ โข(G,Gโ€ฒ)โ‰”supโˆฅ๐ฑโˆฅ๐Œ=1โกโˆฅฮ โข๐’ฒโ€ฒโขฮ Tโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2.

We will also let ๐’œโข(G,Gโ€ฒ)=๐’œ๐ˆโข(G,Gโ€ฒ) and ๐’žโข(G,Gโ€ฒ)=๐’ž๐ˆโข(G,Gโ€ฒ) when ฮ  is the indentity.

Theorem 11 provides stability guarantees for the windowed and non-windowed scattering transform with bounds that are functions of ๐’œโข(G,Gโ€ฒ) and ๐’žโข(G,Gโ€ฒ). Corollary 3 uses the permutation invariance results of Theorems 5 and 6 to extend these results by infimizing the same functions over all permutations. Since the non-windowed scattering transform is always fully permutation invariant, this corollary will always apply to it. By Theorem 5, it will apply to the windowed scattering transform when ๐Œ=๐ƒ1/2 (or any other case in which the windowed scattering transform has provable invariance guarantees). These results imply, by Theorems 7, 8, 9, and 10, that the scattering transforms constructed from ๐’ฒJ(1) or ๐’ฒJ(2) are stable in the sense that the spectral properties of G are similar to the spectral properties of Gโ€ฒ and the โˆฅโ‹…โˆฅM and โˆฅโ‹…โˆฅ๐Œโ€ฒ norms are well-aligned, then the scattering transforms ๐’ and ๐’โ€ฒ will produce similar representations of an inputted signal ๐ฑ. Many of the ideas in the proof of Theorem 11 are similar to those used to prove Theorem 5.3 in [8]. The primary difference is Lemma 4 which is needed because ๐’ฒโ€ฒ is a non-expansive frame on ๐‹2โข(G,๐Œโ€ฒ), but not in general a non-expansive frame on ๐‹2โข(G,๐Œ).

Theorem 11.

Let G=(V,E,W) and Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ,Wโ€ฒ) be two graphs such that |V|=|Vโ€ฒ|=n, let M and Mโ€ฒ be invertible nร—n matrices, and let J be an indexing set. Let W={ฮจj,ฮฆ}jโˆˆJ and be Wโ€ฒ={ฮจjโ€ฒ,ฮฆโ€ฒ}jโˆˆJ be frames on L2โข(G,M) and L2โข(Gโ€ฒ,Mโ€ฒ), such that Bโ‰ค1 in (7), and let ๐› and ๐›โ€ฒ be weighting vectors on L2โข(G,M), and L2โข(Gโ€ฒ,Mโ€ฒ). Let Sโ„“(L), (Sโ„“(L))โ€ฒ, Sยฏโ„“(L), and (Sยฏโ„“(L))โ€ฒ be the partial windowed and non-windowed scattering transforms on G and Gโ€ฒ with coefficients from layers โ„“โ‰คmโ‰คL. Then, for all xโˆˆL2โข(G,M)

โˆฅ๐’โ„“(L)โข๐ฑ-(๐’โ„“(L))โ€ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))โ‰ค2โข๐’œโข(G,Gโ€ฒ)โข(โˆ‘m=โ„“Lโˆ‘k=0m๐’žฮ โข(G,Gโ€ฒ)k/2)โขโˆฅ๐ฑโˆฅ๐Œ, (19)


โˆฅ๐’ยฏโ„“(L)โข๐ฑ-(๐’ยฏโ„“(L))โ€ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))โ‰ค2โข((L-โ„“)โขโˆฅ๐-๐โ€ฒโˆฅ๐Œ+โˆฅ๐โ€ฒโˆฅ๐Œโข๐’œโข(G,Gโ€ฒ)โ‹…โˆ‘m=โ„“Lโˆ‘k=0m-1๐’žk/2โข(G,Gโ€ฒ))โขโˆฅ๐ฑโˆฅ๐Œ. (20)
Corollary 3.

Under the assumptions of Theorem 11, the non-windowed scattering transform satisfies

โ‰ค 2โขinfฮ โˆˆSnโก((L-โ„“)โขโˆฅ๐-๐โ€ฒโˆฅ๐Œ+โˆฅ๐โ€ฒโˆฅ๐Œโข๐’œฮ โข(G,Gโ€ฒ)โ‹…โˆ‘m=โ„“Lโˆ‘k=0m-1๐’žฮ โข(G,Gโ€ฒ)k/2)โขโˆฅ๐ฑโˆฅ๐Œ. (21)

Moreover, if we further assume that the windowed scattering transform (Sโ„“(L))โ€ฒ is permutation invariant up to a factor of B in the sense that for all ฮ โˆˆSn and for all xโˆˆL2โข(G,M),

โˆฅ(๐’โ„“(L))โ€ฒโ€ฒโขฮ โข๐ฑ-(๐’โ„“(L)โข๐ฑ)โ€ฒโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2โ‰คโ„ฌโขโˆฅ๐ฑโˆฅ๐Œ2, (22)


โˆฅ๐’โ„“(L)โข๐ฑ-(๐’โ„“(L))โ€ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐))โ‰ค(โ„ฌ+infฮ โˆˆSnโก2โข๐’œฮ โข(G,Gโ€ฒ)โขโˆ‘m=โ„“Lโˆ‘k=0m๐’žฮ โข(G,Gโ€ฒ)k/2)โขโˆฅ๐ฑโˆฅ๐Œ. (23)
The Proof of Theorem 11.

Let ๐’œโ‰”๐’œโข(G,Gโ€ฒ) and ๐’žโ‰”๐’žโข(G,Gโ€ฒ). By the triangle inequality,

โˆฅ๐’โ„“(L)โข๐ฑ-(๐’โ„“(L))โ€ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ)) =(โˆ‘m=โ„“Lโˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’โข[๐ฃ]โข๐ฑ-๐’โ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ2)1/2

Therefore, to prove (19) it suffices to show

โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’โข[๐ฃ]โข๐ฑ-๐’โ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ2โ‰ค2โข๐’œโ‹…(โˆ‘k=0m๐’žk/2)2โขโˆฅ๐ฑโˆฅ๐Œ2 (24)

for all 0โ‰คmโ‰คL. Similarly, to prove (20), it suffices to show

โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’ยฏโข[๐ฃ]โข๐ฑ-๐’ยฏโ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ2โ‰ค2โขโˆฅ๐-๐โ€ฒโˆฅ๐Œ2โขโˆฅ๐ฑโˆฅ๐Œ2+2โขโˆฅ๐โ€ฒโˆฅ๐Œ2โข๐’œโ‹…(โˆ‘k=0m-1๐’žk/2)2โขโˆฅ๐ฑโˆฅ๐Œ2 (25)

for all 0โ‰คmโ‰คL, and then use the inequality a2+b2โ‰ค|a|+|b|.

Since the zeroth-order windowed scattering coefficient of ๐ฑ is given by


where ๐ฃe is the empty-index, we see that by the definition of ๐’œ we have


Therefore, (24) holds when m=0. Similarly, since ๐’ยฏโข[๐ฃ๐ž]โข๐ฑ=โŸจ๐,๐ฑโŸฉ๐Œ, we see that (25) holds when m=0. The case where 1โ‰คmโ‰คL relies on the following two lemmas. They iteratively apply the assumption that Bโ‰ค1 in (7) and use the definitions of ๐’œ and ๐’ž to bound {๐”โข[๐ฃ]โข๐ฑ}๐ฃโˆˆ๐’ฅm and (โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑ-๐”โ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ2)1/2. Full details are provided in Appendix F.

Lemma 3.

For all mโ‰ฅ1,

Lemma 4.

For all mโ‰ฅ1,


For ๐ฃโˆˆ๐’ฅm, the triangle inequality implies that,

โˆฅ๐’โข[๐ฃ]โข๐ฑ-๐’โ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ =โˆฅฮฆโขMโขฮจjmโขโ€ฆโขMโขฮจj1โข๐ฑ-ฮฆโ€ฒโขMโขฮจjmโ€ฒโขโ€ฆโขMโขฮจj1โ€ฒโข๐ฑโˆฅ๐Œ

Therefore, by Lemmas 3 and 4

โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’โข[๐ฃ]โข๐ฑ-๐’โ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ2 โ‰ค2โขโˆฅ(ฮฆ-ฮฆโ€ฒ)โˆฅ๐Œ2โขโˆ‘๐ฃโˆˆ๐’ฅmโˆฅMโขฮจjmโขโ€ฆโขMโขฮจj1โˆฅ๐Œ2

which completes the proof of (24) and therefore of (19). Similarly, by the Cauchy-Schwarz inequality

|๐’ยฏโข[๐ฃ]โข๐ฑ-๐’ยฏโ€ฒโข[๐ฃ]โข๐ฑ| =|๐โขMโขฮจjmโขโ€ฆโขMโขฮจj1โข๐ฑ-๐โ€ฒโขMโขฮจjmโ€ฒโขโ€ฆโขMโขฮจj1โ€ฒโข๐ฑ|

Squaring both sides and summing over ๐ฃ implies (25) and therefore (20). โˆŽ

The Proof of Corollary 3.

Choose ฮ 0โˆˆSn such that

2โข๐’œฮ 0โข(G,Gโ€ฒ)โขโˆ‘m=0Mโˆ‘k=0m๐’žฮ 0โข(G,Gโ€ฒ)k/2=infฮ โˆˆSnโก2โข๐’œฮ โข(G,Gโ€ฒ)โขโˆ‘m=0Mโˆ‘k=0m๐’žฮ โข(G,Gโ€ฒ)k/2.

Let Gโ€ฒโ€ฒ=ฮ 0โขGโ€ฒ, and let ๐’โ€ฒโ€ฒ be the scattering transform on Gโ€ฒโ€ฒ constructed from the wavelets ๐’ฒโ€ฒโ€ฒโ‰”ฮ 0โข๐’ฒโ€ฒโขฮ 0T. Then under the assumption (22), we see

โˆฅ๐’โ„“(L)โข๐ฑ-(๐’โ„“(L))โ€ฒโข๐ฑโˆฅโ„“2โข(๐‹โข(G,๐Œ))2 โ‰คโˆฅ๐’โ„“(L)โข๐ฑ-(๐’โ„“(L))โ€ฒโ€ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,ยกยฏ))+โˆฅ(๐’โ„“(L))โ€ฒโ€ฒโข๐ฑ-(๐’โ„“(L))โ€ฒโข๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))

(23) now follows from Theorem 11. The proof of (11) is similar, using the fact that the non-windowed scattering transform is always fully permutation invariant by Theorem 6. โˆŽ

5 Future Work

As alluded to in Section 1.2, we believe that our work opens up several new lines of inquiry for future research. Graph scattering transforms typically get numerical results which are good, but not quite state of the art in most situations. Our work has introduced a large class of scattering networks with provable guarantees. Therefore, one might attempt to learn the optimal choices of the matrix ๐Œ and the spectral function g based on training data and produce a network which retains the invariance and stability properties of the scattering transform but has superior numerical performance. This would be an important step towards bridging the gap between theory and practice by producing an increasingly realistic model of graph neural networks with provable guarantees. Another possible extension would be to consider a construction similar to ours but which uses the spectral decomposition of the unnormalized graph Laplacian rather than the normalized Laplacian. Such a work would generalize [17] in a manner analogous to the way that this work generalizes [8] and [9]. Lastly, particularly in the case where ๐Œ is a function of ๐ƒ, e.g. when ๐Š=๐, one might wish to study the behavior of the graph scattering transform on data-driven graphs obtained by subsampling a Riemannian manifold โ„ณ. Such data-driven graphs typically arise in high-dimensional data analysis and in manifold learning. It can be shown that, under certain conditions, the normalized graph Laplacian of the data-driven graph converges pointwise [5, 15] or in a spectral sense [2, 3, 6, 14, 16] to the Laplace Beltrami operator on โ„ณ as the number of samples tends to infinity. It would be interesting to see if one could use these results to study the convergence the graph scattering transforms constructed here to the manifold scattering transform constructed in [13].

Appendix A Lemma 5

In this section, we state and prove the following lemma which is useful in the proof of Theorems 1 and 2.

Lemma 5.

Assume Bโ‰ค1 in (7). Then, for all mโ‰ฅ1 and for all xโˆˆL2โข(G,M)

โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2โ‰ฅโˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2+โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’โข[๐ฃ]โข๐ฑโˆฅ๐Œ2 (26)

with equality holding if A=B=1. Furthermore, for all x,yโˆˆL2โข(G,M),

โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒโˆฅ๐Œ2โ‰ฅโˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒโˆฅ๐Œ2+โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’โข[๐ฃ]โข๐ฑ-๐’โข[๐ฃ]โข๐ฒโˆฅ๐Œ2. (27)
The Proof of Lemma 5.

Since by assumption we have Bโ‰ค1, in (7) it follows that for all ๐ฃโˆˆ๐’ฅm that

โˆฅ๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒโˆฅ๐Œ2 โ‰ฅโˆ‘jm+1โˆˆ๐’ฅโˆฅฮจjm+1โข(๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒ)โˆฅ๐Œ2+โˆฅฮฆโข(๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒ)โˆฅ๐Œ2.


โ‰ฅโˆ‘๐ฃโˆˆ๐’ฅm(โˆ‘jm+1โˆˆ๐’ฅโˆฅฮจjm+1โข(๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒ)โˆฅ๐Œ2+โˆฅฮฆโข(๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒ)โˆฅ๐Œ2) (28)
โ‰ฅโˆ‘๐ฃโˆˆ๐’ฅm(โˆ‘jm+1โˆˆ๐’ฅโˆฅMโขฮจjm+1โข๐”โข[๐ฃ]โข๐ฑ-Mโขฮจjm+1โข๐”โข[๐ฃ]โข๐ฒโˆฅ๐Œ2+โˆฅฮฆโข(๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒ)โˆฅ๐Œ2) (29)

This completes the proof of (27). (26) follows from setting ๐ฒ=0. Lastly, we observe that if that A=B=1 in (7) and ๐ฒ=0, we have equality in the inequalities (28) and (29).


Appendix B The Proof of Theorem 1


Applying Lemma 5, which is stated in Appendix A, and recalling that Uโข[๐ฃ๐ž]โข๐ฑ=๐ฑ, we see

โˆฅ๐’๐ฑ-๐’๐ฒโˆฅ๐Œ2 =limNโ†’โˆžโกโˆ‘m=0Nโˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐’โข[๐ฃ]โข๐ฑ-๐’โข[๐ฃ]โข๐ฒโˆฅ๐Œ2
โ‰คโˆฅ๐ฑ-๐ฒโˆฅ๐Œ2-lim supNโ†’โˆžโกโˆ‘๐ฃโˆˆ๐’ฅN+1โˆฅ๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒโˆฅ๐Œ2

This proves (8). Turning our attention to ๐’ยฏ, we have that for any ๐ฃ,

|๐’ยฏโข[๐ฃ]โข๐ฑ-๐’ยฏโข[๐ฃ]โข๐ฒ| =โŸจ๐,๐”โข[๐ฃ]โข๐ฑ-๐”โข[๐ฃ]โข๐ฒโŸฉ๐Œ

(9) follows from squaring both sides, summing over ๐ฃ, and applying (8).


Appendix C The Proof of Theorem 2


Let mโ‰ฅ1, let t=2J-1 if ๐’ฒ=๐’ฒ(1), and let t=2J if ๐’ฒ=๐’ฒ(2), so that in either case ฮฆ=๐“t. Let ๐ฑโˆˆ๐‹2โข(G,๐Œ), and let ๐ฒ=๐”โข[๐ฃ]โข๐ฑ. (3) implies that for any ๐ณโˆˆ๐‹2โข(G,๐Œ)


Therefore, by Lemma 2 and the relationship ๐ฎi=๐Œ-1โข๐ฏi, we have


By Parsevalโ€™s identity, the fact that {๐ฎ0,โ€ฆ,๐ฎn-1} is an orthornomal basis for ๐‹2โข(G,๐Œ), and the fact that ฮป0=1, we have that for all let ๐ฃโˆˆ๐’ฅm,

โˆฅ๐’โข[๐ฃ]โข๐ฑโˆฅ๐Œ2 =โˆฅ๐Štโข๐ฒโˆฅ๐Œ2

Since ๐ฏ0=๐1/2โˆฅ๐1/2โˆฅ2=๐1/2โˆฅ๐โˆฅ1,

|โŸจ๐ฏ0,๐Œ๐ฒโŸฉ2|2 =|โˆ‘i=0n-1๐โข(i)โˆฅ๐1/2โˆฅ2โข(๐Œ๐ฒ)โข(i)|

Summing over ๐ฃ, this gives


Therefore, by Lemma 5 (stated in Appendix A) we see


This proves (10). To prove (11), we note that since Bโ‰ค1 in (7), we have


Therefore, (11) holds when m=0. The result follows for mโ‰ฅ1 by iteratively applying (10). โˆŽ

Appendix D The Proof of Theorem 3


By Propositions 1 and 2 and by Lemma 5, we have that for all mโ‰ฅ0



โˆฅ๐’๐ฑโˆฅโ„“2โข(๐‹2โข(G,๐Œ))2 =limNโ†’โˆžโกโˆ‘m=0N(โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2-โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2)

where the last equality follows from Theorem 2. โˆŽ

Appendix E The Proof of Theorem 8


Let ๐ฏโ‰”๐ฏ0 denote the lead eigenvector of ๐“. Since ฮป1<1, we may write




and ๐“ยฏโข๐ฏ=0. Since ๐ฏ0,๐ฏ1,โ€ฆ,๐ฏn-1 form an orthonormal basis for ๐‹2โข(G), we have that

๐“k=๐ฏ๐ฏT+๐“ยฏk (30)

for all kโ‰ฅ1. Therefore, we see that

ฮจj={๐ˆ-๐“=๐ˆ-๐ฏ๐ฏ-๐“ยฏย forย โขj=0๐“2j-1-๐“2j=๐“ยฏ2j-1-๐“ยฏ2jย forย โข1โ‰คjโ‰คJ,



with similar equations being valid for ฮจjโ€ฒ and ฮฆJโ€ฒ. Thus,

โˆฅ๐’ฒ-๐’ฒโ€ฒโˆฅ22 =โˆฅฮฆJ-ฮฆJโ€ฒโˆฅ22+โˆ‘j=0Jโˆฅฮจj-ฮจjโ€ฒโˆฅ22
โ‰ค4โข(โˆฅ๐ฏ๐ฏT-๐ฏโ€ฒโข๐ฏโ€ฒโฃTโˆฅ22+โˆ‘j=0Jโˆฅ๐“ยฏ2j-๐“ยฏโ€ฒโฃ2jโˆฅ22). (31)

The following lemma follows by imitating equation (23) of [8] and summing over j.

Lemma 6.







and โˆฅ๐“ยฏโˆฅ2,โˆฅ๐“ยฏโ€ฒโˆฅ2โ‰คฮป1*, this implies



โˆ‘j=0Jโˆฅ๐“ยฏ2j-(๐“ยฏโ€ฒ)2jโˆฅ22 โ‰คโˆฅ๐“ยฏ-๐“ยฏโ€ฒโˆฅ22โขโˆ‘j=0โˆž22โขjโข(ฮป1*)2j+1-2

since ฮป1*<1. โˆŽ

By the triangle inequality,


Therefore, by (31), we have

โˆฅ๐’ฒ-๐’ฒโ€ฒโˆฅ22โ‰คCฮป1*โข(โˆฅ๐“-๐“โ€ฒโˆฅ22+โˆฅ๐ฏ๐ฏT-๐ฏโ€ฒโข๐ฏโ€ฒโฃTโˆฅ22). (32)

To bound โˆฅ(๐ฏ๐ฏT-๐ฏโ€ฒโข๐ฏโ€ฒโฃT)โข๐ฑโˆฅ2, we note that for all ๐ฑ

โˆฅ๐ฏ๐ฏT-๐ฏโ€ฒโข๐ฏโ€ฒโฃTโˆฅ2 โ‰คโˆฅ(๐ฏ(๐ฏ-๐ฏโ€ฒ)T๐ฑโˆฅ2+โˆฅ(๐ฏ-๐ฏโ€ฒ)๐ฏโ€ฒโฃT๐ฑโˆฅ2

with the last equality following from the fact that โˆฅ๐ฏโˆฅ2=โˆฅ๐ฏโ€ฒโˆฅ2=1. Therefore, the proof is complete, pending the following lemma (a restatement of Lemma 5.2 of [8]) which bounds โˆฅ๐ฏ-๐ฏโ€ฒโˆฅ2.

Lemma 7.


The Proof of Lemma 7.

Let ฮฑ=โŸจ๐ฏ,๐ฏโ€ฒโŸฉ2. Since ๐“=๐ฏ๐ฏT+๐“ยฏ and ๐“โ€ฒ=๐ฏโ€ฒโข(๐ฏโ€ฒ)T+๐“ยฏโ€ฒ, with ๐“ยฏโข๐ฏ=ฮฑโข๐“ยฏโ€ฒโข๐ฏโ€ฒ=0, we see

(๐“-๐“โ€ฒ)โข๐ฏ =(๐ฏ๐ฏT-๐ฏโ€ฒโข(๐ฏโ€ฒ)T)โข๐ฏ+(๐“ยฏ-๐“ยฏโ€ฒ)โข๐ฏ

Since โˆฅ๐ˆ-๐“ยฏโ€ฒโˆฅ2=1-ฮป1โ€ฒโ‰ฅ1-ฮป1*, and โˆฅ๐ฏ-๐ฏโ€ฒโขฮฑโˆฅ2โ‰ฅ1-ฮฑ, this implies


since โˆฅ๐ฏ-๐ฏโ€ฒโˆฅ22=2โข(1-ฮฑ). Therefore, we have



Appendix F The Proof of Lemmas 3 and 4

The Proof of Lemma 3.

When m=1, this follows immediately from the fact that we have assumed that Bโ‰ค1 in (7) and the fact that M is nonexpansive. Now, suppose by induction that the result holds for m, then

โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ๐”โข[๐ฃ]โข๐ฑโˆฅ๐Œ2 =โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅMโขฮจjm+1โขโ€ฆโขMโขฮจ1โข๐ฑโˆฅ๐Œ2

with the last inequality following from the inductive assumption. โˆŽ

The Proof of Lemma 4.

Let ๐ฑโˆˆ๐‹2โข(G,๐Œ), and let tmโ‰”(โˆ‘๐ฃโˆˆ๐’ฅmโˆฅ๐”โข[๐ฃ]โข๐ฑ-๐”โ€ฒโข[๐ฃ]โข๐ฑโˆฅ๐Œ2)1/2. Since the modulus operator is nonexpansive, the definition of ๐’œ implies t1โ‰ค๐’œ1/2โขโˆฅ๐ฑโˆฅ๐Œ. Now, by induction, suppose the result holds for m. Then, rcalling that ๐”โข[๐ฃ]=Mโขฮจjmโขโ€ฆโขMโขฮจj1, we have

tm+1= (โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅMโขฮจjm+1โขโ€ฆโขMโขฮจj1โข๐ฑ-Mโขฮจjm+1โ€ฒโขโ€ฆโขMโขฮจj1โ€ฒโข๐ฑโˆฅ๐Œ2)1/2
โ‰ค (โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅ(ฮจjm+1-ฮจjm+1โ€ฒ)โขMโขฮจjmโขโ€ฆโขMโขฮจj1โข๐ฑโˆฅ๐Œ2)1/2
โ‰ค ๐’œ1/2โข(โˆ‘๐ฃโˆˆ๐’ฅm+1โˆฅMโขฮจjmโขโ€ฆโขMโขฮจj1โข๐ฑโˆฅ๐Œ2)1/2
โ‰ค ๐’œ1/2โขโˆฅ๐ฑโˆฅ๐Œ+tmโข๐’ž1/2โขโˆฅ๐ฑโˆฅ๐Œ

by the definitions of ๐’œ and ๐’ž and by Lemma 3. By the inductive hypothesis, we have that




Squaring both sides completes the proof.



  • [1] Joakim Andรฉn and Stรฉphane Mallat. Multiscale scattering for audio classification. In Proceedings of the ISMIR 2011 conference, pages 657โ€“662, 2011.
  • [2] Mikhail Belkin and Partha Niyogi. Convergence of Laplacian eigenmaps. In Advances in Neural Information Processing Systems, pages 129โ€“136, 2007.
  • [3] Dmitri Burago, Sergei Ivanov, and Yaroslav Kurylev. A graph discretization of the Laplace-Beltrami operator. Journal of Spectral Theory, 4, 01 2013.
  • [4] V.ย Chudacek, R.ย Talmon, J.ย Anden, S.ย Mallat, R.ย R. Coifman, P.ย Abry, and M.ย Doret. Low dimensional manifold embedding for scattering coefficients of intrapartum fetale heart rate variability. In 2014 Internat. IEEE Conf. in Medicine and Biology, 2014.
  • [5] Ronaldย R. Coifman and Stรฉphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21:5โ€“30, 2006.
  • [6] Koji Fujiwara. Eigenvalues of Laplacians on a closed Riemannian manifold and its nets. 1995.
  • [7] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability of graph scattering transforms. In Advances in Neural Information Processing Systems 33, 2019.
  • [8] Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms on graphs. In International Conference on Learning Representations, 2019.
  • [9] Feng Gao, Guy Wolf, and Matthew Hirn. Geometric scattering for graph data analysis. In Proceedings of the 36th International Conference on Machine Learning, PMLR, volumeย 97, pages 2122โ€“2131, 2019.
  • [10] Matthew Hirn, Stรฉphane Mallat, and Nicolas Poilvert. Wavelet scattering regression of quantum chemical energies. Multiscale Modeling and Simulation, 15(2):827โ€“863, 2017.
  • [11] Stรฉphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331โ€“1398, October 2012.
  • [12] Edouard Oyallon and Stรฉphane Mallat. Deep roto-translation scattering for object classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2865โ€“2873, 2015.
  • [13] Michael Perlmutter, Feng Gao, Guy Wolf, and Matthew Hirn. Geometric scattering networks on compact Riemannian manifolds. arXiv:1905.10448, 2019.
  • [14] Zuoqiang Shi. Convergence of laplacian spectra from random samples. ArXiv, 1507.00151, 2015.
  • [15] Amit Singer. From graph to manifold Laplacian: The convergence rate. Applied and Computational Harmonic Analysis, 21(1):128โ€“134, July 2006.
  • [16] Nicolas Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepcev. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplaceโ€“Beltrami operator. Foundations of Computational Mathematics, 01 2018.
  • [17] Dongmian Zou and Gilad Lerman. Encoding robust representation for graph generation. In International Joint Conference on Neural Networks, 2019.
  • [18] Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 2019. In press.