CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube

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- ${d}$ hypercube ${H_d}$ has ${\lambda_2 = 1- \frac 2d}$ and ${h(H_d) = \frac 1d}$ , giving an infinite family of graphs for which ${\frac{1-\lambda_2}{2} = h(G)}$ , showing that the first Cheeger inequality is exactly tight.
The ${n}$ -cycle ${C_n}$ has ${\lambda_2 = 1 - O(n^{-2})}$ , and ${h(C_n) \geq \frac 2n}$ , giving an infinite family of graphs for which ${h(G) = \Omega(\sqrt{1-\lambda_2})}$ , showing that the second Cheeger inequality is tight up to a constant.
There is an eigenvector of the second eigenvalue of the hypercube ${H_d}$ , such that the SpectralPartitioning algorithm, given such a vector, outputs a cut ${(S,V-S)}$ of expansion ${h(S) = \Omega(1/\sqrt{d})}$ , showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.

1. Cayley Graphs and Their Spectrum

Let ${\Gamma}$ be a finite group. We will use additive notation, although the following definition applies to non-commutative groups as well. A subset ${S\subseteq \Gamma}$ is symmetric if ${a\in S \Leftrightarrow -a\in S}$ .

Definition 1 For a group ${\Gamma}$ and a symmetric subset ${S\subseteq \Gamma}$ , the Cayley graph ${Cay(\Gamma,S)}$ is the graph whose vertex set is ${\Gamma}$ , and such that ${(a,b)}$ is an edge if and only if ${b-a \in S}$ . Note that the graph is undirected and ${|S|}$ -regular.

We can also define Cayley weighted graphs: if ${w : \Gamma \rightarrow {\mathbb R}}$ is a function such that ${w(a) = w(-a)}$ for every ${a\in \Gamma}$ , then we can define the weighted graph ${Cay(G,w)}$ in which the edge ${(a,b)}$ has weight ${w(b-a)}$ . We will usually work with unweighted graphs.

Example 1 (Cycle) The ${n}$ -vertex cycle can be constructed as the Cayley graph ${Cay({\mathbb Z}/n{\mathbb Z},\{-1,1\})}$ .

Example 2 (Hypercube) The ${d}$ -dimensional hypercube can be constructed as the Cayley graph

$\displaystyle Cay( ({\mathbb Z}/2{\mathbb Z})^d, \{ (1,0,\ldots,0), (0,1,\ldots,0), \ldots, (0,0,\ldots,1) \} )$

where the group is the set ${\{ 0,1 \}^d}$ with the operation of bit-wise xor, and the set ${S}$ is the set of bit-vectors with exactly one ${1}$ .

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 ${\Gamma}$ be a finite abelian group, ${\chi: \Gamma \rightarrow {\mathbb C}}$ be a character of ${\Gamma}$ , ${S\subseteq \Gamma}$ be a symmetric set. Let ${M}$ be the normalized adjacency matrix of the Cayley graph ${G=Cay(\Gamma,S)}$ . Consider the vector ${{\bf x} \in {\mathbb C}^\Gamma}$ such that ${x_a = \chi(a)}$ .

Then ${{\bf x}}$ is an eigenvector of ${G}$ , with eigenvalue

$\displaystyle \frac 1{|S|} \sum_{s\in S} \chi(s)$

Proof: Consider the ${a}$ -th entry of ${M{\bf x}}$ :

$\displaystyle (M{\bf x})_a = \sum_b M_{a,b} x_b$

$\displaystyle = \frac 1{|S|} \sum_{b: b-a\in S} \chi (b)$

$\displaystyle = \frac{1}{|S|} \sum_{s\in S} \chi(a+s)$

$\displaystyle = x_a \cdot \frac 1 {|S|} \cdot \sum_{s\in S} \chi (s)$

And so

$\displaystyle M{\bf x} = \left( \frac 1 {|S|} \sum_{s\in S} \chi(s) \right) \cdot {\bf x}$

$\Box$

The eigenvalues of the form ${\frac 1 {S}\sum_{s\in S} \chi(s)}$ , where ${\chi}$ 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 ${\chi : \Gamma \rightarrow {\mathbb C}}$ and, equivalently, as vectors in ${{\mathbb C}^\Gamma}$ );
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 ${S}$ .

2. The Cycle

The ${n}$ -cycle is the Cayley graph ${Cay({\mathbb Z}/n{\mathbb Z},\{-1,+1\})}$ . Recall that, for every ${n\in \{0,\ldots,n-1\}}$ , the group ${{\mathbb Z}/n{\mathbb Z}}$ has a character ${\chi_r (x) = e^{2\pi i r x /n}}$ .

This means that for every ${r\in \{0,\ldots,n-1\}}$ we have the eigenvalue

$\displaystyle \lambda_r = \frac 12 e^{2\pi i r /n} + \frac 12 e^{-2\pi i r /n} = \cos (2\pi r/n)$

where we used the facts that ${e^{ix} = \cos(x) + i \sin(x)}$ , that ${\cos(x) = \cos(-x)}$ , and ${\sin(x) = -\sin(-x)}$ .

For ${r=0}$ we have the eigenvalue ${1}$ . For ${r=1}$ we have the second largest eigenvalue ${\cos(2\pi /n) = 1- \Theta(1/n^2)}$ .

The expansion of the cycle is ${h(C_n) \geq 2/n}$ , and so the cycle is an example in which the second Cheeger inequality is tight.

3. The Hypercube

The group ${\{ 0,1 \}^d}$ with bitwise xor has ${2^d}$ characters; for every ${r\in \{ 0,1 \}^d}$ there is a character ${\chi_r: \{ 0,1 \}^d \rightarrow \{-1,1\}}$ defined as

$\displaystyle \chi_r(x) = (-1)^{\sum_i r_i x_i }$

Let us denote the set ${S}$ by ${\{ e^{1}, \ldots, e^d \}}$ , where we let ${e^{j} \in \{ 0,1 \}^d}$ denote the bit-vector that has a ${1}$ in the ${j}$ -th position, and zeroes everywhere else. This means that, for every bit-vector ${r\in \{ 0,1 \}^d}$ , the hypercube has the eigenvalue

$\displaystyle \frac 1d \sum_j \chi_r(e^j) = \frac 1d \sum_j (-1)^{r_j } = \frac 1d ( -|r| + d-|r| ) = 1 - 2\frac{|r|}{d}$

where we denote by ${|r|}$ the weight of ${r}$ , that is, the number of ones in ${r}$ .

Corresponding to ${r=(0,\ldots,0)}$ , we have the eigenvalue ${1}$ .

For each of the ${d}$ vectors ${r}$ with exactly one ${1}$ , we have the second largest eigenvalue ${1-2/d}$ .

Let us compute the expansion of the hypercube. Consider “dimension cuts” of the form ${S_i := \{ x\in \{ 0,1 \}^n : x_i = 0 \}}$ . The set ${S_i}$ contains half of the vertices, and the number of edges that cross the cut ${(S_i,V-S_i)}$ is also equal to half the number of vertices (because the edges form a perfect matching), so we have ${h(S_i) = \frac 1d}$ .

These calculations show that the first Cheeger inequality ${(1-\lambda_2)/2 \leq h(G)}$ 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 ${d}$ -dimensional hypercube, the second eigenvalue has multiplicity ${d}$ , and that its eigenvectors are vectors ${{\bf x}^j \in {\mathbb R}^{2^d}}$ such that ${x^j_a = (-1)^{a_j}}$ . Consider now the vector ${{\bf x} := \sum_j {\bf x}^j}$ ; this is still clearly an eigenvector of the second eigenvalue. The entries of the vector ${{\bf x}}$ are

$\displaystyle x_a = \sum_j (-1)^{a_j} = d-2|a|$

Suppose now that we apply the spectral partitioning algorithm using ${{\bf x}}$ as our vector. This is equivalent to considering all the cuts ${(S_t,V-S_t)}$ in the hypercube in which we pick a threshold ${t}$ and define ${S_t: = \{ a\in \{ 0,1 \}^n : |a| \geq t \}}$ .

Some calculations with binomial coefficients show that the best such “threshold cut” is the “majority cut” in which we pick ${t=n/2}$ , and that the expansion of ${S_{n/2}}$ is

$\displaystyle h(S_{n/2}) = \Omega \left( \frac 1 {\sqrt d} \right )$

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 ${(S,V-S)}$ such that ${h(S) \geq \Omega( \sqrt {h(G)} )}$ . Recall that we proved ${h(S) \leq 2 \sqrt{h(G)}}$ , which is thus tight.

1 thought on “CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube”

Pingback: The expansion of the Payley graph | in theory

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube

1 thought on “CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube”

Leave a Reply

Share this:

Like this:

Related

1 thought on “CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube”

Leave a Reply