In the previous post, we saw that the sparsest cut of a graph (which is within a factor of 2 of the edge expansion of the graph), is defined as
and can also be written as
while the eigenvalue gap of , can be written as
and so it can be seen as a relaxation of , considering that
when are boolean.
Let us now take a broader look at efficiently computable continuous relaxations of sparsest cut, and see that the eigenvalue gap is a semidefinite programming relaxation of sparsest cut, that by adding the triangle inequality to it we derive the Arora-Rao-Vazirani relaxation, and that by removing the semidefinite constraint from the ARV relaxation we get the Leighton-Rao relaxation.
We first prove that (2) is equivalent to
The difference is that instead of optimizing over all possible ways to assign a real number to each vertex , we are now optimizing over all possible ways to assign a vector to each vertex . The absolute value is then replaced by the Euclidean distance . The right-hand-side of is clearly a relaxation of the right-hand-side of , so we just need to establish that, in the right-hand-side of , it is optimal to take 1-dimensional vectors. For every vector solution , we see that
where the last inequality follows from
which, in turn, has a one-line proof:
The formulation (3) is equivalent to the following semidefinite program:
An optimization problem is a semidefinite program if every variable is allowed to be an arbitrary vector, and both the objective function and the constraints are linear functions of inner products of pairs of variables. In our case,
is a linear combination of inner products, and so the formulation (5) is a semidefinite program. Another way to define semidefinite programming (indeed, the definition that is usually given first, deriving the one in terms of inner products as an equivalent characterization) is that a semidefinite program is an optimization problem in which the variables are the entries of a positive semidefinite matrix , and the objective function and the constraints are linear in the entries of . A real matrix is positive semidefinite if it is symmetric and all its eigenvalues are non-negative. We can see that an matrix is positive semidefinite if and only if there are vectors such that .
(The proof is simple: if is real and symmetric, then all its eigenvalues are real, and there is an orthonormal system of eigenvectors such that
If the eigenvalues are non-negative, we can let and have .
On the other hand, if there are such that , let be any eigenvalue of and be a length-1 eigenvector of . Then:
which completes the characterization.)
So we have gotten to the point where we can see as a semidefinite programming relaxation of sparsest cut. An interesting property of semidefinite programs is that, like linear programs, they admit a dual. From a minimization (primal) semidefinite program, we can write a maximization (dual) semidefinite program such that the cost of any feasible solution for the dual is a lower bound to the cost of any feasible solution for the primal; furthermore, the two programs have the same optimum cost. Returning to our motivating question of certifying the expansion of a given graph, any feasible solution to the dual of (5) gives us a lower bound to the expansion of the graph.
We shall have to suffer a bit longer before we can write the dual of (5). It is best to first move to a formulation in terms of entries of semidefinite matrices. A few calculations show that (5) can be written as
Where we write to mean that the matrix is positive semidefinite (we shall also write when is positive semidefinite), we write to mean , is the Laplacian of , that is the matrix , and is the Laplacian of the clique on vertices.
From this, we look up in Wikipedia the rules to form a semidefinite dual, and we get
It is possible to make sense of (7) independently of all the above discussion, that is, to see from first principles that the cost of any feasible solution to (7) is a lower bound to the sparsest cut of .
A feasible solution is a value and a positive semidefinite matrix such that . Equivalently, it is a value and vectors such that
Take any cut in . Then
and so the cost of the cut is at least . The justify the last inequality above, we need to prove that if is positive semidefinite than
We can also see, from first principles, that if are the eigenvalues of and is a corresponding system of eigenvectors, we can find a feasible solution to (7) of cost .
We defined , where we assume that is -regular. We can write
And we are almost there because , and it remains to prove that the matrix
is positive semidefinite. This we can see by noting that are eigenvectors of with eigenvalues . Alternatively, we could construct vectors such that .
Essentially, what is going on is that we are “embedding” a scaled version of the complete graph into our graph. The edge expansion and sparsest cut of the complete graph are known, and the semidefinite constraint in (7) is telling us that the difference between our graph and the scaled complete graph can only add to the sparsest cut, so the sparsest cut of is at least the known sparsest cut of the scaled complete graph.
Why did we go through all this trouble? Now that we understand the spectral gap inside out, we can derive the Arora-Rao-Vazirani relaxation (ARV) of sparsest cut by just adding the “triangle inequalities” to (5), and we can derive the Leighton-Rao relaxation by removing the semidefinite constraints from ARV. In the dual of Leighton-Rao, we again “embed” a complete graph in our graph, by realizing every edge as a flow. In the dual of ARV, we will find both flows and spectral considerations.
[to be continued]