# Wavelets on Graphs via Spectral Graph Theory

@article{Hammond2009WaveletsOG, title={Wavelets on Graphs via Spectral Graph Theory}, author={David K. Hammond and Pierre Vandergheynst and R{\'e}mi Gribonval}, journal={ArXiv}, year={2009}, volume={abs/0912.3848} }

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 graph analogue of the Fourier domain, namely the spectral decomposition of the discrete graph Laplacian L. Given a wavelet generating kernel g and a scale parameter t, we define the scaled wavelet operator Ttg = g(tL). The spectral graph wavelets are then formed by localizing this operator by applying it to… Expand

#### 1,446 Citations

Splines and Wavelets on Circulant Graphs

- Mathematics, Computer Science
- Applied and Computational Harmonic Analysis
- 2019

This work leverage the inherent vanishing moment property of the circulant graph Laplacian operator, and by extension, the e-graph LaPLacian, for the design of vertex-localized and critically-sampled higher-order graph (e-)spline wavelet filterbanks, which can reproduce and annihilate classes of (exponential) polynomial signals oncirculant graphs. Expand

An adaptive spectral graph wavelet method for PDEs on networks

- Computer Science
- Adv. Comput. Math.
- 2021

An adaptive spectralgraph wavelet method to solve partial differential equations on network-like structures using so-called spectral graph wavelets based on the discrete graph Laplacian is proposed. Expand

The Spectral Graph Wavelet Transform: Fundamental Theory and Fast Computation

- Mathematics
- Signals and Communication Technology
- 2018

The spectral graph wavelet transform (SGWT) defines wavelet transforms appropriate for data defined on the vertices of a weighted graph. Weighted graphs provide an extremely flexible way to model the… Expand

The graph FRI framework-spline wavelet theory and sampling on circulant graphs

- Mathematics, Computer Science
- 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
- 2016

It is demonstrated that for a sufficiently banded adjacency matrix A of G, the obtained coarse graph preserves the original generating set S of G in a scheme of spectral sampling with respect to the original eigenbasis of A. Expand

Tight Wavelet Frames on Multislice Graphs

- Computer Science, Mathematics
- IEEE Transactions on Signal Processing
- 2013

This framework generalizes the recently proposed spectral graph wavelet transform (SGWT) and proposes a design for multislice graphs that is based on the higher-order singular value decomposition (HOSVD), a powerful tool from multilinear algebra. Expand

On the Graph Fourier Transform for Directed Graphs

- Mathematics, Computer Science
- IEEE Journal of Selected Topics in Signal Processing
- 2017

This paper addresses the general case of directed graphs and proposes an alternative approach that builds the graph Fourier basis as the set of orthonormal vectors that minimize a continuous extension of the graph cut size, known as the Lovász extension. Expand

On the sparsity of wavelet coefficients for signals on graphs

- Computer Science, Engineering
- Optics & Photonics - Optical Engineering + Applications
- 2013

This paper begins to explore notions of global and local regularity of graph signals, and analyzes the decay of spectral graph wavelet coefficients for regular graph signals. Expand

Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Frames

- Mathematics, Computer Science
- IEEE Transactions on Signal Processing
- 2015

This paper considers the problem of designing spectral graph filters for the construction of dictionaries of atoms that can be used to efficiently represent signals residing on weighted graphs, and proposes filters adapted to the distribution of graph Laplacian eigenvalues that lead to atoms with better discriminatory power. Expand

Shape Analysis Using the Spectral Graph Wavelet Transform

- Computer Science
- e-Science
- 2013

The proposed framework for morphological characterization of galaxies based on the Spectral Graph Wavelet Transform has been assessed through two case studies, namely, the case study of analyzing 2D binary images from shapes and preliminary results of 2D gray tone images from galaxies. Expand

Lifting scheme on graphs with application to image representation

- Computer Science, Mathematics
- 2013 IEEE Global Conference on Signal and Information Processing
- 2013

A new multiscale transform for scalar functions defined on the vertex set of a general undirected weighted graph is proposed and a comparison with standard orthogonal and biorthogonal wavelet transforms is provided. Expand

#### References

SHOWING 1-10 OF 97 REFERENCES

Diffusion Wavelets

- 2004

Our goal in this paper is to show that many of the tools of signal processing, adapted Fourier and wavelet analysis can be naturally lifted to the setting of digital data clouds, graphs and… Expand

Diffusion wavelet packets

- Mathematics
- 2006

Abstract Diffusion wavelets can be constructed on manifolds, graphs and allow an efficient multiscale representation of powers of the diffusion operator that generates them. In many applications it… Expand

Multiscale methods for data on graphs and irregular multidimensional situations

- Mathematics
- 2009

For regularly spaced one-dimensional data, wavelet shrinkage has proven to be a compelling method for non-parametric function estimation. We create three new multiscale methods that provide… Expand

DECOMPOSITION OF HARDY FUNCTIONS INTO SQUARE INTEGRABLE WAVELETS OF CONSTANT SHAPE

- Mathematics
- 1984

An arbitrary square integrable real-valued function (or, equivalently, the associated Hardy function) can be conveniently analyzed into a suitable family of square integrable wavelets of constant… Expand

Diffusion kernels on graphs and other discrete structures

- Computer Science
- ICML 2002
- 2002

This paper focuses on generating kernels on graphs, for which a special class of exponential kernels, based on the heat equation, are proposed, called diffusion kernels, and shows that these can be regarded as the discretization of the familiar Gaussian kernel of Euclidean space. Expand

Exact reconstruction with directional wavelets on the sphere

- Physics
- 2008

A new formalism is derived for the analysis and exact reconstruction of band-limited signals on the sphere with directional wavelets. It represents an evolution of a previously developed wavelet… Expand

Diffusion polynomial frames on metric measure spaces

- Mathematics
- 2008

We construct a multiscale tight frame based on an arbitrary orthonormal basis for the L2 space of an arbitrary sigma finite measure space. The approximation properties of the resulting multiscale are… Expand

From graph to manifold Laplacian: The convergence rate

- Mathematics
- 2006

Abstract The convergence of the discrete graph Laplacian to the continuous manifold Laplacian in the limit of sample size N → ∞ while the kernel bandwidth e → 0 , is the justification for the success… Expand

From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians

- Mathematics, Computer Science
- COLT
- 2005

This paper establishes the strong pointwise consistency of a family of graph Laplacians with data-dependent weights to some weighted Laplace operator. Expand

Diffusion Kernels on Graphs and Other Discrete Input Spaces

- Mathematics, Computer Science
- ICML
- 2002

This paper proposes a general method of constructing natural families of kernels over discrete structures, based on the matrix exponentiation idea, and focuses on generating kernels on graphs, for which a special class of exponential kernels called diffusion kernels are proposed. Expand