Buser Inequalities in Graphs

Posted on October 7, 2021 by luca

As life is tentatively returning to normal, I would like to once again post technical material here. Before returning to online optimization, I would like to start with something from 2015 that we never wrote up properly, that has to do with graph curvature and with Buser inequalities in graphs.

Continue reading →

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

Posted on February 11, 2016 by luca

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

Continue reading →

CS294 Lecture 6: Higher-order Cheeger Inequality

Posted on February 10, 2016 by luca

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} } }$ .

Continue reading →

CS294 Lecture 4: Cheeger Inequalities cont’d

Posted on February 7, 2016 by luca

In which we finish the proof of Cheeger’s inequalities.

It remains to prove the following statement.

Lemma 1 Let ${{\bf y}\in {\mathbb R}^V_{\geq 0}}$ be a vector with non-negative entries. Then there is a ${0< t \leq \max_v \{ y_v \} }$ such that

$\displaystyle \phi ( \{ v : y_v \geq t \} ) \leq \sqrt {2 R_L({\bf y}) }$

Continue reading →

CS294 Lecture 3: Cheeger Inequalities

Posted on February 2, 2016 by luca

In which we generalize the notion of normalized Laplacian to irregular graphs, we extend the basic spectral graph theory results from last lecture to irregular graphs, and we prove the easy direction of Cheeger’s inequalities.

1. Irregular Graphs

Let ${G=(V,E)}$ be an undirected graph, not necessarily regular. We will assume that every vertex has non-zero degree. We would like to define a normalized Laplacian matrix associated to ${G}$ so that the properties we proved last time are true: that the multiplicity of 0 as an eigenvalue is equal to the number of connected components of ${G}$ , that the largest eigenvalue is at most 2, and that it is 2 if and only if (a connected component of) the graph is bipartite.

Continue reading →

Proof of the Cheeger inequality in manifolds

Posted on March 21, 2013 by luca

Having (non-rigorously) defined the Laplacian operator in manifolds in the previous post, we turn to the proof of the Cheeger inequality in manifolds, which we restate below.

Theorem 1 (Cheeger’s inequality) Let ${M}$ be an ${n}$ -dimensional smooth, compact, Riemann manifold without boundary with metric ${g}$ , let ${L:= - {\rm div} \nabla}$ be the Laplace-Beltrami operator on ${M}$ , let ${0=\lambda_1 \leq \lambda_2 \leq \cdots }$ be the eigenvalues of ${L}$ , and define the Cheeger constant of ${M}$ to be

$\displaystyle h(M):= \inf_{S\subseteq M : \ 0 < \mu(S) \leq \frac 12 \mu(M)} \ \frac{\mu_{n-1}(\partial(S))}{\mu(S)}$

where the ${\partial (S)}$ is the boundary of ${S}$ , ${\mu}$ is the ${n}$ -dimensional measure, and ${\mu_{n-1}}$ is ${(n-1)}$ -th dimensional measure defined using ${g}$ . Then

$\displaystyle h(M) \leq 2 \sqrt{\lambda_2} \ \ \ \ \ (1)$

We begin by recalling the proof of the analogous result in graphs, and then we will repeat the same steps in the context of manifolds.

Theorem 2 (Cheeger’s inequality in graphs) Let ${G=(V,E)}$ be a ${d}$ -regular graph, ${A}$ be its adjacency matrix, ${L:= I - \frac 1d A}$ be its normalized Laplacian matrix, ${0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_{|V|}}$ be the eigenvalues of ${L}$ , and define ${\mu(S):= d \cdot |S|}$ for every subset of vertices ${S\subseteq V}$ . Define the conductance of ${G}$ as

$\displaystyle \phi(G) := \min_{S\subseteq V: \ 0 < \mu(S) \leq \frac 12 \mu(V) } \frac{| \partial S|}{\mu(S)}$

where ${\partial S}$ is the number of edges with one endpoint in ${S}$ and one endpoint in ${\bar S}$ . Then

$\displaystyle \phi(G) \leq \sqrt{2 \lambda_2} \ \ \ \ \ (2)$

1. Proof the Cheeger inequality in graphs

We will use the variational characterization of the eigenvalues of the Laplacian ${L}$ of a graph ${G}$ .

$\displaystyle \lambda_1 = \min_{f \in {\mathbb R}^v} \frac {f^T Lf}{f^T f} \ \ \ \ \ (3)$

and if ${f_1}$ is a minimizer in the above expression then

$\displaystyle \lambda_2 = \min_{f \in {\mathbb R}^V: \ f \perp f_1} \frac {f^T Lf}{f^T f}$

Following the definition of ${L}$ we see that

$\displaystyle f^T L f = \frac 1d \sum_{(u,v)\in E} |f_u - f_v |^2$

and so the minimum in (3) is 0, and it is achieved for ${f = (1,\cdots,1)}$ . This means that

$\displaystyle \lambda_2 = \min_{f \in {\mathbb R}^V: \ \sum_v f_v = 0} \frac {\sum_{(u,v) \in E} |f_u-f_v|^2}{d \sum_v f_v^2} \ \ \ \ \ (4)$

The expression in the right-hand-side of (4) is an important one, and it is called the Rayleigh quotient of ${f}$ , which we will denote by ${R(f)}$ :

$\displaystyle R(f):= \frac {\sum_{(u,v) \in E} |f_u-f_v|^2}{d \sum_v f_v^2}$

It is also useful to consider the variant of the Rayleigh quotient where there are no squares; this does not have a standard name, so let us call it the ${\ell_1}$ Rayleigh quotient and denote it by ${R_1}$ :

$\displaystyle R_1(g):= \frac {\sum_{(u,v) \in E} |g_u-g_v|}{d \sum_v |g_v|}$

The proof of the graph Cheeger inequality now continues with the proof of the following three facts.

Lemma 3 (Rounding of ${\ell_1}$ embeddings) For every non-negative vector ${g\in {\mathbb R}^V_{\geq 0}}$ there is a value ${t\geq 0}$ such that

$\displaystyle \phi(\{ v: g(v) > t \}) \leq R_1(g)$

Lemma 4 (Embedding of ${\ell_2^2}$ into ${\ell_1}$ ) For every non-negative vector ${f\in {\mathbb R}^V_{\geq 0}}$ , we have

$\displaystyle R_1(f^2) \leq \sqrt{2 R(f)}$

Lemma 5 (From an eigenvector to a non-negative vector) For every ${f\in {\mathbb R}^V}$ such that ${\sum_v f_v =0}$ there is a non-negative ${f'\in {\mathbb R}^V_{\geq 0}}$ such that ${\mu(\{ v: f'(v) >0 \}) \leq \frac 12 \mu(V)}$ and such that

$\displaystyle R(f') \leq R(f)$

Now let us start from a function ${f}$ that optimizes (4), so that ${\sum_v f_v = 0}$ and ${R(f) = \lambda_2}$ , then apply Lemma 5 to find a function ${f'}$ such that the volume of the vertices having positive coordinates in ${f'}$ is at most ${\frac 12 \mu(V)}$ and such that ${R(f') \leq R(f) = \lambda_2}$ . Then consider the vector ${g\in {\mathbb R}^V}$ such that ${g_v := f'^2_v}$ ; by Lemma 4, we have ${R_1(g) \leq \sqrt{2 R(f')} \leq \sqrt{2\lambda_2}}$ , and by Lemma 3 there is a threshold ${t}$ such that the set ${S:= \{ v: g(v) > t \}}$ has conductance ${h(S) \leq \sqrt {2\lambda_2}}$ . Since ${S}$ is a subset of the vertices having positive coordinates in ${g}$ , we have ${\mu(S) \leq \frac 12 \mu(V)}$ , and so

$\displaystyle \phi(G) \leq \sqrt{2 \lambda_2 }$

which is the Cheeger inequality for graphs. It remains to prove the three lemmas.

Proof: of Lemma 3. For each threshold ${t}$ , define the set

$\displaystyle S_t := \{ v: g_v > t \}$

The idea of the proof is that if we pick ${t}$ at random then the probability that an edge belongs to ${\partial S_t}$ is proportional to ${|g_u - g_v|}$ and the probability that ${v\in S_t}$ is proportional to ${|g_v|}$ , so that the expected number of edges in ${\partial S_t}$ is proportional to the numerator of ${R_1(g)}$ and the expected number of vertices in ${S_t}$ is proportional to the denominator of ${R_1(g)}$ ; if ${R_1(g)}$ is small, it is not possible for ${\partial S_t/\mu(S_t)}$ to always be large for every ${t}$ .

To avoid having to normalize the range of ${t}$ to be between ${0}$ and ${1}$ , instead of taking averages over a random choice of ${t}$ , we will consider the integral over all values of ${t}$ . We have

$\displaystyle \int_0^\infty |\partial (S_t) | {\rm d} t = \sum_{u,v} |g_u - g_v |$

because we can write ${|\partial (S_t)| = \sum_{(u,v) \in E} I_{u,v} (t)}$ , where ${I_{u,v} (t) = 1}$ if ${(u,v) \in \partial S_t}$ and ${I_{u,v}(t) = 0}$ otherwise, and we see that only the values of ${t}$ between ${g_u}$ and ${g_v}$ make ${I_{u,v}(t) =1}$ , so ${\int_{0}^\infty I_{u,v} (t) {\rm d} t = |g_u - g_v|}$ .

We also have

$\displaystyle \int_0^\infty d |S_t| {\rm d} t = d \sum_v |g_v|$

and if we denote by ${t^*}$ the threshold such that ${\phi(S_{t^*})}$ is smallest among all the ${\phi(S)}$ , then

$\displaystyle \sum_{u,v} |g_u - g_v | = \int_0^\infty |\partial (S_t) | {\rm d} t$

$\displaystyle \geq \int_0^\infty h(S_{t^*}) d|S_t| {\rm d} t$

$\displaystyle = h(S_{t^*}) d \sum_v |g_v|$

so that

$\displaystyle h(S_{t^*}) \leq \frac { \sum_{u,v} |g_u - g_v | }{d \sum_v |g_v| } = R_1(g)$

$\Box$

Proof: of Lemma 3. Let us consider the numerator of ${R_1(f^2)}$ ; it is:

$\displaystyle \sum_{(u,v)\in E} |f^2_u - f^2_v|$

$\displaystyle = \sum_{(u,v)\in E} |f_u - f_v| \cdot (f_u + f_v)$

$\displaystyle \leq \sqrt{\sum_{(u,v)\in E} |f_u - f_v|^2} \sqrt{ \sum_{(u,v)\in E}(f_u + f_v)^2 }$

(we used Cauchy-Swarz)

$\displaystyle \leq \sqrt{R(f) \cdot d\sum_v f_v^2} \sqrt{ \sum_{(u,v)\in E} 2f_u^2 + 2f_v^2 }$

(we used the definition of ${R_2}$ and Cauchy-Swarz again)

$\displaystyle = \sqrt{R(f) \cdot d\sum_v |f_v|^2} \sqrt{ 2 d\sum_{v} f_v^2 }$

$\displaystyle = \sqrt{2 R(f) } \cdot d \sum_v f_v^2$

And so

$\displaystyle R_1(f^2) = \frac {\sum_{(u,v)\in E} |f^2_u - f^2_v|}{d \sum_v f_v^2} \leq \sqrt{2 R_2(f) }$

$\Box$

Proof: of Lemma 5. Let ${m}$ be the median of ${f}$ , and consider ${\bar f}$ defined as ${\bar f_v := f_v - m}$ . We have

$\displaystyle R(\bar f) \leq R(f)$

because the numerators of ${R(\bar f)}$ and ${R(f)}$ are the same (the additive term ${-m}$ cancels). The denominators are such that

$\displaystyle \sum_v \bar f_v^2 = || \bar f||^2 = || f||^2 + || - m \cdot {\bf 1} ||^2 \geq || f||^2 = \sum_v f_v^2$

because ${f}$ and the vector ${{\bf 1} = (1,\ldots,1)}$ are orthogonal, and so by Pythagoras’s theorem the length-squared of ${\bar f = f - m {\bf 1}}$ equals the length-squared of ${f}$ plus the length-squared of ${-m {\bf 1}}$ .

Let us define ${f^+_v := \min\{ 0, \bar f_v\}}$ and ${f^-_v := \min \{ 0, -\bar f_v\}}$ so that ${\bar f = f^+ - f^-}$ . We use the following fact:

Fact 6 Let ${a,b \in {\mathbb R}^V_{\geq 0}}$ be disjointly supported non-negative vectors (“disjointly supported” means that they are non-zero on disjoint subsets of coordinates), then

$\displaystyle \min\{ R(a) , R(b) \} \leq R(a-b)$

Proof: The numerator of ${R(a-b)}$ is

$\displaystyle \sum_{(u,v)\in E} |a_v - b_v + b_u - a_v|^2 \geq \sum_{(u,v)\in E} |a_v - a_u|^2 + |b_v - b_u|^2$

and, using orthogonality and Pythagoras’s theorem, the denominator of ${R(a-b)}$ is

$\displaystyle d || a- b||^2 = d||a ||^2 + d|| b||^2$

The fact now follows from the inequality

$\displaystyle \min \left \{ \frac {n_1}{d_1} , \frac{n_2}{d_2} \right \} \leq \frac{n_1+n_2}{d_1+d_2}$

$\Box$

The lemma now follows by observing that ${f^+}$ and ${f^-}$ are non-negative and disjointly supported, so

$\displaystyle \min\{ R(f^+) , R(f^-) \} \leq R(\bar f) \leq R(f)$

and that both ${f^+}$ and ${f^-}$ have at most ${n/2}$ non-zero coordinate. $\Box$

2. Proof of the Cheeger inequality in manifolds

We will now translate the proof of the graph Cheeger inequality to the setting of manifolds.

As you may remember, we started off by saying that ${L}$ is symmetric and so all its eigenvalues are real and they are given by the variational characterization. Now we are already in trouble because the operator ${L}$ on manifolds cannot be thought of as a matrix, so what does it mean for it to be symmetric? The consequence of symmetry that is exploited in the analysis of the spectrum of symmetric matrices is the fact that if ${A}$ is symmetric, then for every ${x,y}$ we have

$\displaystyle \langle x,Ay \rangle = x^T Ay = (A^Tx)^Ty = (Ax)^Ty = \langle Ax,y \rangle$

and the property ${\langle x, Ay \rangle = \langle Ax , y \rangle}$ makes no references to coordinates, and it is well defined even for linear operators over infinite-dimensional spaces, provided that there is a notion of inner product. If we the define the inner product

$\displaystyle \langle f,g \rangle := \int_M f(x)\cdot g(x) \ {\rm d} \mu(x)$

on functions ${f: M \rightarrow {\mathbb R}}$ , and more generally

$\displaystyle \langle f,g \rangle := \int_M \langle f(x), g(x)\rangle_X \ {\rm d} \mu(x)$

for functions ${f: M \rightarrow X}$ , where ${X}$ is a vector space with inner product ${\langle \cdot,\cdot,\rangle_X}$ , then we can say that an operator ${A}$ is self-adjoint if

$\displaystyle \langle f, Ag \rangle = \langle Af ,g \rangle$

for all (appropriately restricted) functions ${f,g}$ . If ${M}$ is compact, this property is true for the Laplacian, and, in particular, ${-{\rm div}}$ and ${\nabla}$ are adjoints of each others, that is,

$\displaystyle \langle \nabla f, g \rangle = \langle f, - {\rm div} g \rangle$

(The discrete analog would be that ${C^T}$ is the transpose of ${C}$ .)

Self-adjointness (and appropriate conditions on ${M}$ ) imply a version of the spectral theorem and of the variational characterization. In particular, all eigenvalues of ${L}$ are real, and if there is a minimum one then it is

$\displaystyle \lambda_1 = \min_{f: M \rightarrow {\mathbb R}} \frac {\langle f, Lf \rangle}{\langle f,f\rangle}$

and if ${f_1}$ is a minimizer of the above, then

$\displaystyle \lambda_2 = \min_{f: M \rightarrow {\mathbb R},\ \langle f, f_1 \rangle = 0} \frac {\langle f, Lf \rangle}{\langle f,f\rangle}$

(The minimization is quantified over all functions that are square-integrable, and the minimum is achieved because if ${M}$ is compact then the space of such functions is also compact and the cost function that we are minimizing is continuous. In this post, whenever we talk about “all functions,” it should be understood that we are restricting to whatever space of functions makes sense in the context.)

From the property that ${-{\rm div}}$ and ${\nabla}$ are adjoint, we have

$\displaystyle \langle f, Lf \rangle = \langle f, -{\rm div} \nabla f \rangle = \langle \nabla f,\nabla f \rangle$

$\displaystyle \lambda_1 = \min_{f:M \rightarrow {\mathbb R}} \frac{ \int_M \langle \nabla f(x),\nabla f(x) \rangle \ {\rm d} \mu(x) } {\int M f^2(x) \ {\rm d} \mu (x)}$

where the Rayleigh quotient

$\displaystyle R(f):= \frac{ \int_M \langle \nabla f(x),\nabla f(x) \rangle \ {\rm d} \mu(x) } {\int M f^2(x) \ {\rm d} \mu (x)} = \frac {\int_M ||\nabla f(x)||^2 \ {\rm d} \mu (x)}{\int_M f^2(x) \ {\rm d} \mu (x)}$

is always non-negative, and it is zero for constant ${f\equiv 1}$ , so we see that ${\lambda_1=0}$ and

$\displaystyle \lambda_2 = \min_{f:M \rightarrow {\mathbb R} : \int_M f=0 \ {\rm d} \mu} R(f)$

By analogy with the graph case, we define the “ ${\ell_1}$ Rayleigh quotient”

$\displaystyle R_1(g) := \frac {\int_M ||\nabla g(x)|| \ {\rm d} \mu (x)}{\int_M |g(x)| \ {\rm d} \mu (x)}$

And we can prove the analogs of the lemmas that we proved for graphs.

Lemma 7 (Rounding of ${\ell_1}$ embeddings) For every non-negative function ${g: V \rightarrow {\mathbb R}_{\geq 0}}$ there is a value ${t\geq 0}$ such that

$\displaystyle h(\{ x: g(x) > t \}) \leq R_1(g)$

where the Cheeger constant ${h(S)}$ of a subset ${S\subseteq M}$ of the manifold is

$\displaystyle h(S) := \frac{\mu_{n-1} (\partial S)}{\mu(S)}$

Lemma 8 (Embedding of ${\ell_2^2}$ into ${\ell_1}$ ) For every non-negative function ${f; m \rightarrow {\mathbb R}_{\geq 0}}$ , we have

$\displaystyle R_1(f^2) \leq \sqrt{2 R(f)}$

Lemma 9 (From an eigenfunction to a non-negative function) For every function ${f: M \rightarrow R}$ such that ${\int_M f \ {\rm d} \mu =0}$ there is a non-negative ${f': M \rightarrow {\mathbb R}_{\geq 0}}$ such that ${\mu(\{ x: f'(x) >0 \}) \leq \frac 12 \mu(V)}$ and such that

$\displaystyle R(f') \leq R_2(f)$

Let us see the proof of these lemmas.

Proof: of Lemma 7. For each threshold ${t}$ , define the set

$\displaystyle S_t := \{ x: g(x) > t \}$

Let ${t*}$ be a threshold for which ${h(S_{t*})}$ is minimized

We will integrate the numerator and denominator of ${h(S_t)}$ over all ${t}$ . The coarea formula for nonnegative functions is

$\displaystyle \int_M || \nabla g || {\rm d} \mu = \int_{0}^\infty \mu_{n-1} ( \partial \{ x: g(x) > t \}) {\rm d} t$

and we also have

$\displaystyle \int_M |g| {\rm d} \mu = \int_{0}^\infty \mu ( \{ x: g(x) > t \}) {\rm d} t$

which combine to

$\displaystyle \int_M || \nabla g || {\rm d} t = \int_0^\infty \mu_{n-1} ( \partial S_t) {\rm d} t$

$\displaystyle = \int_0^\infty h(S_t) \mu(S_t) {\rm d} t$

$\displaystyle \geq h(S_{t^*}) \int_0^\infty \mu(S_t) {\rm d} t$

$\displaystyle = h(S_{t^*}) \int_M g {\rm d} t$

so that

$\displaystyle h(S_{t^*}) \leq \frac{\int_M || \nabla g || {\rm d} t }{ \int_M g {\rm d} t} = R_1(g)$

$\Box$

Proof: of Lemma 8. Let us consider the numerator of ${R_1(f^2)}$ ; it is:

$\displaystyle \int_M || \nabla f^2|| {\rm d} \mu$

We can apply the chain rule, and see that

$\displaystyle \nabla f^2(x) = 2f(x) \cdot \nabla f(x)$

which implies

$\displaystyle \int_M || \nabla f^2 || {\rm d} \mu$

$\displaystyle = \int_M || 2f(x) \nabla f(x)|| {\rm d} \mu(x)$

$\displaystyle = \int_M 2|f(x)| \cdot ||\nabla f(x)|| {\rm d} \mu (x)$

and, after applying Caucy-Swarz,

$\displaystyle \leq \sqrt{\int_M 4 f^2(x) {\rm d} \mu(x)} \cdot \sqrt{\int_M ||\nabla f(x)||^2 {\rm d} \mu(x)}$

$\displaystyle = 2 \cdot \left( \int_M f^2 {\rm d} \mu \right) \cdot \sqrt{ R(f)}$

And so

$\displaystyle R_1(f^2) \leq 2 \sqrt{R_2(f) }$

$\Box$

Proof: of Lemma 9. Let ${m}$ be a median of ${f}$ , and consider ${\bar f}$ defined as ${\bar f(x) := f(x) - m}$ . We have

$\displaystyle R(\bar f) \leq R(f)$

because the numerators of ${R(\bar f)}$ and ${R(f)}$ are the same (the derivatives of functions that differ by a constant are identical) and the denominators are such that

$\displaystyle \int_M \bar f^2{\rm d} \mu$

$\displaystyle = \int_M f^2 - 2mf + m^2 {\rm d} \mu$

$\displaystyle = \int_M f^2 + m^2 {\rm d} \mu$

$\displaystyle \geq \int_M f^2 {\rm d} \mu$

where we used the fact the integral of ${f}$ is zero.

Let us define ${f^+(x) := \min\{ 0, \bar f(x)\}}$ and ${f^-_v := \min \{ 0, -\bar f(x)\}}$ so that ${\bar f(x) = f^+(x) - f^-(x)}$ . We use the following fact:

Fact 10 Let ${a,b : M \rightarrow {\mathbb R}_{\geq 0}}$ be disjointly supported non-negative functions (“disjointly supported” means that they are non-zero on disjoint subsets of inputs), then

$\displaystyle \min\{ R(a) , R(b) \} \leq R(a-b)$

Proof: We begin with the following observation: if ${a}$ is a non-negative function, and ${a(x)=0}$ , then ${\nabla a(x) = \{ \bf 0 \}}$ , because ${x}$ has to be a local minimum.

Consider the expression ${||\nabla (a-b)||^2}$ occurring in the numerator of ${R(a-b)}$ . We have

$\displaystyle ||\nabla (a-b)||^2$

$\displaystyle = || \nabla a - \nabla b ||^2$

$\displaystyle = || \nabla a||^2 + || \nabla b||^2 - 2 \langle \nabla a,\nabla b \rangle$

But

$\displaystyle \langle \nabla a,\nabla b \rangle = 0$

because for every ${x}$ at least one of ${a(x)}$ or ${b(x)}$ is zero, and so at least one of ${\nabla a(x)}$ or ${\nabla b(x)}$ is zero.

Using this fact, we have that the numerator of ${R(a-b)}$ is equal to the sum of the numerators of ${R(a)}$ and ${R(b)}$ :

$\displaystyle \int_M ||\nabla a-b||^2 {\rm d} \mu = \int_M ||\nabla a-b||^2 {\rm d} \mu + \int_M ||\nabla a-b||^2 {\rm d}$

and the denominator of ${R(a-b)}$ is also the sum of the denominators of ${R(a)}$ and ${R(b)}$ :

$\displaystyle =\int_M (a-b)^2 {\rm d} \mu$

$\displaystyle =\int_M a^2 {\rm d} \mu + \int_M b^2 {\rm d} \mu - 2 \int_M ab {\rm d} \mu$

$\displaystyle =\int_M a^2 {\rm d} \mu + \int_M b^2 {\rm d} \mu$

because ${a(x)b(x)=0}$ for every ${x}$ . The fact now follows from the inequality

$\displaystyle \min \left \{ \frac {n_1}{d_1} , \frac{n_2}{d_2} \right \} \leq \frac{n_1+n_2}{d_1+d_2}$

$\Box$

The lemma now follows by observing that ${f^+}$ and ${f^-}$ are non-negative and disjointly supported, so

$\displaystyle \min\{ R(f^+) , R(f^-) \} \leq R(\bar f) \leq R(f)$

and that both ${f^+}$ and ${f^-}$ have a support of volume at most ${\frac 12 \mu(M)}$ . $\Box$

If anybody is still reading, it is worth observing a couple of differences between the discrete proof and the continuous proof.

The ${\ell_1}$ Rayleigh quotient is defined slightly differently in the continuous case. It would correspond to defining it as

$\displaystyle \frac {\sum_{u\in V} \sqrt{\sum_{v: (u,v)\in E} (f_u-f_v)^2 } }{d \sum_v |f_v|}$

in the discrete case.

If ${a,b \in {\mathbb R}^V}$ are disjointly supported and nonnegative, the sum of the numerators of the Rayleigh quotients ${R(a)}$ and ${R(-b)}$ can be strictly smaller than the numerator of ${R(a-b)}$ , while we always have equality in the continuous case. In the discrete case, the sum of the numerators of ${R(a)}$ and ${R(b)}$ can be up to twice the numerator of ${R(a+b)}$ (this fact is useful, but it did not come up in this proof), while again we have exact equality in the continuous case.

The chain rule calculation

$\displaystyle \nabla f^2 = 2f \nabla f$

corresponds to the step

$\displaystyle f_v^2 - f_u^2 = (f_v + f_u) \cdot (f_v - f_u)$

In the continuous case, ${f_v}$ and ${f_u}$ are “infinitesimally close”, so we can approximate ${f_v + f_u}$ by ${2f_v}$ .

The Cheeger inequality in manifolds

Posted on March 20, 2013 by luca

Readers of in theory have heard about Cheeger’s inequality a lot. It is a relation between the edge expansion (or, in graphs that are not regular, the conductance) of a graph and the second smallest eigenvalue of its Laplacian (a normalized version of the adjacency matrix). The inequality gives a worst-case analysis of the “sweep” algorithm for finding sparse cuts, it shows a necessary and sufficient for a graph to be an expander, and it relates the mixing time of a graph to its conductance.

Readers who have heard this story before will recall that a version of this result for vertex expansion was first proved by Alon and Milman, and the result for edge expansion appeared in a paper of Dodzuik, all from the mid-1980s. The result, however, is not called Cheeger’s inequality just because of Stigler’s rule: Cheeger proved in the 1970s a very related result on manifolds, of which the result on graphs is the discrete analog.

So, what is the actual Cheeger’s inequality?

Theorem 1 (Cheeger’s inequality) Let ${M}$ be an ${n}$ -dimensional smooth, compact, Riemann manifold without boundary with metric ${g}$ , let ${L:= - {\rm div} \nabla}$ be the Laplace-Beltrami operator on ${M}$ , let ${0=\lambda_1 \leq \lambda_2 \leq \cdots }$ be the eigenvalues of ${L}$ , and define the Cheeger constant of ${M}$ to be

$\displaystyle h(M):= \inf_{S\subseteq M : \ 0 < \mu(S) \leq \frac 12 \mu(M)} \ \frac{\mu_{n-1}(\partial(S))}{\mu(S)}$

where the ${\partial (S)}$ is the boundary of ${S}$ , ${\mu}$ is the ${n}$ -dimensional measure, and ${\mu_{n-1}}$ is ${(n-1)}$ -th dimensional measure defined using ${g}$ . Then

$\displaystyle h(M) \leq 2 \sqrt{\lambda_2} \ \ \ \ \ (1)$

The purpose of this post is to describe to the reader who knows nothing about differential geometry and who does not remember much multivariate calculus (that is, the reader who is in the position I was in a few weeks ago) what the above statement means, to describe the proof, and to see that it is in fact the same proof as the proof of the statement about graphs.

In this post we will define the terms appearing in the above theorem, and see their relation with analogous notions in graphs. In the next post we will see the proof.

Continue reading →

CS359G Lecture 4: Spectral Partitioning

Posted on January 26, 2011 by luca

In which we prove the difficult direction of Cheeger’s inequality.

As in the past lectures, consider an undirected ${d}$ -regular graph ${G=(V,E)}$ , call ${A}$ its adjacency matrix, and ${M: = \frac 1d A}$ its scaled adjacency matrix. Let ${\lambda_1 \geq \cdots \geq \lambda_n}$ be the eigenvalues of ${M}$ , with multiplicities, in non-increasing order. We have been studying the edge expansion of a graph, which is the minimum of ${h(S)}$ over all non-trivial cuts ${(S,V-S)}$ of the vertex set (a cut is trivial if ${S=\emptyset}$ or ${S=V}$ ), where the expansion ${h(S)}$ of a cut is

$\displaystyle h(S) := \frac{Edges(S,V-S)}{d\cdot \min \{ |S|, |V-S| \} }$

We have also been studying the (uniform) sparsest cut problem, which is the problem of finding the non-trivial cut that minimizes ${\phi(S)}$ , where the sparsisty ${\phi(S)}$ of a cut is

$\displaystyle \phi(S) := \frac{Edges(S,V-S)}{\frac dn |S| \cdot |V-S|}$

We are proving Cheeger’s inequalities:

$\displaystyle \frac {1-\lambda_2}{2} \leq h(G) \leq \sqrt{2 \cdot (1-\lambda_2) } \ \ \ \ \ (1)$

and we established the left-hand side inequality in the previous lecture, showing that the quantity ${1-\lambda_2}$ can be seen as the optimum of a continuous relaxation of ${\phi(G)}$ , so that ${1-\lambda_2 \leq \phi(g)}$ , and ${\phi(G) \leq 2 h(G)}$ follows by the definition.

Today we prove the more difficult, and interesting, direction. The proof will be constructive and algorithmic. The proof can be seen as an analysis of the following algorithm.

Algorithm: SpectralPartitioning

Input: graph ${G=(V,E)}$ and vector ${{\bf x} \in {\mathbb R}^V}$
Sort the vertices of ${V}$ in non-decreasing order of values of entries in ${{\bf x}}$ , that is let ${V=\{ v_1,\ldots,v_n\}}$ where ${x_{v_1} \leq x_{v_2} \leq \ldots x_{v_n}}$
Let ${i\in \{1,\ldots,n-1\}}$ be such that ${h(\{ v_1,\ldots, v_i \} )}$ is minimal
Output ${S= \{ v_1,\ldots, v_i \}}$

We note that the algorithm can be implemented to run in time ${O(|V|+|E|)}$ , assuming arithmetic operations and comparisons take constant time, because once we have computed ${h(\{ v_1,\ldots,v_{i} \})}$ it only takes time ${O(degree(v_{i+1}))}$ to compute ${h(\{ v_1,\ldots,v_{i+1} \})}$ .

We have the following analysis of the quality of the solution:

Lemma 1 (Analysis of Spectral Partitioning) Let ${G=(V,E)}$ be a d-regular graph, ${{\bf x}\in {\mathbb R}^V}$ be a vector such that ${{\bf x} \perp {\bf 1}}$ , let ${M}$ be the normalized adjacency matrix of ${G}$ , define

$\displaystyle \delta:= \frac{ \sum_{i,j} M_{i,j} |x_i - x_j |^2}{\frac 1n \sum_{i,j} |x_i - x_j |^2}$

and let ${S}$ be the output of algorithm SpectralPartitioning on input ${G}$ and ${x}$ . Then

$\displaystyle h(S) \leq \sqrt{2\delta}$

Remark 1 If we apply the lemma to the case in which ${{\bf x}}$ is an eigenvector of ${\lambda_2}$ , then ${\delta = 1-\lambda_2}$ , and so we have

$\displaystyle h(G) \leq h(S) \leq \sqrt{2 \cdot (1-\lambda_2)}$

which is the difficult direction of Cheeger’s inequalities.

Remark 2 If we run the SpectralPartitioning algorithm with the eigenvector ${{\bf x}}$ of the second eigenvalue ${\lambda_2}$ , we find a set ${S}$ whose expansion is

$\displaystyle h(S) \leq \sqrt{2\cdot (1-\lambda_2) } \leq 2 \sqrt{h(G)}$

Even though this doesn’t give a constant-factor approximation to the edge expansion, it gives a very efficient, and non-trivial, approximation.

As we will see in a later lecture, there is a nearly linear time algorithm that finds a vector ${x}$ for which the expression ${\delta}$ in the lemma is very close to ${1-\lambda_2}$ , so, overall, for any graph ${G}$ we can find a cut of expansion ${O(\sqrt {h(G)})}$ in nearly linear time.

Continue reading →

CS359G Lecture 3: Cheeger’s inequality

Posted on January 19, 2011 by luca

In which we prove the easy case of Cheeger’s inequality.

1. Expansion and The Second Eigenvalue

Let ${G=(V,E)}$ be an undirected ${d}$ -regular graph, ${A}$ its adjacency matrix, ${M = \frac 1d \cdot A}$ its normalized adjacency matrix, and ${1=\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n}$ be the eigenvalues of ${M}$ .

Recall that we defined the edge expansion of a cut ${(S,V-S)}$ of the vertices of ${G}$ as

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

and that the edge expansion of ${G}$ is ${h(G) := \min_{S\subseteq V} h(S)}$ .

We also defined the related notion of the sparsity of a cut ${(S,V-S)}$ as

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

and ${\phi(G) := \min_S \phi(S)}$ ; the sparsest cut problem is to find a cut of minimal sparsity.

Recall also that in the last lecture we proved that ${\lambda_2 = 1}$ if and only if ${G}$ is disconnected. This is equivalent to saying that ${1-\lambda_2 = 0 }$ if and only if ${h(G)=0}$ . In this lecture and the next we will see that this statement admits an approximate version that, qualitatively, says that ${1-\lambda_2}$ is small if and only if ${h(G)}$ is small. Quantitatively, we have

Theorem 1 (Cheeger’s Inequalities)

$\displaystyle \frac{1-\lambda_2}2 \leq h(G) \leq \sqrt{2 \cdot (1-\lambda_2) } \ \ \ \ \ (1)$

Continue reading →

in theory

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

Tag Archives: Cheeger inequality

Buser Inequalities in Graphs

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

CS294 Lecture 6: Higher-order Cheeger Inequality

CS294 Lecture 4: Cheeger Inequalities cont’d

CS294 Lecture 3: Cheeger Inequalities

Proof of the Cheeger inequality in manifolds

The Cheeger inequality in manifolds

CS359G Lecture 4: Spectral Partitioning

CS359G Lecture 3: Cheeger’s inequality