CS294 Lecture 17: Zig-zag Product, continued

In which we analyze the zig-zag graph product.

In the previous lecture, we claimed it is possible to “combine” a {d}-regular graph on {D} vertices and a {D}-regular graph on {N} vertices to obtain a {d^2}-regular graph on {ND} vertices which is a good expander if the two starting graphs are. Let the two starting graphs be denoted by {H} and {G} respectively. Then, the resulting graph, called the zig-zag product of the two graphs is denoted by {G \textcircled{\rm z} H}.

We will use {\lambda(G)} to denote the eigenvalue with the second-largest absolute value of the normalized adjacency matrix {\frac 1d A_G} of a {d}-regular graph {G}. If {0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n \leq 2} are the eigenvalues of the normalized Laplacian of {G}, then {\lambda(G) = \max \{ 1 - \lambda_2 , \lambda_n -1 \}}.

We claimed that if {\lambda(H) \leq b} and {\lambda(G) \leq a}, then {\lambda(G \textcircled{\rm z} H) \leq a+ 2b + b^2}. In this lecture we shall recall the construction for the zig-zag product and prove this claim.

1. Replacement Product and Zig-Zag Product

We first describe a simpler product for a “small” {d}-regular graph on {D} vertices (denoted by {H}) and a “large” {D}-regular graph on {N} vertices (denoted by {G}). Assume that for each vertex of {G}, there is some ordering on its {D} neighbors. Then we construct the replacement product (see figure) {G \textcircled{\rm r} H} as follows:

  • Replace each vertex of {G} with a copy of {H} (henceforth called a cloud). For {v \in V(G), i \in V(H)}, let {(v,i)} denote the {i^{th}} vertex in the {v^{th}} cloud.
  • Let {(u, v) \in E(G)} be such that {v} is the {i}-th neighbor of {u} and {u} is the {j}-th neighbor of {v}. Then {((u,i),(v,j)) \in E(G \textcircled{\rm r} H)}. Also, if {(i,j) \in E(H)}, then {\forall u \in V(G)~ ((u,i),(u,j)) \in E(G \textcircled{\rm r} H)}.

Note that the replacement product constructed as above has {ND} vertices and is {(d+1)}-regular.

2. Zig-zag product of two graphs

Given two graphs {G} and {H} as above, the zig-zag product {G\textcircled{\rm z} H} is constructed as follows (see figure):

  • The vertex set {V(G \textcircled{\rm z} H)} is the same as in the case of the replacement product.
  • {((u,i),(v,j)) \in E(G \textcircled{\rm z} H)} if there exist {\ell} and {k} such that {((u,i)(u,\ell)}, {((u,\ell),(v,k))} and {((v,k),(v,j))} are in {E(G \textcircled{\rm r} H)} i.e. {(v,j)} can be reached from {(u,i)} by taking a step in the first cloud, then a step between the clouds and then a step in the second cloud (hence the name!).

It is easy to see that the zig-zag product is a {d^2}-regular graph on {ND} vertices.

Let {M \in {\mathbb R}^{([N] \times [D]) \times ([N] \times [D])}} be the normalized adjacency matrix of {G \textcircled{\rm z} H}. Using the fact that each edge in {G \textcircled{\rm r} H} is made up of three steps in {G \textcircled{\rm r} H}, we can write {M} as {BAB}, where

\displaystyle  \begin{array}{rcl}  B[(u,i),(v,j)] = \left\{ \begin{array}{ll} 0 \ u\neq v \\ \frac 1d \ u=v \ {\rm and} \ \{ i,j \} \in H \\ \end{array} \right. \end{array}

And {A[(u,i),(v,j)]=1} if {u} is the {j}-th neighbor of {v} and {v} is the {i}-th neighbor of {u}, and {A[(u,i),(v,j)]=0} otherwise.

Note that {A} is the adjacency matrix for a matching and is hence a permutation matrix.

3. A Technical Preliminary

We will use the following fact. Suppose that {M = \frac 1d A_G} is the normalized adjacency matrix of a graph {G}. Thus the largest eigenvalue of {M} is 1, with eigenvector {{\bf 1}}; we have

\displaystyle  \lambda(G) = \max_{{\bf x} \perp {\bf 1}} \frac {| {\bf x}^T M {\bf x} |}{ ||{\bf x}||^2 } = \max_{{\bf x} \perp {\bf 1}} \frac {|| M {\bf x} ||}{ || {\bf x}||} \ \ \ \ \ (1)

which is a corollary of the following more general result. Recall that a vector space {S\subseteq {\mathbb R}^n} is an invariant subspace for a matrix {M \in {\mathbb R}^{n\times n}} if {M {\bf x} \in S} for every {{\bf x} \in S}.

Lemma 1 Let {M} be a symmetric matrix, and {S} be a {k}-dimensional invariant subspace for {M}. Thus, (from the proof of the spectral theorem) we have that {S} has an orthonormal basis of eigenvectors; let {\lambda_1\leq \cdots \leq \lambda_k} be the corresponding eigenvalues with multiplicities; we have

\displaystyle  \max_{i=1,\ldots k} | \lambda_i | = \max_{{\bf x} \in S} \frac {| {\bf x}^T M {\bf x} |}{ ||{\bf x}||^2 } = \max_{{\bf x} \in S} \frac {|| M {\bf x} ||}{ || {\bf x}||}

Proof: If the largest eigenvalue in absolute value is {\lambda_k}, then

\displaystyle  \max_{i=1,\ldots k} | \lambda_i | = \lambda_k = \max_{{\bf x} \in S} \frac { {\bf x}^T M {\bf x} }{ ||{\bf x}||^2 }

and if it is {- \lambda_1} (because {\lambda_1} is negative, and {-\lambda_1 > \lambda_n})

\displaystyle  \max_{i=1,\ldots k} | \lambda_i | = - \lambda_1 = - \min_{{\bf x} \in S} \frac { {\bf x}^T M {\bf x} }{ ||{\bf x}||^2 } = \max_{{\bf x} \in S} - \frac { {\bf x}^T M {\bf x} }{ ||{\bf x}||^2 }

so we have

\displaystyle   \max_{i=1,\ldots k} | \lambda_i | \leq \max_{{\bf x} \in S} \frac {| {\bf x}^T M {\bf x} |}{ ||{\bf x}||^2 } \ \ \ \ \ (2)

From Cauchy-Schwarz, we have

\displaystyle  | {\bf x}^T M {\bf x} | \leq || {\bf x}|| \cdot ||M {\bf x}||

and so

\displaystyle   \max_{{\bf x} \in S} \frac {| {\bf x}^T M {\bf x} |}{ ||{\bf x}||^2 } \leq \max_{{\bf x} \in S} \frac {||M {\bf x} ||}{ ||{\bf x}|| } \ \ \ \ \ (3)

Finally, if {{\bf x}_1,\ldots,{\bf x}_k} is the basis of orthonormal eigenvectors in {S} such that {M {\bf x}_i = \lambda_i}, then, for every {{\bf x} \in S}, we can write {{\bf x} = \sum_i a_i {\bf x}_i} and

\displaystyle  || M {\bf x} || = || \sum_i \lambda_i a_i {\bf x}_i || = \sqrt{ \sum_i \lambda_i^2 a_i^2} \leq \max_{i=1,\ldots, k} |\lambda_i| \cdot \sqrt{\sum_i a_i^2} = \max_{i=1,\ldots, k} |\lambda_i| \cdot ||{\bf x}||

so

\displaystyle   \max_{{\bf x} \in S} \frac {||M {\bf x} |}{ ||{\bf x}|| } \leq \max_{i=1,\ldots, k} |\lambda_i| \ \ \ \ \ (4)

and the Lemma follows by combining (2), (3) and (4). \Box

4. Analysis of the zig-zag Product

Theorem 2 Let {G} be a {D}-regular graph with {n} nodes, {H} be a {d}-regular graph with {D} nodes, and let {a:= \lambda(G)}, {b:= \lambda(H)}, and let the normalized adjacency matrix of {G \textcircled{\rm z} H} be {M = BAB} where {A} and {B} are as defined in Section 1.

Then {\lambda(G\textcircled{\rm z} H) \leq a + b + b^2}

Proof: Let {{\bf x} {\mathbb R}^{n \times D}} be such that {{\bf x} \perp {\bf 1}}. We refer to a set of coordinates of {{\bf x}} corresponding to a copy of {H} as a “block” of coordinate.

We write {{\bf x} = {\bf x}_{||} + {\bf x}_{\perp}}, where {{\bf x}_{||}} is constant within each block, and {{\bf x}_{\perp}} sums to zero within each block. Note both {{\bf x}_{||}} and {{\bf x}_{\perp}} are orthogonal to {{\bf 1}}, and that they are orthogonal to each other.

We want to prove

\displaystyle  \frac{|{\bf x}^T M {\bf x}|}{||{\bf x}||^2} \leq a + b + b^2 \ \ \ \ \ (5)

We have (using the fact that {M} is symmetric)

\displaystyle  | {\bf x}^T M {\bf x}| = \leq | {\bf x}_{||}^T M {\bf x}_{||} | + 2 | {\bf x}_{||} ^T M {\bf x}_{\perp} | + | {\bf x}_{\perp} ^T M {\bf x}_{\perp} |

And it remains to bound the three terms.

  1. { | {\bf x}_{||}^T M {\bf x}_{||} | \leq a || {\bf x}_{||}||^2}

    Because, after writing {M = BAB}, we see that {B {\bf x}_{||} = {\bf x}_{||}}, because {B} is the same as {I_n \otimes \left( \frac 1d A_H\right)}, the tensor product of the identity and of the normalized adjacency matrix of {H}. The normalized adjacency matrix of {H} leaves a vector parallel to all-ones unchanged, and so {B} leaves every vector that is constant in each block unchanged.

    Thus

    \displaystyle  | {\bf x}_{||}^T M {\bf x}_{||} | = | {\bf x}_{||}^T A {\bf x}_{||}

    Let {{\bf y}} be the vector such that {y_v} is equal to the value that {{\bf x}_{||}} has in the block of {v}. Then

    \displaystyle  | {\bf x}_{||}^T A {\bf x}_{||} | = 2 \sum_{ \{ (v,i), (w,j) \} \in E_{G\textcircled{\rm z} H} } y_v y_w = {\bf y}^T A_G {\bf y} = a D || {\bf y} ||^2 \leq a ||{\bf x}_{||}||^2

    because {{\bf y} \perp {\bf 1}} and {||{\bf y}||^2 = \frac 1 D || {\bf x}_{||}||^2}

  2. {|{\bf x}_{\perp}^T M {\bf x}_{\perp}| \leq b^2 || {\bf x}_{\perp} ||^2} Because, from Cauchy-Schwarz and the fact that permutation matrices preserve length, we have

    \displaystyle  | {\bf x}_{\perp} ^T BAB {\bf x}_{\perp} | \leq || B {\bf x}_{\perp} || \cdot || A B {\bf x}_{\perp} || =|| B {\bf x}_{\perp} ||^2

    Now let us call {{\bf x}^v_{\perp}} the restriction of {{\bf x}_\perp} to coordinates of the form {(v,i)} for {i=1,\ldots, D}. Then each {{\bf x}^v _ {\perp}} is orthogonal to the all-one vector and {A_H {\bf x}^v_{\perp} \leq db || {\bf x}^v_{\perp} ||}, so

    \displaystyle  || B {\bf x}_{\perp} ||^2 = \sum_v || d^{-1} A_H {\bf x}^v _{\perp} ||^2 \leq \sum_v b^2 || {\bf x}^v_{\perp} ||^2 = b^2 || {\bf x}_{\perp} ||^2

  3. {2|{\bf x}_{||} ^T M {\bf x}_{\perp} | \leq b || {\bf x}||^2}

    Because, from Cauchy-Schwarz, the fact that {B {\bf x}_{||} = {\bf x}_{||}} and the fact that permutation matrices preserve length, we have

    \displaystyle  | {\bf x}_{||} ^T BAB {\bf x}_{\perp} | \leq || B {\bf x}_{||} || \cdot || A B {\bf x}_{\perp} || = || {\bf x}_{||} || \cdot || B {\bf x}_{\perp} ||

    and we proved above that

    \displaystyle  || B {\bf x}_{\perp} || \leq b || {\bf x}_{\perp} ||

    so

    \displaystyle  | {\bf x}_{||} ^T BAB {\bf x}_{\perp} | \leq b \cdot || {\bf x}_{||} || \cdot ||{\bf x}_{\perp} || \leq \frac b2 (|| {\bf x}_{||} ||^2 + ||{\bf x}_{\perp} ||^2 ) = \frac b2 ||{\bf x}||^2

\Box

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s