Filter Design on Graphs

Abstract

Graphs are a fundamental tool in Computer Science in a variety of areas such as Artificial Intelligence, Machine Learning, Networking, Signal Processing, Brain Mapping, Social Networks, and many others. Many of these graphs can have millions of nodes, so some sort of filtering is usually in order to extract the useful information. The aim of this thesis is develop the mathematical background and building blocks that are fundamental to designing these filters, as well as lay out a clear blueprint for how to create graph filters for undirected graphs. The two major approaches that will be focused on will be developing filters in the vertex domain and spectral domains. Filter design in the vertex domain aims to act on the laplacian or adjacency matrices directly, while design in the spectral domain looks at acting on the spectral properties of the graph. Some polynomial and rational filters are proposed in this thesis, and are applied to sample graphs to demonstrate their effectiveness. Further study could be conducted with regard to directed graphs, looking at a different variety of families of polynomials, or analyzing the efficiency of computing these filters on larger graphs.