CS 591 Fall 2016: Iterative Methods for Graphs and Networks

Lectures: M,W 1.00-2.30pmin MCS B31.

Instructor: Prof. Lorenzo Orecchia, MCS 135D. Office hours: TBA


Homework 1 is out! Find it here.

Please sign-up for two sections of scribing on this google-doc

Lecture Notes

Date Topic Overleaf Link
9/7 Graph Matrices, Linear Algebra Review link
9/12 Linear Algebra Review, Spectral Theorem link
9/14 Courant-Fischer, Connected Components Notes by Spielman
9/19 PSD Matrices and Graph Approximations link
9/21 Markov Chains and their Convergence to Stationary link
9/26 Rate of Convergence of Random Walks on Graphs I link
9/28 Rate of Convergence or Random Walks on Graphs II link
10/5 Conductance and Its Relation to the SpectralGap link
10/11 Metric Embeddings and the Cut Cone link
10/17 Proof of Cheeger's Inequality link
10/19 Eigenvector Computation Notes by Vishnoi
10/24 Homework Review, Intro to Spectral Clustering link
10/26 Singular Value Decomposition, Subspaces and Principal Angles link
10/31 More Principal Angles link
11/2-7 Davis-Kahan Theorem and SMB Notes by Montanari
11/9 Electrical Circuits soon…
11/14-16 Effective Resistance old notes
11/21 Power Method and Gradient Descent Notes by Vishnoi and old notes
11/28 Chebyshev Iteration and Conjugate Gradient Notes by Vishnoi and old notes
11/30 Preconditioning soon …


Homework 1 Due: October 12, in class link
Homework 2 Due: December 12, in class link

Course Information

Course Outline: Iterative methods allow us to trade-off precision and running time to produce theoretically sound, fast algorithms for many optimization problems. These methods rely on a very “continuous” interpretation of the problem, incorporating techniques such as steepest-descent and coordinate descent that strongly rely on geometric intuition. In this class, we will turn this perspective on his head and show that iterative methods can be extremely useful in understanding and efficiently solving fundamental combinatorial problems on graphs, a characteristically discrete structure. This has important implications at a time when input graphs may have even billions of nodes and any super-linear running time is practically infeasible.

Tentative Syllabus: The following topics will be covered:

Spectral Graph Theory: Graph Matrices and Graph Eigenvalues, Random Walks, Applications to Clustering

Electrical Circuits as Graphs: Laplacian systems, Preconditioning, Fast Solvers

Iterative Methods in Convex Optimization: Basics of Convex Optimization, Gradient Descent, Coordinate Descent, Application to Graph Problems

Some of the following topics may also be included:

Metric Embeddings

Semidefinite Programming

Matrix Concentration Bounds for Sparsification and Random Graphs

Course Policies

While the class will not depend heavily on background material, it will require familiarity with fundamental algorithmic problems and techniques at the level of CS330 or equivalent. A working knowledge of basic linear algebra is also required. Do not hesitate to contact me if you are not sure whether your previous preparation will allow you to benefit from the class.

There will be three components to the workload in this class: scribing, homework and final exam.


In most lectures, two students will act as scribes. These students are expected to collaborate to produce high-quality lecture notes in Latex through the collaborative Latex editor overleaf.com. The scribes should submit a final draft of their notes within 5 days of the class. The quality and clarity of the notes will be part of the evaluation. No student will be asked to scribe more than 3 times.


There will be 3-5 homework assignments. There will be 3 homework assignments. You are encouraged to collaborate on the solution of the homeworks, but you must write up your own answers. If you do collaborate, you must acknowledge your collaborators.

Final Exam

This will be a take-home exam, on which collaboration is not allowed.

In both homeworks and in the exam, you may rely on published or online material, but you must ackowledge your sources.

The grading will roughly work out as follows: Scribing 50%, Homeworks and Final 50%.