New Analysis of Spectral Graph Algorithms through HIgher Eigenvalues


February 26, 2013


Shayan Oveis Gharan


Stanford University


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.


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