In which we dwell at great length on the “easy” part of Cheeger’s inequality.
The edge expansion of a graph , defined as
is a measure of how “well connected” is a graph. A graph has edge expansion at least if and only if, in order to disconnect a set of vertices from the rest of the graph, one must remove at least edges. In other words, the removal of edges from a graph of edge expansion must leave a connected component of size , where is the number of vertices.
As readers of in theory know, graphs of large edge expansion (expander graphs) have many applications, and in this post we are going to return to the question of how one certifies that a given graph has large edge expansion.
For simplicity, we shall only talk about regular graphs. In a previous post we mentioned that if is the adjacency matrix of a graph, there are numbers (the eigenvalues of ), not necessarily distinct, and an orthonormal basis of , such that for all
And if the graph is -regular, then , , and for all we have . Finally, the numbers and the vectors are computable in polynomial time. (This is all the linear algebra we will need.)
Given this setup, we have the lower bound
That is, the difference between largest and second largest eigenvalue gives a lower bound to the edge expansion of the graph.
Although (1) is very easy to prove, it is a remarkable result, in the sense that it gives a polynomial-time computable certificate of a “coNP” statement, namely, that for all cuts, at least a certain number of edges cross the cut. Since computing edge expansion is NP-complete, the inequality cannot always be tight. Eventually shall compare it with other methods to lower bound the edge expansion, and see that they are all special cases of the same general approach. To begin with, in this post we shall show that is an efficiently computable relaxation of the edge expansion problem. (Or, rather, of the closely related sparsest cut problem.)
We define the sparsest cut of a graph as
Clearly we have
so we need to prove . We will do so by showing that is a relaxation of , that is, the computation of can be seen as an optimization problem that is identical to , except that we optimize over a bigger range of feasible solutions. To get started, we need to think about eigenvalues as solutions to optimization problems. This comes from characterizing eigenvalues via Rayleigh quotients. For our purposes (in which is the adjacency matrix of a -regular graph) we shall use the following simple identity
To prove the identity, take any vector orthogonal to (and hence to ), and write it in the orthonormal basis as
then the quotient in (2) is
and the quotient is equal to when .
The next step is to consider, for a vector , the quadratic form
which (up to normalization) measures the expected value of the quantity for a random edge , that is, how much the value of changes along edges. Since is the adjacency matrix of a -regular graph, we have
and so, combined with equation (2), we have
We are almost done with our manipulations. In the same spirit as Equation (4) we have
where is the matrix with a 1 in every entry. If , then
is the all-zero vector, and so we have
Finally, we observe that the quotient in (7) does not change if one adds the same constant to each coordinate of , and for every vector there is a contant (the average of the entries of ) such that is orthogonal to . This means that the requirement to optimize over vectors orthogonal to can be removed from (7) with no loss of generality. Hence,
Compare now Equation to the following way to look at sparsest cut, which is clearly equivalent to the standard definition
where the last equality comes from the fact that the absolute value of the difference of two boolean values is a boolean value, and hence equal to its square.
So we have found the reason why . Both and are the solution of a minimization problem, the cost function is the same in the two problems, but in the case of we are allowed to optimize over all of , while in the case of we restrict ourselves to .
In computer science, we very often see cases of intractable minimization combinatorial problems that can be relaxed to continuous optimization problems which can then be optimally solved, and the optimal solution of the relaxation gives a lower bound to the minimum of the combinatorial problem. When our continuous relaxation is a linear program, we have a theory of duality that gives us a maximization continuous dual problem such that the cost of any solution to the dual problem gives a lower bound to the optimum of the primal linear problem, and hence a lower bound to the minimum of the combinatorial problem.
Although it is not clear from the formulations given so far, it is possible to cast the computation of as the optimum of a semidefinite programming relaxation of sparsest cut; such a relaxation admits a semidefinite dual, and so any solution that is feasible for that semidefinite dual provides a lower bound to edge expansion. (And this fact can be checked very simply, with no reference to eigenvalues and eigenvectors, although there is in general no easier way to construct semidefinite dual feasible solutions than to use a system of eigenvectors.) This will be the subject of the next post.