Continuing from the previous post, we are going to prove the following result: let be a -regular Cayley graph of an Abelian group, be the normalized edge expansion of , be the value of the ARV semidefinite programming relaxation of sparsest cut on (we will define it below), and be the second smallest normalized Laplacian eigenvalue of . Then we have
For a positive integer parameter , call the multigraph whose adjacency matrix is , where is the adjacency matrix of . So is a -regular graph, and each edge in corresponds to a length- walk in . Our proof boils down to showing
which gives (1) after we note that
and we combine the above inequalities with :
The reader will see that our argument could also prove (roughly as done by Bauer et al.) that , simply by reasoning about distributions of cuts instead of reasoning about ARV solutions, which would give (2) more directly. By reasoning about ARV solutions, however, we are also able to establish (3), which we think is independently interesting.
It remains to prove (4). I will provide a completely self-contained proof, including the definition of Cayley graphs and of the ARV relaxation, but, first, here is a summary for the reader already familiar with this material: we take an optimal solution of ARV for , and bound how well it does for . We need to understand how much bigger is the fraction of edges cut by the solution in compared to the fraction of edges cut in ; a random edge in is obtained by randomly sampling generators and adding them together, which is roughly like sampling times each generator, each time with a random sign. Because of cancellations, we expect that the sum of these random generators can be obtained by summing roughly copies of each of the generators, or generators in total. So a random edge of corresponds roughly to edges of , and this is by how much, at most, the fraction of cut edges can grow.
Now we present more details and definition. Recall that if is a group, for which we use additive notation, and is a set or multiset of group elements, then the Cayley graph is the graph that has a vertex for every group element and an edge for every group element and every element . We restrict ourselves to undirected graphs, so we will always assume that if is an element of , then is also an element of (with the same multiplicity, if if a multiset). Note that the resulting undirected graph is -regular.
Several families of graphs can be seen to be Cayley graphs, including cycles, cliques, balanced complete bipartite graphs, hypercubes, toruses, and so on. All the above examples are actually Cayley graphs of Abelian groups. Several interesting families of graphs, for example several families of expanders, are Cayley graphs of non-Abelian groups, but the result of this post will apply only to Abelian groups.
To define the ARV relaxation, let us take it slowly and start from the definition of the sparsest cut problem. The edge expansion problem is closely related to the sparsest cut problem, which can be defined as
where is the normalized Laplacian of and is the normalized Laplacian of the clique on vertices. We wrote it this way to emphasize the similarity with the computation of the second smallest normalized Laplacian eigenvalue, which can be written as
where the second equality is perhaps not obvious but is easily proved (all the solutions have the same cost function on both sides, and the last expression is shift invariant, so there is no loss in optimizing over all or just in the space ). We see that the computation of is just a relaxation of the sparsest cut problem, and so we have
We can write the sparsest cut problem in a less algebraic version as
and recall that
The cost function for does not change if we switch with , so could be defined equivalently as an optimization problem over subsets , and at this point and are the same problem except for an extra factor of in the denominator of . Such a factor is always between and , so we have:
(Note that all these definitions have given us a particularly convoluted proof that .)
Yet another way to characterize is as
Where is the Frobenius inner product between matrices. This is also something that is not obvious but that it is not difficult to prove, the main point being that if we write a PSD matrix as , then
and so there is no loss in passing from an optimization over all PSD matrices versus all rank-1 PSD matrices.
We can rewrite in terms of the Cholesky decomposition of as
where the correspondence between PSD matrices and vectors is that we have (that is, is the Cholesky decomposition of and is the Gram matrix of the ). An integral solution of the sparsest cut problem corresponds to choosing rank and solutions in which each 1-dimensional is either 1 or 0, corresponding on whether is in the set or not. The ARV relaxation is
which is a relaxation of sparsest cut because the “triangle inequality” constraints that we introduced are satisfied by 1-dimensional 0/1 solutions. Thus we have
3. The Argument
Let us take any solution for ARV, and let us symmetrize it so that the symmetrized solution satisfies
That is, make sure that the contribution of each edge to the numerator of the cost function depends only on the generator that defines the edge, and not on the pair of endpoints.
It is easier to see that this symmetrization is possible if we view our solution as a PSD matrix . In this case, for every group element , we can let be the solution (with the same cost) obtained by permuting rows and columns according to the mapping ; then we can consider the solution , which satisfies the required symmetry condition.
Because of this condition, the cost function applied to in is
and the cost function applied to in is
meaning that our goal is now simply to prove
or, if we take a probabilistic view
If we let be the number of times that generator appears in the sum , counting cancellations (so that, if appears 4 times and appears 6 times we let and ) we have
where multiplying an integer by a generator means adding the generator to itself that many times. Using the triangle inequality and the symmetrization we have
The next observation is that, for every ,
where the expectation is over the choice of . This is because can be seen as , where we define if , if and otherwise. We have
Combining everything, we have
So every solution of ARV for is also a solution for with a cost that increases at most by a factor, which proves (4) as promised.
4. A Couple of Interesting Questions
We showed that ARV has integrality gap at most for every -regular Abelian Cayley graph, but we did not demonstrate a rounding algorithm able to achieve an approximation ratio.
If we follow the argument, starting from an ARV solution of cost , choosing of the order of we see that has an ARV solution (the same as before) of cost at most, say, , and so , implying that and so Fiedler’s algorithm according to a Laplacian eigenvalue finds a cut of sparsity at most .
We can also see that if is the matrix corresponding to an ARV solution of value for , then one of the eigenvectors of must be a test vector of Rayleigh quotient at most for the Laplacian , where is order of . However it is not clear how to get, from such a vector, a test vector for the Laplacian of of Rayleigh quotient at most for the Laplacian of , though one such vector should be for a properly chosen in the range .
If this actually work, then the following, or something like that, would be a rounding algorithm: given a PSD solution of ARV of cost , consider PSD matrices of the form , which do not necessarily satisfy the triangle inequalities any more, for , and try to round them using a random hyperplane. Would this make sense for other classes of graphs?
It is plausible that sparsest cut in Abelian Cayley graphs has actually a constant-factor approximation in polynomial or quasi-polynomial time, and maybe either that ARV achieves constant-factor approximation.