New Analysis of Spectral Graph Algorithms through HIgher Eigenvalues

Date

February 26, 2013

Speaker

Shayan Oveis Gharan

Affiliation

Stanford University

Overview

Spectral graph algorithms are simple heuristics that explore the structure of a graph using eigenvectors of its adjacency matrix or its various normalizations. They are usually fast, simple to implement, and widely used in practice for data clustering, image segmentation, community detection, and VLSI design.

In practice, spectral algorithms that employ several eigenvectors usually outperform those that use very few. However, classical analyses of spectral graph algorithms have only exploited two eigenvalues or eigenvectors. For example, Cheeger’s famous and influential inequality relates the second eigenvalue of a graph to the sparsity of its sparsest cut [Alon,Milman’85].

In this talk, I will explore a number of spectral graph algorithms that use higher-order eigenvalues, and analyze their performance. I will present joint results that create a bridge between the classical analysis of spectral graph algorithms and their practical applications. For example, we generalize the Cheeger’s inequality by relating the k-th eigenvalue of a graph to the sparsity of k-way partitionings. This gives a rigorous justification for spectral clustering algorithms that use several eigenvectors. Our analysis provides new insights and introduces new components that can improve the performance of classical spectral clustering algorithms.

Speakers

Shayan Oveis Gharan

Shayan Oveis Gharan is currently finishing his PhD at Stanford University under the supervision of Amin Saberi. Prior to Stanford, Shayan received a BA in computer engineering from Sharif University of Technology. His research interests include Approximation Algorithms, Spectral Algorithms, Online Algorithms and Applied Probability. He is a recipient of several awards including best paper award at SODA 2010 and FOCS 2011 for his works on the Traveling Salesman Problem, Stanford Graduate Fellowship, and the Miller Fellowship