The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains
By David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, Pierre Vandergheynst. 2012
4,524 citations recorded by the source corpus.
In applications such as social, energy, transportation, sensor, and neuronal networks, high-dimensional data naturally reside on the vertices of weighted graphs. The emerging field of signal processing on graphs merges algebraic and spectral graph theoretic concepts with computational harmonic analysis to process such signals on graphs. In this tutorial overview, we outline the main challenges of the area, discuss different ways to define graph spectral domains, which are the analogs to the classical frequency domain, and highlight the importance of incorporating the irregular structures of graph data domains when processing signals on graphs. We then review methods to generalize fundamental operations such as filtering, translation, modulation, dilation, and downsampling to the graph setting and survey the localized, multiscale transforms that have been proposed to efficiently extract information from high-dimensional data on graphs. We conclude with a brief discussion of open issues and possible extensions.
Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics, 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 Artificial Intelligence
- Michael M. Bronstein
- Jure Leskovec
- Yoshua Bengio
- William L. Hamilton
- Philip S. Yu
- Xavier Bresson
- Percy Liang
- Matthias Fey
In Molecular Biology
- Matthias Fey
- Jure Leskovec
- Marinka Zitnik
- Michael M. Bronstein
- Pierre Vandergheynst
- Xavier Bresson
- William L. Hamilton
- José M. F. Moura
In Statistical and Nonlinear Physics
- Michael M. Bronstein
- Jure Leskovec
- Pierre Vandergheynst
- Xavier Bresson
- Matthias Fey
- Marinka Zitnik
- William L. Hamilton
- Wenwu Zhu
In Graph Learning
- Michael M. Bronstein
- Jure Leskovec
- Matthias Fey
- Xavier Bresson
- William L. Hamilton
- Stephan Günnemann
- Federico Monti
- Pierre Vandergheynst
Citations in the corpus
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, methodology): “This work leverages the recent works of [12, 8, 4, 15, 14, 32] to introduce an efficient implementation of CNNs on irregular domains represented here as graphs.”
- Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, background): “More recent works tried to generalize signal processing methods to graph-based data [47].”
- Representation Learning on Graphs with Jumping Knowledge Networks (2018, methodology): “Spectral graph convolutional neural networks apply convolution on graphs by using the graph Laplacian eigenvectors as the Fourier atoms (Bruna et al., 2014; Shuman et al., 2013; Defferrard et al., 2016).”
- Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks (2017, methodology): “These approaches can be generally related to the field of signal processing on graphs (Shuman et al., 2013), extending classical harmonic analysis methods to non-Euclidean domains.”
- Geometric Deep Learning: Going beyond Euclidean data (2016, methodology): “…problem, the domain (social graph) is assumed to be fixed; methods of signal processing on graphs , which have previously been reviewed in Signal Processing Magazine [51], can be applied to this setting, in particular, in order to define an operation similar to convolution in the spectral domain.”
- Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning (2018, methodology): “Spectral GCNNs define the convolution by decomposing a graph signal s ∈ R n (a scalar for each vertex) on the spectral domain and then applying a spectral filter g θ (a function of eigenvalues of L sym ) on the spectral components (Bruna et al. 2014; Sandryhaila and Moura 2013; Shuman et al. 2013).”
- Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks (2019, methodology): “GNNs follow a simple neighborhood aggregation procedure motivated by two major perspectives: The generalization of classical CNNs to irregular domains (Shuman et al., 2013), and their strong relations to the Weisfeiler & Lehman (1968) algorithm (Xu et al., 2019; Morris et al., 2019).”
- Dynamic Graph CNN for Learning on Point Clouds (2018, methodology): “[2015] generalized convolution to graphs via the Laplacian eigenvectors [Shuman et al. 2013].”
- SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels (2017, background): “The former is based on spectral graph theory [5], where eigenvalues of a graph’s Laplacian matrix are interpreted as frequencies of node signals [22].”
- Distance Metric Learning Using Graph Convolutional Networks: Application to Functional Brain Networks (2017, methodology): “Spectral graph convolutional networks filter signals defined on a common graph structure for all samples, since these operations are parametrised on the graph Laplacian.”
- A Multiscale Pyramid Transform for Graph Signals (2013, background): “However, multiscale transforms such as wavelets and filter banks designed to process analog and discrete-time signals and images cannot be directly applied to analyze high-dimensional data residing on the vertices of a weighted graph, as they do not capture the intrinsic topology of the underlying…”
- Label Efficient Semi-Supervised Learning via Graph Filtering (2019, methodology): “In graph signal processing [44], the eigenvalues and eigenvectors of the graph Laplacian correspond to frequencies and Fourier basis in classical harmonic analysis.”
- Pose2Mesh: Graph Convolutional Network for 3D Human Pose and Mesh Recovery from a 2D Human Pose (2020, methodology): “To this end, MeshNet uses the spectral graph convolution [8,55], which can be defined as the multiplication of a signal x ∈ R with a filter gθ = diag(θ) in Fourier domain as follows:”
- Spectral Graph Skeletons for 3D Action Recognition (2014, methodology): “Recent approaches for using graphs in machine learning include graph kernels [1,14,38], generalizations of signal processing frameworks to the graph domain [7, 24], and also graph wavelets [5,6,12,20,22], such as the spectral graph wavelet transform [12].”
- Graph-based Isometry Invariant Representation Learning (2017, methodology): “Similarly to regular 1-D or 2-D signals, the graph signals can be efficiently analysed via harmonic analysis and processed in the spectral domain (Shuman et al., 2013).”
- Spectral–Spatial Graph Convolutional Networks for Semisupervised Hyperspectral Image Classification (2019, background): “We provide theoretical analysis for convolution on graph signal, which can multiply each frequency of graph signal x̄ by a filter gθ parameterized by Fourier coefficients θ ∈ RN in the Fourier domain gθ x̄ = UgθUT x̄ (6) where the eigenvectors U represent an analog to the discrete Fourier transform ”
- Exploiting Spatial-Temporal Relationships for 3D Pose Estimation via Graph Convolutional Networks (2019, methodology): “Motivated by the natural graph-based representation for a series of skeletal forms and inspired by recent advances in graph convolution networks (GCNs) [9, 20, 41, 50], in this work, we propose to utilize GCNs to exploit spatial and temporal relationships for 3D pose estimation.”