PaperlayerView exact revision on arXiv

Source-linked AI summary

Diffusion Scattering Transforms on Graphs

Fernando Gama, Alejandro Ribeiro, Joan Bruna

arXiv:1806.08829v2cs.LGstat.ML

TL;DR

The paper addresses how to define deformation-stable representations for signals on graphs, where Euclidean deformation notions do not directly apply. It constructs diffusion-wavelet scattering and shows that its stability bound is controlled by graph diffusion distance, while its representations retain useful signal information.

  • Problem

    For graph signals, the paper seeks a representation stable to changes in the underlying domain while retaining discriminative information.

    Source: §3 · p. 3, §3.1 · p. 3

  • Method

    The paper composes graph diffusion-wavelet filter banks with pointwise nonlinearities, using spatially localized wavelets for its scattering construction.

    Source: §1 · p. 1, §4 · p. 5

  • Results

    The operator norm distance between graph scattering transforms is bounded by a constant times graph diffusion distance, and the representation is sufficiently rich for classification examples.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Diffusion scattering combines stability with useful signal detail, including high-frequency information relevant to graph-signal classification.

    Source: §1 · p. 2, §7 · p. 10

    The stability bound depends on the diffusion spectral gap, which can degrade asymptotically for regular graphs as graph size increases.

    Source: §5.1 · p. 7, §7 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Scattering transforms offer a layered, untrained alternative to CNNs and provide a framework for studying stability to domain deformations. This paper constructs graph diffusion scattering and shows stability under diffusion-distance perturbations while retaining useful signal detail.

1 INTRODUCTION

  • Diffusion scattering is built from graph diffusion wavelet filter banks and pointwise nonlinearities, and is stable to changes in the graph support measured by diffusion distance.Source: §1 · p. 1
  • The operator norm distance between diffusion scattering transforms on two graphs is bounded by a constant times their diffusion distance.The bound’s constant depends on the graph’s spectral gap, not its number of nodes.Source: §1 · pp. 1–2
  • Numerical analyses find that diffusion scattering is stable and sufficiently rich for graph-signal classification, unlike linear filters that cannot be both stable and rich.Removing high-frequency components can yield stability but lose signal features; retaining them can yield richer but unstable representations.Source: §1 · p. 2

2 RELATED WORK

The paper situates graph scattering among graph neural networks and prior scattering methods, distinguishing its diffusion-wavelet construction and diffusion-metric stability analysis.

2 RELATED WORK

  • Graph scattering generalizes convolutional processing to graph signals, while its filters are not trained as in graph neural networks.Graph shift-invariant filters have been used in practical GNNs [Defferrard et al., 2016; Gama et al., 2018; Gilmer et al., 2017; Kipf & Welling, 2017].Source: §2 · p. 2
  • Scattering transforms have also been extended beyond Euclidean computer vision to roto-translations, audio processing, and quantum chemistry.The cited extensions include Sifre & Mallat (2013), Oyallon & Mallat (2015), And´en & Mallat (2014), and Eickenberg et al. (2017).Source: §2 · p. 2
  • Compared with graph scattering based on spectral wavelets, this work uses diffusion wavelets and establishes stability for diffusion-metric perturbations.The cited spectral-wavelet work establishes energy conservation and stability to spectral perturbations.Source: §2 · p. 2

3 PROBLEM SET-UP

The setup recasts deformation stability as stability to changes in a domain’s metric, then develops graph diffusion tools to define a stable, discriminative representation. It builds from Euclidean scattering, where localized wavelets transform high-frequency information into stable features.

3.1 EUCLIDEAN STABILITY TO DEFORMATIONS WITH SCATTERING

  • Euclidean deformation stability concerns representations of signals that remain stable under small differentiable changes of variables, while preserving discriminative power.The deformation field is constrained by ∥∇τ∥<1.Source: §3.1 · p. 3
  • For Euclidean signals, scattering cascades wavelet decompositions with pointwise modulus nonlinearities and average pooling to form layered features.Spatially localized wavelets capture high-frequency information with appropriate spatio-temporal tradeoffs.Source: §3.1 · p. 3

3.2 DEFORMATIONS AND METRIC STABILITY

  • For non-Euclidean domains without a low-dimensional embedding, the setup generalizes deformation stability by comparing representations under changes to the domain’s metric.The representation must be definable on generic metric spaces, and the spaces need a measure of closeness.Source: §3.2 · p. 3

3.3 DIFFUSION WAVELETS AND METRICS ON GRAPHS

  • The setup focuses on deformations of the graph support while holding the signal mapping fixed.Source: §3.3 · p. 4
  • Graph diffusion uses a normalized adjacency operator, with lazy diffusion T = 1/2(I + A) used to define multiscale wavelets and low-pass pooling.The normalized adjacency is A = D^-1/2WD^-1/2; lazy diffusion avoids folding negative eigenvalues into positive ones when taking powers.Source: §3.3 · p. 4
  • The graph distance compares diffusion metrics at a chosen time, with larger times yielding a weaker distance; this work uses s = 1/2 for tractability.The selected distance defines a stronger topology than alternatives such as Gromov-Hausdorff distance, and stability for other diffusion times is left for future work.Source: §3.3 · p. 4

3.4 PROBLEM STATEMENT

  • The problem statement seeks a representation stable under diffusion-metric changes while distinguishing graph signals and, in some applications, graphs themselves.Graph representations may be formed for a prespecified signal or by marginalizing over an exchangeable signal distribution; matching graph kernels is NP-hard.Source: §3.4 · p. 5

4 GRAPH DIFFUSION SCATTERING

Graph diffusion scattering combines multiscale diffusion wavelets, pointwise activation, and averaging into a graph representation. Under a spectral-gap condition, the wavelet filter bank has stable frame bounds that also inform its maximum diffusion scale.

4 GRAPH DIFFUSION SCATTERING

  • Diffusion wavelet filters are formed from powers of a lazy diffusion operator, using ψ0=I−T and ψj=T^(2^j−1)−T^(2^j) for j>0.The construction uses dyadic scales, with analogous alternatives using ⌈γ^j⌉ for γ>1.Source: §4 · p. 5
  • These filters favor spatial over frequency localization, with coarser scales capturing temporal differences at increasingly spaced diffusion times.The finest scale corresponds to half the normalized Laplacian, interpreted as a temporal difference in diffusion.Source: §4 · p. 5
  • When βG<1, the diffusion wavelet filter bank defines a stable frame whose bounds inform energy loss and maximum-scale selection.The scale is adjusted using the spectral gap so it does not extend into spectral ranges where the graph has no information.Source: §4 · pp. 5–6
  • Diffusion scattering cascades wavelet decomposition, pointwise activation, and domain averaging, with deeper representations formed by repeated transformations.The average is interpreted as diffusion at infinite time.Source: §4 · p. 6

5 STABILITY OF GRAPH DIFFUSION SCATTERING

The section establishes graph-scattering stability bounds in terms of diffusion distance, with constants affected by spectral gaps and depth. It also relates diffusion scattering to graph neural networks (GNNs), whose representations retain stability with parameter-dependent constants.

5.1 STABILITY AND EQUIVARIANCE OF DIFFUSION WAVELETS

  • The low-pass operator’s stability is bounded by 2d(G, G′)/(1 − min(β, β′)), while the diffusion-wavelet bound depends on the graph’s spectral gap.For regular graphs, the gap may vanish asymptotically with graph size, degrading the upper bound; improving it using structural properties is left open.Source: §5.1 · pp. 6–7

5.2 STABILITY AND INVARIANCE OF DIFFUSION SCATTERING

  • The scattering representation is stable across graphs under a shared non-expansive nonlinearity and spectral gaps bounded below 1; its bound worsens with smaller gaps and more layers.The bound compares graphs using diffusion distance, and the authors caution that the spectral-gap estimate may be poor for regular graphs.Source: §5.2 · p. 7
  • The stability guarantee uses a permutation-invariant graph metric that the authors describe as stronger than desired; extension to weaker multiscale-deformation metrics is future work.Graph size affects the result through its effect on the distance measure.Source: §5.2 · pp. 7–8

5.3 FROM DIFFUSION SCATTERING TO DIFFUSION GNNS

  • Diffusion scattering is a multiscale GNN whose layer j uses the operator pair {I, Tj−1}.The wavelets can be approximated by low-pass diffusions followed by a high-pass filter at resolution 2^j.Source: §5.3 · p. 8
  • The resulting learned GNN representation remains stable with respect to d(G, G′), but its stability constants depend on the parameters.The bound is learning-agnostic; connecting stability to gradient-descent optimization biases is left for future work.Source: §5.3 · p. 8

6 NUMERICAL EXPERIMENTS

The experiments examine how diffusion scattering responds to graph perturbations and how useful its features are for classification. Across the two tasks, scattering shows stability under graph changes alongside discriminative power, while its stability bound worsens as the spectral gap approaches one.

6 NUMERICAL EXPERIMENTS

  • Scattering varies less under graph perturbations than linear representations in the Facebook task, while in authorship attribution its error improves with more training data as other methods vary more erratically.Figure 1 reports error against perturbation for both tasks; the authorship experiment uses Jane Austen excerpts and contemporary-author excerpts.Source: Figure 1 · p. 9, §6 · pp. 9–10
  • As the spectral gap β approaches one, the observed representation difference increases, and deeper scattering also increases the difference, though not linearly as the bound predicts.The authors interpret the nonlinearity as suggesting that the bound is not tight.Source: §6 · p. 9
  • The experiments compare representations using linear SVM classifiers, including data-based signals, graph Fourier coefficients, and scattering features at varying depths.The authors use the comparisons to illustrate scattering's stability and discriminative power relative to linear representations.Source: §6 · p. 9
  • Deeper scattering features improve classification accuracy, although trainable GNNs generally outperform scattering when labeled examples are sufficient.The authors state this qualification for regimes with sufficient labeled examples.Source: §6 · p. 10

7 CONCLUSIONS

The paper concludes that diffusion-wavelet scattering is stable under deformations of graph support, with representation differences proportional to diffusion distance. It also reports classification utility while identifying spectral-gap dependence as an open limitation.

7 CONCLUSIONS

  • Diffusion-wavelet scattering is stable under graph-support deformations, with representation differences proportional to the diffusion distance between graphs.The analysis also yields stability bounds for Graph Neural Networks generated by diffusion operators.Source: §7 · p. 10
  • The resulting representations classify plays by author and identify the community origin of signals in source localization.Source: §7 · p. 10
  • The stability bounds depend on the diffusion spectral gap and may not be tight as graph size increases, motivating bounds robust to vanishing gaps.The paper notes this issue for regular graphs and identifies broader wavelet families and Gromov-Hausdorff stability as future directions.Source: §7 · p. 10

A PROOF OF PROPOSITION 4.1

The proof uses the common eigenbasis of diffusion-polynomial filters to evaluate the frame bounds through their spectral responses.

A PROOF OF PROPOSITION 4.1

  • Because each operator ψ_j is a polynomial of diffusion T, all operators diagonalize in T's eigenbasis.The frame-bound evaluation excludes v_0, which corresponds to the square-root degree vector, because x is assumed orthogonal to it.Source: A PROOF OF PROPOSITION 4.1 · p. 13
  • The spectrum of ψ_j is given by p_j applied to the eigenvalues of T, with p_j(x) = x^(2j−1) − x^(2j) for j > 0 and p_0(x) = 1 − x.Source: A PROOF OF PROPOSITION 4.1 · p. 13
  • The squared norm of Ψv_i equals Q_J(λ_i), the sum of squared filter responses, which is used to establish the frame bounds.The supplied proof gives C_1 ≥ (1 − β)^2 and C_2 = 1.Source: A PROOF OF PROPOSITION 4.1 · p. 13

B PROOF OF LEMMA 5.1

The proof of Lemma 5.1 bounds differences between graph diffusion operators by decomposing each operator into its stationary component and a contracting remainder.

B PROOF OF LEMMA 5.1

  • Self-adjointness of the graph operators and their filters lets the proof apply the triangle inequality to bound their differences.Source: B PROOF OF LEMMA 5.1 · p. 13
  • For β < 1, T is decomposed into the stationary projector vv^T and a remainder with norm below one, yielding T^r = vv^T + T̄^r.The passage defines v as the eigenvector associated with λ_0 = 1.Source: B PROOF OF LEMMA 5.1 · p. 13
  • The proof applies a bound for powers of two operators with norms at most β, then substitutes it into the preceding inequalities to obtain the claimed result.It concludes using equality between the norms of the normalized-operator difference and the corresponding diffusion-operator difference.Source: B PROOF OF LEMMA 5.1 · pp. 13–14

C PROOF OF LEMMA 5.2

The proof bounds the leading eigenvectors of two symmetric matrices by decomposing their difference into leading-eigenvector and residual components, then uses the freedom to swap the eigenvectors to conclude.

C PROOF OF LEMMA 5.2

  • The proof assumes the node assignment minimizing the distance between the graph operators is the identity, without loss of generality.It then considers the leading eigenvectors of two symmetric matrices with a spectral gap.Source: C PROOF OF LEMMA 5.2 · p. 14
  • Writing each operator as its leading-eigenvector component plus a residual separates their difference into those two contributions.The proof denotes the leading-eigenvector inner product by α and the residual difference by E.Source: C PROOF OF LEMMA 5.2 · p. 14
  • Swapping the roles of the two leading eigenvectors completes the result.The preceding bound is stated in terms of 1 − α and the graph distance.Source: C PROOF OF LEMMA 5.2 · p. 14

D PROOF OF THEOREM 5.3

Theorem 5.3 is proved by induction over layers, bounding errors from filter mismatch and propagated earlier errors; the Corollary 5.5 proof then invokes the theorem and a triangle inequality.

D PROOF OF THEOREM 5.3

  • At k = 0, the difference is bounded using Lemma 5.2, while the proof separately verifies the induction base cases k = 1 and k = 2.The modulus nonlinearity is independent of graph topology, and the operator norms used in the argument are bounded as stated in the proof.Source: D PROOF OF THEOREM 5.3 · pp. 14–15
  • For general depth k, the proof separates the error into low-pass mismatch εU, propagation of initial error εΨ, and accumulated prior-layer error (k −1)εΨ.The proof establishes the claim by induction, using the base cases and repeated application of the pointwise-modulus inequality and operator-norm submultiplicativity.Source: D PROOF OF THEOREM 5.3 · pp. 15–16

E PROOF OF COROLLARY 5.5

F PROOF OF COROLLARY 5.4

The proof simplifies its bound for small graph distance by showing that two terms vanish, leaving the first term to yield the corollary.

F PROOF OF COROLLARY 5.4

  • The proof derives the corollary by applying the inequality from Theorem 5.3 to the terms under consideration.It cites the definition given by Bruna and Mallat (2013, Sec. 3.1).Source: F PROOF OF COROLLARY 5.4 · p. 16
  • The analysis considers each term and finds that the second and third terms vanish when graph distance d(G, G′) ≪ 1, leaving only the first term.Source: F PROOF OF COROLLARY 5.4 · p. 17
  • When d(G, G′) ≪ 1, the second and third terms vanish, leaving the first term to yield the corollary.The proof then states that this leads to the corollary result.Source: F PROOF OF COROLLARY 5.4 · p. 17

Related papers

Loading 1806.08829v2…