In which we prove an analog of Cheeger’s inequalities for the largest Laplacian eigenvalue and we show how to use it to develop a spectral approximation algorithm for Max Cut.
1. Cheeger-type Inequalities for
Let be an undirected graph (not necessarily regular), its diagonal matrix of degrees, its adjacency matrix, its normalized Laplacian matrix, and be the eigenvalues of , counted with multiplicities and listed in non-decreasing order.
In Handout 2, we proved that if and only if has at least connected component and if and only if there is a connected component of (possibly, all of ) that is bipartite.
A special case of the former fact is that if and only if the graph is disconnected, and the Cheeger inequalities give a “robust” version of this fact, showing that can be small if and only if the expansion of the graph is small. In these notes we will see a robust version of the latter fact; we will identify a combinatorial parameter that is zero if and only if the graph has a bipartite connected component, and it is small if and only if the graph is “close” (in an appropriate sense) to having a bipartite connected components, and we will show that this parameter is small if and only if is small.
We will study the following combinatorial problem, which formalizes the task of finding an “almost bipartite connected component:” we are looking for a non-empty subset of vertices (we allow ) and a bipartition of such that there is a small number of “violating edges” compared to the number of edges incident on , where an edge is violating if it is in the cut , if it has both endpoints in , or if it has both endpoints in . (Note that if there are no violating edges, then is a bipartite connected component of .)
It will be convenient to package the information about as a vector , where the non-zero coordinates correspond to , and the partition of is given by the positive versus negative coordinates. We define the “bipartiteness ratio” of as
Note that in the numerator we have the number of violating edges, with edges contained in or in counted with a weight of 2, and edges from to counted with a weight of 1. In the denominator we have the sum of the degrees of the vertices of (also called the volume of , and written ) which is, up to a factor of 2, the number of edges incident on .
(Other definitions would have been reasonable, for example in the numerator we could just count the number of violating edges without weights, or we could have the expression . Those choices would give similar bounds to the ones we will prove, with different multiplicative constants.)
We define the bipartiteness ratio of as
We will prove the following analog of Cheeger’s inequalities:
The first inequality is the easy direction
The other direction follows by applying the following lemma to the case in which is the eigenvector of .
Lemma 1 (Main) For every there is a threshold , , such that, if we define as
Note that the Lemma is giving the analysis of an algorithm that is the “bipartite analog” of Fiedler’s algorithm. We sort vertices according to , and then we consider all sets which are suffixes of the sorted order and cut into according to sign. We pick the solution, among those, with smallest bipartiteness ratio. Given , such a solution can be found in time as in the case of Fiedler’s algorithm.
1.1. Proof of Main Lemma
We will assume without loss of generality that . (Scaling by a multiplicative constant does not change the Rayleigh quotient and does not change the set of that can be obtained from over the possible choices of thresholds.)
Consider the following probabilistic experiment: we pick at random in such that is uniformly distributed in , and we define the vector as in the statement of the lemma. We claim that
and we note that the Main Lemma follows from the above claim and from the fact, which we have used before, that if and are random variables such that , then there is a positive probability that .
We immediately see that
To analyze the numerator, we distinguish two cases
- If and have the same sign, and, let’s say, then there is a probability that both and are non-zero (and have the same sign), meaning that ; and there is an additional probability that and , so that . Overall we have
since the last expression is symmetric with respect to and , the equation
holds also if ;
- If and have opposite signs, and, let’s say, , there is probability that and , in which case , and otherwise we have . If , then equals 1 with probability and it equals zero otherwise. In either case, we have
In both cases, the inequality
Applying Cauchy-Schwarz as in the proof of Cheeger’s inequalities we have
and, combining all the bounds, we get (1).
2. Application to Max Cut
In the Max Cut problem, given an undirected graph we want to find a cut maximizing the number of cut edges . We call the fraction of edges of cut by the optimal solution. We see that if , then , as seen by taking the boolean vector such that iff .
This means that, in polynomial time, we can find a such that . Unfortunately, the number of non-zero vertices in could be very small, and so would not help find a way to partition all vertices.
We can, however, apply the algorithm of the previous section recursively: after we find , we remove the non-zero vertices from (because gives us a way to partition them with few violating edges) and then we can recurse on the residual graph. If the (volume of) the residual graph is very small, then we already almost have a global cut, and if the volume of the residual graph is large, then the optimal cut of is still a good cut in the residual graph, and it implies that is close to 2 and that we can find a of small bipartiteness ratio, and so on.
The overall algorithm is as follows:
- Use algorithm of previous section to find disjoint sets of vertices such that
- If , then return
- Let , and let be the subgraph of induced by
- Return best cut between and
We prove the following bound.
Lemma 2 If , then RecursiveSpectralCut finds a cut crossed by at least edges.
Proof: We proceed by induction on the number of recursive steps.
If there is no recursive call, then , and so is already a cut. The number of edges of that do not cross the cut is
because and . This settles the base case.
For the inductive step, the number of edges not cut by the algorithm is at most
because we should count all the edges with both endpoints in and both endpoints in , all the edges of not cut in the recursive step, and half of the edges from to , because the best way of combining the cuts loses at most half of those edges.
By using the fact that and the inductive hypothesis we have
where is defined so that .
Let us call the fraction of edges of that is not in . Then we have
We also have
because the number of edges not cut by the optimal cut of is at most the number of edges not cut by the optimal cut of , given that is a subgraph of . So we have
Putting everything together, the number of uncut edges is at most
where the last line is equivalent to
which follows from the fact that
For small , the bound of the previous lemma is close to the bound achieved by the Goemans-Williamson semidefinite programming-based algorithm, that, under the assumption that , finds a cut crossed by about a fraction of edges, which is best possible for polynomial time algorithms assuming the unique games conjecture.
The bound of the lemma is not very good for large , however: if , the lemma guarantees a number of cut edges that is less than half the number of edges, which is worse than the performance of a simple greedy algorithm, and if the lemma does not guarantee than any edge at all is cut.
If one always chooses the best between the cut returned by the recursion and a greedy cut, it is possible to derive an analysis that works well even in graphs in which the value of is small, and show that the algorithm finds a cut crossed by at least a fraction of edges.