
Speaker Shayan Oveis Gharan Affiliation Stanford University Host Yuval Peres Duration 00:54:04 Date recorded 26 February 2013 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 higherorder 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 kth eigenvalue of a graph to the sparsity of kway 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.
©2013 Microsoft Corporation. All rights reserved.
By the same speakerPeople also watched 