Spectral Embedding and Higher-Order Cheeger Inequalities

Опубликовано 12 августа 2016, 3:18

A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero. In this talk I show an analogous characterization holds for higher multiplicities, i.e., there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. Our result provides a rigorous justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into R^k, and then apply heuristic geometric considerations to the embedding. Our proof is based on a fascinating new tool called the ``Spectral Embedding'' of graphs. If time allows I will also talk about new applications of this technique. Very recently, we use spectral embedding to prove tighter Cheeger inequalities. Also, using this tool we provide a unifying framework for lower bounding all the eigenvalues of normalized adjacency matrix of graphs. Consequently, our work introduces spectral embedding as a new tool in analyzing reversible Markov chains.