Discrete Signal Processing on Graphs

Дискретная обработка сигналов на графах
José M. F. Moura, Aliaksei Sandryhaila
2013-03-08

graph Fourier transformgraph convolutiongraph filtersgraph signal processingsignals on graphs
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.
1
Applications demonstrate graph DSP for blog classification, linear prediction and compression of data from irregularly located weather stations, and mobile-customer behavior prediction.
2
It develops graph-based counterparts of core DSP concepts, including filters, convolution, z-transform, impulse response, spectral representation, Fourier transform, and frequency response.
3
The framework supports describing, representing, transforming, analyzing, processing, and synthesizing signals defined on complex networks.
4
The paper extends discrete signal processing methodology from regularly ordered time or image signals to data indexed by nodes of arbitrary graphs.

signals indexed by the nodes of complex graphs, including social-network, weather-station, and mobile-service customer data

discrete signal processing properties and operations for graph signals, including filtering, convolution, spectral/Fourier representation, prediction, compression, and classification

Publication Details
Publication Date
2013-03-08
Journal
Publisher
ISSN
Cited by
1540
Access Type
Author Information
Authors
José M. F. Moura
Aliaksei Sandryhaila
Explore further
Open the scid.ai AI chat with a ready-made request: it will find papers on a similar topic and help build a literature review.
Find similar papers in the chat →
Make a presentation
100%