CS-455 Topics in Theoretical Computer Science
Spectral Graph Algorithms
Short description: The convergence of continuous and discrete methods is a major trend in modern combinatorial optimization. This course will focus on some of the recent algorithmic results in graph processing that crucially rely on spectral techniques to perform graph partitioning, solve linear systems and more. We will start from the basics and build an algorithmic toolbox that relies on deep connections to random walks, electrical networks and metric embeddings, and results in nearly linear time algorithms for several fundamental graph problems.
List of topics (tentative):
-
Laplacians, random walks, graph sparsification: It is possible to compress graphs while approximately preserving their spectral properties (in particular, properties of random walks)? We will cover the main results from the recent influential line of work on spectral sparsification that provides such compression schemes.
-
Laplacian system solvers: given a linear system Ax=b, how quickly can we find x? We will cover nearly linear time algorithms for solving Ax=b when A is a symmetric diagonally dominant matrix (a common scenario in practice).
-
Spectral clustering: given a graph, can we find a partition of the graph into $k$ vertex disjoint parts such that few edges cross from one part to another? This is the fundamental graph clustering problem that arises in many applications. We will cover several results on spectral graph partitioning, where one first embeds vertices of the graph into Euclidean space using the bottom few eigenvectors of the graph Laplacian, and then employs Euclidean clustering primitives to find the partition.
-
Local clustering with random walks: Given a very large graph and a seed node in it, can we find a small cut that separates the seed node from the rest of the graph, without reading the entire graph? We will cover local clustering algorithms, which identify such cuts in time roughly proportional to the number of vertices on the small side of the cut, by carefully analyzing distributions of random walks in the graph.
Prerequisites: Bachelor courses on algorithms, complexity theory, and discrete mathematics; mathematical maturity.
Grading: The grade will be based on problem sets (60%) and a final (40%).
For more details see the official course book here.