TWO VIEWPOINTS ON GRAPH LIMIT THEORY AND AN APPLICATION TO GRAPH SIGNAL PROCESSING
Date
2025-05
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
Graphs lend themselves to modeling data with a non-Euclidean structure. Graph
signal processing utilizes the spectrum of the adjacency matrix or graph Laplacian to
study and denoise signals on graphs. However, when the data modeled by a graph
changes the associated spectral information changes as well. Particularly so when new
vertices are added to the graph as this changes the dimension of the vector space in
which signals live. Graph limit theory o↵ers the ability to associate a growing sequence
of graphs, possessing similar structures, with a limit object that can be thought of as
an operator on an infinite dimensional function space. The spectrum of the limiting op erator is closely related to the spectrum of the adjacency matrices of the graphs in the
sequence. A Fourier transform defined with respect to the limit of a sequence of graphs
can approximate the graph Fourier transform for every graph in the sequence. This
theory has limitations, namely there are not very many known examples of convergent
graph sequences. This thesis describes in detail how instance independent graph signal
processing can be developed for stochastic block model graphs and utilizes the most
general framework for studying graph limits to prove the existence of limit objects for
certain sequences of Cayley graphs.