# 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$

Advertisements