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
which, together with the fact that and
, implies the Buser inequality
The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).
1. Ideas
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
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.
2. Definitions
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.
Hi Luca,
Thanks for the post! Do you think hierarchies might help with removing the dependence on $\sqrt{d}$?
Potentially, yes. At this point, even a sub-exponential time constant-factor approximation for Abelian Cayley graphs would be interesting, possibly by using hierarchies with
rounds