随机算法 (Spring 2013)/Expander Graphs and Mixing

Expander Graphs

According to wikipedia:

"Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, extractors, pseudorandom generators, sorting networks and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as SL=L and the PCP theorem. In cryptography too, expander graphs are used to construct hash functions."

We will not explore everything about expander graphs, but will focus on the performances of random walks on expander graphs.

Consider an undirected (multi-)graph $G(V,E)$, where the parallel edges between two vertices are allowed.

Some notations:

• For $S,T\subset V$, let $E(S,T)=\{uv\in E\mid u\in S,v\in T\}$.
• The Edge Boundary of a set $S\subset V$, denoted $\partial S$, is $\partial S=E(S,\overline{S})$.

Definition (Graph expansion)

The expansion ratio of an undirected graph $G$ on $n$ vertices, is defined as $\varphi (G)=\underset{\stackrel{S\subset V}{|S|\le \frac{n}{2}}}{min}\frac{|\partial S|}{|S|}.$

Expander graphs are $d$-regular (multi)graphs with $d=O(1)$ and $\varphi (G)=\mathrm{\Omega }(1)$.

This definition states the following properties of expander graphs:

• Expander graphs are sparse graphs. This is because the number of edges is $dn/2=O(n)$.
• Despite the sparsity, expander graphs have good connectivity. This is supported by the expansion ratio.
• This one is implicit: expander graph is a family of graphs $\{G_n\}$, where $n$ is the number of vertices. The asymptotic order $O(1)$ and $\mathrm{\Omega }(1)$ in the definition is relative to the number of vertices $n$, which grows to infinity.

The following fact is directly implied by the definition.

An expander graph has diameter $O(\log n)$.

The proof is left for an exercise.

For a vertex set $S$, the size of the edge boundary $|\partial S|$ can be seen as the "perimeter" of $S$, and $|S|$ can be seen as the "volume" of $S$. The expansion property can be interpreted as a combinatorial version of isoperimetric inequality.

Vertex expansion

We can alternatively define the vertex expansion. For a vertex set $S\subset V$, its vertex boundary, denoted $\delta S$ is defined as that

$\delta S=\{u\notin S\mid uv\in E\text{ and }v\in S\}$,

and the vertex expansion of a graph $G$ is $\psi (G)=\underset{\stackrel{S\subset V}{|S|\le \frac{n}{2}}}{min}\frac{|\delta S|}{|S|}$.

Existence of expander graph

We will show the existence of expander graphs by the probabilistic method. In order to do so, we need to generate random $d$-regular graphs.

Suppose that $d$ is even. We can generate a random $d$-regular graph $G(V,E)$ as follows:

• Let $V$ be the vertex set. Uniformly and independently choose $\frac{d}{2}$ cycles of $V$.
• For each vertex $v$, for every cycle, assuming that the two neighbors of $v$ in that cycle is $w$ and $u$, add two edges $wv$ and $uv$ to $E$.

The resulting $G(V,E)$ is a multigraph. That is, it may have multiple edges between two vertices. We will show that $G(V,E)$ is an expander graph with high probability. Formally, for some constant $d$ and constant $\alpha$,

$Pr[\varphi (G)\ge \alpha ]=1-o(1)$.

By the probabilistic method, this shows that there exist expander graphs. In fact, the above probability bound shows something much stronger: it shows that almost every regular graph is an expander.

Recall that $\varphi (G)=\underset{S:|S|\le \frac{n}{2}}{min}\frac{|\partial S|}{|S|}$. We call such $S\subset V$ that $\frac{|\partial S|}{|S|}<\alpha$ a "bad $S$". Then $\varphi (G)<\alpha$ if and only if there exists a bad $S$ of size at most $\frac{n}{2}$. Therefore,

$\begin{array}{rl}Pr[\varphi (G)<\alpha ]& =Pr[\underset{S:|S|\le \frac{n}{2}}{min}\frac{|\partial S|}{|S|}<\alpha ]\\ & =\sum _{k=1}^{\frac{n}{2}}Pr[\mathrm{\exists }\text{bad }S\text{ of size }k]\\ & \le \sum _{k=1}^{\frac{n}{2}}\sum _{S\in (\genfrac{}{}{0ex}{}{V}{k})}Pr[S\text{ is bad}]\end{array}$

Let $R\subset S$ be the set of vertices in $S$ which has neighbors in $\overline{S}$, and let $r=|R|$. It is obvious that $|\partial S|\ge r$, thus, for a bad $S$, $r<\alpha k$. Therefore, there are at most $\sum _{r=1}^{\alpha k}(\genfrac{}{}{0ex}{}{k}{r})$ possible choices such $R$. For any fixed choice of $R$, the probability that an edge picked by a vertex in $S-R$ connects to a vertex in $S$ is at most $k/n$, and there are $d(k-r)$ such edges. For any fixed $S$ of size $k$ and $R$ of size $r$, the probability that all neighbors of all vertices in $S-R$ are in $S$ is at most ${\left(\frac{k}{n}\right)}^{d(k-r)}$. Due to the union bound, for any fixed $S$ of size $k$,

$\begin{array}{rl}Pr[S\text{ is bad}]& \le \sum _{r=1}^{\alpha k}(\genfrac{}{}{0ex}{}{k}{r}){\left(\frac{k}{n}\right)}^{d(k-r)}\le \alpha k(\genfrac{}{}{0ex}{}{k}{\alpha k}){\left(\frac{k}{n}\right)}^{dk(1-\alpha )}\end{array}$

Therefore,

$\begin{array}{rl}Pr[\varphi (G)<\alpha ]& \le \sum _{k=1}^{\frac{n}{2}}\sum _{S\in (\genfrac{}{}{0ex}{}{V}{k})}Pr[S\text{ is bad}]\\ & \le \sum _{k=1}^{\frac{n}{2}}(\genfrac{}{}{0ex}{}{n}{k})\alpha k(\genfrac{}{}{0ex}{}{k}{\alpha k}){\left(\frac{k}{n}\right)}^{dk(1-\alpha )}\\ & \le \sum _{k=1}^{\frac{n}{2}}{\left(\frac{en}{k}\right)}^k\alpha k{\left(\frac{ek}{\alpha k}\right)}^{\alpha k}{\left(\frac{k}{n}\right)}^{dk(1-\alpha )}& (\text{Stirling formula }(\genfrac{}{}{0ex}{}{n}{k})\le {\left(\frac{en}{k}\right)}^k)\\ & \le \sum _{k=1}^{\frac{n}{2}}\exp (O(k)){\left(\frac{k}{n}\right)}^{k(d(1-\alpha )-1)}.\end{array}$

The last line is $o(1)$ when $d\ge \frac{2}{1-\alpha }$. Therefore, $G$ is an expander graph with expansion ratio $\alpha$ with high probability for suitable choices of constant $d$ and constant $\alpha$.

Computing graph expansion

Computation of graph expansion seems hard, because the definition involves the minimum over exponentially many subsets of vertices. In fact, the problem of deciding whether a graph is an expander is co-NP-complete. For a non-expander $G$, the vertex set $S\subset V$ which has low expansion ratio is a proof of the fact that $G$ is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the $\varphi (G)$ unless NP=P.

The expansion ratio of a graph is closely related to the sparsest cut of the graph, which is the dual problem of the multicommodity flow problem, both NP-complete. Studies of these two problems revolutionized the area of approximation algorithms.

We will see right now that although it is hard to compute the expansion ratio exactly, the expansion ratio can be approximated by some efficiently computable algebraic identity of the graph.

Spectral Graph Theory

Graph spectrum

The adjacency matrix of an $n$-vertex graph $G$, denoted $A=A(G)$, is an $n\times n$ matrix where $A(u,v)$ is the number of edges in $G$ between vertex $u$ and vertex $v$. Because $A$ is a symmetric matrix with real entries, due to the Perron-Frobenius theorem, it has real eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$, which associate with an orthonormal system of eigenvectors $v_1,v_2,\dots ,v_n$ with $A{v}_i={\lambda }_i{v}_i$. We call the eigenvalues of $A$ the spectrum of the graph $G$.

The spectrum of a graph contains a lot of information about the graph. For example, supposed that $G$ is $d$-regular, the following lemma holds.

Lemma

$|{\lambda }_i|\le d$ for all $1\le i\le n$. ${\lambda }_1=d$ and the corresponding eigenvector is $(\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}},\dots ,\frac{1}{\sqrt{n}})$. $G$ is connected if and only if ${\lambda }_1>{\lambda }_2$. If $G$ is bipartite then ${\lambda }_1=-{\lambda }_n$.

Proof. Let $A$ be the adjacency matrix of $G$, with entries $a_{ij}$. It is obvious that $\sum _j{a}_{ij}=d$ for any $j$. (1) Suppose that $Ax=\lambda x,x\ne \mathbf{0}$, and let $x_i$ be an entry of $x$ with the largest absolute value. Since $(Ax{)}_i=\lambda x_i$, we have $\sum _j{a}_{ij}{x}_j=\lambda x_i,$ and so $|\lambda ||x_i|=\left|\sum _j{a}_{ij}{x}_j\right|\le \sum _j{a}_{ij}|x_j|\le \sum _j{a}_{ij}|x_i|\le d|x_i|.$ Thus $|\lambda |\le d$. (2) is easy to check. (3) Let $x$ be the nonzero vector for which $Ax=dx$, and let $x_i$ be an entry of $x$ with the largest absolute value. Since $(Ax{)}_i=d{x}_i$, we have $\sum _j{a}_{ij}{x}_j=d{x}_i.$ Since $\sum _j{a}_{ij}=d$ and by the maximality of $x_i$, it follows that $x_j=x_i$ for all $j$ that $a_{ij}>0$. Thus, $x_i=x_j$ if $i$ and $j$ are adjacent, which implies that $x_i=x_j$ if $i$ and $j$ are connected. For connected $G$, all vertices are connected, thus all $x_i$ are equal. This shows that if $G$ is connected, the eigenvalue $d={\lambda }_1$ has multiplicity 1, thus ${\lambda }_1>{\lambda }_2$. If otherwise, $G$ is disconnected, then for two different components, we have $Ax=dx$ and $Ay=dy$, where the entries of $x$ and $y$ are nonzero only for the vertices in their components components. Then $A(\alpha x+\beta y)=d(\alpha x+\beta y)$. Thus, the multiplicity of $d$ is greater than 1, so ${\lambda }_1={\lambda }_2$. (4) If $G$ if bipartite, then the vertex set can be partitioned into two disjoint nonempty sets $V_1$ and $V_2$ such that all edges have one endpoint in each of $V_1$ and $V_2$. Algebraically, this means that the adjacency matrix can be organized into the form $P^{T}AP=\left[\begin{array}{cc}0& B\\ B^T& 0\end{array}\right]$ where $P$ is a permutation matrix, which has no change on the eigenvalues. If $x$ is an eigenvector corresponding to the eigenvalue $\lambda$, then $x^{\prime }$ which is obtained from $x$ by changing the sign of the entries corresponding to vertices in $V_2$, is an eigenvector corresponding to the eigenvalue $-\lambda$. It follows that the spectrum of a bipartite graph is symmetric with respect to 0. $◻$

Cheeger's Inequality

One of the most exciting results in spectral graph theory is the following theorem which relate the graph expansion to the spectral gap.

Theorem (Cheeger's inequality)

Let $G$ be a $d$-regular graph with spectrum ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. Then $\frac{d-{\lambda }_2}{2}\le \varphi (G)\le \sqrt{2d(d-{\lambda }_2)}.$

The theorem was first stated for Riemannian manifolds, and was proved by Cheeger and Buser (for different directions of the inequalities). The discrete case is proved independently by Dodziuk and Alon-Milman.

For a $d$-regular graph, the quantity $(d-{\lambda }_2)$ is called the spectral gap. The name is due to the fact that it is the gap between the first and the second largest eigenvalues of a graph.

If we write $\alpha =1-\frac{{\lambda }_2}{d}$ (sometimes it is called the normalized spectral gap), the Cheeger's inequality is turned into a nicer form:

$\frac{\alpha }{2}\le \frac{\varphi }{d}\le \sqrt{2\alpha }$ or equivalently $\frac{1}{2}{\left(\frac{\varphi }{d}\right)}^2\le \alpha \le 2\left(\frac{\varphi }{d}\right)$.

Optimization Characterization of Eigenvalues

Theorem (Rayleigh-Ritz theorem)

Let $A$ be a symmetric $n\times n$ matrix. Let ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ be the eigen values of $A$ and $v_1,v_2,\dots ,v_n$ be the corresponding eigenvectors. Then $\begin{array}{rl}{\lambda }_1& =\underset{x\in {\mathbb{R}}^n}{max}\frac{x^{T}Ax}{x^{T}x}\end{array}$ and $\begin{array}{rl}{\lambda }_2& =\underset{x\mathrm{\perp }{v}_1}{max}\frac{x^{T}Ax}{x^{T}x}.\end{array}$

Proof. Without loss of generality, we may assume that $v_1,v_2,\dots ,v_n$ are orthonormal eigen-basis. Then it holds that $\frac{v_1^{T}A{v}_1}{v_1^T{v}_1}={\lambda }_1{v}_1^T{v}_1={\lambda }_1$, thus we have $\underset{x\in {\mathbb{R}}^n}{max}\frac{x^{T}Ax}{x^{T}x}\ge {\lambda }_1$. Let $x\in {\mathbb{R}}^n$ be an arbitrary vector and let $y=\frac{x}{\sqrt{x^{T}x}}=\frac{x}{\parallel x\parallel }$ be its normalization. Since $v_1,v_2,\dots ,v_n$ are orthonormal basis, $y$ can be expressed as $y=\sum _{i=1}^n{c}_i{v}_i$. Then $\begin{array}{rl}\frac{x^{T}Ax}{x^{T}x}& =y^{T}Ay={\left(\sum _{i=1}^n{c}_i{v}_i\right)}^{T}A\left(\sum _{i=1}^n{c}_i{v}_i\right)={\left(\sum _{i=1}^n{c}_i{v}_i\right)}^T\left(\sum _{i=1}^n{\lambda }_i{c}_i{v}_i\right)\\ & =\sum _{i=1}^n{\lambda }_i{c}_i^2\le {\lambda }_1\sum _{i=1}^n{c}_i^2={\lambda }_1\parallel y\parallel ={\lambda }_1.\end{array}$ Therefore, $\underset{x\in {\mathbb{R}}^n}{max}\frac{x^{T}Ax}{x^{T}x}\le {\lambda }_1$. Altogether we have $\underset{x\in {\mathbb{R}}^n}{max}\frac{x^{T}Ax}{x^{T}x}={\lambda }_1$ It is similar to prove $\underset{x\mathrm{\perp }{v}_1}{max}\frac{x^{T}Ax}{x^{T}x}={\lambda }_2$. In the first part take $x=v_2$ to show that $\underset{x\mathrm{\perp }{v}_1}{max}\frac{x^{T}Ax}{x^{T}x}\ge {\lambda }_2$; and in the second part take an arbitrary $x\mathrm{\perp }{v}_1$ and $y=\frac{x}{\parallel x\parallel }$. Notice that $y\mathrm{\perp }{v}_1$, thus $y=\sum _{i=1}^n{c}_i{v}_i$ with $c_1=0$. $◻$

The Rayleigh-Ritz Theorem is a special case of a fundamental theorem in linear algebra, called the Courant-Fischer theorem, which characterizes the eigenvalues of a symmetric matrix by a series of optimizations:

Theorem (Courant-Fischer theorem)

Let $A$ be a symmetric matrix with eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. Then $\begin{array}{rl}{\lambda }_k& =\underset{v_1,v_2,\dots ,v_{n-k}\in {\mathbb{R}}^n}{max}\underset{\stackrel{x\in {\mathbb{R}}^n,x\ne \mathbf{0}}{x\mathrm{\perp }{v}_1,v_2,\dots ,v_{n-k}}}{min}\frac{x^{T}Ax}{x^{T}x}\\ & =\underset{v_1,v_2,\dots ,v_{k-1}\in {\mathbb{R}}^n}{min}\underset{\stackrel{x\in {\mathbb{R}}^n,x\ne \mathbf{0}}{x\mathrm{\perp }{v}_1,v_2,\dots ,v_{k-1}}}{max}\frac{x^{T}Ax}{x^{T}x}.\end{array}$

Graph Laplacian

Let $G(V,E)$ be a $d$-regular graph of $n$ vertices and let $A$ be its adjacency matrix. We define $L=dI-A$ to be the Laplacian of the graph $G$. Take $x\in {\mathbb{R}}^V$ as a distribution over vertices, its Laplacian quadratic form $x^{T}Lx$ measures the "smoothness" of $x$ over the graph topology, just as what the Laplacian operator does to the differentiable functions.

Laplacian Property

For any vector $x\in {\mathbb{R}}^n$, it holds that $x^{T}Lx=\sum _{uv\in E}(x_u-x_v{)}^2$.

Proof. $\begin{array}{rl}{x}^{T}Lx& =\sum _{u,v\in V}{x}_u(dI-A{)}_{uv}{x}_v\\ & =\sum _u(d{x}_u^2-\sum _{uv\in E}{x}_u{x}_v)\\ & =\sum _{u\in V}\sum _{uv\in E}(x_u^2-x_u{x}_v).\end{array}$ On the other hand, $\begin{array}{rl}\sum _{uv\in E}(x_u-x_v{)}^2& =\sum _{uv\in E}(x_u^2-2x_u{x}_v+x_v^2)\\ & =\sum _{uv\in E}((x_u^2-x_u{x}_v)+(x_v^2-x_v{x}_u))\\ & =\sum _{u\in V}\sum _{uv\in E}(x_u^2-x_u{x}_v).\end{array}$ $◻$

Applying the Rayleigh-Ritz theorem to the Laplacian matrix of the graph, we have the following "variational characterization" of the spectral gap $d-{\lambda }_2$.

Theorem (Variational Characterization)

Let $G(V,E)$ be a $d$-regular graph of $n$ vertices. Suppose that its adjacency matrix is $A$, whose eigenvalues are ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. Let $L=dI-A$ be the Laplacian matrix. Then $\begin{array}{rl}d-{\lambda }_2& =\underset{x\mathrm{\perp }\mathbf{1}}{min}\frac{x^{T}Lx}{x^{T}x}=\underset{x\mathrm{\perp }\mathbf{1}}{min}\frac{\sum _{uv\in E}(x_u-x_v{)}^2}{\sum _{v\in V}{x}_v^2}.\end{array}$

Proof. For $d$-regular graph, we know that ${\lambda }_1=d$ and $\mathbf{1}A=d\mathbf{1}$, thus $\mathbf{1}$ is the eigenvector of ${\lambda }_1$. Due to Rayleigh-Ritz Theorem, it holds that ${\lambda }_2=\underset{x\mathrm{\perp }\mathbf{1}}{max}\frac{x^{T}Ax}{x^{T}x}$. Then $\begin{array}{rl}\underset{x\mathrm{\perp }\mathbf{1}}{min}\frac{x^{T}Lx}{x^{T}x}& =\underset{x\mathrm{\perp }\mathbf{1}}{min}\frac{x^T(dI-A)x}{x^{T}x}\\ & =\underset{x\mathrm{\perp }\mathbf{1}}{min}\frac{d{x}^{T}x-x^{T}Ax}{x^{T}x}\\ & =\underset{x\mathrm{\perp }\mathbf{1}}{min}(d-\frac{x^{T}Ax}{x^{T}x})\\ & =d-\underset{x\mathrm{\perp }\mathbf{1}}{max}\frac{x^{T}Ax}{x^{T}x}\\ & =d-{\lambda }_2.\end{array}$ We know it holds for the graph Laplacian that $x^{T}Lx=\sum _{uv\in E}(x_u-x_v{)}^2$. So the variational characterization of the second eigenvalue of graph is proved. $◻$

Proof of Cheeger's Inequality

We will first give an informal explanation why Cheeger's inequality holds.

Recall that the expansion is defined as

$\varphi (G)=\underset{\stackrel{S\subset V}{|S|\le \frac{n}{2}}}{min}\frac{|\partial S|}{|S|}.$

Let ${\chi }_S$ be the characteristic vector of the set $S$ such that

${\chi }_S(v)=\{\begin{array}{ll}1& v\in S,\\ 0& v\notin S.\end{array}$

It is easy to see that

$\frac{\sum _{uv\in E}({\chi }_S(u)-{\chi }_S(v){)}^2}{\sum _{v\in V}{\chi }_S(v{)}^2}=\frac{|\partial S|}{|S|}.$

Thus, the expansion can be expressed algebraically as

$\varphi (G)=\underset{\stackrel{S\subset V}{|S|\le \frac{n}{2}}}{min}\frac{\sum _{uv\in E}({\chi }_S(u)-{\chi }_S(v){)}^2}{\sum _{v\in V}{\chi }_S(v{)}^2}=\underset{\stackrel{x\in \{0,1{\}}^n}{\parallel x{\parallel }_1\le \frac{n}{2}}}{min}\frac{\sum _{uv\in E}(x_u-x_v{)}^2}{\sum _{v\in V}{x}_v^2}.$

On the other hand, due to the variational characterization of the spectral gap, we have

$d-{\lambda }_2=\underset{x\mathrm{\perp }\mathbf{1}}{min}\frac{\sum _{uv\in E}(x_u-x_v{)}^2}{\sum _{v\in V}{x}_v^2}.$

We can easily observe the similarity between the two formulas. Both the expansion ration $\varphi (G)$ and the spectral gap $d-{\lambda }_2$ can be characterized by optimizations of the same objective function $\frac{\sum _{uv\in E}(x_u-x_v{)}^2}{\sum _{v\in V}{x}_v^2}$ over different domains (for the spectral gap, the optimization is over all $x\mathrm{\perp }\mathbf{1}$; and for the expansion ratio, it is over all such vectors $x\in \{0,1{\}}^n$ with at most $n/2$ many 1-entries).

---

Notations

Throughout the proof, we assume that $G(V,E)$ is the $d$-regular graph of $n$ vertices, $A$ is the adjacency matrix, whose eigenvalues are ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$, and $L=(dI-A)$ is the graph Laplacian.

Large spectral gap implies high expansion

Cheeger's inequality (lower bound)

$\varphi (G)\ge \frac{d-{\lambda }_2}{2}.$

Proof. Let $S^{\ast }\subset V$, $|S^{\ast }|\le \frac{n}{2}$, be the vertex set achieving the optimal expansion ratio $\varphi (G)=\underset{\stackrel{S\subset V}{|S|\le \frac{n}{2}}}{min}\frac{|\partial S|}{|S|}=\frac{|\partial S^{\ast }|}{|S^{\ast }|}$, and $x\in {\mathbb{R}}^n$ be a vector defined as $x_v=\{\begin{array}{ll}1/|S^{\ast }|& \text{if }v\in S^{\ast },\\ -1/\left|\overline{S^{\ast }}\right|& \text{if }v\in \overline{S^{\ast }}.\end{array}$ Clearly, $x\cdot \mathbf{1}=\sum _{v\in S^{\ast }}\frac{1}{|S^{\ast }|}-\sum _{v\in \overline{S^{\ast }}}\frac{1}{\left|\overline{S^{\ast }}\right|}=0$, thus $x\mathrm{\perp }\mathbf{1}$. Due to the variational characterization of the second eigenvalue, $\begin{array}{rl}d-{\lambda }_2& \le \frac{\sum _{uv\in E}(x_u-x_v{)}^2}{\sum _{v\in V}{x}_v^2}\\ & =\frac{\sum _{u\in S^{\ast },v\in \overline{S^{\ast }},uv\in E}{(1/|S^{\ast }|+1/|\overline{S^{\ast }}|)}^2}{1/|S^{\ast }|+1/|\overline{S^{\ast }}|}\\ & =(\frac{1}{|S^{\ast }|}+\frac{1}{\left|\overline{S^{\ast }}\right|})\cdot |\partial S^{\ast }|\\ & \le \frac{2|\partial S^{\ast }|}{|S^{\ast }|}& (\text{since }|S^{\ast }|\le \frac{n}{2})\\ & =2\varphi (G).\end{array}$ $◻$

High expansion implies large spectral gap

We next prove the upper bound direction of the Cheeger's inequality:

Cheeger's inequality (upper bound)

$\varphi (G)\le \sqrt{2d(d-{\lambda }_2)}.$

This direction is harder than the lower bound direction. But it is mathematically more interesting and also more useful to us for analyzing the mixing time of random walks.

We prove the following equivalent inequality:

$\frac{{\varphi }^2}{2d}\le d-{\lambda }_2.$

Let $x$ satisfy that

• $Ax={\lambda }_{2}x$, i.e., it is a eigenvector for ${\lambda }_2$;
• $|\{v\in V\mid x_v>0\}|\le \frac{n}{2}$, i.e., $x$ has at most $n/2$ positive entries. (We can always choose $x$ to be $-x$ if this is not satisfied.)

And let nonnegative vector $y$ be defined as

$y_v=\{\begin{array}{ll}{x}_v& x_v>0,\\ 0& \text{otherwise.}\end{array}$

We then prove the following inequalities:

1. $\frac{y^{T}Ly}{y^{T}y}\le d-{\lambda }_2$;
2. $\frac{{\varphi }^2}{2d}\le \frac{y^{T}Ly}{y^{T}y}$.

The theorem is then a simple consequence by combining these two inequalities.

We prove the first inequality:

Lemma

$\frac{y^{T}Ly}{y^{T}y}\le d-{\lambda }_2$.

Proof. If $x_u\ge 0$, then $\begin{array}{rl}(Ly{)}_u& =((dI-A)y{)}_u=d{y}_u-\sum _{v}A(u,v)y_v=d{x}_u-\sum _{v:x_v\ge 0}A(u,v)x_v\\ & \le d{x}_u-\sum _{v}A(u,v)x_v=((dI-A)x{)}_u=(d-{\lambda }_2)x_u.\end{array}$ Then $\begin{array}{rl}{y}^{T}Ly& =\sum _u{y}_u(Ly{)}_u=\sum _{u:x_u\ge 0}{y}_u(Ly{)}_u=\sum _{u:x_u\ge 0}{x}_u(Ly{)}_u\\ & \le (d-{\lambda }_2)\sum _{u:x_u\ge 0}{x}_u^2=(d-{\lambda }_2)\sum _u{y}_u^2=(d-{\lambda }_2)y^{T}y,\end{array}$ which proves the lemma. $◻$

We then prove the second inequality:

Lemma

$\frac{{\varphi }^2}{2d}\le \frac{y^{T}Ly}{y^{T}y}$.

Proof. To prove this, we introduce a new quantity $\frac{\sum _{uv\in E}|y_u^2-y_v^2|}{y^{T}y}$ and shows that $\varphi \le \frac{\sum _{uv\in E}|y_u^2-y_v^2|}{y^{T}y}\le \sqrt{2d}\cdot \sqrt{\frac{y^{T}Ly}{y^{T}y}}$. This will give us the desired inequality $\frac{{\varphi }^2}{2d}\le \frac{y^{T}Ly}{y^{T}y}$. Lemma $\frac{\sum _{uv\in E}|y_u^2-y_v^2|}{y^{T}y}\le \sqrt{2d}\cdot \sqrt{\frac{y^{T}Ly}{y^{T}y}}$. Proof. By the Cauchy-Schwarz Inequality, $\begin{array}{rl}\sum _{uv\in E}|y_u^2-y_v^2|& =\sum _{uv\in E}|y_u-y_v||y_u+y_v|\\ & \le \sqrt{\sum _{uv\in E}(y_u-y_v{)}^2}\cdot \sqrt{\sum _{uv\in E}(y_u+y_v{)}^2}.\end{array}$ By the Laplacian property, the first term $\sqrt{\sum _{uv\in E}(y_u-y_v{)}^2}=\sqrt{y^{T}Ly}$. By the Inequality of Arithmetic and Geometric Means, the second term $\sqrt{\sum _{uv\in E}(y_u+y_v{)}^2}\le \sqrt{2\sum _{uv\in E}(y_u^2+y_v^2)}=\sqrt{2d\sum _{u\in V}{y}_u^2}=\sqrt{2d{y}^{T}y}.$ Combining them together, we have $\sum _{uv\in E}|y_u^2-y_v^2|\le \sqrt{2d}\cdot \sqrt{y^{T}Ly}\cdot \sqrt{y^{T}y}$. $◻$ Lemma $\varphi \le \frac{\sum _{uv\in E}|y_u^2-y_v^2|}{y^{T}y}$. Proof. Suppose that $y$ has $t$ nonzero entries. We know that $t\le n/2$ due to the definition of $y$. We enumerate the vertices $u_1,u_2,\dots ,u_n\in V$ such that $y_{u_1}\ge y_{u_2}\ge \cdots \ge y_{u_t}>y_{u_{t+1}}=\cdots =y_{u_n}=0$. Then $\begin{array}{rl}\sum _{uv\in E}|y_u^2-y_v^2|& =\sum _{\genfrac{}{}{0ex}{}{u_i{u}_j\in E}{i<j}}(y_{u_i}^2-y_{u_j}^2)=\sum _{\genfrac{}{}{0ex}{}{u_i{u}_j\in E}{i<j}}\sum _{k=i}^{j-1}(y_{u_k}^2-y_{u_{k+1}}^2)\\ & =\sum _{i=1}^n\sum _{j>i}A(u_i,u_j)\sum _{k=i}^{j-1}(y_{u_k}^2-y_{u_{k+1}}^2)=\sum _{i=1}^n\sum _{j>i}\sum _{k=i}^{j-1}A(u_i,u_j)(y_{u_k}^2-y_{u_{k+1}}^2).\end{array}$ We have the following universal equation for sums: $\begin{array}{rl}\sum _{i=1}^n\sum _{j>i}\sum _{k=i}^{j-1}A(u_i,u_j)(y_{u_k}^2-y_{u_{k+1}}^2)& =\sum _{k=1}^n\sum _{i\le k}\sum _{j>k}A(u_i,u_j)(y_{u_k}^2-y_{u_{k+1}}^2)\\ & =\sum _{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)\sum _{i\le k}\sum _{j>k}A(u_i,u_j)\end{array}$ Notice that $\sum _{i\le k}\sum _{j>k}A(u_i,u_j)=|\partial \{u_1,\dots ,u_k\}|$, which is at most $\varphi k$ since $k\le t\le n/2$. Therefore, combining these together, we have $\begin{array}{rl}\sum _{uv\in E}|y_u^2-y_v^2|& =\sum _{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)\sum _{i\le k}\sum _{j>k}A(u_i,u_j)\\ & =\sum _{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)|\partial \{u_1,\dots ,u_k\}|\\ & \le \varphi \sum _{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)k\\ & =\varphi \sum _{k=1}^t{y}_{u_k}^2\\ & =\varphi y^{T}y.\end{array}$ $◻$ $◻$

Spectral approach for symmetric chain

We consider the symmetric Markov chains defined on the state space $\mathrm{\Omega }$, where the transition matrix $P$ is symmetric.

We have the following powerful spectral theorem for symmetric matrices.

Theorem (Spectral theorem)

Let $S$ be a symmetric $n\times n$ matrix, whose eigenvalues are ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. There exist eigenvectors $v_1,v_2,\dots ,v_n$ such that $v_{i}S={\lambda }_i{v}_i$ for all $i=1,\dots ,n$ and $v_1,v_2,\dots ,v_n$ are orthonormal.

A set of orthonormal vectors $v_1,v_2,\dots ,v_n$ satisfy that

• for any $i\ne j$, $v_i$ is orthogonal to $v_j$, which means that $v_i^T{v}_j=0$, denoted $v_i\mathrm{\perp }{v}_j$;
• all $v_i$ have unit length, i.e., $\parallel v_i{\parallel }_2=1$.

Since the eigenvectors $v_1,v_2,\dots ,v_n$ are orthonormal, we can use them as orthogonal basis, so that any vector $x\in {\mathbb{R}}^n$ can be expressed as $x=\sum _{i=1}^n{c}_i{v}_i$ where $c_i=q^T{v}_i$, therefore

$xS=\sum _{i=1}^n{c}_i{v}_{i}S=\sum _{i=1}^n{c}_i{\lambda }_i{v}_i.$

So multiplying by $S$ corresponds to multiplying the length of $x$ along the direction of every eigenvector by a factor of the corresponding eigenvalue.

---

Back to the symmetric Markov chain. Let $\mathrm{\Omega }$ be a finite state space of size $N$, and $P$ be a symmetric transition matrix, whose eigenvalues are ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_N$. The followings hold for a symmetric transition matrix $P$:

• Due to the spectral theorem, there exist orthonormal eigenvectors $v_1,v_2,\dots ,v_N$ such that $v_{i}P={\lambda }_i{v}_i$ for $i=1,2,\dots ,N$ and any distribution $q$ over $\mathrm{\Omega }$ can be expressed as $q=\sum _{i=1}^N{c}_i{v}_i$ where $c_i=q^T{v}_i$.
• A symmetric $P$ must be double stochastic, thus the stationary distribution $\pi$ is the uniform distribution.

Recall that due to Perron-Frobenius theorem, ${\lambda }_1=1$. And $\mathbf{1}P=\mathbf{1}$ since $P$ is double stochastic, thus $v_1=\frac{\mathbf{1}}{\parallel \mathbf{1}{\parallel }_2}=(\frac{1}{\sqrt{N}},\dots ,\frac{1}{\sqrt{N}})$.

When $q$ is a distribution, i.e., $q$ is a nonnegative vector and $\parallel q{\parallel }_1=1$, it holds that $c_1=q^T{v}_1=\frac{1}{\sqrt{N}}$ and $c_1{v}_1=(\frac{1}{N},\dots ,\frac{1}{N})=\pi$, thus

$q=\sum _{i=1}^N{c}_i{v}_i=\pi +\sum _{i=2}^N{c}_i{v}_i,$

and the distribution at time $t$ when the initial distribution is $q$, is given by

$q{P}^t=\pi P^t+\sum _{i=2}^N{c}_i{v}_i{P}^t=\pi +\sum _{i=2}^N{c}_i{\lambda }_i^t{v}_i.$

It is easy to see that this distribution converges to $\pi$ when the absolute values of ${\lambda }_2,\dots ,{\lambda }_N$ are all less than 1. And the rate at which it converges to $\pi$, namely the mixing rate, is determined by the quantity ${\lambda }_{max}=max\{|{\lambda }_2|,|{\lambda }_N|\}$, which is the largest absolute eigenvalues other than ${\lambda }_1$.

Theorem

Let $P$ be the transition matrix for a symmetric Markov chain on state space $\mathrm{\Omega }$ where $|\mathrm{\Omega }|=N$. Let ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_N$ be the spectrum of $P$ and ${\lambda }_{max}=max\{|{\lambda }_2|,|{\lambda }_N|\}$. The mixing rate of the Markov chain is $\tau (ϵ)\le \frac{\frac{1}{2}\ln N+\ln \frac{1}{2ϵ}}{1-{\lambda }_{\text{max}}}$.

Proof. As analysed above, if $P$ is symmetric, it has orthonormal eigenvectors $v_1,\dots ,v_N$ such that any distribution $q$ over $\mathrm{\Omega }$ can be expressed as $q=\sum _{i=1}^N{c}_i{v}_i=\pi +\sum _{i=2}^N{c}_i{v}_i$ with $c_i=q^T{v}_i$, and $q{P}^t=\pi +\sum _{i=2}^N{c}_i{\lambda }_i^t{v}_i.$ Thus, $\begin{array}{rl}\parallel q{P}^t-\pi {\parallel }_1& ={\parallel \sum _{i=2}^N{c}_i{\lambda }_i^t{v}_i\parallel }_1\\ & \le \sqrt{N}{\parallel \sum _{i=2}^N{c}_i{\lambda }_i^t{v}_i\parallel }_2& \text{(Cauchy-Schwarz)}\\ & =\sqrt{N}\sqrt{\sum _{i=2}^N{c}_i^2{\lambda }_i^{2t}}\\ & \le \sqrt{N}{\lambda }_{max}^t\sqrt{\sum _{i=2}^N{c}_i^2}\\ & =\sqrt{N}{\lambda }_{max}^t\parallel q{\parallel }_2\\ & \le \sqrt{N}{\lambda }_{max}^t.\end{array}$ The last inequality is due to a universal relation $\parallel q{\parallel }_2\le \parallel q{\parallel }_1$ and the fact that $q$ is a distribution. Then for any $x\in \mathrm{\Omega }$, denoted by ${\mathbf{1}}_x$ the indicator vector for $x$ such that ${\mathbf{1}}_x(x)=1$ and ${\mathbf{1}}_x(y)=0$ for $y\ne x$, we have $\begin{array}{rl}{\mathrm{\Delta }}_x(t)& ={\parallel {\mathbf{1}}_x{P}^t-\pi \parallel }_{TV}=\frac{1}{2}{\parallel {\mathbf{1}}_x{P}^t-\pi \parallel }_1\\ & \le \frac{\sqrt{N}}{2}{\lambda }_{max}^t\le \frac{\sqrt{N}}{2}{\mathrm{e}}^{-t(1-{\lambda }_{max})}.\end{array}$ Therefore, we have ${\tau }_x(ϵ)=min\{t\mid {\mathrm{\Delta }}_x(t)\le ϵ\}\le \frac{\frac{1}{2}\ln N+\ln \frac{1}{2ϵ}}{1-{\lambda }_{max}}$ for any $x\in \mathrm{\Omega }$, thus the bound holds for $\tau (ϵ)=\underset{x}{max}{\tau }_x(ϵ)$. $◻$

Rapid mixing of expander walk

Let $G(V,E)$ be a $d$-regular graph on $n$ vertices. Let $A$ be its adjacency matrix. The transition matrix of the lazy random walk on $G$ is given by $P=\frac{1}{2}(I+\frac{1}{d}A)$. Specifically,

$P(u,v)=\{\begin{array}{ll}\frac{1}{2}& \text{if }u=v,\\ \frac{1}{2d}& \text{if }uv\in E,\\ 0& \text{otherwise.}\end{array}$

Obviously $P$ is symmetric.

Let ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ be the eigenvalues of $A$, and ${\nu }_1\ge {\nu }_2\ge \cdots \ge {\nu }_n$ be the eigenvalues of $P$. It is easy to verify that

${\nu }_i=\frac{1}{2}(1+\frac{{\lambda }_i}{d})$.

We know that $-d\le {\lambda }_i\le d$, thus $0\le {\nu }_i\le 1$. Therefore, ${\nu }_{max}=max\{|{\nu }_2|,|{\nu }_n|\}={\nu }_2$. Due to the above analysis of symmetric Markov chain,

$\tau (ϵ)\le \frac{\frac{1}{2}(\ln n+\ln \frac{1}{2ϵ})}{1-{\nu }_{max}}=\frac{\frac{1}{2}(\ln n+\ln \frac{1}{2ϵ})}{1-{\nu }_2}=\frac{d(\ln n+\ln \frac{1}{2ϵ})}{d-{\lambda }_2}$.

Thus we prove the following theorem for lazy random walk on $d$-regular graphs.

Theorem

Let $G(V,E)$ be a $d$-regular graph on $n$ vertices, with spectrum ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. The mixing rate of lazy random walk on $G$ is $\tau (ϵ)\le \frac{d(\ln n+\ln \frac{1}{2ϵ})}{d-{\lambda }_2}$.

Due to Cheeger's inequality, the spectral gap is bounded by expansion ratio as

$d-{\lambda }_2\ge \frac{{\varphi }^2}{2d},$

where $\varphi =\varphi (G)$ is the expansion ratio of the graph $G$. Therefore, we have the following corollary which bounds the mixing time by graph expansion.

Corollary

Let $G(V,E)$ be a $d$-regular graph on $n$ vertices, whose expansion ratio is $\varphi =\varphi (G)$. The mixing rate of lazy random walk on $G$ is $\tau (ϵ)\le \frac{2d^2(\ln n+\ln \frac{1}{2ϵ})}{{\varphi }^2}$. In particular, the mixing time is ${\tau }_{\text{mix}}=\tau (1/2\mathrm{e})\le \frac{2d^2(\ln n+2)}{{\varphi }^2}$.

For expander graphs, both $d$ and $\varphi$ are constants. The mixing time of lazy random walk is ${\tau }_{\text{mix}}=O(\ln n)$ so the random walk is rapidly mixing.