CS294 Lecture 5: Cheeger-type Inequalities for λn

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 {\lambda_n}

Let {G=(V,E)} be an undirected graph (not necessarily regular), {D} its diagonal matrix of degrees, {A} its adjacency matrix, {L = I - D^{-1/2} A D^{-1/2}} its normalized Laplacian matrix, and {0 = \lambda_1 \leq \cdots \leq \lambda_n \leq 2} be the eigenvalues of {L}, counted with multiplicities and listed in non-decreasing order.

In Handout 2, we proved that {\lambda_k = 0} if and only if {G} has at least {k} connected component and {\lambda_n = 2} if and only if there is a connected component of {G} (possibly, all of {G}) that is bipartite.

A special case of the former fact is that {\lambda_2 = 0} if and only if the graph is disconnected, and the Cheeger inequalities give a “robust” version of this fact, showing that {\lambda_2} 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 {2-\lambda_n} is small.

Recall that

\displaystyle  2- \lambda_n = \min_{{\bf x} \in {\mathbb R}^n - \{ {\bf 0} \}} \ \ \frac { \sum_{\{ u,v \} \in E} (x_u + x_v)^2 } {\sum_{v\in V} d_v x_v^2 }

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 {S\subseteq V} (we allow {S=V}) and a bipartition {(A,B)} of {S} such that there is a small number of “violating edges” compared to the number of edges incident on {S}, where an edge {\{ u,v\}} is violating if it is in the cut {(S,V-S)}, if it has both endpoints in {A}, or if it has both endpoints in {B}. (Note that if there are no violating edges, then {S} is a bipartite connected component of {G}.)

It will be convenient to package the information about {A,B,S} as a vector {{\bf y} \in \{ -1,0,1 \}^n}, where the non-zero coordinates correspond to {S}, and the partition of {S} is given by the positive versus negative coordinates. We define the “bipartiteness ratio” of {{\bf y}} as

\displaystyle  \beta( {\bf y} ) := \frac { \sum_{\{ u,v \} \in E} |y_u + y_v| } {\sum_{v\in V} d_v| y_v| }

Note that in the numerator we have the number of violating edges, with edges contained in {A} or in {B} counted with a weight of 2, and edges from {S} to {V-S} counted with a weight of 1. In the denominator we have the sum of the degrees of the vertices of {S} (also called the volume of {S}, and written {vol(S)}) which is, up to a factor of 2, the number of edges incident on {S}.

(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 {\sum_{\{ u,v \} \in E} (y_u + y_v)^2 }. Those choices would give similar bounds to the ones we will prove, with different multiplicative constants.)

We define the bipartiteness ratio of {G} as

\displaystyle  \beta(G) = \min_{{\bf y} \in \{-1,0,1\}^n - \{ {\bf 0} \} } \ \ \beta({\bf y} )

We will prove the following analog of Cheeger’s inequalities:

\displaystyle  \frac {2-\lambda_n}{2} \leq \beta(G) \leq \sqrt { 2 \cdot (2 - \lambda_n) }

Continue reading

On the Unique Games Conjecture (part 1)

[I am preparing a survey talk on Unique Games for a mathematics conference, and writing a survey paper for a booklet that will be distributed at the conference. My first instinct was to write a one-line paper that would simply refer to Subhash’s own excellent survey paper. Fearing that I might come off as lazy, I am instead writing my own paper. Here is part 1 of some fragments. Comments are very welcome.]

Khot formulated the Unique Games Conjecture in a remarkably influential 2002 paper. In the subsequent eight years, the conjecture has motivated and enabled a large body of work on the computational complexity of approximating combinatorial optimization problems (the original context of the conjecture) and on the quality of approximation provided by “semidefinite programming” convex relaxations (a somewhat unexpected byproduct). Old and new questions in analysis, probability and geometry have played a key role in this development. Representative questions are:

  • The central limit theorem explains what happens when we sum several independent random variables. What happens if, instead of summing them, we apply a low degree polynomial function to them?
  • In Gaussian space, what is the body of a given volume with the smallest boundary?
  • What are the balanced boolean function whose value is most likely to be the same when evaluated at two random correlated inputs?
  • What conditions on the Fourier spectrum of a function of several variables imply that the function essentially depends on only few variables?
  • With what distortion is it possible to embed various classes of finite metric spaces into L1?

Continue reading

Max Cut-Gain and the Smallest Eigenvalue

In June, I wrote about my work on using spectral partitioning to approximate Max Cut.

I have now posted a revised paper with a couple new things.

One is an improved analysis due to Moses Charikar, of the algorithm described in the June paper. Moses shows that if one starts from a graph in which the optimum cuts a 1-\epsilon fraction of edges, then the algorithm cuts at least a 1-4\sqrt \epsilon + 8\epsilon fraction of edges (and also at least half of the edges). Cutting more than a 1-\frac 2 \pi \sqrt \epsilon + o_\epsilon(1) fraction of edges is Unique-Games-hard. Optimizing the fraction

\displaystyle \frac{ \max \{ \ \frac 12  \ , \ (1-4\sqrt \epsilon + 8\epsilon) \ \} }{1-\epsilon}

we see that the approximation ratio of the algorithm is always at least .531.

The second new result answers a question raised by an anonymous commenter in June: what about Max Cut Gain? Continue reading

Max Cut and the Smallest Eigenvalue

In the Max Cut problem, we are given an undirected graph G=(V,E) and we want to find a partition (L,\bar L) of the set of vertices such that as many edges as possible have one endpoint in L and one endpoint in \bar L, and are hence cut by the partition.

It is easy, as recognized since the 1970s, to find a partition that cuts half of the edges and that, thus, is at least half as good as an optimal solution. No approximation better than 1/2 was known for this problem, until Goemans and Williamson famously proved that one could achieve a .878… approximation using semidefinite programming (SDP).

No other approximation algorithm achieving an approximation asymptotically better than 1/2 is known, and it seems that a fundamental difficulty is the following. Suppose we prove that a certain algorithm achieves approximation > 51\%. Then, given a graph in which the optimum is, say, < 50.4 \%, the algorithm and its analysis must provide a certificate that the optimum cut in the given graph is < 50.4/51 < 99\%, and there is no general technique to prove upper bounds to the Max Cut optimum of a general graph other than Semidefinite Programming. (And see here and here for negative results showing that large classes of linear programming relaxations are unable to give such certificates.)

Spectral techniques can prove upper bounds to Max Cut in certain cases (and can be seen as special cases of the upper bounds provided by the Goemans-Williamson relaxation).

In the simplified case in which G=(V,E) is a d-regular graph, let A be the adjacency matrix of G and \lambda_1 \geq \lambda_2 \geq \cdots \lambda_n be the eigenvalues of A; then it is easy to show that

(1) \ \ \ \displaystyle maxcut(G) \leq \frac 12  + \frac 12 \cdot \frac {|\lambda_n|}{d}

where maxcut(G) is the fraction of edges cut by an optimal solution. Unfortunately (1) does not quite have an approximate converse: there are graphs where |\lambda_n|=d but maxcut(G) = \frac 12 + o_d(1).

The following fact, however, is always true and well known:

  • |\lambda_n|=d if and only if G contains a bipartite connected component.

Is there an “approximate” version of the above statement characterizing the cases in which d-|\lambda_n| is small? Surprisingly, as far as I know the question had not been considered before.

For comparison, the starting point of the theory of edge expansion is the related fact

  • \lambda_2=d if and only if G is disconnected.

Which can be rephrased as:

  • \lambda_2=d if and only if there is a non-empty S\subseteq V, |S| \leq |V|/2 such that edges(S,V-S)=0.

Cheeger’s inequality characterizes the case in which d-\lambda_2 is small:

  • If there is a non-empty S\subseteq V, |S| \leq |V|/2 such that edges(S,V-S) \leq \epsilon \cdot d \cdot |S|, then \lambda_2 \geq d\cdot (1-2\epsilon);
  • If \lambda_2 \geq d\cdot (1-\epsilon) then there is a non-empty S\subseteq V, |S| \leq |V|/2 such that edges(S,V-S) \leq \sqrt{2 \epsilon} \cdot d \cdot |S|.

For a subset S\subseteq V, and a bipartition L,R=S-L of S, we say that an edge (i,j) fails [to be cut by] the bipartition if (i,j) is incident on S but it is not the case that one endpoint is in L and one endpoint is in R. (This means that either both endpoints are in L, or both endpoints are in R, or one endpoint is in S and one endpoint is not in S.) Then we can express the well-known fact about \lambda_n as

  • |\lambda_n|=d if and only if there is S\subseteq V and a bipartition of S with zero failed edges.

In this new paper I prove the following approximate version

  • If there is a non-empty S\subseteq V, and a bipartition of S with at most \epsilon \cdot d \cdot |S| failed edges, then |\lambda_n| \geq d\cdot (1-4\epsilon);
  • If |\lambda_n| \geq d\cdot (1-\epsilon), then there is a non-empty S\subseteq V, and a partition of S with at most \sqrt{2 \epsilon} \cdot d \cdot |S| failed edges.

The following notation makes the similarity with Cheeger’s inequality clearer. Define the edge expansion of a graph G as

\displaystyle h(G) = \min_{S\subseteq V. \ |S| \leq \frac {|V|}{2} } \frac {edges(S,V-S)} {d|S|}

Let us define the bipartiteness ratio of G as

\displaystyle \beta(G) = \min_{S, \ L \subseteq S, \ R=S-L} \frac{edges(L) + edges(R) + edges(S,V-S)}{d|S|}

that is, as the minimum ratio between failed edges of a partition of a set S over d|S|.

Then Cheeger’s inequality gives

\displaystyle \frac 12 \cdot \frac{d-\lambda_2}{d}  \leq h(G) \leq \sqrt{2 \cdot \frac{d-\lambda_2}{d} }

and our results give

\displaystyle \frac 14 \cdot \frac{d-|\lambda_n|}{d} \leq \beta(G) \leq \sqrt{2 \cdot \frac{d-|\lambda_n|}{d}}

This translates into an efficient algorithm that, given a graph G such that maxcut(G) \geq 1-\epsilon, finds a set S and a bipartition of S such that at least a 1- 4\sqrt{\epsilon} fraction of the edges incident on S are cut by the bipartition. Removing the vertices in S and continuing recursively on the residual graph yields a .50769… approximation algorithm for Max Cut. (The algorithm stops making recursive calls, and uses a random partition, when the partition of S found by the algorithm has too many failed edges.)

The paper is entirely a by-product of the ongoing series of posts on edge expansion: the question of relations between spectral techniques to max cut was asked by a commenter and the probabilistic view of the proof of Cheeger’s inequality that I wrote up in this post was very helpful in understanding the gap between \lambda_n and -d.