A Multiscale Pyramid Transform for Graph Signals

By David I. Shuman, Mohammad Javad Faraji, Pierre Vandergheynst. 2013

179 citations recorded by the source corpus.

Multiscale transforms 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 graph data domain. In this paper, we adapt the Laplacian pyramid transform for signals on Euclidean domains so that it can be used to analyze high-dimensional data residing on the vertices of a weighted graph. Our approach is to study existing methods and develop new methods for the four fundamental operations of graph downsampling, graph reduction, and filtering and interpolation of signals on graphs. Equipped with appropriate notions of these operations, we leverage the basic multiscale constructs and intuitions from classical signal processing to generate a transform that yields both a multiresolution of graphs and an associated multiresolution of a graph signal on the underlying sequence of graphs.

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

In Graph Learning

Citations in the corpus

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “And the last step is the graph pooling operation that trades spatial resolution for higher filter resolution.”
Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017, neutral): “[35, 28], which works by repeated downsampling and graph reduction of the input graph.”
Data-Driven Tree Transforms and Metrics (2017, background): “data [18], [20], the multiscale nature of our transform arises from partitioning of the data via the tree.”
Spectral Clustering with Graph Neural Networks for Graph Pooling (2019, methodology): “Node decimation pooling (NDP) is a method originally proposed in graph signal processing literature (Shuman et al., 2016), which has been adapted to perform pooling in GNNs (Simonovsky & Komodakis, 2017; Bianchi et al., 2019b).”
Graph Neural Networks With Convolutional ARMA Filters (2019, methodology): “Furthermore, Lnew does not introduce self-loops and guarantees spectral interlacing and resistance distance preservation (Shuman et al., 2016).”
Deep Learning on Graphs: A Survey (2018, unknown): “ECC [63] adopted another hierarchical clustering method by performing eigendecomposition [86].”
GSPBOX: A toolbox for signal processing on graphs (2014, methodology): “This chapter should help making the connection between the theoretical concepts introduced in [7, 9, 6] and the technical documentation provided with the toolbox.”
Graph Based Convolutional Neural Network (2016, methodology): “Common methods of generating V̂ are to either select a subset of V to carry forward to Ĝ [18] or to form completely new set of nodes V̂ from some aggregation of related nodes within V [16].”