John Urschel | Tackling Graph Theory

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.

Patreon: https://www.patreon.com/timothynguyen

Originally published on June 9, 2022 on YouTube: https://youtu.be/O6k0JRpA2mg

Timestamps:

I. Introduction

• 00:00: Introduction
• 04:30: Being a professional mathematician and academia vs industry
• 09:41: John's taste in mathematics
• 13:00: Outline
• 17:23: Braess's Paradox: "Opening a highway can increase traffic congestion."
• 25:34: Prisoner's Dilemma. We need social forcing mechanisms to avoid undesirable outcomes (traffic jams).

II. Spectral Graph Theory Basics

• 31:20: What is a graph
• 36:33: Graph bottlenecks. Practical situations: Task assignment, the economy, organizational management.
• 42:44: Quantifying bottlenecks: Cheeger's constant
• 46:43: Cheeger's constant sample computations
• 52:07: NP Hardness
• 55:48: Graph Laplacian
• 1:00:27: Graph Laplacian: 1-dimensional example

III. Cheeger's Inequality and Harmonic Oscillators

• 1:07:35: Cheeger's Inequality: Statement
• 1:09:37: Cheeger's Inequality: A great example of beautiful mathematics
• 1:10:46: Cheeger's Inequality: Computationally tractable approximation of Cheeger's constant
• 1:19:16: Harmonic oscillators: Springs heuristic for lambda_2 and Cheeger's inequality
• 1:22:20: Interlude: Tutte's Spring Embedding Theorem (planar embeddings in terms of springs)
• 1:29:45: Interlude: Graph drawing using eigenfunction

IV. Graph bisection and clustering

• 1:38:26: Summary thus far and graph bisection
• 1:42:44: Graph bisection: Large eigenvalues for PCA vs low eigenvalues for spectral bisection
• 1:43:40: Graph bisection: 1-dimensional intuition
• 1:47:43: Spectral graph clustering (complementary to graph bisection)

V. Markov chains and PageRank

• 1:52:10: PageRank: Google's algorithm for ranking search results
• 1:53:44: PageRank: Markov chain (Markov matrix)
• 1:57:32: PageRank: Stationary distribution
• 2:00:20: Perron-Frobenius Theorem
• 2:06:10: Spectral gap: Analogy between bottlenecks for graphs and bottlenecks for Markov chain mixing
• 2:07:56: Conclusion: State of the field, Urschel's recent results
• 2:10:28: Joke: Two kinds of mathematicians

Further Reading:

• A. Ng, M. Jordan, Y. Weiss. "On Spectral Clustering: Analysis and an algorithm"
• D. Spielman. "Spectral and Algebraic Graph Theory"