CS5030: Topics in TCS: Spectral Graph Theory and Algorithms

Jan-May 2024, CSE, IITH

Logistics

Instructor: Dr. Rakesh Venkat, CSE Department
Course name: CS5030, Topics in Theoretical Computer Science
Lecture timings: R-slot (Tue 2:30pm-4pm and Fri 4pm-5:30pm)
Location: ~~C-LH5~~ A-117, from 12th Jan onwards
First meeting: Tue Jan 02nd, 2:30pm.

Course Overview

In this (iteration of the) course on Topics in Theoretical Computer Science, we will be looking at Spectral Graph Theory and Algorithms. Spectral Graph Theory deals with the use of eigenvalues and eigenvectors of matrices associated with a graph to understand its structural and combinatorial properties. Spectral algorithms broadly refers to a class of algorithms based on linear algebraic tools that exploit the properties of eigenvalues and eigenvectors of matrices associated with input data (often graphs). Spectral algorithms on graphs have come to occupy a central role in computer science, with diverse applications spanning both theory and practice. A few salient examples include estimating the conductance in networks, ranking nodes in web graphs, converting randomized algorithms to deterministic ones, designing error correcting codes, and finding sparse approximations to graphs (among many more). The course will look at the basics of spectral graph theory with a view towards exploring its various applications in Computer Science.

Spectral algorithms are also widely used in instances other than graphs. Based on the progress of the course, we may get a glimpse of a few of these in the latter half of the course.

The course will be at the level of an advanced undergraduate/beginning graduate level theory elective: it will begin from the basics, and will likely pick up at a brisk pace. Most of the course will involve understanding (and writing) mathematical proofs of statements and analysis of algorithms. Familiarity with basic linear algebra and probability will be assumed.

Syllabus:

A tentative (super)set of topics:

Basic spectral graph theory, Cheeger's inequality
Random Walks on graphs and their applications
Expander graphs, use in Error correcting codes and Derandomization
Connection to electrical networks and algorithmic applications
Graph Sparsification
Beyond worst-case analysis of graph algorithms: Random graphs and Planted models
High-Dimensional Expanders and applications
Other spectral Algorithms: Mixture models, Spectral Clustering, and Optimization via low-rank approximations.

The closest to a textbook resource is a draft of a book by Prof. Dan Spielman: Spectral and Algebraic Graph theory

Similar courses at other universities (all have lecture notes available):

Prof. Dan Spielman at Yale: Spectral Graph Theory - Fall 2019
Prof. Lap Chi Lau at UWaterloo: Spectral Graph Theory, 2019
Prof. Luca Trevisan's lecture notes: Lecture notes link.

Note that I expect the average pace to be slower than the above courses.

Evaluation

Rough scheme:
a)

3 \times

In-Class Exams (35%-40%).
b) Assignments (40%)
c) Scribe notes (10%)
d) Class Participation (10%).
Exact evaluation weightage will be finalized and announced by Lecture No. 3 in class.

Piazza

A Piazza page (https://piazza.com/iit_hyderabad/spring2024/cs5030) will be set up and enrollment link sent to all registered students.

Discussions and supplementary notes will be posted on Piazza.

Lectures and Schedule

Lec 1: (Tue, 2nd Jan)
- Administrivia, logistics, overview of the course
- Overview of applications of spectral graph theory
- The Adjacency and Laplacian matrices for a graph
  $G$
  Reading: No specific reference, as this was just a general overview.
Lec 2: (Fri, 5th Jan)
- Review of basic Linear Algebra:
- Matrices as linear operators, rank, nullspace, range, determinant, eigenvalues and eigenvectors, trace
- Theorem:
  $G$ is bipartite iff all non-zero eigenvalues of
  $A_{G}$ occur in
  $+ λ, - λ$ pairs.
Reading: One of many detailed resources for basic Linear Algebra: https://dept.math.lsa.umich.edu/~speyer/LinearAlgebraVideos/
While we will revise concepts as the lectures progress, our reviews will be brief (out of necessity). You can refer to the above link for more details.
Proof of bipartite graph property: Lap Chi Lau notes
Lec 3: (Tue, 09th Jan)
- More linear algebra: Multiplicities, eigenspaces, Spectral Theorem
- The Laplacian matrix and quadratic form
- Theorem: Connected iff
  $L_{G}$ has exactly one zero eigenvalue
Reading: For muliplicities and properties, see the Linear Algebra notes linked in Lec 2 Reading.
Connectivity property: Prop 3.18 in Lap Chi Lau notes
Lec 4: (Fri, 12th Jan)
- Linear Algebra: Outer products, Spectral theorem representation in terms of outer products
- Hoffman's bound on
  $α (G)$ (application of Spectral Theorem)
Reading:
Hoffman's bound: A Blog post
Tue 16th Jan: Class Cancelled
Lec 5: (Fri, 19th Jan)
- Linear Algebra: Rayleigh coefficient, optimization formulation of eigenvalues
- Positive semidefiniteness, quadratic forms and Laplacian representations
- $d_{a v g} \leq μ_{1} (A_{G}) \leq d_{max}$
Reading: Dan Spielman Book Draft Chap 2 and Chap 4, Sec 4.2-4.3.
Scribe: Subham B.
Problems posted on 20th Jan, due 26th Jan
(Tue 23rd Jan): Class cancelled, Instructor unwell.
(Fri 26th Jan): Holiday on account of Republic Day
Lec 6: (Tue 30th Jan)
- Comparing graphs: bounding the eigenvalues of the Path graph
- Edge expansion: definition and examples
- Cheeger's inequality : Statement
Reading: Dan Spielman Book Draft: Sec 5.4

Scribe: Aayush
Lec 7: (Fri 02nd Feb)
- Proof of "Easy" direction of Cheeger's inequality
- "Hard" direction of Cheeger's inequality: Preprocessing step
Reading: Lap Chi Lau notes
Scribe: Suryaansh
Lec 8: (Tue 06th Feb)
- Proof of Cheeger's inequality (hard direction)
Reading: Lap Chi Lau notes : https://cs.uwaterloo.ca/~lapchi/cs860-2019/notes/L03.pdf
Scribe: Kunal
Lec 9: (Fri 09 Feb)
- Review of Cheeger's inequality
- Power method to find top eigenvector
Reading: Luca Trevisan's notes: http://theory.stanford.edu/~trevisan/expander-online/lecture03.pdf
Scribe: Kartheek
Lec 10: (Tue 13 Feb)
- Ways to find an approximation to the second smallest eigenvector of Laplacian using power method (use
  $2 I - L$ or pseudoinverse)
- Pseudoinverse of a matrix : definition and properties
Reading:: Notes by Luca Trevisan referenced for Lec 9
Scribe: Santoshi
Lec 11: (Fri 16th Feb)
- Definitions of Expansion: Spectral, Edge, Vertex
Reading: https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf (also the reference for next 3 lectures.)
Scribe: Ganesh
Lec 12: (Tue 20th Feb)
- Equivalence of definitions of expansion: Spectral implies Vertex Expansion
- $w_{G} \geq \frac{1}{\sqrt{d}} (1 - o (1))$ , for any
  $d$ -regular graph.
Reading: Same as Lec 11
Scribe: Ketan
QUIZ -1 (Fri 23rd Feb)
Lec 13: (Tue, 27th Feb)
- Introduction to randomized algorithms
- Karger's min-cut algorithm, primality testing
- Complexity class RP, intuition for derandomization of RP
Reading:
Scribe: Yuvraj
Lec 14: (Fri 01st Mar)
- Derandomization of RP using expanders: KPS
- Fully explicit expanders
Reading:
Scribe: Namita (Due Mar 10th)
Lec 15: (Tue 05th Mar)
- A better derandomization of RP using Random Walks on expanders
Reading: Prahladh Harsha's Lecture notes
Scribe: Aayush J (Due Mar 15th)
Lec 16: (Fri 08th Mar)
- BPP error reduction: Chernoff bounds
- Statement of Chernoff bounds for expander walks (no proof)
- Expander mixing lemma
Reading: For chernoff bounds: See Wikipedia, or {https://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf}
Expander mixing lemma: Theorem 8 in these notes
(Proof presented in class of the Expander mixing lemma follows the above and has minor differences from Salil Vadhan's notes)
Scribe: None
Lec 17:
- Random walks, stationary distribution
- Conditions for convergence to stationary distribution (no proof)
- Lovasz-Simonovits method for relating convergence to conductance (overview of main technique)
- Pagerank and introduction to personalized pagerank
Reading: Lap Chi Lau's notes
Lovasz-Simonovits technique in detail: Akash Kumar's notes from IITB
Scribe: M Shah
Lec 18: (Tue 19th Mar)
- Personalized pagerank, approximation via Taylor series
- Spilling paint method and convergence
- Approximation using the spilling paint method
Reading: Dan Spielman's notes: https://www.cs.cmu.edu/afs/cs/academic/class/15750-s17/RelatedWork/SpielmanResets-2013.pdf
Scribe: Rishit
Quiz-2 (Fri 22nd Mar)
-Semester break week -
Lec 19: (Tue 02nd Apr)
- Electrical networks - Introduction
- Ohm's law, KVL equivalence
- Potentials given by solutions to
  $L_{G} p = e_{s} - e_{t}$
- Effective resistance definition
Reading: David Williamson's lecture notes
Scribe: (Two per lecture) Subham, Suryaansh. Due 12th Apr
Lec 20: (Fri 05th Apr)
- Effective resistance definition
- Monotonicity law for
  $R_{e f f}$ ,
  $R_{e f f}$ is a metric
- Flow based on spanning trees (proof outline only)
Reading: Effective resistance definition David Williamson Lec 12
Monotonicity law and metric property: Dan Spielman's 2010 lecture notes

The complete proof for electrical flows based on spanning trees can be found here: [Lec 13, Williamson] (https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture13.pdf)

Scribe: (Two per lecture). Kunal, Kartheek. . Due 15th Apr
(Tue 09th Apr): Holiday for Ugadi
Lec 21: (Fri 12th Apr)
- More on effective resistances:
  $\underset{T}{Pr} [(i, j) \in T] = \frac{r_{e f f} (i, j)}{r (i, j)}$ , and
  $\sum_{{i, j} \in E} \frac{r_{e f f} (i, j)}{r (i, j)} = n - 1$
- Iterative methods (Richardson iteration) to solve
  $A x = b$ , and analysis for
  $A$ being positive definite. Extension to Laplacian systems
  $L_{G} x = b$
- Preconditioning
  Reading: Lec 13 Williamson, Lec 15 Williamson
  Scribe (Two per lecture): Santoshi, Ganesh. Due 22nd Apr.
Lec 22: (Tue 16th Apr)
- Preconditioning on Low-Stretch Spanning trees
- $κ (L_{T}^{- 1} L_{G}) = O (s t_{T} (G))$
- Statement of result on solving Laplacian systems in near linear time
- Brief introduction to graph sparsification
  Reading: Lec 15 Williamson
  Scribe: (Two per lecture): Namita, Ketan. Due 26th Apr
Lec 23: (Fri 19th Apr)
- Graph Sparsification: Cut and Spectral
- Template for edge-sampling for sparsification
- Sampling using effective resistances to get a sparsifier with
  $O (n \log n / ϵ^{2})$ edges (only statement+idea of proof using Matrix Chernoff bounds, details skipped)
Reading: Chap 10 of Nisheeth Vishnoi's
$L x = b$ survey,
Relevant parts of Nikhil Srivastava's slides, Talk video

Scribe: (Two per lecture): Rishit. Due 29th Apr
Lec 24 (Tue 23rd Apr) (Final lecture for the course)
- Estimating effective resistances for all edges in
  $\tilde{O} (m)$ time.
  
  Reading: Nisheeth Vishnoi's
  $L x = b$ survey, Sec 11.2
  Scribe: (Two per lecture) M Shah, Aayush Patel (Due 3rd May)
Quiz-3 / Endsem (30th Apr, Tue)