Graphon Filters: Graph Signal Processing in the Limit

Matthew Morency, Geert Leus

Research output: Contribution to journalArticleScientificpeer-review

4 Downloads (Pure)

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.

Original languageEnglish
Article number9362328
Pages (from-to)1740-1754
Number of pages15
JournalIEEE Transactions on Signal Processing
Volume69
DOIs
Publication statusPublished - 2021

Keywords

  • Graph signal processing
  • graph filter design
  • graphons
  • random graphs

Fingerprint

Dive into the research topics of 'Graphon Filters: Graph Signal Processing in the Limit'. Together they form a unique fingerprint.

Cite this