CS359G Lecture 10: Non-uniform Sparsest Cut

In which we prove that there are ${n}$ -point metric spaces that cannot be embedded into L1 with distortion ${o(\log n)}$ , and we see further applications of Leighton-Rao type relaxations and of the use of metric embeddings as rounding schemes.

1. Tightness of the Analysis of the Leighton-Rao Relaxation

If ${(X,d)}$ and ${(X',d')}$ are metric spaces, we say that a mapping ${f: X \rightarrow X'}$ is an embedding of ${(X,d)}$ into ${(X',d)}$ with distortion at most ${c}$ if there are parameters ${c_1,c_2}$ , with ${c=c_1c_2}$ such that, for every ${u,v\in X}$ , we have

$\displaystyle \frac 1 {c_1} \cdot d'(u,v) \leq d(u,v) \leq c_2 \cdot d'(u,v)$

The metric space ${{\mathbb R}^m}$ with distance ${||u-v|| = \sqrt{ \sum_i (u_i-v_i)^2}}$ is denoted by ${\ell_m^2}$ , and the metric space ${{\mathbb R}^m}$ with distance ${||u-v||_1 = \sum_i |u_i-v_i|}$ is denoted by ${\ell_m^1}$ . In the past lecture we proved the following result.

Theorem 1 (Bourgain) There is an absolute constant ${c}$ such that every finite metric space ${(V,d)}$ embeds into ${\ell_m^1}$ with distortion at most ${c \log |V|}$ , where ${m = O(\log^3 |V|)}$ .

If we solve the Leighton-Rao linear programming relaxation to approximate the sparsest cut of a graph ${G=(V,E)}$ , and we let ${d(\cdot,\cdot)}$ be an optimal solution, we note that, if we weigh each edge ${(u,v)\in E}$ by ${d(u,v)}$ , and then compute shortest paths in this weighted graph, then, for every two vertices ${x,y}$ , the distance ${d(x,y)}$ is precisely the length of the shortest path from ${x}$ to ${y}$ . In particular, if we are using the Leighton-Rao relaxation in order to approximate the sparsest cut in a given planar graph, for example, then the solution ${d(\cdot,\cdot)}$ that we need to round is not an arbitrary metric space, but it is the shortest path metric of a weighted planar graph. It is conjectured that, in this case, the Leighton-Rao relaxation could deliver a constant-factor approximation.

Is there an absolute constant ${c}$ such that every metric space ${(X,d)}$ constructed as the shortest-path metric over the vertices of a planar graph can be embedded into ${\ell_m^1}$ with distortion at most ${c}$ , where ${m = |V|^{O(1)}}$ ?

So far, it is known that ${k}$ –outerplanar graphs, for constant ${k}$ , embed in ${\ell^1}$ with constant distortion.

This is just an example of a large family of questions that can be asked about the embeddability of various types of metric spaces into each other.

For general finite metric spaces, the logarithmic distortion of Bougain’s theorem is best possible.

In order to prove the optimality of Bourgain’s theorem, we will state without proof the existence of constant degree families of expanders. In a later part of the course we will prove their existence and give efficient constructions.

Theorem 2 (Existence of Expanders) There are absolute constants ${d}$ and ${c}$ such that, for infinitely many ${n}$ , there is an ${n}$ -vertex ${d}$ -regular graph ${G_n}$ such that ${\phi(G_n)\geq c}$ .

On such graphs, the Leighton-Rao relaxation is ${LR(G_n) \leq O(1/\log n)}$ , showing that our proof that ${LR(G) \geq \phi(G)O(log n)}$ is tight.

For every two vertices ${u,v}$ , define ${d(u,v)}$ as the length of (that is, the number of edges in) a shortest path from ${u}$ to ${v}$ in ${G_n}$ .

Then

$\displaystyle \sum_{u,v} A_{u,v} d(u,v) = 2|E|$

Because each graph ${G_n}$ is ${d}$ -regular, it follows that for every vertex ${v}$ there are ${\leq 1 + d+ \cdots + d^k < d^{k+1}}$ vertices at distance ${\leq k}$ from ${v}$ . In particular, at least half of the vertices have distance ${\geq t}$ from ${v}$ , where ${t = \lfloor \log_{d} n/2 \rfloor - 1}$ , which implies that

$\displaystyle \sum_{u,v} d(u,v) \geq n \cdot \frac n2 \cdot t = \Omega( n^2 \log n)$

Recall that

$\displaystyle LR(G) = \min_{d \ {\rm semimetric}} \frac {|V|^2}{2|E|} \frac {\sum_{u,v} A_{u,v} d(u,v)}{\sum_{u,v} d(u,v) }$

and so

$\displaystyle LR(G_n) \leq O\left( \frac 1 {\log n} \right)$

even though

$\displaystyle \phi(G_n) \geq \Omega(1)$

Note that we have also shown that every embedding of the shortest-path metric ${d(\cdot,\cdot)}$ on ${G_n}$ into ${\ell^1}$ requires distortion ${\Omega(\log n)}$ , and so we have proved the tightness of Bourgain’s theorem.

2. The Non-Uniform Sparsest Cut Problem

In the non-uniform sparsest cut problem, we are given two graphs ${G=(V,E_G)}$ and ${H= (V,E_H)}$ over the same set of vertices, and we want to find a non-trivial cut ${(S,V-S)}$ of the vertex set that minimizes the non-uniformity sparsity

$\displaystyle \phi(G,H,S) := \frac {|E_H|}{|E_G|} \cdot \frac{\sum_{(u,v) \in G} |1_S(u) - 1_S(v)|}{\sum_{(u,v) \in H} |1_S(u) - 1_S(v)|}$

The non-uniformity sparsity of an optimal solution is denoted by ${\phi(G,H)}$ . Note that the standard sparsest cut problem corresponds to taking ${H}$ to be a clique.

The graph ${G}$ is called the capacity graph and the graph ${H}$ is called the demand graph. This terminology will become more clear when we discuss the dual of the Leighton-Rao relaxation of sparsest cut at a later point. The intuition for the problem is that ${H}$ specifies which pairs of nodes we would like to see disconnected in ${G}$ , and our goal is to find a set of edges to remove such that their number is small compared to the number of pairs of elements of ${H}$ that are disconnected by their removal.

We can easily adapt the theory that we have developed for sparsest cut to the non-uniform version of the problem. In particular, we can define a Leighton-Rao relaxation

$\displaystyle LR(G,H) := \min_{d \ {\rm semimetric}} \frac {|E_H|}{|E_G|} \frac {\sum_{u,v} A_{u,v} d(u,v)}{\sum_{u,v} B_{u,v} d(u,v) }$

where ${A}$ is the adjacency matrix of ${G}$ and ${B}$ is the adjacency matrix of ${H}$ .

We can also define the special case of the Leighton-Rao relaxation in which the distance function is an ${\ell^1}$ embedding:

$\displaystyle \phi'(G,H) := \min_{m, f: V \rightarrow {\mathbb R}^m} \frac {|E_H|}{|E_G|} \frac {\sum_{u,v} A_{u,v} || f(u) - f(v)||_1}{\sum_{u,v} B_{u,v} ||f(u)-f(v)||_1 }$

Exactly the same proof that established ${\phi(G) = \phi'(G)}$ can be used to prove

$\displaystyle \phi'(G,H) = \phi'(G,H)$

And, finally, Bourgain’s embedding can be used to map a solution of the Leighton-Rao relaxation to an ${\ell^1}$ solution, with ${O(\log n)}$ increase in the cost function, and then the ${\ell^1}$ solution can be mapped to a cut with no loss, leading to the relation

$\displaystyle LR(G,H) \leq \phi(G,H) \leq O(\log |V|) \cdot LR(G,H)$

for every two graphs ${G,H}$ over the same set of vertices.

One thought on “CS359G Lecture 10: Non-uniform Sparsest Cut”

Thang on March 20, 2011 at 10:20 am said:

Prof. Trevisan, the sparsest cut problem seems to be “easier” in d-regular graph. Is the problem still NP-hard in d-regular graph?

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS359G Lecture 10: Non-uniform Sparsest Cut

One thought on “CS359G Lecture 10: Non-uniform Sparsest Cut”

Leave a Reply Cancel reply

Share this:

Like this:

Related

One thought on “CS359G Lecture 10: Non-uniform Sparsest Cut”

Leave a Reply Cancel reply