Discrete Signal Processing on Graphs

By Aliaksei Sandryhaila, José M. F. Moura. 2012

1,572 citations recorded by the source corpus.

In social settings, individuals interact through webs of relationships. Each individual is a node in a complex network (or graph) of interdependencies and generates data, lots of data. We label the data by its source, or formally stated, we index the data by the nodes of the graph. The resulting signals (data indexed by the nodes) are far removed from time or image signals indexed by well ordered time samples or pixels. DSP, discrete signal processing, provides a comprehensive, elegant, and efficient methodology to describe, represent, transform, analyze, process, or synthesize these well ordered time or image signals. This paper extends to signals on graphs DSP and its basic tenets, including filters, convolution, z-transform, impulse response, spectral representation, Fourier transform, frequency response, and illustrates DSP on graphs by classifying blogs, linear predicting and compressing data from irregularly located weather stations, or predicting behavior of customers of a mobile service provider.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

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 Computer Vision and Pattern Recognition

Citations in the corpus

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning (2018, methodology): “We compare our methods with several state-of-the-art methods, including GCN with validation (GCN+V); GCN without validation (GCN-V); GCN with Chebyshev ﬁlter (Cheby) (Kipf and Welling 2017); label propagation using ParWalks (LP) (Wu et al. 2012); Planetoid (Yang, Cohen, and Salakhutdinov 2016); Deep”
A Comprehensive Survey on Graph Neural Networks (2019, methodology): “Background Spectral-based methods have a solid mathematical foundation in graph signal processing [82], [83], [84].”
Data-Free Knowledge Distillation for Deep Neural Networks (2017, methodology): “In the framework presented in [20], a graph Fourier basis simply corresponds to the Jordan basis of the graph adjacency matrix A: A = V JV − 1 , where F = V − 1 is the graph Fourier transform matrix, with the frequency content ˆ s of s given by ˆ s = Fs .”
Discrete Signal Processing on Graphs: Sampling Theory (2015, background): “2) Simulations: We consider 150 weather stations in the United States that record local temperatures [5].”
General-Purpose Deep Point Cloud Feature Extractor (2018, background): “[38], which proposes a shift-invariant convolutional filter as a polynomial of the adjacency matrix, as in (1).”
Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies (2015, methodology): “t;i ju j+ P u=2S u1 u, where 1 u is SUBMITTED TO IEEE TRANSACTIONS ON SIGNAL PROCESSING 10 TABLE III: Comparison of complexity of different sampling set selection algorithms. Method in [11] Method in [12] Proposed Method Eigen-pair computations O((jEjjSj+ CjSj3)T 1) O((jEjjSj+ CjSj3)T 1) O(kjEjjSjT ”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, background): “, topology), associated with the graph G one can introduce the so-called graph-shift operator S [48].”
Learning Graphs From Data: A Signal Representation Perspective (2018, methodology): “Graph learning: A signal representation perspective There is a growing interest in the signal processing community to analyze signals that are supported on the vertex set of weighted graphs, leading to the fast-growing field of GSP [3], [12].”
Random walks and diffusion on networks (2016, background): “[134, 135] and will be explained in this section [see Eqs.”
A Multiscale Pyramid Transform for Graph Signals (2013, background): “For example, in [35], [36], Sandryhaila and Moura examine filters that are polynomial functions of the adjacency matrix.”
Signals on Graphs: Uncertainty Principle and Sampling (2015, background): “Over the last few years, a series of papers produced a signiﬁcant advancement in the development of tools for the analysis of signals deﬁned over a graph, or graph signals for short [1], [3], [4].”
Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, background): “2602809 representations have led to the emerging field of graph signal processing [1], [2], which studies the representation, approximation and processing of such structured signals.”
On the degrees of freedom of signals on graphs (2015, background): “The last years witnessed a significant advancement in the development of signal processing tools devoted to the analysis of signals on graph [1], [2].”
Graph Learning Based on Total Variation Minimization (2018, methodology): “GSP has been used to deal with applications ranging from online social networks [4–6], recommender systems [7], and proteomics [8, 9] (see [1] and [3] for further application examples).”
Transforms and Operators for Directional Bioimage Analysis: A Survey. (2016, background): “9 A further possible direction is the extension of directional wavelet transforms to nonuniform lattices such as polar grids or general graphs (Hammond et al. 2011; Shuman et al. 2013; Sandryhaila and Moura 2013).”
Compressive Spectral Clustering (2016, methodology): “In this work, inspired by recent advances in the emerging ﬁeld of graph signal processing (Sandryhaila & Moura, 2014; Shuman et al., 2013), we circumvent SC’s last two bottlenecks and detail a fast approximate spectral clustering method for large datasets, as well as the supporting theory.”
Signal Recovery on Graphs: Variation Minimization (2014, methodology): “We adopt the dataset of temperature data described in Section VII-C [3].”
Optimal Power Flow Using Graph Neural Networks (2019, background): “In the context of graph signal processing (GSP) the state X ∈ R N × F of the nodes can be seen as a graph signal [24–26].”