Stability is a key aspect of data analysis. In many applications, the natural notion of stability is geometric, as illustrated for example in computer vision. Scattering transforms construct deep convolutional representations which are certified stable to input deformations. This stability to deformations can be interpreted as stability with respect to changes in the metric structure of the domain. 

 In this work, we show that scattering transforms can be generalized to non-Euclidean domains using diffusion wavelets, while preserving a notion of stability with respect to metric changes in the domain, measured with diffusion maps. The resulting representation is stable to metric perturbations of the domain while being able to capture ''high-frequency'' information, akin to the Euclidean Scattering. Convolutional Neural Networks (CNN) are layered information processing architectures. Each of the layers in a CNN is itself the composition of a convolution operation with a pointwise nonlinearity where the filters used at different layers are the outcome of a data-driven optimization process BID22 . Scattering transforms have an analogous layered architecture but differ from CNNs in that the convolutional filters used at different layers are not trained but selected from a multi-resolution filter bank BID25 BID3 . The fact that they are not trained endows scattering transforms with intrinsic value in situations where training is impossible -and inherent limitations in the converse case. That said, an equally important value of scattering transforms is that by isolating the convolutional layered architecture from training effects it permits analysis of the fundamental properties of CNN information processing architectures. This analysis is undertaken in BID25 ; BID3 where the fundamental conclusion is about the stability of scattering transforms with respect to deformations in the underlying domain that are close to translations.In this paper we consider graphs and signals supported on graphs such as brain connectivity networks and functional activity levels BID17 , social networks and opinions BID19 , or user similarity networks and ratings in recommendation systems BID18 . Our specific goals are: (i) To define a family of graph-scattering transforms. (ii) To define a notion of deformation for graph signals. (iii) To study the stability of graph scattering transforms with respect to this notion of deformation. To accomplish goal (i) we consider the family of graph diffusion wavelets which provide an appropriate construction of a multi-resolution filter bank BID8 . Our diffusion scattering transforms are defined as the layered composition of diffusion wavelet filter banks and pointwise nonlinearities. To accomplish goal (ii) we adopt the graph diffusion distance as a measure of deformation of the underlying domain BID27 . Diffusion distances measure the similarity of two graphs through the time it takes for a signal to be diffused on the graph. The major accomplishment of this paper is to show that the diffusion graph scattering transforms are stable with respect to deformations as measured with respect to diffusion distances. Specifically, consider a signal x supported on graph G whose diffusion scattering transform is denoted by the operator Ψ G . Consider now a deformation of the signal's domain so that the signal's support is now described by the graph G whose diffusion scattering operator is Ψ G . We show that the operator norm distance Ψ G − Ψ G is bounded by a constant multiplied by the diffusion distance between the graphs G and G . The constant in this bound depends on the spectral gap of G but, very importantly, does not depend on the number of nodes in the graph.It is important to point out that finding stable representations is not difficult. E.g., taking signal averages is a representation that is stable to domain deformations -indeed, invariant. The challenge is finding a representation that is stable and rich in its description of the signal. In our numerical analyses we show that linear filters can provide representations that are either stable or rich but that cannot be stable and rich at the same time. The situation is analogous to (Euclidean) scattering transforms and is also associated with high frequency components. We can obtain a stable representation by eliminating high frequency components but the representation loses important signal features. Alternatively, we can retain high frequency components to have a rich representation but that representation is unstable to deformations. Diffusion scattering transforms are observed to be not only stable -as predicted by our theoretical analysis -but also sufficiently rich to achieve good performance in graph signal classification examples. In this work we addressed the problem of stability of graph representations. We designed a scattering transform of graph signals using diffusion wavelets and we proved that this transform is stable under deformations of the underlying graph support. More specifically, we showed that the scattering transform of a graph signal supported on two different graphs is proportional to the diffusion distance between those graphs. As a byproduct of our analysis, we obtain stability bounds for Graph Neural Networks generated by diffusion operators. Additionally, we showed that the resulting descriptions are also rich enough to be able to adequately classify plays by author in the context of authorship attribution, and identify the community origin of a signal in a source localization problem.That said, there are a number of directions to build upon from these results. First, our stability bounds depend on the spectral gap of the graph diffusion. Although lazy diffusion prevents this spectral gap to vanish, as the size of the graph increases we generally do not have a tight bound, as illustrated by regular graphs. An important direction of future research is thus to develop stability bounds which are robust to vanishing spectral gaps. Next, and related to this first point, we are working on extending the analysis to broader families of wavelet decompositions on graphs and their corresponding graph neural network versions, including stability with respect to the GromovHausdorff metric, which can be achieved by using graph wavelet filter banks that achieve bounds analogous to those in Lemmas 5.1 and 5.2.A PROOF OF PROPOSITION 4.1Since all operators ψ j are polynomials of the diffusion T , they all diagonalise in the same basis. Let T = V ΛV T , where V T V = I contains the eigenvectors of T and Λ = diag(λ 0 , . . . , λ n−1 ) its eigenvalues. The frame bounds C 1 , C 2 are obtained by evaluating Ψx 2 for x = v i , i = 1, . . . , n− 1, since v 0 corresponds to the square-root degree vector and x is by assumption orthogonal to v 0 .We verify that the spectrum of ψ j is given by (p j (λ 0 ) , . . . , p j (λ n−1 )), where DISPLAYFORM0 2 . It follows from the definition that DISPLAYFORM1 . . , n − 1 and therefore DISPLAYFORM2 We check that DISPLAYFORM3 2 . One easily verifies that Q(x) is continuous in [0, 1) since it is bounded by a geometric series. Also, observe that DISPLAYFORM4 since x ∈ [0, 1). By continuity it thus follows that DISPLAYFORM5 which results in g ( t) ≤ rβ r−1 B − A , proving (23).By plugging FORMULA5 into (22) we thus obtain DISPLAYFORM6 (1−β 2 ) 3 . Finally , we observe that DISPLAYFORM7 Without loss of generality, assume that the node assignment that minimizes T G − ΠT G Π T is the identity. We need to bound the leading eigenvectors of two symmetric matrices T G and T G with a spectral gap. As before , let DISPLAYFORM8 Since we are free to swap the role of v and v , the result follows. DISPLAYFORM9 First, note that ρ G = ρ G = ρ since it is a pointwise nonlinearity (an absolute value), and is independent of the graph topology. Now, let's start with k = 0. In this case, we get U G x − U G x which is immediately bounded by Lemma 5.2 satisfying equation 15.For k = 1 we have DISPLAYFORM10 where the triangular inequality of the norm was used, together with the fact that ρu − ρu ≤ ρ(u − u ) for any real vector u since ρ is the pointwise absolute value. Using the submultiplicativity of the operator norm, we get DISPLAYFORM11 From Lemmas 5.1 and 5.2 we have that Ψ G − Ψ G ≤ ε Ψ and U G − U G ≤ ε U , and from Proposition 4.1 that Ψ G ≤ 1. Note also that U G = U G = 1 and that ρ = 1. This yields DISPLAYFORM12 satisfying equation 15 for k = 1.For k = 2, we observe that DISPLAYFORM13 The first term is bounded in a straightforward fashion by DISPLAYFORM14 analogy to the development for k = 1. Since U G = 1, for the second term, we focus on DISPLAYFORM15 We note that, in the first term in equation 33, the first layer induces an error, but after that, the processing is through the same filter banks. So we are basically interested in bounding the propagation of the error induced in the first layer. Applying twice the fact that ρ(u ) − ρ(u ) ≤ ρ(u − u ) we get DISPLAYFORM16 And following with submultiplicativity of the operator norm, DISPLAYFORM17 For the second term in equation 33, we see that the first layer applied is the same in both, namely ρΨ G so there is no error induced. Therefore, we are interested in the error obtained after the first layer, which is precisely the same error obtained for k = 1. Therefore, DISPLAYFORM18 Plugging equation 35 and equation 36 back in equation 31 we get DISPLAYFORM19 satisfying equation 15 for k = 2.For general k we see that we will have a first term that is the error induced by the mismatch on the low pass filter that amounts to ε U , a second term that accounts for the propagation through (k − 1) equal layers of an initial error, yielding ε Ψ , and a final third term that is the error induced by the previous layer, (k − 1)ε Ψ . More formally, assume that equation 15 holds for k − 1, implying that DISPLAYFORM20 Then, for k, we can write DISPLAYFORM21 Again, the first term we bound it in a straightforward manner using submultiplicativity of the operator norm DISPLAYFORM22 For the second term, since U G = 1 we focus on DISPLAYFORM23 The first term in equation 42 computes the propagation in the initial error caused by the first layer. Then, repeatedly applying ρ(u) − ρ(u ) ≤ ρ(u − u ) in analogy with k = 2 and using submultiplicativity, we get DISPLAYFORM24 The second term in equation 42 is the bounded by equation 38, since the first layer is exactly the same in this second term. Then, combining equation 43 with equation 38, yields DISPLAYFORM25 Overall, we get DISPLAYFORM26 which satisfies equation 15 for k. Finally, since this holds for k = 2, the proof is completed by induction .E PROOF OF COROLLARY 5.4From Theorem 5.3, we have DISPLAYFORM27 and, by definition (Bruna & Mallat, 2013, Sec. 3 .1), DISPLAYFORM28 so that DISPLAYFORM29 Then, applying the inequality of Theorem 5.3, we get DISPLAYFORM30 Now, considering each term, such that DISPLAYFORM31 + m−1 k=0 2 3/2 k β 2 + (1 + β 2 + ) (1 − β − )(1 − β 2 + ) 3 d
Stability of scattering transform representations of graph data to deformations of the underlying graph support.
{"src": "scitldr-AIC_train", "paper_id": "BygqBiRcFQ"}