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