Graphon Signal Processing

Graphons are infinite-dimensional objects that represent the limit of convergent sequences of graphs as their number of nodes goes to infinity. This paper derives a theory of graphon signal processing centered on the notions of graphon Fourier transform and linear shift invariant graphon filters , t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2021, Vol.69, p.4961-4976
Main Authors: Ruiz, Luana, Chamon, Luiz F. O., Ribeiro, Alejandro
Format: Article
Language:English
Subjects:
Convergence
convergent graph sequences
Filter design (mathematics)
Fourier analysis
Fourier transforms
graph filters
graph Fourier transform
graph signal processing
Graphons
Graphs
Large scale integration
Nodes
Pipelines
Sequences
Signal analysis
Signal processing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graphons are infinite-dimensional objects that represent the limit of convergent sequences of graphs as their number of nodes goes to infinity. This paper derives a theory of graphon signal processing centered on the notions of graphon Fourier transform and linear shift invariant graphon filters , the graphon counterparts of the graph Fourier transform and graph filters. It is shown that for convergent sequences of graphs and associated graph signals: (i) the graph Fourier transform converges to the graphon Fourier transform when the graphon signal is bandlimited; (ii) the spectral and vertex responses of graph filters converge to the spectral and vertex responses of graphon filters with the same coefficients. These theorems imply that for graphs that belong to certain families, i.e., that are part of sequences that converge to a certain graphon, graph Fourier analysis and graph filter design have well defined limits. In turn, these facts extend applicability of graph signal processing to graphs with large number of nodes - since signal processing pipelines designed for limit graphons can be applied to finite graphs - and to dynamic graphs - since we can relate the result of SP pipelines designed for different graphs from the same convergent graph sequence.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2021.3106857