Downsampling of signals on graphs: an algebraic perspective

Abstract

Real-world data such as weather data, seismic activity data, sensor networks data and social network data can be represented and processed conveniently using a mathematical structure called Graph. Graphs are a collection of vertices and edges. The relational structure between the vertices can be represented in form of a matrix called the adjacency matrix. A Graph Signal is a signal supported on a given graph. The framework of processing of signals on graphs is called Graph Signal Processing (GSP). Various signal processing concepts (e.g. Fourier Transform, filtering, translation, downsampling) need to be defined in the context of graphs. A common approach is to define a Fourier Transform for a graph (called Graph Fourier Transform - GFT), and use it to define other signal processing concepts. There are two popular approaches to define GFT for a graph: 1) using Graph Laplacian 2) using adjacency matrix. In the first method, GFT is interpreted as expansion of a given signal in the eigenvectors of the Graph Laplacian. The second method, i.e., using the adjacency matrix, results in an algebraic framework for graph signals and shift invariant filters. In the study of Graph Signal Processing, we often encounter signals which are smooth in nature. Such signals, which have low variations, can be represented efficiently using samples on fewer number of vertices. The process of selecting such vertices is called graph downsampling. As graphs do not exhibit a natural ordering of data, selection of vertices is not trivial. In this thesis, we analyze a class of graphs called Bipartite Graphs from downsampling perspective and then provide a GFT based approach to downsample signals on arbitrary graphs. For bandlimited signals on a graph, a test is provided to identify whether signal reconstruction is possible from the given downsampled signal. Moreover, if the signal is not bandlimited, we provide a quality measure for comparing different downsampling schemes. Using this quality measure, we propose a greedy downsampling algorithm. The proposed method is applicable to directed graphs, undirected graphs, and graphs with negative edge-weights. We provide several experiments demonstrating our downsampling scheme, and compare our quality measure with other existing measures (e.g. cut-index). We also provide a method to assign adjacency matrix to the downsampled vertices using an analogy from the bipartite graphs. We also examine the concepts of homomorphism and isomorphism between two graphs from signal processing point of view, and refer to them as GSP-isomorphism and GSP-homomorphism, respectively. Collectively, we refer to these concepts as Structure Preserving Maps. The fact that linear combination of signals and linear transforms on signals are meaningful operations has implications on the GSP-isomorphism and GSP-homomorphism, which diverges from the topological interpretations of the same concepts (i.e. graph-isomorphism and graphhomomorphism). When Structure Preserving Maps exist between two graphs, signals and filters can be mapped between them while preserving spectral properties. We examine conditions on adjacency matrices for such maps to exist. We also show that isospectral graphs form a special case of GSP-isomorphism and that GSP-isomorphism and GSP-homomorphism is intrinsic to resampling and downsampling process.