New Analysis of Spectral Graph Algorithms through HIgher Eigenvalues

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.