Abstract
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 analogues to the classical frequency domain, and highlight the importance of incorporating the irregular structures of graph data domains when processing signals on graphs. We then review methods to generalize fundamental operations such as filtering, translation, modulation, dilation, and downsampling to the graph setting, and survey the localized, multiscale transforms that have been proposed to efficiently extract information from high-dimensional data on graphs. We conclude with a brief discussion of open issues and possible extensions.
Keywords
UpsamplingComputer scienceSpectral graph theoryTheoretical computer scienceSignal processingPower graph analysisGraphAlgorithmDigital signal processingArtificial intelligenceLine graphVoltage graph
Affiliated Institutions
Related Publications
Graph Signal Processing: Overview, Challenges, and Applications
Research in graph signal processing (GSP) aims to develop tools for processing data defined on irregular graph domains. In this paper, we first provide an overview of core ideas...
Graph convolutional networks: a comprehensive review
Abstract Graphs naturally appear in numerous application domains, ranging from social analysis, bioinformatics to computer vision. The unique capability of graphs enables captur...
Spectral partitioning works: planar graphs and finite element meshes
Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These method...
Spectral Networks and Locally Connected Networks on Graphs
Convolutional Neural Networks are extremely efficient architectures in image and audio recognition tasks, thanks to their ability to exploit the local translational invariance o...
Pattern vectors from algebraic graph theory
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences mus...
Publication Info
- Year
- 2013
- Type
- article
- Volume
- 30
- Issue
- 3
- Pages
- 83-98
- Citations
- 4205
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
4205
OpenAlex
Cite This
David I Shuman,
Sunil K. Narang,
Pascal Frossard
et al.
(2013).
The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.
IEEE Signal Processing Magazine
, 30
(3)
, 83-98.
https://doi.org/10.1109/msp.2012.2235192
Identifiers
- DOI
- 10.1109/msp.2012.2235192