Many complex systems in the real-world can be appropriately modeled by graphs, e.g., social networks, traffic networks, sensor systems, chemical reaction networks to only name a few. Additionally, many methods from modern data science can be interpreted as working with fully connected, weighted graphs (e.g., when working with a Gaussian similarity function on arbitrary data sets).

Clearly, understanding properties of graphs thus helps tremendously when trying to find crucial properties of these real-world systems. There are countless ways how to analyze graphs, and in the first part of this course we focus on a particularly elegant approach which connects graph theory and linear algebra:

We study different matrix representations of graphs, in particular the adjacency matrix and the graph Laplacian, and will learn how the eigenvalues and eigenvectors of those matrices reveal combinatorial properties of the graph (and can thus subsequently help analyze and structure the underlying data). Among other things, we learn how spectral information can be used to find clusters/communities in a graph, identify the most important nodes or even neatly draw the graph for visualization.

The second part of the course deals with the analysis and manipulation of graph signals. The techniques used in this context can be interpreted as methods from classical digital signal processing (like the Fourier transform, band-pass filters, FIR filters, ...), generalized from very regular data (samples taken from a signal at equidistant points in time) to data living on arbitrary, possibly highly irregular domains, represented by graphs.

We start by investigating what a sensible concept of frequencies on a graph is and then consider classical topics such as denoising signals that are polluted by measurement errors and smoothing signals by applying appropriate filters. More advanced topics include reconstruction of partially observed signals (compressed sensing) and automatically learning unknown graph structures in order to explain observed data.

The topics of this course interconnect many areas of computer science and applied mathematics, including linear algebra, numerical mathematics, optimization, graph theory, data mining and machine learning. Throughout the course, we illustrate all concepts using Python implementations in Jupyter notebooks.