# 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](http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf)

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

- Prof. Dan Spielman at Yale: [Spectral Graph Theory - Fall 2019](http://www.cs.yale.edu/homes/spielman/462/462schedule.html)
- Prof. Lap Chi Lau at UWaterloo: [Spectral Graph Theory, 2019](https://cs.uwaterloo.ca/~lapchi/cs860-2019/})
- Prof. Luca Trevisan's lecture notes: [Lecture notes link.](https://lucatrevisan.github.io/books/expanders-2016.pdf)

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 $+\lambda, -\lambda$ 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](https://cs.uwaterloo.ca/~lapchi/cs860/notes/03-graph-spectrum.pdf)

- **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](https://cs.uwaterloo.ca/~lapchi/cs860/notes/03-graph-spectrum.pdf)

- **Lec 4**: (Fri, 12th Jan)
- Linear Algebra: Outer products, Spectral theorem representation in terms of outer products
- Hoffman's bound on $\alpha(G)$ (application of Spectral Theorem)

*Reading:*
Hoffman's bound: [A Blog post](https://uniformlyatrandom.wordpress.com/2009/03/21/hoffmans-eigenvalue-bound-on-the-size-of-an-independent-set/)

- 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_{avg} \leq \mu_1(A_G) \leq d_{\max}$

*Reading:* [Dan Spielman Book Draft](http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf) 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](http://www.cs.yale.edu/homes/spielman/sagt/sagt.pdf): 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](https://cs.uwaterloo.ca/~lapchi/cs860-2019/notes/L03.pdf)
*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 $2I-\mathcal{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](https://home.ttic.edu/~prahladh/teaching/spring05/lectures/lec4.pdf)
*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](https://sites.math.rutgers.edu/~sk1233/courses/topics-S18/lec2.pdf)
(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](https://appsrv.cse.cuhk.edu.hk/~chi/csc5160/notes/L06.pdf)
Lovasz-Simonovits technique in detail: [Akash Kumar's notes from IITB](https://drive.google.com/file/d/1sZylNdj7XS4jLIFvoNiDhvC1n8ASs6eh/view)
*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](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture12.pdf)
*Scribe*: (Two per lecture) Subham, Suryaansh. Due 12th Apr

- **Lec 20**: (Fri 05th Apr)
- Effective resistance definition
- Monotonicity law for $R_{eff}$, $R_{eff}$ is a metric
- Flow based on spanning trees (proof outline only)

*Reading*: Effective resistance definition [David Williamson Lec 12](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture12.pdf)
Monotonicity law and metric property: [Dan Spielman's 2010 lecture notes](https://www.cs.yale.edu/homes/spielman/462/2010/lect13-10.pdf)

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: $\Pr_T[(i,j) \in T] = \frac{r_{eff}(i,j)}{r(i,j)}$, and $\sum_{\{i,j\}\in E} \frac{r_{eff}(i,j)}{r(i,j)} = n-1$
- Iterative methods (Richardson iteration) to solve $Ax=b$, and analysis for $A$ being positive definite. Extension to Laplacian systems $L_Gx = b$
- Preconditioning
*Reading:* [Lec 13 Williamson](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture13.pdf), [Lec 15 Williamson](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture15.pdf)
*Scribe* (Two per lecture): Santoshi, Ganesh. Due 22nd Apr.

- **Lec 22**: (Tue 16th Apr)
- Preconditioning on Low-Stretch Spanning trees
- $\kappa(L_T^{-1} L_G) = O(st_T(G))$
- Statement of result on solving Laplacian systems in near linear time
- Brief introduction to graph sparsification
*Reading:* [Lec 15 Williamson](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture15.pdf)
*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/\epsilon^2)$ edges (only statement+idea of proof using Matrix Chernoff bounds, details skipped)

*Reading:* Chap 10 of [Nisheeth Vishnoi's $Lx=b$ survey](https://theory.epfl.ch/vishnoi/Lxb-Web.pdf),
Relevant parts of [Nikhil Srivastava's slides](https://simons.berkeley.edu/sites/default/files/docs/1768/slidessrivastava1.pdf), [Talk video](https://youtu.be/qXRs8-LouSQ)

*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 $Lx=b$ survey](https://theory.epfl.ch/vishnoi/Lxb-Web.pdf), Sec 11.2
*Scribe:* (Two per lecture) M Shah, Aayush Patel (Due 3rd May)

- **Quiz-3 / Endsem (30th Apr, Tue)**