# The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

@article{Shuman2013TheEF, title={The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains}, author={David I. Shuman and Sunil K. Narang and Pascal Frossard and Antonio Ortega and Pierre Vandergheynst}, journal={IEEE Signal Processing Magazine}, year={2013}, volume={30}, pages={83-98} }

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… Expand

#### 2,515 Citations

Graph Signal Processing - Part I: Graphs, Graph Spectra, and Spectral Clustering

- Computer Science, Engineering
- ArXiv
- 2019

This work revisits graph topologies from a Data Analytics point of view, and establishes a taxonomy of graph networks through a linear algebraic formalism of graph topology (vertices, connections, directivity) which serves as a basis for spectral analysis of graphs. Expand

Signal Processing on Signed Graphs: Fundamentals and Potentials

- Computer Science
- IEEE Signal Processing Magazine
- 2020

GSP uses tools from linear algebra, (spectral) graph theory, computational harmonic analysis, and optimization theory to extend conventional signal processing concepts to data located on irregular domains that are characterized by graphs (networks). Expand

Data Science with Graphs: A Signal Processing Perspective

- Computer Science
- 2016

This thesis considers five fundamental tasks on graphs from the perspective of graph signal processing: representation, sampling, recovery, detection and localization, and illustrates the power of the proposed tools on two real-world problems: fast resampling of 3D point clouds and mining of urban traffic data. Expand

Graph Signal Processing - Part II: Processing and Analyzing Signals on Graphs

- Computer Science, Mathematics
- ArXiv
- 2019

Part II of this monograph embarks on these concepts to address the algorithmic and practical issues centered round data/signal processing on graphs, that is, the focus is on the analysis and estimation of both deterministic and random data on graphs. Expand

A Time-Vertex Signal Processing Framework: Scalable Processing and Meaningful Representations for Time-Series on Graphs

- Computer Science
- IEEE Transactions on Signal Processing
- 2018

This paper aims to elevate the notion of joint harmonic analysis to a full-fledged framework denoted as time-vertex signal processing, that links together the time-domain signal processing techniques with the new tools of graph signal processing. Expand

Vertex-frequency graph signal processing: A comprehensive review

- Computer Science
- Digit. Signal Process.
- 2020

A comprehensive account of the relation of general vertex- frequencies analysis with classical time-frequency analysis is presented, an important but missing link for more advanced applications of graph signal processing. Expand

Distributed Graph Filters

- Mathematics, Computer Science
- 2015

This thesis proposes distributed graph filters that converge fast, even in the presence of dynamics, and sets the foundations of distributed scale-invariant analysis of graph signals. Expand

Vertex-Frequency Graph Signal Processing: A review

- Computer Science
- 2019

A localized form of the graph Fourier transform is presented and an analogy with classical signal processing is established through the concept of local smoothness, which is subsequently related to the particular paradigm of signal smoothness on graphs. Expand

Multi-windowed vertex-frequency analysis for signals on undirected graphs

- Computer Science
- Comput. Commun.
- 2021

Experimental results show that the proposed two types of frames can efficiently extract vertex-frequency features of synthetic graph signals and anomaly data can also be detected by these frames. Expand

A non-commutative viewpoint on graph signal processing

- Computer Science
- 2019 13th International conference on Sampling Theory and Applications (SampTA)
- 2019

This article investigates a new approach to develop concepts of Fourier analysis for graphs that is inspired by the theory of non-commutative harmonic analysis, and is founded upon the representation theory ofnon-Abelian groups. Expand

#### References

SHOWING 1-10 OF 75 REFERENCES

Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning

- Mathematics, Computer Science
- ICML
- 2010

It is proved that in analogy to the Euclidean case, function smoothness with respect to a specific metric induced by the tree is equivalent to exponential rate of coefficient decay, that is, to approximate sparsity, which readily translate to simple practical algorithms for various learning tasks. Expand

A windowed graph Fourier transform

- Mathematics, Computer Science
- 2012 IEEE Statistical Signal Processing Workshop (SSP)
- 2012

This paper defines generalized translation and modulation operators for signals on graphs, and uses these operators to adapt the classical windowed Fourier transform to the graph setting, enabling vertex-frequency analysis. Expand

Uncertainty principles for signals defined on graphs: Bounds and characterizations

- Mathematics, Computer Science
- 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
- 2012

This paper describes the notions of “spread” in the graph and spectral domains, using the eigenvectors of the graph Laplacian as a surrogate Fourier basis and describes how to find signals that, among all signals with the same spectral spread, have the smallest graph spread about a given vertex. Expand

MULTISCALE ANALYSIS OF TIME SERIES OF GRAPHS

- 2010

Time series of graphs arise in a variety of applications, from the analysis of network traffic to time-dependent data sets to social networks. We introduce novel techniques for measuring distances… Expand

Diffusion-driven multiscale analysis on manifolds and graphs: top-down and bottom-up constructions

- Computer Science, Mathematics
- SPIE Optics + Photonics
- 2005

A novel multiscale construction is introduced, based on a top-down recursive partitioning induced by the eigenfunctions of the Laplacian, which yields associated local cosine packets on manifolds, generalizing local cosines in Euclidean spaces. Expand

Wavelets on Graphs via Spectral Graph Theory

- Mathematics, Computer Science
- ArXiv
- 2009

A novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph using the spectral decomposition of the discrete graph Laplacian L, based on defining scaling using the graph analogue of the Fourier domain. Expand

Multiscale methods for data on graphs and irregular multidimensional situations

- Mathematics
- 2009

For regularly spaced one-dimensional data, wavelet shrinkage has proven to be a compelling method for non-parametric function estimation. We create three new multiscale methods that provide… Expand

Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data

- Mathematics, Computer Science
- IEEE Transactions on Signal Processing
- 2012

This work proposes the construction of two-channel wavelet filter banks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph, and proposes quadrature mirror filters for bipartite graph which cancel aliasing and lead to perfect reconstruction. Expand

Graph wavelets for spatial traffic analysis

- Computer Science
- IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428)
- 2003

A number of problems in network operations and engineering call for new methods of traffic analysis. While most existing traffic analysis methods are fundamentally temporal, there is a clear need for… Expand

Nonlocal Discrete Regularization on Weighted Graphs: A Framework for Image and Manifold Processing

- Computer Science, Mathematics
- IEEE Transactions on Image Processing
- 2008

A nonlocal discrete regularization framework on weighted graphs of the arbitrary topologies for image and manifold processing, which leads to a family of simple and fast nonlinear processing methods based on the weighted -Laplace operator, parameterized by the degree of regularity, the graph structure and the graph weight function. Expand