Graph signal processing tailored for subgraph focus and community structure

Community structure in graph-modeled data appears in a range of disciplines that comprise network science. Its importance relies on the influence it bears on other properties of graphs such as resilience, or prediction of missing connections. Nevertheless, research to date seems to overlook its effect on the properties of signals defined in the domain of graphs' vertices. Indeed, the framework of graph signal processing mainly focuses on local connectivity patterns reflected by the graph Laplacian, and the Laplacian's effect on signals as the graph equivalent of a differential operator. This dissertation investigates the aforementioned interplay between graph signals and the underlying community structure. We make an effort to answer questions like -- do signal's values align and in what way with the communities?; does localization of signal's energy favors a community as the vertex support? Answers to these questions should provide a clearer perspective on the relation between graph signals and networks at the level of subgraphs.

This dissertation consists of two main parts. First, we investigate a particular approach -- based on modularity matrix -- of informing the graph Fourier transform about the communities without explicitly detecting them. Thereof, we show that the derived community-aware operators on signals, such as filtering or subsampling, provide a complementary view on the framework to the conventional one based on the Laplacian. Indeed, reduced signal variability within a community seems to be a valuable metric of important signal behavior, aside from its smoothness. Secondly, we explore the intricacies of a broader definition of a community -- a subgraph of any special interest, possibly identified through metadata on vertices instead of the underlying edge connectivity. Within this context, the goal is to understand the benefits of processing signals in a subgraph-restricted way. We design a new, more computationally stable type of Slepians -- bandlimited signals with energy concentrated on a subgraph. Consequently, we show that such bandlimited vectors can be successfully employed to identify a signal's oscillatory pattern localized in a subgraph of interest, by means of a modified filtering procedure. Findings from both lines of research confirm the need and benefits of a better understanding of the interaction between communities and graph signals.