Graphon Signal Processing
arXiv:2003.05030 · doi:10.1109/TSP.2021.3106857
Abstract
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.
arXiv commentAccepted for publication in IEEE TSP
References in corpus (23)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Spectral clustering and the high-dimensional stochastic blockmodel
- Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks
- Convolutional Neural Network Architectures for Signals Supported on Graphs
- Sampling of graph signals with successive local aggregations
- Stability Properties of Graph Neural Networks
- Rate-optimal graphon estimation
- Greedy Sampling of Graph Signals
- Nonparametric graphon estimation
- Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
- Connectivity of soft random geometric graphs
- Graphon Control of Large-scale Networks of Linear Systems
- Centrality measures for graphons: Accounting for uncertainty in networks
- A User Guide to Low-Pass Graph Signal Processing and its Applications
- Invariance-Preserving Localized Activation Functions for Graph Neural Networks
- Graphon Neural Networks and the Transferability of Graph Neural Networks
- Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
- On Gromov-Hausdorff convergence for operator metric spaces
- Notes on the sin2Θ theorem
- Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers
- Model-free consistency of graph partitioning
Cited by in corpus (8)
- Graphon Neural Networks and the Transferability of Graph Neural Networks
- Causal Fourier Analysis on Directed Acyclic Graphs and Posets
- Algebraic Neural Networks: Stability to Deformations
- Convolutional Learning on Multigraphs
- Discrete Signal Processing on Meet/Join Lattices
- On Local Distributions in Graph Signal Processing
- A noncommutative approach to the graphon Fourier transform
- Graph and graphon neural network stability