Sparsity Bounds for Spectral Approximations of Graphs

Abstract

Graph sparsification is the concept of using a sparse graph to approximate a much denser one --- a powerful tool for improving the complexity of graph algorithms. In this thesis, we focus on the setting of \emph{spectral sparsification}, which requires our sparsifiers to roughly preserve the original graph's linear-algebraic nature. Specifically, the central goal is to understand and obtain existence results for the level of sparsity achievable under spectral approximation. Given an arbitrary graph and an approximation factor we would like to achieve, we ask: how few edges can we hope for a spectral sparsifier to have? We present a blend of expository material and novel contributions throughout this thesis to this end.

We begin by developing the basic theory and motivations behind spectral approximation for undirected, weighted graphs. Then, we present a few existing algorithms for obtaining spectral sparsifiers, including one which attains the state-of-the-art \emph{linear size} bound, meaning the sparsifiers produced have number of edges linear in the number of vertices $n$. Next, we present our joint work with Phevos Paschalidis, in which give a constructive proof for recovering the existence of linear-sized sparsifiers from the proof by Marcus, Spielman, and Srivastava of the long-standing \emph{Kadison-Singer} conjecture, formalizing deep connections between these two results. Finally, we expand our view to stronger definitions of spectral approximation in the literature that allow for sparsifying directed graphs and provide more preservation guarantees, and we unify our view on these through the lens of \emph{graph lifts}. Lifts encode the local structure of a graph into a larger graph with a new global structure, and they have been shown to be a promising technique for reductions both within and between these different spectral approximation definitions. While only $O(n \polylog n)$ size bounds are generally known for these stronger spectral sparsifiers, we give a proof for obtaining linear-sized \emph{unit-circle} sparsifiers in the special case of undirected regular graphs using lifts. Lastly, we outline a path to generalizing this lift perspective for directed unit-circle sparsification, proving some original results and stating interesting open problems toward this goal.