Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A theory of spectral graph clustering

Algebra & Discrete Mathematics

Speaker: Luca Trevisan
Location: 2112 MSB
Start time: Wed, Mar 7 2018, 4:10PM

In spectral graph theory, one is interested in relating
combinatorial properties of a graph to properties of the eigenvalues
and eigenvectors of certain matrices associated to the graph, such as
the adjacency matrix or the Laplacian matrix. A foundational result is
Cheeger's inequality, which relates the second smallest normalized
Laplacian eigenvalue of a graph to its "conductance," which is a
measure of whether the graph can be partitioned in a meaningful way
into two "clusters."

We discuss a higher-order version of Cheeger's inequality, relating
the k-th smallest normalized Laplacian eigenvalue to how well the
graph can be split into k clusters. The result has an algorithmic
proof that partly explains why spectral embeddings are useful in
practice for clustering problems. The ideas in the proof have been
applied to solve a conjecture from the 1970s about
infinite-dimensional Markov processes. I will also discuss some other
generalizations of Cheeger's inequality that take the full spectrum of
the normalized Laplacian into account.

The talk is based on joint work with Tsz-Chiu Kwok, Lap-Chi Lau,
James Lee, Yin-Tat Lee, and Shayan Oveis-Gharan