Vertex-Frequency Analysis on Graphs

By David I. Shuman, Benjamin Ricaud, Pierre Vandergheynst. 2013

407 citations recorded by the source corpus.

One of the key challenges in the area of signal processing on graphs is to design dictionaries and transform methods to identify and exploit structure in signals on weighted graphs. To do so, we need to account for the intrinsic geometric structure of the underlying graph data domain. In this paper, we generalize one of the most important signal processing tools - windowed Fourier analysis - to the graph setting. Our approach is to rst dene

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, background): “In [6], the same authors proposed a CNN-type architecture in the spatio-frequency domain us-ing the windowed Fourier transform formalism [48].”
Geometric Deep Learning: Going beyond Euclidean data (2016, background): “The generalization of such a construction to non-Euclidean domains requires the definition of translation and modulation operators [83].”
SyncSpecCNN: Synchronized Spectral CNN for 3D Shape Segmentation (2016, background): “Functional map Different shapes deﬁne shape graphs with varied bases and spectral domains, which results in incomparable graph vertex function.”
Learning shape correspondence with anisotropic convolutional neural networks (2016, methodology): “Another intrinsic CNN construction (Localized Spectral CNN) using an alternative charting technique based on the windowed Fourier transform [22] was proposed in [4].”
Learning Structural Node Embeddings via Diffusion Wavelets (2017, methodology): “For simplicity, we use the heat kernel g s ( λ ) = e − λs throughout this paper, but our results apply to any low-pass ﬁlter kernel (Shuman et al., 2016).”
Robust Spatial Filtering With Graph Convolutional Neural Networks (2017, background): “In [12], [18], it is shown that a K-order polynomial formulation of the graph Laplacian perform a K-hop filtering operation, despite being a “spectral” operation.”
Parallel Transport Convolution: A New Tool for Convolutional Neural Networks on Manifolds (2018, methodology): “Method Filter Type Support Extraction Directional Transferable Deformable Spectral [13] Spectral Global Eigen Yes No No TFG [14] Spectral Global Eigen Yes No No WFT [18] Spectral Local Windowed Eigen Yes No No GCNN [16] Patch Local Variable No Yes Yes ACNN [17] Patch Local Fixed Yes Yes No PTC Geode”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, methodology): “The requirement of having a covariance matrix diagonalizable by the eigenvectors of the Laplacian is itself adopted as a definition in [42], where the requirement is shown to be equivalent to statistical invariance with respect to the non-isometric translation operator introduced in [59].”
Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, background): “Representative works include studies on the generalizations of the Fourier transform [9], [10], the wavelet transform [11]–[16], dictionary learning methods [17], [18], and time-frequency analysis [19], [20] on graphs, with applications to image processing [21], brain network classification [22], mo”
Toward an uncertainty principle for weighted graphs (2015, background): “Graph signal processing [3] is a generalization of classical Fourier analysis in which the support for the signal is not necessarily a uniform sampling in time but may be a more complex structure, represented as a graph.”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “Even though fi changes with the chosen vertex, it was proved in [92] that this signal is localized around i in a way that only depends on the smoothness of the filter h.”
Accelerated filtering on graphs using Lanczos method (2015, background): “This framework, called graph signal-processing, has recently become a general ﬁeld of research [16, 17] and applications of graph signal-processing can be found in many different areas.”
Geometric deep learning (2016, background): “In [79, 10] these operations were deﬁned in the frequency domain.”
GSPBOX: A toolbox for signal processing on graphs (2014, methodology): “compute_ fourier_basis [9] that adds the fields U, e and lmax to the graph structure.”
Anisotropic Diffusion Descriptors (2016, methodology): “Boscaini et al. [B ∗ 15] used localized spectral CNNs based on vertex-frequency analysis [SRV15] to learn intrinsic 3D shape descriptors.”