PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Convolutional Neural Networks via Scattering

Dongmian Zou, Gilad Lerman

arXiv:1804.00099v2cs.ITcs.LGeess.SPmath.IT

TL;DR

Graph learning methods’ invariance and stability properties remain poorly understood. This paper adapts graph wavelets to build a graph scattering network; it establishes permutation invariance and stability to graph manipulations and reports competitive performance on classification and community-detection tasks.

  • Problem

    Graph neural networks’ performance and their invariance or stability to signal and graph manipulations are poorly understood, despite the importance of graph-structured datasets.

    Source: §1 · p. 1

  • Method

    The authors adapt graph wavelets to construct a scattering transform and convolutional neural network on graphs.

    Source: §1 · p. 2, §2.1 · p. 3

  • Results

    The transform is permutation-invariant and stable to graph manipulations, with comparable, slightly improved accuracy over state-of-the-art graph-based methods for CORA community detection.

    Source: §6.2 · p. 23, §7 · p. 24

  • Takeaways & Limitations

    The authors report that the transform’s invariance and stability properties make it effective for classification and community detection.

    Source: §7 · p. 24

    The method relies on full spectral decomposition of the graph Laplacian, making computation demanding for very large graphs.

    Source: §7 · p. 24

Abstract

from arXiv · show

We generalize the scattering transform to graphs and consequently construct a convolutional neural network on graphs. We show that under certain conditions, any feature generated by such a network is approximately invariant to permutations and stable to graph manipulations. Numerical results demonstrate competitive performance on relevant datasets.

1 Introduction

Graph data call for learning tools whose mathematical properties, especially invariance and stability, are understood. This paper adapts scattering to graphs and establishes such properties for its network.

1 Introduction

  • Graph datasets include social, physical, and transportation networks, motivating tools for both signal analysis and graph-structure learning.The tasks described include classification, prediction, inference, clustering, and matching.Source: §1 · p. 1
  • Graph neural networks’ performance and their invariance or stability to signal and graph manipulations are poorly understood.The paper identifies these properties as central questions for graph learning tools.Source: §1 · p. 1
  • Graph wavelets built from graph operators provide a route to scattering, but whether the resulting transform has the desired invariance and stability remains a key question.The introduction notes the connection between graph wavelet operators and those used in graph neural networks.Source: §1 · pp. 1–2
  • The authors use graph wavelets to build a scattering network and establish permutation covariance, approximate permutation invariance, and stability to graph manipulations.They also demonstrate practical effectiveness on signal-analysis and graph-structure tasks.Source: §1 · p. 2

2 Wavelet graph convolutional neural network

The network adapts graph wavelets to construct a scattering transform for graph signals. Spectral wavelet coefficients feed a multilayer network that propagates signals and extracts features along scale paths.

2 Wavelet graph convolutional neural network

  • The graph scattering network uses graph wavelets and scattering ideas to define a convolutional neural network on graphs.Its construction adapts wavelets to the graph setting.Source: §2 · p. 2, §2.2 · pp. 3–4

2.1 Wavelets on graphs

  • The construction assumes a weighted, undirected, connected graph without self-loops and defines graph signals through the Laplacian’s spectral representation.Wavelet filters are specified over Laplacian eigenvalues, with graph convolution defined through the graph Fourier transform.Source: §2.1 · pp. 2–3

2.2 Scattering on graphs

  • At each layer, scale paths propagate signals and produce scattering features using successive wavelet operations and an absolute-value nonlinearity.The transform collects features across finite paths and can also be defined for matrices of signals on the same graph.Source: §2.2 · p. 4

3 Energy preservation

The full graph scattering transform preserves input energy, while its propagated energy has a generic layerwise decay bound. In practice, energy can concentrate in only a few layers.

3 Energy preservation

  • The full scattering transform preserves the input norm for signals and signal matrices.The proof combines layerwise energy accounting with a bound on propagated-energy decay.Source: §3 · p. 5, §3.3 · p. 8

3.1 Proof of Proposition 3.2

  • At each layer, propagated energy splits between the next layer and the current scattering outputs, the energy-accounting step used in the norm-preservation argument.This layerwise relation is established for the signal propagation and applied across paths.Source: §3 · p. 5, §3.1 · pp. 6–7

3.2 Proof of Proposition 3.3

  • At every layer after the first, the generic energy decay rate is at least 1 − 2/N; stronger rates require additional assumptions on J, φ, ψ, and L.The stated generic bound is sharp, although specific choices can permit stronger rates.Source: §3 · p. 5, §3.2 · p. 7

3 Energy preservation

  • By the third layer, the transform extracts almost all signal energy on the tested MNIST images, supporting practical use of a small number of layers.The observation is based on 100 randomly selected images and the graph described for the MNIST experiment.Source: §3 · p. 5, Figure 2 · p. 6

3.3 Proof of Theorem 3.1

  • The proof of total norm preservation sums the layerwise energy relation and uses the decay bound to account for energy across the network.The proof applies the resulting identities to signals and then extends the equality to signal matrices.Source: §3 · p. 5, §3.3 · p. 8

4 Permutation covariance and invariance

The section distinguishes permutation covariance from invariance and establishes that graph scattering is covariant and, under a smoothness condition, approximately invariant to permutations. It relates some graph permutations to Euclidean rigid motions while showing that graph topology permits broader rearrangements.

4.2 Permutation covariance and invariance of graph neural networks

  • Graph scattering is permutation covariant and becomes approximately invariant when its scaling function is sufficiently smooth; as J approaches infinity, it becomes invariant.The result also extends to matrix-valued signals with the Frobenius norm.Source: §4 · p. 8, §4.2 · p. 10

4.1 Basic examples of graph permutations, covariance and invariance

  • Weight-matrix and Laplacian transformations are permutation covariant, whereas a max-based output can be invariant without being covariant.The section illustrates why invariance can help classification: thresholding the first feature coordinate avoids confusion from signal relabeling.Source: §4.1 · p. 9

4.3 Generalized graph translations

  • Some graph permutations act as Euclidean rigid motions in consistent planar representations, while others change planar geometry but preserve graph topology.In the second rigid-motion example, the rearranged permuted graph and signal differ from (G, P f).Source: §4.3 · pp. 10–11
  • A modified scattering transform is covariant to the localization operator Tc and approximately invariant when its energy decays sufficiently fast, but no analogous adjustment works for the W-based shift.The stated obstacle is that W does not generally commute with the Laplacian eigenvectors.Source: §4.3 · pp. 12–13

4.4 Proof of Proposition 4.1

  • The covariance proof uses the permuted graph Laplacian and its correspondingly permuted eigenvectors to carry the scattering operations through a permutation.The proof identifies the permuted Laplacian as P L P* and concludes the covariance identity for each path.Source: §4.4 · p. 13

4.5 Proof of Theorem 4.2

  • The invariance proof bounds operator and propagated-signal terms using connectedness, which gives λ1 > 0, and scattering energy estimates.These bounds are combined to establish the theorem, with the matrix-signal extension following immediately.Source: §4.5 · p. 14

5 Stability to signal and graph manipulations

The section establishes stability of graph scattering to signal changes and to constrained graph perturbations, while noting that broader edge edits are difficult to handle generally. Under stated energy, spectral, and filter conditions, an SBM experiment finds negligible relative error for sufficiently large graphs.

5 Stability to signal and graph manipulations

  • Signal perturbations are handled by Lipschitz continuity of graph scattering with respect to the input signal; the same result extends to multi-channel inputs.The section relates this stability to energy preservation.Source: §5 · pp. 14–15
  • Theorem 5.2 establishes stability for sufficiently small edge-weight changes, under eigenvalue-gap, energy-decay, and filter regularity conditions.The stability constant depends on the perturbation and decay and filter parameters.Source: §5 · p. 15
  • The guarantees have boundaries: the small-weight result generally excludes adding or removing edges, and the spectral condition may be strong in practice.The authors note that extending a general guarantee to edge edits is difficult because removing one edge can disconnect some graphs; the eigenvalue-gap assumption also excludes higher eigenvalue multiplicities.Source: §5 · pp. 15–16
  • Theorem 5.3 bounds scattering-feature changes under a controlled Laplacian spectral perturbation, assuming fast energy decay and Lipschitz-continuous filters.The bound's constant depends on the stated decay, filter, and perturbation parameters.Source: §5 · p. 16
  • In the SBM edge-addition/deletion test, relative error decays quickly and becomes negligible for sufficiently large graphs.Each graph is perturbed by reversing one randomly selected pair's connectivity; Figure 8 averages the relative error over 20 sampled graphs for each class size.Source: §5 · p. 16, Figure 8 · p. 17

6 Numerical results

The experiments evaluate graph scattering on MNIST image classification and CORA community detection. Results are competitive with graph-based methods, with a slight improvement reported on CORA.

6.1 Image Classification using MNIST

  • MNIST pixels form a weighted grid; J=3 Shannon scattering produces 10,192 features, reduced to 1,000 by PCA.Source: §6.1 · p. 22
  • Scattering features improve all three MNIST classifiers; three layers outperform two, while a fourth adds no observed improvement.The authors note that three layers almost exhaust the input signal's energy.Source: Table 1 · p. 22, §6.1 · p. 22
  • On MNIST, scattering accuracy is comparable to the best graph-based method and competitive with high efficiency.Source: Table 2 · p. 23, §6.1 · p. 23, Table 3 · p. 23

6.2 Community detection using CORA

  • CORA uses three-layer Shannon scattering on a citation graph with an FCN, trained using 140 labeled vertices.The output dimension is 18,629.Source: §6.2 · p. 23
  • On CORA, graph scattering is comparable to state-of-the-art graph neural networks and demonstrates a slight improvement.Source: §6.2 · p. 23, Table 4 · p. 24

7 Conclusion

The graph scattering network adapts the scattering transform to graphs and, with appropriate graph wavelets, provides permutation invariance and stability to signal and graph manipulations. The authors describe it as a generic, training-free feature extractor, while noting computational and interpretive limits.

7 Conclusion

  • With an appropriate choice of graph wavelets, graph scattering is permutation-invariant and stable to signal and graph manipulations.Source: §7 · p. 24
  • The transform is a generic graph feature extractor that requires no training and can use different wavelets, though experiments used only Shannon wavelets.Source: §7 · p. 24
  • The examples are simple, one somewhat artificial, and the stylized image-classification application does not achieve sufficiently competitive results.Source: §7 · p. 24
  • The authors present the established invariance and stability properties as a conceptual guide to other graph convolutional networks.Source: §7 · p. 24
  • Full graph-Laplacian spectral decomposition is demanding on very large graphs, and deeper-layer high-frequency information remains poorly understood.Source: §7 · p. 24
Loading 1804.00099v2…