In which we prove the difficult direction of Cheeger’s inequality.
As in the past lectures, consider an undirected -regular graph , call its adjacency matrix, and its scaled adjacency matrix. Let be the eigenvalues of , with multiplicities, in non-increasing order. We have been studying the edge expansion of a graph, which is the minimum of over all non-trivial cuts of the vertex set (a cut is trivial if or ), where the expansion of a cut is
We have also been studying the (uniform) sparsest cut problem, which is the problem of finding the non-trivial cut that minimizes , where the sparsisty of a cut is
We are proving Cheeger’s inequalities:
and we established the left-hand side inequality in the previous lecture, showing that the quantity can be seen as the optimum of a continuous relaxation of , so that , and follows by the definition.
Today we prove the more difficult, and interesting, direction. The proof will be constructive and algorithmic. The proof can be seen as an analysis of the following algorithm.
- Input: graph and vector
- Sort the vertices of in non-decreasing order of values of entries in , that is let where
- Let be such that is minimal
We note that the algorithm can be implemented to run in time , assuming arithmetic operations and comparisons take constant time, because once we have computed it only takes time to compute .
We have the following analysis of the quality of the solution:
and let be the output of algorithm SpectralPartitioning on input and . Then
Remark 1 If we apply the lemma to the case in which is an eigenvector of , then , and so we have
which is the difficult direction of Cheeger’s inequalities.
Remark 2 If we run the SpectralPartitioning algorithm with the eigenvector of the second eigenvalue , we find a set whose expansion is
Even though this doesn’t give a constant-factor approximation to the edge expansion, it gives a very efficient, and non-trivial, approximation.
As we will see in a later lecture, there is a nearly linear time algorithm that finds a vector for which the expression in the lemma is very close to , so, overall, for any graph we can find a cut of expansion in nearly linear time.