Discrete Signal Processing on Graphs: Frequency Analysis

By Aliaksei Sandryhaila, José M. F. Moura. IEEE Transactions on Signal Processing, 2013

892 citations recorded by the source corpus.

Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high- and band-pass graph signals and graph filters. In traditional signal processing, these concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/24a968b1a085cfb55072288b7509433c8275a69a

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 Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Signal Recovery on Graphs: Variation Minimization (2014, methodology): “We see that, for both evaluation scores, GMCR outperforms all matrix completion algorithms because it combines the prior information on graph structure and the low-rank assumption to perform a twofold learning scheme.”
Convolutional Neural Network Architectures for Signals Supported on Graphs (2018, methodology): “They not only capture the intuitive idea of convolution, sampling and reconstruction as local operations but also share some other interesting theoretical properties [1], [2], [5].”
Signals on Graphs: Uncertainty Principle and Sampling (2015, methodology): “form of a vector xas the projection onto the space spanned by the Laplacian eigenvectors [1], [4], [8], [13]: x^ = U ontox (3) with inverse Fourier transform x= U^x: (4) Alternatively, the authors of [20] started from the Jordan decomposition of the adjacency matrix as A = VJV 1 where J is a block d”
Network Topology Inference from Spectral Templates (2016, background): “If we make V = U in (6) and (7) we formulate the problem of identifying a graph shift S = VΛV = UΛU whose graph Fourier transform [7] x̃ := Vx = Ux is the given orthonormal transform of interest.”
Graph Signal Processing: Overview, Challenges, and Applications (2017, methodology): “When data labels are presented as signals on a (nearest neighbor) graph, graph signal regularization techniques can be used in the process of estimating labels [5], optimizing the prediction of unknown labels in classification [51] or semisupervised learning problems [195].”
Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies (2015, methodology): “In such cases, one can use generalized eigenvectors in the Jordan normal form of W as stated before [22].”
A Multiscale Pyramid Transform for Graph Signals (2013, background): “For example, in [38], [39], Sandryhaila and Moura examine filters that are polynomial functions of the adjacency matrix.”
CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters (2017, background): “In [22] filters are defined as functions of the adjacency matrix g(W), and in [23] the problem of ordering the eigenvalues of W according to a natural notion of frequency was addressed.”
Global and Local Uncertainty Principles for Signals on Graphs (2016, methodology): “ Dfk 1; which implies that kA Dfk 1 kA Dfk2 2 kA Dfk 1 Akfk 2 max i;kkg i;kk 2 : (44) We then use Corollary 4, the converse of Riesz-Thorin, to interpolate between (44) and (41), and we ﬁnd for p2[1;2]: kA Dfk pA 1 p max i;k kg i;kk 2 1 2 p kfk 2: (45) Combining (45) with the second inequality i”
Discrete Signal Processing on Graphs: Sampling Theory (2015, background): “In this section, we briefly review relevant concepts of discrete signal processing on graphs; a thorough introduction can be found in [4], [28].”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, background): “Consider instead a (possibly asymmetric) graph-shift operator , S which is assumed to be diagonalizable as , S V V 1 K = - and redefine the GFT as ; x V x 1 = u otherwise, one can consider Jordan decompositions [49].”