[In which we finally get to Leighton-Rao and ARV.]
Continuing our edge expansion marathon, we are going to see more ways in which the sparsest cut problem can be relaxed to polynomial-time solvable continuous problems. As before, our goal is to understand how this implies certificates of expansion.
We are talking about the sparsest cut of a graph , which is
We have looked for a while at the eigenvalues gap of . If is -regular and the second largest eigenvalue of is , then the difference between largest and second largest eigenvalue obeys
and, noting that when , we saw that is a relaxation of , and .
Leighton and Rao derive a continuous relaxation of in quite a different way. They note that when , then the “distance”
induces a semi-metric on , that is, , , and the triangle inequality holds
One can then consider the relaxation
where the minimum is taken over all distance functions that define a semi-metric on .
We can rewrite (1) as the linear program
where we only write the triangle inequality constraints by having one variable for every unordered pair .
The minimum of (2) gives a lower bound to the sparsest cut of , and so every feasible solution for the dual of (2) gives a lower bound to .
Before trying to write down the dual of (2), it is convenient to write (2) in a less efficient way. (This is akin to the fact that sometimes, when using induction, it is easier to prove a more general statement.) Instead of writing the triangle inequality for every three vertices, we write it for every arbitrary sequence of vertices.
where we denote by the set of “paths” in the complete graph between and . (That is, is the set of all sequences of vertices that start at and end at .)
Clearly (3) is the same as (2), in the sense that the extra inequalities present in (3) are implied by the triangle inequalities in (2). The dual of (3), however, is cleaner, and is given below
A feasible solution to (4) is thus a weighted set of paths and a parameter . Before reasoning about the meaning of a solution, suppose that satisfy the stronger constraints
Then we can view the as defining a flow between that carries at least units of flow; furthermore, the union of all such flows uses at most a total capacity on each edge . We should think of it as an embedding of the complete graph scaled by into . I want to claim that this means that the sparsest cut of is at least times the sparsest cut of the complete graph, that is, at least .
To verify the claim, take any cut . We know that such a cut separates pairs of vertices , and that at least units of flow are routed between each such pair, so that at least units of flow cross the cut. Since every edge has capacity 1, we see that at least edges of must cross the cut.
It remains to bridge the difference between (4) or (5). One possibility is to show that a solution to (4) can be modified to a solution satisfying (5) with no loss in . Another approach is to directly use (4) and a general weak duality argument to show directly that a solution satisfying (4) implies that has at least the edge expansion of a complete graph with edge weights .
There is, in fact, a broader principle at work, which we can verify by a similar argument: if is an assignment of weights to all possible paths (which we think of as defining a multicommodity flow), is a graph with adjacency matrix , is a graph with adjacency matrix , and we have
then we must have .
The fact that a feasible solution to (4) gives a lower bound to is a special case that applies to the case in which is a scaled version of the complete graph.
This is a good point to pause, look back again at the bound coming from spectral considerations, and compare it with what we have here.
(A couple of notes. (i) From now on it will be convenient to identify a graph with its adjacency matrix. (ii) About notation: recall that if is a -regular graph then its Laplacian is ; more generally, if is a matrix then its Laplacian is defined so that when , and . Observe that is linear, that is, and .)
In the spectral bound, we find a such that is positive semidefinite, and we use this fact to prove that . This works because if and are two symmetric matrices such that , then . In the analysis of the spectral gap, we apply it to the case in which is a scaled version of the complete graph.
An important note: is not a 0/1 matrix, and in fact it may have negative entries. The quantity is, however, always well defined as
To wrap up our comparisons, in both cases we prove a lower bound on by showing that where is a scaled version of the complete graph, so that we know the exact value of . In the spectral analysis, we argue that by showing that
in the Leighton-Rao approach we find a system of multicommodity flows such that
where, to clean up the notation, we define
The two approaches are incomparable, and, naturally, we would like to combine them into a single approach that subsumes both.
Suppose that we find a graph and flows such that
where, again, .
Then, by spectral considerations,
but by Leighton-Rao reasoning
This approach subsumes the two because if are two matrices such that for every entry, then . (This is “obvious” to people who know some linear algebra, but it is actually a great exercise to get the vector solution that proves that is positive semidefinite.)
Hence the following semidefinite program produces lower bound certificates for the sparsest cut of . (As before, we shall take to be a scaled version of the complete graph.)
To make sense of it, we need to understand and a bit better. Let be the matrix that has ones in the and entry, and zeroes everywhere else; hence is the adjacency matrix of the graph consisting of the single edge . Then
where is the matrix that has a one in each entry corresponding to an edge in , a in the entry , where and are the end-points of the path , and zeroes everywhere else. (Equivalently, for a path , the matrix is the adjacency matrix of the graph that has the path plus an edge of weight connecting the endpoints of the path.)
Our semidefinite program (6) now takes the form
We again look up in wikipedia how to form the dual of (7), and we get
Which is a more constrained version of the semidefinite program that gives the spectral bound. Let us unfold what means, and see that it is indeed a natural semidefinite programming relaxation of , and it subsumes the spectral and the Leighton-Rao relaxations. (Although we already know that this is going to be the case given duality considerations.)
If we let be a system of vectors such that , then from our past work on the spectral relaxation, we know how to make sense of the objective function and of the first constraint.
We leave it to the reader to verify that if is a path with endpoints , then
and so the constraints are checking that the “distance function” satisfies the triangle inequality.
We can rewrite in the following form, which makes it clear that is a relaxation of and a strengthening of both the spectral bound and the Leighton-Rao linear program.
This is the Arora-Rao-Vazirani semidefinite programming relaxation of sparsest cut.
Notice that if we have a solution to the sparsest cut problem we can turn into a feasible solution to (9) by letting be a one-dimensional solution; if we have a feasible solution to (9), then it is feasible for the spectral relaxation (which does not require the triangle inequalities) and it is feasible for Leighton-Rao, by setting .
And so we have defined our three relaxations of sparsest cut and their duals, and understood “why” dual solutions give certificates of expansion.
It remains to see how close the optima of the relaxations are to , a question that is answered by algorithmic techniques to “round” a relaxed solution into a cut of comparable cost. If we wonder how good such roundings can be, we are led to the study of metric embeddings.