TWO VIEWPOINTS ON GRAPH LIMIT THEORY AND AN APPLICATION TO GRAPH SIGNAL PROCESSING

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.