John Urschel received his bachelors and masters in mathematics from Penn State and then went on to become a professional football player for the Baltimore Ravens in 2014. During his second season, Urschel began his graduate studies in mathematics at MIT alongside his professional football career. Urschel eventually decided to retire from pro football to pursue his real passion, the study of mathematics, and he completed his doctorate in 2021. Urschel is currently a scholar at the Institute for Advanced Study where he is actively engaged in research on graph theory, numerical analysis, and machine learning. In addition, Urschel is the author of Mind and Matter, a New York Times bestseller about his life as an athlete and mathematician, and has been named as one of Forbes 30 under 30 for being an outstanding young scientist.
In this episode, John and I discuss a hodgepodge of topics in spectral graph theory. We start off light and discuss the famous Braess's Paradox in which traffic congestion can be increased by opening a road. We then discuss the graph Laplacian to enable us to present Cheeger's Theorem, a beautiful result relating graph bottlenecks to graph eigenvalues. We then discuss various graph embedding and clustering results, and end with a discussion of the PageRank algorithm that powers Google search.
Originally published on June 9, 2022 on YouTube: https://youtu.be/O6k0JRpA2mg
Corrections:
01:14:24 : The inequalities are reversed here. It is corrected at 01:16:16.
Timestamps:
00:00:00 : Introduction
00:04:30 : Being a professional mathematician and academia vs industry
00:09:41 : John's taste in mathematics
00:13:00 : Outline
00:17:23 : Braess's Paradox: "Opening a highway can increase traffic congestion."
00:25:34 : Prisoner's Dilemma. We need social forcing mechanisms to avoid undesirable outcomes (traffic jams).
00:31:20 : What is a graph
00:36:33 : Graph bottlenecks. Practical situations: Task assignment, the economy, organizational management.
00:42:44 : Quantifying bottlenecks: Cheeger's constant
00:46:43 : Cheeger's constant sample computations
00:52:07 : NP Hardness
00:55:48 : Graph Laplacian
00:58:30 : Graph Laplacian: Relation to Laplacian from calculus
01:00:27 : Graph Laplacian: 1-dimensional example
01:01:22 : Graph Laplacian: Analyst's Laplacian vs Geometer's Laplacian (they differ by a minus sign)
01:04:44 : Graph Laplacian: Some history
01:07:35 : Cheeger's Inequality: Statement
01:09:37 : ***Cheeger's Inequality: A great example of beautiful mathematics***
01:10:46 : Cheeger's Inequality: Computationally tractable approximation of Cheeger's constant
01:14:57 : Rayleigh quotient, discussion of proof of Cheeger's inequality
01:19:16 : Harmonic oscillators: Springs heuristic for lambda_2 and Cheeger's inequality
01:22:20 : Interlude: Tutte's Spring Embedding Theorem (planar embeddings in terms of springs)
01:26:23 : Harmonic oscillators: Resume lambda_2 discussion and spring tension
01:29:45 : Interlude: Graph drawing using eigenfunctions
01:33:17 : Harmonic oscillators: Resume lambda_2 discussion: complete graph example and bottleneck is a perturbation of two disconnected components
01:38:26 : Summary thus far and graph bisection
01:42:44 : Graph bisection: Large eigenvalues for PCA vs low eigenvalues for spectral bisection
01:43:40 : Graph bisection: 1-dimensional intuition
01:44:40 : Graph bisection: Nodal domains
01:46:29 : Graph bisection: Aha, the 1-d example now makes sense. Splitting by level set of second eigenfunction is a good way to partition domain.
01:47:43 : Spectral graph clustering (complementary to graph bisection)
01:51:50 : Ng-Jordan-Weiss paper
01:52:10 : PageRank: Google's algorithm for ranking search results
01:53:44 : PageRank: Markov chain (Markov matrix)
01:57:32 : PageRank: Stationary distribution
02:00:20 : Perron-Frobenius Theorem
02:06:10 : Spectral gap: Analogy between bottlenecks for graphs and bottlenecks for Markov chain mixing
02:07:56 : Conclusion: State of the field