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 1 Let
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))