# CS294 Lecture 13: ARV Analysis, cont’d

In which we continue the analysis of the ARV rounding algorithm

We are continuing the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio ${O(\sqrt {\log |V|})}$.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

# CS294 Lecture 12: ARV Analysis

In which we begin the analysis of the ARV rounding algorithm

We want to prove

Lemma 1 (ARV Main Lemma) Let ${d}$ be a negative-type metric over a set ${V}$ such that the points are contained in a unit ball and have constant average distance, that is,

• there is a vertex ${z}$ such that ${d(v,z)\leq 1}$ for every ${v\in V}$
• ${\sum_{u,v\in V} d(u,v) \geq c\cdot |V|^2}$

Then there are sets ${S,T \subseteq V}$ such that

• ${|S|, |T| \geq \Omega(|V|)}$;
• for every ${u\in S}$ and every ${v\in T}$, ${d(u,v) \geq 1/{O(\sqrt {\log |V|})}}$

where the multiplicative factors hidden in the ${O(\cdot)}$ and ${\Omega(\cdot)}$ notations depend only on ${c}$.

In this lecture, we will show how to reduce the ARV Main Lemma to a statement of the following form: if ${\{ {\bf x}_v \}_{v\in V}}$ is a set of vectors such that the metric ${d(\cdot, \cdot)}$ in the ARV Main Lemma can be written as ${d(u,v) = || {\bf x}_u - {\bf x}_v ||^2}$, and ${{\bf g}}$ is a random Gaussian vectors, and if ${\ell}$ is such that with ${\Omega(1)}$ probability, there are ${\Omega(n)}$ disjoint pairs ${u,v}$ such that ${d(u,v) < \ell}$ and ${| \langle g, {\bf x}_u\rangle - \langle g, {\bf x}_v \rangle | \geq \Omega(1)}$, then ${\ell \geq \Omega(1/\sqrt{\log n})}$. We will then prove such a statement in the next lecture.

# CS294 Lecture 11: ARV

In which we introduce semi-definite programming and a semi-definite programming relaxation of sparsest cut, and we reduce its analysis to a key lemma that we will prove in the next lecture(s)

# CS294 Lecture 10: Bourgain’s Theorem

In which we prove Bourgain’s theorem.

Today we prove the following theorem.

Theorem 1 (Bourgain) Let ${d: V\times V \rightarrow {\mathbb R}}$ be a semimetric defined over a finite set ${V}$. Then there exists a mapping ${F: V \rightarrow {\mathbb R}^m}$ such that, for every two elements ${u,v \in R}$,

$\displaystyle || F(u) - F(v)||_1 \leq d(u,v) \leq ||F(u)-F(v)||_1 \cdot c\cdot \log |V|$

where ${c}$ is an absolute constant. Given ${d}$, the mapping ${F}$ can be found with high probability in randomized polynomial time in ${|V|}$.

Together with the results that we proved in the last lecture, this implies that an optimal solution to the Leighton-Rao relaxation can be rounded to an ${O(\log n)}$-approximate solution to the sparsest cut problem. This was the best known approximation algorithm for sparsest cut for 15 years, until the Arora-Rao-Vazirani algorithm, which will be our next topic.

# CS294 Lecture 9: The Sparsest Cut Problem

In which we introduce the sparsest cut problem and the Leighton-Rao relaxation.

1. The Uniform Sparsest Cut problem, Edge Expansion and ${\lambda_2}$

Let ${G=(V,E)}$ be an undirected graph with ${n:= | V |}$ vertices.

We define the uniform sparsity of a cut ${(S,V-S)}$ as

$\displaystyle {\sf usc}_G(S) := \frac {E(S,V-S)}{ |S| \cdot |V-S| }$

(we will omit the subscript when clear from the context) and the uniform sparsest cut of a graph is

$\displaystyle {\sf usc}(G):= \min_{S} {\sf usc}_G(S)$

In ${d}$-regular graphs, approximating the uniform sparsest cut is equivalent (up to a factor of 2 in the approximation) to approximating the edge expansion, because, for every cut ${(S,V-S)}$, we have

$\displaystyle \phi(S,V-S) = \frac {E(S,V-S)}{d \cdot \min \{ |S|, |V-S| \} }$

and, noting that, for every, ${S}$,

$\displaystyle \frac 1n |S| \cdot |V-S| \leq \min \{ |S|, |V-S| \} \leq \frac 2n |S| \cdot |V-S|$

we have, for every ${S}$,

$\displaystyle \phi (S,V-S) \leq \frac nd \cdot {\sf usc}(S) \leq 2 \phi(S,V-S)$

and so

$\displaystyle \phi(G) \leq \frac nd \cdot {\sf usc}(G) \leq 2 \phi(G)$

It will be instructive to see that, in ${d}$-regular graphs, ${\lambda_2}$ is a relaxation of ${\frac nd {\sf usc}(G)}$, a fact that gives an alternative proof of the easy direction ${\lambda_2 \leq 2 \phi(G)}$ of Cheeger’s inequalities.

# CS294 Lecture 8: Spectral Algorithms Wrap-up

In which we talk about even more generalizations of Cheeger’s inequalities, and we analyze the power method to find approximate eigenvectors, thus having a complete description of a polynomial-time approximation algorithm for sparsest cut

# I choose to remember Scalia by what he loved best

His own words:

• On where black kids should go to college

“There are those who contend that it does not benefit African-Americans to get them into the University of Texas, where they do not do well, as opposed to having them go to a less-advanced school, a less — a slower-track school, where they do well”

Scalia during oral arguments concerning Fisher vs. University of Texas

• Gay sex should be illegal, or else we may have less homophobia

“Today’s opinion is the product of a Court, which is the product of a law-profession culture, that has largely signed on to the so-called homosexual agenda, by which I mean the agenda promoted by some homosexual activists directed at eliminating the moral opprobrium that has traditionally attached to homosexual conduct. ”

Scalia’s dissent in Lawrence vs Texas

• Native Americans, during their religious rituals, cannot be excluded from obeying the law because of their religious belief

“Conscientious scruples have not, in the course of the long struggle for religious toleration, relieved the individual from obedience to a general law not aimed at the promotion or restriction of religious beliefs. The mere possession of religious convictions which contradict the relevant concerns of a political society does not relieve the citizen from the discharge of political responsibilities. (…) To permit this would be to make the professed doctrines of religious belief superior to the law of the land, and in effect to permit every citizen to become a law unto himself.”

Scalia’s majority opinion in Employment Division v. Smith

• To counteract the consequences of the above ruling, Congress passed the Religious Freedom Restoration Act, to protect the ability of religious minorities to carry on their rituals. Subsequently, the Supreme Court found that corporations have religious beliefs, and that not providing comprehensive health coverage is a ritual

“By requiring the Hahns and Greens and their companies to arrange for such coverage, the HHS mandate demands that they engage in conduct that seriously violates their religious beliefs. (…) The contraceptive mandate, as applied to closely held corporations, violates RFRA”

Alito’s majority opinion, joined by Scalia, in Burwell v. Hobby Lobby, inc.

• On the majority opinion in Obergefell v. Hodges

“If, even as the price to be paid for a fifth vote, I ever joined an opinion for the Court that began: ‘The Constitution promises liberty to all within its reach, a liberty that includes certain specific rights that allow persons, within a lawful realm, to define and express their identity,’ I would hide my head in a bag. The Supreme Court of the United States has descended from the disciplined legal reasoning of John Marshall and Joseph Story to the mystical aphorisms of the fortune cookie.”

Scalia’s dissent in Obergefell v. Hodges

# CS294 Lecture 7: Higher order Cheeger inequality, cont’d

In which we state an analog of Cheeger’s inequalities for the ${k}$-th smallest Laplacian eigenvalue, and we discuss the connection between this result and the analysis of spectral partitioning algorithms

# CS294 Lecture 6: Higher-order Cheeger Inequality

In which we state an analog of Cheeger’s inequalities for the ${k}$-th smallest Laplacian eigenvalue, and we discuss the connection between this result and the analysis of spectral partitioning algorithms

1. Cheeger-type Inequalities for ${\lambda_k}$

Let ${G=(V,E)}$ be an undirected ${d}$-regular graph, ${A}$ its adjacency matrix, ${L = I - \frac 1d A}$ 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 components, that is, if and only if there are ${k}$ disjoint sets ${S_1,\ldots,S_k}$ such that ${\phi(S_i) = 0}$ for ${i=1,\ldots,k}$. In this lecture and the next one we will prove a robust version of this fact.

First we introduce the notion of higher-order expansion. If ${S_1,\ldots,S_k}$ is a collection of disjoint sets, then their order-${k}$ expansion is defined as

$\displaystyle \phi_k (S_1,\ldots,S_k) = \max_{i=1,\ldots,k} \ \ \phi(S_i)$

and the order-${k}$ expansion of a graph ${G}$ is

$\displaystyle \phi_k(G )= \min_ {S_1,\ldots,S_k \ \rm disjoint } \ \ \phi(S_1,\ldots,S_k)$

If the edges of a graph represent a relation of similarity of affinity, a low-expansion collection of sets ${S_1,\ldots,S_k}$ represents an interesting notion of clustering, because the vertices in each set ${S_i}$ are more related to each other than to the rest of the graph. (Additional properties are desirable in a good clustering, and we will discuss this later.)

We will prove the following higher-order Cheeger inequalities:

$\displaystyle \frac { \lambda_k } 2 \leq \phi_k(G) \leq O(k^{3.5} ) \sqrt {\lambda_k}$

Stronger upper bounds are known, but the bound above is easier to prove from scratch. It is known that ${\phi_k (G) \leq O(k^2) \sqrt{\lambda_k}}$ and that ${\phi_k(G) \leq O_\epsilon ( \sqrt {\log k} ) \cdot \sqrt {\lambda_{(1+\epsilon) \cdot k} } }$.

# 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) }$