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. Review
Let be a
-regular undirected graph,
its normalized Laplacian,
be the Laplacian eigenvalues, and
be the order-
expansion of
.
We want to prove
We will prove the somewhat stronger result that, given orthonormal vectors
, we can find
disjointly supported vectors
such that, for every
,
In order to do that, we define the mapping
of vertices to and the normalized distance
between vertices, and we are going to prove the following two lemmas.
Lemma 1 (Localization) Given
sets
such that, for every
,
and,for every
in different sets
, we can construct
disjointly supported vectors
such that for every
, we have
Lemma 2 (Well-Separated Sets) There are
disjoint subsets of vertices
such that
- For every
,
![]()
- For every
and
belonging to different sets,
![]()
Recall that, for a function the Rayleigh quotient of
is defined as
and, by definition of , we have
2. Some Preliminaries
We will prove some simple properties of the embedding and of the distance function
.
First, we observe that
Next, we prove the sense in which “spreads out” vertices across
.
Lemma 3 For every unit vector
,
Proof: Consider the matrix
whose rows are the vectors
and whose columns are the points
. Then we have
where we used the fact that the rows of are orthogonal and so
is the identity.
This means that, for every direction, the points correlate with that direction in the same way, regardless of the direction itself.
In the proof of the localization lemma, we will make use of the following inequality: for every two vectors ,
which is a consequence of Cauchy-Schwarz:
3. Localization
In this section we prove Lemma 1.
3.1. Proof Ideas
The basic idea is that we would like to define the vectors as
The denominator of the Rayleigh quotient of such a vector is, by definition, at least , and we might hope to upper bound the numerator of the Rayleigh quotient of
in terms of the numerator of the Rayleigh quotient of
, which is
.
Indeed, every edge with both endpoints outside of
contributes zero to the numerator of the Rayleigh quotient of
, and every edge
with both endpoints in
contributes
to the numerator of the Rayleigh quotient of , and the right-hand-side above is the contribution of the edge to the numerator of the Rayleigh quotient of
.
So far, so good, but the problem comes from edges with one endpoint
and one endpoint
. Such an edge contributes
to the Rayleigh quotient of
and
to the Rayleigh quotient of
, and the former quantity could be much larger than the latter. If
is large, however,
cannot be much larger than
, because of the following fact
Proof:
We can conclude that the only problem comes from edges such that
,
, and
is small. To deal with such edges, we will modify the definition of
, and use a “smoothed” version of the indicator function of
instead of the actual indicator.
3.2. Proof
If is a vertex and
is a set of vertices, we define
For each , we define the following smooth indicator function of
:
Notice that the functions are disjointly supported: there cannot be a vertex
such that
and
for
, otherwise we would have
and
, contradicting the well-separated condition on the sets
.
We define the vectors as
The vectors are disjointly supported, and it remains to understand their Rayleigh quotient.
The denominator of the Rayleigh quotient of is
The contribution of an edge to the numerator is the square of
where we used the inequality
The numerator of the Rayleigh quotient of is thus
and this proves Lemma 1.
4. Well-Separated Sets
In this section we prove Lemma 2, which follows easily from the following result.
Lemma 5 We can find disjoint sets of vertices
such that
![]()
- For every
,
in different sets,
![]()
- For every set
,
![]()
We can derive Lemma 2 from Lemma 5 as follows. Let us call the quantity the mass of a set
. Starting from the sets
promised by Lemma 5 we run the following process: as long as there are two sets both of mass
we merge them. Call
the sets of mass
obtained at the end of this process; in addition, there may be one more set of mass
. Every set has mass
. This means that the total mass of the sets is at most
, which implies
. Thus we have found
sets of vertices, each of mass at least
, and such that any two sets have separation
.
Now we turn to the proof of Lemma 5. We are going to use the fact that, for every small cone in , the mass of vertices
such that
is in the cone is also small and, in particular, it can made at most
. We will prove the Lemma by covering almost all the points
using a collection of well-separated small cones.
We first formalize the above intuition about cones. If (for region) is a subset of the unit sphere in
, then the diameter of
is
and the cone generated by is the set
of non-negative scalar multiples of elements of
. The set of vertices covered by
, denoted
is the set of vertices
such that
is in the cone generated by
or, equivalently,
If has small diameter, then
has small mass.
Lemma 6 For every subset
of the unit sphere,
Proof: For every two unit vectors and
, we have
For every vertex , call
Let be a vector in
. Then we have
In particular, if , then the mass of
is at most
Another observation is that, for every two subsets of the unit sphere,
Our approach will be to find disjoint subsets of the unit sphere, each of diameter at most
, such that the total mass of the sets
is at least
and such that the separation between any two
is at least
.
To do this, we tile with axis-parallel cubes of side
, which clearly have diameter at most
, and, for every cube
, we define its core
to be a cube with the same center as
and of side
. Note two points in the core of two different cubes have distance at least
. Let now
be the intersections of the cube cores with the unit sphere. Since each
is a subset of a core of a cube, it has diameter at most
, and the distance between any two points in different regions is at least
. We claim that there is a way to choose the location of the centers of the cubes so that
.
Let us start by a fixed configuration of the cubes and then apply an axis-parallel random shift (by adding to each coordinate, a random real in the range . Then, for each fixed point in
and, in particular, for each point
, the probability that it falls in the core of a cube after the shift is at least
, so the average mass of the vertices covered by the regions is at least
, and there must exist a shift that is at least as good.
Typo in proof of lemma 3: should be “w^T X X^T w”
and then “X X^T is identity”
@Yu Zhao: thanks.
I would also like to thank Arnold Filtser, who sent me a lot of corrections for this lecture
Right after Lemma 5, in the paragraph showing the connection of Lemma 5 to Lemma 2, it states that “Every set has mass at most 1 + 1/4k. This means that the total mass of the sets is at most 1/2 + t (1 + 4k)”.
Given the context, I assume that this refers to sets A_1, …, A_t that come up after the merging procedure. Nonetheless the fact that every set has mass at most 1+1/4k is true only for sets T_1, …, T_m. In my understanding the mass of a set A_i can be larger that 1+1/4k since A_i may come up from the merging of several of the sets T_1, …, T_m.
What am I missing here?