In which we talk about the spectrum of Cayley graphs of abelian groups, we compute the eigenvalues and eigenvectors of the cycle and of the hypercube, and we verify the tightness of the Cheeger inequalities and of the analysis of spectral partitioning
In this lecture we will prove the following results:
- The dimension- hypercube has and , giving an infinite family of graphs for which , showing that the first Cheeger inequality is exactly tight.
- The -cycle has , and , giving an infinite family of graphs for which , showing that the second Cheeger inequality is tight up to a constant.
- There is an eigenvector of the second eigenvalue of the hypercube , such that the SpectralPartitioning algorithm, given such a vector, outputs a cut of expansion , showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.
1. Cayley Graphs and Their Spectrum
Let be a finite group. We will use additive notation, although the following definition applies to non-commutative groups as well. A subset is symmetric if .
Definition 1 For a group and a symmetric subset , the Cayley graph is the graph whose vertex set is , and such that is an edge if and only if . Note that the graph is undirected and -regular.
We can also define Cayley weighted graphs: if is a function such that for every , then we can define the weighted graph in which the edge has weight . We will usually work with unweighted graphs.
Example 1 (Cycle) The -vertex cycle can be constructed as the Cayley graph .
Example 2 (Hypercube) The -dimensional hypercube can be constructed as the Cayley graph
where the group is the set with the operation of bit-wise xor, and the set is the set of bit-vectors with exactly one .
If we construct a Cayley graph from a finite abelian group, then the eigenvectors are the characters of the groups, and the eigenvalues have a very simple description.
Lemma 2 Let be a finite abelian group, be a character of , be a symmetric set. Let be the normalized adjacency matrix of the Cayley graph . Consider the vector such that .
Then is an eigenvector of , with eigenvalue
Proof: Consider the -th entry of :
The eigenvalues of the form , where is a character, enumerate all the eigenvalues of the graph, as can be deduced from the following observations:
- Every character is an eigenvector;
- The characters are linearly independent (as functions and, equivalently, as vectors in );
- There are as many characters as group elements, and so as many characters as nodes in the corresponding Cayley graphs.
It is remarkable that, for a Cayley graph, a system of eigenvectors can be determined based solely on the underlying group, independently of the set .
2. The Cycle
The -cycle is the Cayley graph . Recall that, for every , the group has a character .
This means that for every we have the eigenvalue
where we used the facts that , that , and .
For we have the eigenvalue . For we have the second largest eigenvalue .
The expansion of the cycle is , and so the cycle is an example in which the second Cheeger inequality is tight.
3. The Hypercube
The group with bitwise xor has characters; for every there is a character defined as
Let us denote the set by , where we let denote the bit-vector that has a in the -th position, and zeroes everywhere else. This means that, for every bit-vector , the hypercube has the eigenvalue
where we denote by the weight of , that is, the number of ones in .
Corresponding to , we have the eigenvalue .
For each of the vectors with exactly one , we have the second largest eigenvalue.
Let us compute the expansion of the hypercube. Consider “dimension cuts” of the form . The set contains half of the vertices, and the number of edges that cross the cut is also equal to half the number of vertices (because the edges form a perfect matching), so we have .
These calculations show that the first Cheeger inequality is tight for the hypercube.
Finally, we consider the tightness of the approximation analysis of the spectral partitioning algorithm.
We have seen that, in the -dimensional hypercube, the second eigenvalue has multiplicity , and that its eigenvectors are vectors such that . Consider now the vector ; this is still clearly an eigenvector of the second eigenvalue. The entries of the vector are
Suppose now that we apply the spectral partitioning algorithm using as our vector. This is equivalent to considering all the cuts in the hypercube in which we pick a threshold and define .
Some calculations with binomial coefficients show that the best such “threshold cut” is the “majority cut” in which we pick , and that the expansion of is
This gives an example of a graph and of a choice of eigenvector for the second eigenvalue that, given as input to the spectral partitioning algorithm, result in the output of a cut such that . Recall that we proved , which is thus tight.