Wavelets on Graphs via Spectral Graph Theory
By David K. Hammond, Pierre Vandergheynst, Rémi Gribonval. 2009
2,312 citations recorded by the source corpus.
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 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 L. We highlight potential applications of the transform through examples of wavelets on graphs corresponding to a variety of different problem domains.
Subfields: Applied Mathematics, Computer Vision and Pattern Recognition, Media Technology, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Antonio Ortega
- José M. F. Moura
- Pierre Vandergheynst
- Aliaksei Sandryhaila
- David I. Shuman
- Pascal Frossard
- Sunil K. Narang
- Max Welling
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Ming-Hsuan Yang
- Xiaogang Wang
- Trevor Darrell
- Jitendra Malik
- Alan L. Yuille
- Andrea Vedaldi
In Media Technology
- Pierre Vandergheynst
- Aliaksei Sandryhaila
- Antonio Ortega
- José M. F. Moura
- David I. Shuman
- K. Shinoda
- Nakamasa Inoue
- Tommi Kerola
In Graph Learning
- Jure Leskovec
- Stephan Günnemann
- Michael M. Bronstein
- William L. Hamilton
- Marinka Zitnik
- Matthias Fey
- Xavier Bresson
- Max Welling
Citations in the corpus
- Semi-Supervised Classification with Graph Convolutional Networks (2016, methodology): “Firstly, we introduce a simple and well-behaved layer-wise propagation rule for neural network models which operate directly on graphs and show how it can be motivated from a first-order approximation of spectral graph convolutions (Hammond et al., 2011).”
- Representation Learning on Graphs with Jumping Knowledge Networks (2018, background): “Graph Convolu-tional Networks (GCN) (Kipf & Welling, 2017), initially motivated by spectral graph convolutions (Hammond et al., 2011; Defferrard et al., 2016), are a specific instantiation of this framework (Gilmer et al., 2017), of the form where deg ( v ) is the degree of node v in G .”
- Generating 3D faces using Convolutional Mesh Autoencoders (2018, methodology): “The problem is addressed by formulating mesh filtering with a kernel gθ using a recursive Chebyshev polynomial [17, 23].”
- The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (2012, methodology): “Notable examples in this category include diffusion wavelets [24], [44], spectral graph wavelets [41], and graph quadrature mirror filter banks (graph-QMF filter banks) [37].”
- Distance Metric Learning Using Graph Convolutional Networks: Application to Functional Brain Networks (2017, methodology): “To render the filters K-localised in space and reduce their computational complexity they can be approximated by a truncated expansion in terms of Chebyshev polynomials of order K [6].”
- BrainGNN: Interpretable Brain Graph Neural Network for fMRI Analysis (2020, background): “[20] proposed a 490 spectral graph convolution which defines convolution for graphs in the spectral 491 domain.”
- Discrete Signal Processing on Graphs (2012, background): “For example, directed (acyclic) graphs [11], [12] represent Bayesian networks where each random variable is independent of others given the variables defined on its parent nodes.”
- Image denoising with nonlocal spectral graph wavelets (2010, methodology): “In ([1], Theorem 5.”
- Graph convolutional networks: a comprehensive review (2019, methodology): “In addition, to further reduce the computational complexity, the Chebyshev polynomial approximation [35] is used to compute the spectral graph convolution.”
- Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, methodology): “(2), the generalization of the notion of frequency and Fourier transform for graph signals [13].”
- N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification (2018, methodology): “Therefore, the low-rank approximation of the eigendecomposition [12] is still valid, and a one layer of [14] utilizing Âk should still approximatemultiplication in the Fourier domain.”