Mikael Rizvanovic: Coarse graining and out-of-sample approximation for the spectral theory of complex networks

Abstract.

Spectral graph theory have many applications in machine learning and beyond. The graph has been shown to be a very powerful mathematical object and much can be said about it from its spectrum (eigenvectors and eigenvalues) alone. Nevertheless, this relies on us being able to compute the spectrum which is notoriously expensive and often unfeasible for even moderately large data sets. In this thesis we will look at ways to bring down this computational cost while hopefully preserving most of the relevant information in the graph. We will examine two methods to accomplish this: 1) Coarse graining, which reduces the overall size of the graph and thus also the computational cost, and 2) Outof- sample extension, where we extend an already known eigenspace to new data points.