We continue to talk about the problem of estimating the expansion of a graph , focusing on the closely related sparsest cut, defined as
The spectral paritioning algorithm first finds a vector minimizing
(where is the adjacency matrix of ) and then finds the best cut where is of the form for a threshold .
We proved that if the quantity in (1) is and is -regular, then the algorithm will find a cut of sparsity at most , and that if is the eigenvector of the second eigenvalue, then it is an optimal solution to (1), and the cost of an optimal solution to (1) is a lower bound to . This means that the algorithm finds a cut of sparsity at most .
Can the analysis be improved?
Consider first the case in which is a cycle of length , and is a vector such that are equally spaced between 0 and 1 (that is, ) and are equally spaced between 1 and 0 (that is, ). Then the ratio in (1) is , because the numerator is the sum of terms, each being , and the denominator is times a sum which is approximately times the average distance square of two random points in (which is ).
On the other hand, any cut of a cycle with edges has sparsity at least , because every cut is crossed by at least two edges, and the denominator in the definition of sparsest cut is at most .
This means that given a solution to (1) of cost , we cannot hope for a cut of sparsity because, in the case of the cycle, such a cut simply does not exist.
In which way, exactly, is the cycle a “bad” example for the spectral partitioning algorithm? After all, the algorithm will actually find an optimal cut. The point is that if we want our analysis to relate the value of the solution found by the algorithm to the optimum of (1), as we have done, then the existence of inputs on which the optimum of (1) is very far from the true optimum puts a limit to how good our analysis can be. In particular, such analysis cannot show that an algorithm can always find cuts of sparsity . To turn things around, if we had an analysis of any “spectral algorithm” which proved that the algorithm always finds cuts of sparsity , then our analysis must contain a proof that a cycle has expansion larger than , and so it must be implicitly defining a lower bound to sparsest cut which is sometimes asymptotically better than the spectral lower bound. As such, it would not be fair to think of it as “merely” a spectral algorithm since, at least implicitly, the algorithm relates to a tighter relaxation of the problem than implied by the optimum of (1). This issue always comes up when thinking about the limitations of rounding algorithms for convex relaxations, and although it may seem fuzzy to refer to what “really” is a rounding algorithm for a relaxation, it is inevitably so. Consider the “rounding” algorithm that given a relaxed solution discards it and just outputs an optimal solution found by other means. It seems ridiculous to consider it a “rounding” algorithm, but in which way it isn’t?
Returning to the concrete issue of the performance of the spectral partitioning algorithm which partitions based on thresholds, we could still ask the question of whether it might actually always find cuts of sparsity , and, if so, whether we may be able to prove it by some combination of spectral and combinatorial techniques.
Unfortunately the answer is again negative.
Consider a -dimensional hypercube. We can see that the “dimension cuts” are the sparsest cuts, and that their sparsity is 2. We studied the eigenvalues of the hypercube a while ago, and the spectral gap is also 2. The largest eigenvalue is , and then the second largest is , with multiplicity . A basis for the eigenspace of the eigenvalue is made of one vector for each dimension cut, defined by . This is great, because if we get one of these nice eigenvectors we immediately recover the corresponding, optimal, dimension cut by, say, setting the threshold to 0. The problem is that is also an eigenvector for the eigenvalue . Unfortunately, if is a vertex of the hypercube, then depends only on the number of ones of . (Namely, is equal to minus twice the number of ones in .) This means that the cut found by the spectral partitioning algorithm given will partition the vertices according to their weight. The best such cut (and the one found by the algorithm) is the “majority cut” of the hypercube, which has sparsity . This gives an example where the algorithm does indeed find a cut whose sparsity is as bad as .