PaperlayerView exact revision on arXiv

Source-linked AI summary

Wavelets on Graphs via Spectral Graph Theory

David K Hammond, Pierre Vandergheynst, Rémi Gribonval

arXiv:0912.3848v1math.FAcs.IT

TL;DR

Wavelet transforms are difficult to define on arbitrary graph domains because ordinary scaling and translation lack natural graph analogues. The paper constructs spectral graph wavelets from the graph Laplacian, establishing localization and invertibility properties while providing an efficient Chebyshev-based computation scheme.

  • Problem

    Wavelet methods need an extension to functions on arbitrary weighted graphs and other irregular domains where conventional spatial scaling and translation are undefined.

  • Method

    The paper defines graph-domain scaling spectrally through the Laplacian and computes the transform approximately with Chebyshev polynomials instead of explicit diagonalization.

  • Results

    The transform is invertible under an admissibility condition, localized at fine scales, forms a frame at discretized scales, and applies to large graphs through efficient approximation.

  • Takeaways & Limitations

    Spectral graph wavelets provide a flexible framework for analyzing signals on arbitrary weighted graphs and domains represented through graph connectivity.

  • Takeaways & Limitations

    For non-normalized graph Laplacians, zero-mean wavelets cannot recover the signal mean on a discrete graph domain.

Abstract

from arXiv · show

We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral decomposition of the discrete graph Laplacian $Ł$. Given a wavelet generating kernel $g$ and a scale parameter $t$, we define the scaled wavelet operator $T_g^t = g(tŁ)$. The spectral graph wavelets are then formed by localizing this operator by applying it to an indicator function. Subject to an admissibility condition on $g$, this procedure defines an invertible transform. We explore the localization properties of the wavelets in the limit of fine scales. Additionally, we present a fast Chebyshev polynomial approximation algorithm for computing the transform that avoids the need for diagonalizing $Ł$. We highlight potential applications of the transform through examples of wavelets on graphs corresponding to a variety of different problem domains.

1 Introduction

The paper develops wavelet transforms for data on irregular domains by using spectral graph theory to define scaling on arbitrary weighted graphs. It establishes invertibility, localization, efficient computation, and broad application scope.

  • Motivation: Irregular data domains include networks, manifolds, meshes, and point clouds, motivating signal-processing methods beyond regular Euclidean spaces.Weighted graphs can represent network topology, geometric meshes, damaged or irregular grids, and similarity relationships among feature vectors.
  • Applications: The framework is intended for graph-valued data arising in networks, geometric domains, and feature-vector similarity structures, with examples spanning multiple application domains.The paper positions the transform as applicable wherever domain connectivity is available, without requiring vertex positions.
  • Problem: Classical wavelet scaling and translation do not extend directly to arbitrary graphs because graph vertices lack a natural scalar-coordinate interpretation.The paper addresses this obstacle through the spectral graph domain, the graph analogue of the Fourier domain.
  • Method: The spectral graph wavelet transform defines scaling spectrally and forms localized wavelets by applying the resulting operator to impulses at individual vertices.The construction uses a kernel-based operator and produces coefficients equivalent to inner products with graph wavelets.
  • Theory: Subject to an admissibility condition, the transform is formally invertible; discretized scales produce a redundant frame whose overcompleteness equals the number of selected spatial scales.The paper also gives a condition for computing frame bounds from the scale selection.
  • Computation: A low-dimensional Chebyshev approximation avoids Laplacian diagonalization and enables efficient computation through sparse matrix-vector multiplications.The approach targets graphs larger than a few thousand vertices and supports approximate forward-transform computation.

2 Classical Wavelet Transform

Classical wavelets generate localized coefficients by scaling and translating a mother wavelet, with scaling expressible as a Fourier-domain multiplier. This formulation motivates a graph analogue because direct spatial scaling is undefined on graph vertices.

  • Classical construction: The continuous wavelet transform analyzes square-integrable functions using a mother wavelet whose translated and scaled copies generate coefficients by inner products.The transform uses positive scales and a specified scaling convention.
  • Inversion: Admissibility permits inversion of the continuous wavelet transform when the wavelet satisfies the zero-mean condition.The inverse reconstructs the signal from wavelet coefficients and wavelets across scales and locations.
  • Graph extension: Directly extending spatial scaling to graphs is problematic because a graph vertex has no interpretation under multiplication by a real scale.The paper therefore transfers scaling to the Fourier domain before generalizing it through graph spectral theory.
  • Fourier-domain formulation: At each scale, the wavelet transform can be viewed as a Fourier multiplier operator determined by a scaled frequency-domain filter.For admissible wavelets, the filter is bandpass because its value at zero frequency vanishes.
  • Localization: Wavelet translation can be implemented by localizing the wavelet operator with an impulse, yielding the wavelet centered at the impulse location for real-valued even wavelets.This operator-based view separates localization from the direct spatial construction.

3 Weighted Graphs and Spectral Graph Theory

The paper models finite weighted graphs through adjacency and degree structures, defines the graph Laplacian, and uses its eigenvectors and eigenvalues as the graph Fourier basis. This spectral representation supports wavelet construction on graph vertices.

  • Spectral foundation: The graph spectral domain generalizes the Fourier-domain formulation of classical wavelets to functions defined on weighted-graph vertices.This analogy provides the foundation for the spectral graph wavelet transform.
  • Weighted-graph notation: A finite weighted graph consists of vertices, edges, and positive edge weights, with functions on vertices represented as vectors in R^N.The adjacency matrix records edge weights, while the degree matrix stores weighted incident-edge sums.
  • Graph assumptions: The paper considers undirected graphs with symmetric adjacency matrices and permits loops, while excluding negative edge weights.These assumptions define the graph class used in the presentation.
  • Graph Laplacian: The non-normalized graph Laplacian is L = D − A, and its quadratic form reflects weighted differences between values on connected vertices.The Laplacian is the central operator used to define graph frequencies and spectral wavelets.
  • Laplacian choice: Normalized and non-normalized Laplacians can both define spectral graph wavelet transforms, but their eigenvectors and resulting transforms are not equivalent.The paper uses the non-normalized form unless otherwise noted.
  • Graph Fourier transform: The graph Fourier transform expands vertex signals in the complete orthonormal eigenbasis of the real symmetric graph Laplacian.For a connected graph, eigenvalues are nonnegative and the zero eigenvalue has multiplicity one.

4 Spectral Graph Wavelet Transform

The SGWT defines graph wavelets as Laplacian spectral operators localized at vertices, with scaling functions added to stabilize low-frequency recovery at discrete scales.

  • Transform definition: The SGWT is determined by a kernel g acting as a Fourier-domain band-pass filter on the graph Laplacian spectrum.The kernel satisfies g(0) = 0 and limx→∞g(x) = 0.
  • Transform definition: At scale t, the wavelet operator is T_g^t = g(tL), with t allowed to vary over positive real values.Although graph vertices form a discrete spatial domain, the kernel domain is continuous.
  • Transform definition: Applying the wavelet operator to a single-vertex impulse localizes the operator and produces the spectral graph wavelets.Wavelet coefficients are obtained by inner products with these localized wavelets or directly through the wavelet operators.
  • Scaling functions: The wavelets are orthogonal to the null eigenvector, so scaling functions are introduced to represent low-frequency graph content stably.The scaling functions are analogous to lowpass residual functions in classical wavelet analysis.
  • Scaling functions: For discretized scales, stable recovery requires G(λ) = h(λ)^2 + Σ_j g(t_jλ)^2 to remain nonzero on the Laplacian spectrum.The scaling-function generator h is uncoupled from g provided the resulting spectral tiling is reasonable.

5 Transform properties

The transform has an inverse under an admissibility condition, becomes localized at fine scales, and forms redundant frames when scales are discretized, with practical limits for discrete reconstruction and zero-frequency recovery.

  • 5.1 Continuous SGWT Inverse: Subject to the kernel admissibility condition, the continuous-scale transform reconstructs the zero-mean component, while the omitted zero-frequency term is restored separately.The complete reconstruction is f = f# + f̂(0)χ0.
  • 5.1 Continuous SGWT Inverse: For the non-normalized Laplacian, the zero-frequency component is the mean, which zero-mean wavelets alone cannot recover on a discrete graph.The paper attributes this difference from the continuous wavelet transform to the discrete nature of the graph domain.
  • 5.1 Continuous SGWT Inverse: The continuous-scale reconstruction formula may be impractical when coefficients are available only at finitely many scales.The paper revisits reconstruction for discrete scales in later sections.
  • 5.2 Localization in small scale limit: For sufficiently regular kernels, normalized wavelets centered at a vertex vanish on sufficiently distant vertices as t approaches zero.This establishes fine-scale spatial localization in addition to spectral localization.
  • 5.2 Localization in small scale limit: If dG(m,n) > s, then the s-th power of the graph Laplacian has zero matrix entry at (m,n), linking shortest-path separation to localization.The result holds for normalized and non-normalized Laplacians.
  • 5.2 Localization in small scale limit: Theorem 5.7 provides a quantitative fine-scale bound for wavelet values at vertices more than K graph-distance steps from the center.The bound holds for sufficiently small t under the theorem’s kernel hypotheses.
  • 5.3 Spectral Graph Wavelet Frames: At discretized scales, the wavelets and scaling functions form a frame, and the frame bounds govern representation stability and inversion convergence.The paper examines these bounds to assess how well the vectors represent graph signals.

6 Polynomial Approximation and Fast SGWT

The fast SGWT replaces Laplacian diagonalization with low-order Chebyshev polynomial approximations, enabling sparse-graph computation through matrix-vector multiplications while supporting approximate adjoints and reconstruction operations.

  • Direct diagonalization scales poorly for large graphs, with general-purpose eigensolvers requiring O(N^3) computation and O(N^2) memory.
  • The fast algorithm approximates each scaled kernel g with a low-order polynomial and evaluates it using repeated matrix-vector multiplications by L.This avoids explicitly diagonalizing the Laplacian.
  • Truncated Chebyshev polynomials are used because their wavelet-kernel error is only slightly above minimax error and can be lower where the kernel varies smoothly.For degree m = 20, the reported maximum errors are 0.206 for truncated Chebyshev and 0.107 for minimax approximation.
  • For sparse graphs, the fast SGWT has complexity O(M|E| + N Σ_j M_j), and becomes O(N) when |E| scales linearly with N.
  • The approximate transform, its adjoint, and W*W can all be computed efficiently with the same Chebyshev scheme.This supports inversion and regularization methods based on the adjoint or composition operator.

7 Reconstruction

Because the SGWT is overcomplete, reconstruction uses a pseudoinverse; conjugate gradients provides an iterative route that avoids directly inverting the large normal-equation matrix.

  • The SGWT maps an N-dimensional input to N(J + 1) coefficients, making it an overcomplete transform with infinitely many left-inverses.
  • The pseudoinverse (W*W)^-1W* is a natural reconstruction choice and has the minimum-norm property.
  • For modified coefficient sets, the pseudoinverse projects onto the transform range before inverting on that range.
  • Conjugate gradients solves (W*W)f = W*c iteratively, with each step dominated by applying W*W to one vector.

8 Implementation and examples

The paper specifies graph-adapted kernels and scales, then demonstrates spectral graph wavelets on point clouds, transportation and cortical graphs, and an irregular lake domain.

  • 8.1 SGWT design details: The generating kernel is designed for fine-scale localization, using monic-power behavior near zero, power-law decay at large arguments, and a continuous cubic-spline transition.
  • 8.2 Illustrative examples : spectral graph wavelet gallery: On the Swiss roll, wavelets are centered at one vertex and displayed across four scales alongside a scaling function.The underlying weighted graph uses Gaussian edge weights with σ = 0.1, K = 20, and J = 4.
  • 8.1 SGWT design details: Wavelet scales are logarithmically spaced and adapted to the Laplacian spectrum through λmax and the design parameter K.
  • 8.2 Illustrative examples : spectral graph wavelet gallery: The Minnesota example applies four-scale wavelets to an unweighted road-intersection graph, using spatial coordinates only for display.
  • 8.2 Illustrative examples : spectral graph wavelet gallery: On Lake Geneva, comparison with truncated complete-mesh wavelets provides direct evidence that graph wavelets adapt automatically to arbitrarily shaped domains.

9 Conclusions and Future Work

The paper presents spectral graph wavelets as a general framework for arbitrary weighted graphs, with scalable computation and applications beyond the transform itself. It also identifies open challenges involving redundancy, graph structure, directionality, connectivity design, and kernel selection.

  • Conclusions: The framework constructs wavelets on arbitrary weighted graphs, using the graph Laplacian’s spectral domain and yielding localized wavelets with calculable frame bounds.The construction is presented as an analogue of classical Fourier-domain wavelet operators.
  • Computational applications: Chebyshev polynomial approximation avoids explicit graph-Laplacian diagonalization and enables applying the transform to large graphs.The same approximation scheme can support filtering on irregular domains and approximate diffusion kernels for large sparse graphs.
  • Future work: The transform is overcomplete by a factor of J+1 because it does not subsample wavelets at coarser spatial scales.Choosing masks that preserve frame bounds while limiting overcompleteness is identified as a difficult future problem on arbitrary weighted graphs.
  • Future work: Automatically defining graph contractions at each scale remains difficult, although repeated contractions could provide a multiscale graph representation.The contracted graph is formed by partitioning vertices and summing edge weights between partitions.
  • Future work: The wavelets are not directional, and directionality may require additional local structure unavailable in completely arbitrary graphs.For graphs sampled from known orientable manifolds, local directionality may be inferred from the original manifold.
  • Future work: The examples use a somewhat ad-hoc generating kernel g, leaving optimization of g and spatial scales for different applications unresolved.The paper specifically notes that frame-bound optimization was not performed.
Loading 0912.3848v1…