Graphon Filters: Graph Signal Processing in the Limit

Abstract

Graph signal processing is an emerging field which aims to model processes that exist on the nodes of a network and are explained through diffusion over this structure. Graph signal processing works have heretofore assumed knowledge of the graph shift operator. Our approach is to investigate the question of graph filtering on a graph about which we only know a model. To do this we leverage the theory of graphons proposed by L. Lovasz and B. Szegedy. We make three key contributions to the emerging field of graph signal processing. We show first that filters defined over the scaled adjacency matrix of a random graph drawn from a graphon converge to filters defined over the Fredholm integral operator with the graphon as its kernel. Second, leveraging classical findings from the theory of the numerical solution of Fredholm integral equations, we define the Fourier-Galerkin shift operator. Lastly, using the Fourier-Galerkin shift operator, we derive a graph filter design algorithm which only depends on the graphon, and thus depends only on the probabilistic structure of the graph instead of the particular graph itself. The derived graphon filtering algorithm is verified through simulations on a variety of random graph models.

arXiv comment13 pages, 14 figures, submitted to Transactions on Signal Processing January 30th 2020

References in corpus (10)

• Statistical mechanics of complex networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Geometric deep learning: going beyond Euclidean data
• Discrete Signal Processing on Graphs
• The phase transition in inhomogeneous random graphs
• Matrix estimation by Universal Singular Value Thresholding
• Autoregressive Moving Average Graph Filtering
• Advances in Distributed Graph Filtering
• Sparse exchangeable graphs and their limits via graphon processes
• Centrality measures for graphons: Accounting for uncertainty in networks

Cited by in corpus (3)

• A noncommutative approach to the graphon Fourier transform
• Multi-dimensional graph fractional Fourier transform and its application
• Learning Graphon Autoencoders for Generative Graph Modeling