Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile

We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph G, $\lambda_2 = \Omega(\phi^V(G) \phi(G))$, where $\phi^V(G)$ denotes the robust vertex expansion of G and $\phi(G)$ denotes the edge expansion of G. The second generalization relates the second eigenvalue to the edge expansion and the expansion profile of G, for all $k \ge 2$, $\lambda_2 = \Omega(\phi_k(G) \phi(G) / k)$, where $\phi_k(G)$ denotes the k-way expansion of G. These show that the spectral partitioning algorithm has better performance guarantees when $\phi^V(G)$ is large (e.g. planted random instances) or $\phi_k(G)$ is large (instances with few disjoint non-expanding sets). Both bounds are tight up to a constant factor. Our approach is based on a method to analyze solutions of Laplacian systems, and this allows us to extend the results to local graph partitioning algorithms. In particular, we show that our approach can be used to analyze personal pagerank vectors, and to give a local graph partitioning algorithm for the small-set expansion problem with performance guarantees similar to the generalizations of Cheeger's inequality. We also present a spectral approach to prove similar results for the truncated random walk algorithm. These show that local graph partitioning algorithms almost match the performance of the spectral partitioning algorithm, with the additional advantages that they apply to the small-set expansion problem and their running time could be sublinear. Our techniques provide common approaches to analyze the spectral partitioning algorithm and local graph partitioning algorithms.