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

**1. Cheeger-type Inequalities for **

Let be an undirected -regular graph, its adjacency matrix, its normalized Laplacian matrix, and be the eigenvalues of , counted with multiplicities and listed in non-decreasing order.

In Handout 2, we proved that if and only if has at least connected components, that is, if and only if there are disjoint sets such that for . 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 is a collection of disjoint sets, then their order- expansion is defined as

and the order- expansion of a graph is

If the edges of a graph represent a relation of similarity of affinity, a low-expansion collection of sets represents an interesting notion of clustering, because the vertices in each set 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:

Stronger upper bounds are known, but the bound above is easier to prove from scratch. It is known that and that .

**2. The Easy Direction **

As usual, the direction is the easy one, and it comes from viewing as a sort of continuous relaxation of the problem of minimizing order- expansion.

Recall that, in order to prove the easy direction of Cheeger’s inequality for , we proved that if and are two orthogonal vectors, both of Rayleigh quotient at most , then the Rayleigh quotient of their sum is at most . A similar argument could be made to show that the Rayleigh quotient of the sum of such vectors is at most . Such results hold for every positive semidefinite matrix.

In the special case of the Laplacian of a graph, and of vectors that are not just orthogonal but actually *disjointly supported*, then we can lose only a factor of 2 instead of a factor of . (The *support* of a vector is the set of its non-zero coordinates; two vectors are disjointly supported if their supports are disjoint.)

Lemma 1Let be disjointly supported vectors. Then

*Proof:* We just have to prove that, for every edge ,

The support disjointness implies that there is an index such that for , and an index such that for . If , then

and, if , then

and now, using also the fact that disjoint support implies orthogonality, we have

To finish the proof of the easy direction, let be sets such that for every . Consider the -dimensional space of linear combinations of the indicator vectors of such sets. The indicator vectors have Rayleigh quotient at most and are disjointly supported, so all their linear combinations have Rayleigh quotient at most . We have found a -dimensional space of vectors all of Rayleigh quotient , which proves .

**3. The Difficult Direction: Main Lemma **

We will prove the following result

Lemma 2 (Main)Let be orthonormal vectors. Then we can find disjointly supported non-negative vectors such that for every

By applying the Main Lemma to the eigenvectors of , we get disjointly supported vectors all of Rayleigh quotient at most . In a past lecture, we proved that for every non-negative vector there is a subset of its support such that , and applying this fact to the vectors we find disjoint sets all of expansion at most , proving

It is possible, with a more involved proof, to improve the factor in the conclusion of the Main Lemma to , implying that . A different approach, which we will not discuss, is used to show that, given orthonormal vectors, one can find disjoint sets such that, for all ,

implying , which is the best known bound.

Note that, in all the known arguments, the bounds still hold if one replaces by the (possibly smaller) quantity

There are graphs, however, in which

so, if a bound of the form is true, then, in order to prove it, we need to develop new techniques that distinguish between and the quantity (1).

**4. The Spectral Embedding **

Given orthonormal vectors as in the premise of the Main Lemma, we define the mapping

If are the eigenvectors of the smallest Laplacian eigenvalues of , then is called the *spectral embedding* of into . *Spectral clustering* algorithms compute such an embedding, and then find clusters of nodes by clustering the points using geometric clustering algorithms, such as -means, according either to Euclidian distance, or to the normalized distance function

Our construction of disjointly supported vectors with small Rayleigh quotient will proceed similarly, by working only with the points and forgetting the edge structure of the graph, and by making use of the above distance function.

To develop some intuition about the spectral mapping, we introduce a notion of Laplacian Rayleigh quotient for a mapping , defined, by formally replacing absolute values with norms, as

For a mapping defined in terms of orthonormal vectors as in (2), we have

In particular, if are the eigenvectors of the smallest Laplacian eigenvalues, then .

Let us use this setup to prove again that if then has at least connected components. If , and we construct using the eigenvectors of the smallest Laplacian eigenvalues, then , which means that for every edge , and so for every and which are in the same connected component. Equivalently, if , then and are in different connected component. For every point in the range in the range of , let us consider its pre-image, and let be the sets constructed in this way. Clearly, every set has expansion zero.

How many sets do we have? We claim that the range of must contain at least distinct points, and so and has at least connected component. To prove the claim, consider the matrix whose rows are the vectors ; since the rows of are linearly independent, has full rank ; but if the range of contained distinct points, then would have distinct columns, and so its rank would be .

Our proof of the higher-order Cheeger inequality will be somewhat analogous to the previous argument: we will use the fact that, if the Rayleigh quotient of is small, then the endpoints of edges are typically close, in the sense that the distance defined in (3) between and will typically be small; we will also use the fact that, because the are orthonormal, tends to “spread out” vertices across , so that we can find regions of each containing a large (in a certain weighted sense) number of vertices, and such that the regions are well-separated according to the distance (3), implying that there are few edges crossing from one region to the other, so that the vertices in each region are a non-expanding set. (This is an imprecise description of the argument, but it conveys the basic intuition.)

**5. Overview of the Proof of the Main Lemma **

We will break up the proof of the Main Lemma into the following two Lemmas.

Lemma 3 (Well-Separated Sets)Given a function defined in terms of orthonormal vectors as in (2), we can find disjoint subsets of vertices such that

- For every ,
- For every and belonging to different sets,

Lemma 4 (Localization)Given a function defined in terms of orthonormal vectors as in (2), and sets such that, for every , and,for every in different sets , we can construct disjointly supported vectors such that for every , we have

For the second equation, I believe that the k-way edge expansion (of a graph) should be defined as the __minimum__ edge expansion of any choice of k disjoint subsets.

Thanks, I corrected it

Thank you for the great note.

Two small corrections (w.r.t pdf file):

eq. (1) from pg. 4. should be x^(1),…,x^(k) and not x^(k),…,x^(k).

The second equation in pg. 5. While the conclusion is true, the first equality seems to me to be simply wrong.

Thanks. That equality is correct, but I guess it was not obvious, so I added some intermediate steps

Typo in last line of Lemma 4, R_L(y^(i)) not R_L(y^(t))