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
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.
- 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 .
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:
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
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.
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.
- 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.