Cheeger Inequality and Spectral Clustering

Today’s post will be concerned with the clustering problem. Suppose one has a data set and wants to split the set into two “meaningful” clusters. We will show how the eigenvectors of the graph Laplacian can provide such a clustering, giving an efficient method for clustering. The result that guarantees the performance of this method is inspired in an isoperimetric inequality proved in the late 60’s. This post is tightly related to my previous post about Spectral Clustering and Diffusion Maps.

The setting is the same, consider a weighted graph ${G = ( V , E , W)}$ , with ${|V|=n}$ . Let us assume as we did before that the weights are symmetric and that ${d_i = \sum_{j=1}^nw_{ij} = 1}$ . Again these assumptions are not needed but they slightly clean up the math below.

Recall that we are interested in splitting the graph ${G}$ into two subsets ${S}$ and ${S^c}$ such that there are very few connections between the two sets. We make this precise by asking for a cut, that separates the graph into two parts, ${S}$ and ${S^c}$ , such that the sum of the weights of the edges between ${S}$ and ${S^c}$ (we call this ${cut(S,S^c)}$ ) is small. This is however not yet a good notion of a good cut, the reason is that we could simply make ${S}$ the whole graph or the empty set and the cut would be zero. To remedy for this we define the Cheeger cut as

$\displaystyle h(S) = \frac{cut(S,S^c)}{\min\{|S|,|S^c|\}},$

and the Cheeger constant as ${h_G = \min_S h(S)}$ .

Instead of directly analyzing the Cheeger cut we are going to analyze the normalized cut as

$\displaystyle Ncut(S) = \frac{cut(S,S^c)}{|S|}+\frac{cut(S,S^c)}{|S^c|},$

where ${|S|}$ is the number of vertices in ${S}$ . It is clear to check that

$\displaystyle h(S) \leq Ncut(S) \leq 2h(S)$

A clever trick allows us to pose this problem as quadratic form minimization. Let ${S\subset V}$ and define the vector in ${x^S\in\mathbb{R}^n}$ given as

$\displaystyle x_i^S=\left\{\begin{array}{rl} -\sqrt{\frac{|S^c|}{|S|}} & \text{ if } i\in S \\ \sqrt{\frac{|S|}{|S^c|}} & \text{ if } i\in S^c. \end{array}\right.$

Now, the quadratic form

$\displaystyle \begin{array}{rcl} \frac12\frac{\sum_{ij}w_{ij}\left( x^S_i - x^S_j\right)^2}{\sum_{i}\left(x^S_i\right)^2} & = & \frac{\sum_{ij}w_{i\in S, j\in S^c}\left( \sqrt{\frac{|S^c|}{|S|}} + \sqrt{\frac{|S|}{|S^c|}} \right)^2}{\sum_{i\in S}\frac{|S^c|}{|S|} + \sum_{i\in S^c}\frac{|S|}{|S^c|}} \\ & = & cut(S,S^c) \frac{\left( \sqrt{\frac{|S^c|}{|S|}} + \sqrt{\frac{|S|}{|S^c|}} \right)^2}{|V|} \\ & = & cut(S,S^c) \frac{\frac{|V|}{|S|} + \frac{|V|}{|S^c|}} {|V|} \\ & = & Ncut(S). \end{array}$

We can therefore pose the problem of minimizing the ${Ncut(\cdot)}$ as finding the minimum of the quadratic form over all vectors ${x}$ that are of the form ${x^S}$ for some ${S}$ . We note that ${\sum_i x^S_i = \sum_{i\in S^c}\sqrt{\frac{|S|}{|S^c|}}-\sum_{i\in S}\sqrt{\frac{|S^c|}{|S|}}= 0}$ , for all ${S}$ .

In the previous post we defined the graph Laplacian as ${L=I-W}$ where ${W}$ was the adjacency matrix (containing the weights ${w_{ij}}$ ). It turns out that the Rayleigh quotient of this matrix gives the quadratic form used above (this can be seen as discrete analogue of a integration by parts formula for the continuous Laplacian):

$\displaystyle \frac{x^TLx}{x^Tx} = \frac12\frac{\sum_{ij}w_{ij}\left( x_i - x_j\right)^2}{\sum_{i}x_i^2}.$

We are thus interested in minimizing this Rayleigh quotient, which is obviously minimized by the first eigenvector of ${L}$ . It is easy to see that ${L}$ has an eigenvector in its null space, the all-ones vector which is very different from any ${x^S}$ , given that we just showed that any ${x^S}$ is orthogonal to it. Let us then look at minimizing ${\frac{x^TLx}{x^Tx}}$ orthogonal to this vector, this space of vectors contains all vector of the form ${x^S}$ which implies that this problem is a relaxation of the Normalized cut minimization problem.

It is a basic fact in linear algebra that the minimizer of ${\frac{x^TLx}{x^Tx}}$ subject to ${x^T\textbf{1}=0}$ is the second eigenvector of ${L}$ , ${\phi_2}$ , and the minimum is its second eigenvalue ${\lambda_2}$ . The observation that this problem is a relaxation of the minimizing the ${Ncut(\cdot)}$ problem already gives:

$\displaystyle \frac12\lambda_2 \leq \frac12\min_S Ncut(S) \leq h_S,$

which is one side of the Cheeger’s inequality. The question now is how tight this relaxation is. It turns out that, if one minimizes the Rayleigh quotient and then performs a clever rounding procedure to the eigenvector (to make it two-valued so that it defines two clusters) one gets a partitioning of the graph whose Cheeger cut is less than ${\sqrt{2\lambda_2}}$ , this automatically implies the hard part of Cheeger’s inequality and shows that

Theorem 1 (Cheeger’s inequality)

$\displaystyle \frac12\lambda_2 \leq h_S \leq \sqrt{2\lambda_2}.$

This result serves as a guarantee of performance of the Clustering Algorithm proposed in the previous post.

I will not prove this inequality in this post (the post is already a bit long and I rather keep my posts on the shorter side). The result was originally shown here. I would however recommend the reader to take a look at a very nice proof that can be found in Luca Trevisan’s blog: in theory. Very roughly, the idea is to perform random rounding (with a very clever probability distribution) that will in expectation perform better than ${\sqrt{2\lambda_2}}$ implying that there must exist at least one instance for which such performance is achieve (this kind of argument is often refereed to as the probabilistic method).

It is interesting to note that before this result was known for graphs it was shown in the context of Riemannian Geometry by Cheeger here.

3 thoughts on “Cheeger Inequality and Spectral Clustering”

dustingmixon says:

May 4, 2012 at 5:06 AM

That choice for $x_i^S$ is magic!

1. Afonso Bandeira says:
  
  May 8, 2012 at 1:44 AM
  
  Hi Dustin,
  
  Thanks for the question!
  
  It looks like magic but it is not quite, you know you want the vector $x^S$ to be orthogonal to the all-ones vector and, since it is suppose to be a proxy for a partitioning it should be bi-valued. These two requirements already give you the vector up to scaling and then you just pick the scaling that makes it look nicer =)
  
  Best,
  Afonso
  
Pingback: The Angular Synchronization problem and a Cheeger Inequality | Relax and Conquer