The University of Texas at Austin

Computer Science 395T


The course covers the mathematics of applications of spectral graph theory, broaderly defined. Grading is based on homeworks (60%) and the final project (40%).
Prereqs: The course assumes a good knowledge of linear algebra and probability. Please talk to me or email me if you are unsure if the course is a good match for your background.
Date  Topics  Reading  Notes 
Jaunary 18th  Introduction  
January 20th  Adjacency Matrix, Laplacian Matrix, and Spectral Graph Drawing  
January 25th  Normalized Adjacency Matrix and Laplacian Matrix  Homework 1 out.  
January 27th  Fast Power Iterations  
Feburary 1st  Cheeger's Inequality (Discrete)  
Feburary 3th  Cheeger's Inequality (Continuous)  
Feburary 8th  Random walk, Diffusion distance and Heat kernel  Homework 1 due. Homework 2 out.  
Feburary 10th  Spectral Theory of Random Graphs I  
Feburary 15th  Spectral Theory of Random Graphs II.  
Feburary 17th  Expanders, interlacing polynomials, and Ramanujan Graphs I  
Feburary 22th  Expanders, interlacing polynomials, and Ramanujan Graphs II  Homework 2 due. Homework 3 out.  
Feburary 24th  Spectral Sparsification I  
March 1st  Spectral Sparsification II  
March 3rd  Spectral Theory of Directed Graphs I  PerronFrobenius Theorem  Final project proposal Due. 
March 8th  Spectral Theory of Directed Graphs II  Homework 3 due. Homework 4 out.  
March 10th  Laplacian Operators of Triangular Meshes (Guest Lecture)  
March 22th  Spectral VectorField Design I  
March 24th  Spectral VectorField Design II  
March 29th  Spectral Surface Parameterization I  
March 31th  Spectral Surface Parameterization II  Homework 4 due. Homework 5 out.  
April 5th  Normalized Cut and Spectral Shape Segmentation I  
April 7th  Normalized Cut and Spectral Shape Segmentation II  
April 12th  Spectral Graph Matching and Spectral Shape Matching  
April 14th  Functional Maps  
April 19th  Functional Map Networks  Homework 5 due. Homework 6 out.  
April 21th  Spectral Map Synchronization I  
April 26th  Spectral Map Synchronization II  
April 28th  Spectral Graph Neural Networks and Geometric Deep Learning I  
May 3rd  Spectral Graph Neural Networks and Geometric Deep Learning II  Homework 6 due.  
May 5th  Course Wrapup  Final project report due. 