Eigenvalues & Expansion (Cheeger’s Inequality)

Eigenvalue gaps allow us to upper bound the rate of convergence of random walks on graphs.

In this note, we will look at the connection between the eigenvalue gap and a combinatorial graph parameter, called “expansion”"

Let \(G\) be a \(d\)-regular graph with \(n\) vertices. We identify \(G\) with its random-walk matrix (normalized adjacency matrix).

Definition: The eigenvalue gap of \(G\) is defined as \[ \gamma(G)=\min_{f\bot u} \frac{\langle f,L_G f\rangle }{\|f\|_2^2}, \] where \(L_G=I-G\) is the Laplacian of \(G\).

Exercise: Check that \(\gamma(G)=\lambda_1(G)-\lambda_2(G)\) is indeed the gap between the largest and second largest eigenvalue of \(G\).

We would like to characterize the eigenvalue gap of a graph in terms of a combinatorial property. The right combinatorial property turns out to be expansion, which measures how well \(G\) is connected.

Definition: The expansion of \(G\) is defined as \[ \phi(G) = \min_{S\subseteq V,~|S|\le n/2} \frac{\tfrac1d |E(S,\bar S)|}{|S|}. \] (Here, \(E(S,\bar S)\) is the set of edges from \(S\) to \(\bar S\).) The quantity \(\phi(S)=\tfrac1d|E(S,\bar S)|/|S|\) is the expansion of \(S\).

Exercise: Check that \[ {\langle f,L_G f\rangle} = \sum_i \mathbf E_{j\sim i}\tfrac12(f_i-f_j)^2. \] (So the Laplacian exactly measures how close the values of \(f\) are for a typical edge of the graph.)

It follows that \({\langle 1_S,L_G 1_S\rangle}=\tfrac1d |E(S,\bar S)|\) and therefore \[\phi(G) = \min_{S\subseteq V,~|S|\le n/2} {\langle 1_S,L_G 1_S\rangle}/{\|1_S\|_2^2}.\]

Cheeger’s inequality asserts that \(\gamma(G)\) is the same as \(\phi(G)\) up to quadratic factor.

Theorem: (Cheeger’s inequality) \[ \gamma(G)/2 \le \phi(G) \le 2\sqrt{\gamma(G)}. \]

The following direction is the easier one.

Lemma: \(\phi(G)\ge \gamma(G)/2\)

Proof: Let \(S\) be a subset of vertices with \(|S|\le n/2\). We like to lower bound its expansion. Let \(p=1_S/|S|\) be the uniform distribution over \(S\). Then \(p=u+f\), where \(u\) is the uniform distribution and \(f\) is orthogonal to \(u\). Then, \[ \phi(S) = \frac{\langle p,L_G p\rangle}{\|p\|_2^2} =\frac{\langle f,L_G f\rangle}{\|u\|_2^2+\|f\|_2^2} \ge \frac{\gamma\|f\|_2^2}{\|u\|_2^2+\|f\|_2^2}. \]

To finish the proof, it is enough to show that \(\|f\|_2^2 \ge \|u\|_2^2\). (This means that the distribution \(p\) is “far” from \(u\).) Recall that \(f=1_S/|S|-u\). It’s that the distance of \(1_S/|S|\) and \(u\) decreases as the size of \(S\) grows. Hence, the distance is smallest if \(|S|=n/2\). In this case, \(f\) takes values \(\pm 1/n\). Hence, \(\|f\|_2^2=n\cdot 1/n^2=1/n=\|u\|_2^2\).

Next, we will prove the other direction of Cheeger’s inequality.

The first step is the following lemma (which we have seen in class).

Lemma: Suppose \(h\) is a function with \(|\mathrm{supp}(h)|\le n/2\) and \(\langle h,L_G h\rangle\le \epsilon\|h\|_2^2\). Then there exists a set \(S\) with \(|S|\le n/2\) and \(\phi(S)\le \sqrt{2\epsilon}\).

Proof: W.l.o.g. we may assume \(0\le h\le 1\). The main idea is to construct a distribution over sets \(S\) by choosing a random threshold \(\tau\in[0,1]\) and setting \(S=\{i \mid h_i^2>\tau\}\). It is easy to verify that \(\mathbf E_S |S|=\|h\|_2^2\). Using Cauchy-Schwarz, one can also show \(\mathbf E_S \tfrac1d|E(S,\bar S)|\le \sqrt{2\epsilon}\|h\|_2^2\). Hence, there exists a set in the support of the distribution with expansion at most \(\sqrt{2\epsilon}\).

The next step is to construct such a function \(h\).

Lemma: There exists a function \(h\) with \(|\mathrm{supp}(h)|\le n/2\) and \(\langle h,L_G h\rangle\le 2\gamma(G)\|h\|_2^2\).

Proof: Let \(f\) be a function such that \(f\bot u\) and \(\langle f,L_G f\rangle \le \gamma(G)\|f\|_2^2\). Let \(m\) be the median of this function. (So that \(f\) has value larger than \(m\) for exactly half of the vertices.) Let \(h_1=(f-m)_+\) be the positive part of \(f-m\) and let \(h_2=(f-m)_{-}\) be the negative part of \(f-m\). Notice that both \(h_1\) and \(h_2\) have exactly half of the vertices in their support. We claim that one of the functions \(h_1,h_2\) satisfies also the other condition of the lemma.

Indeed, we can see that \(\langle h_1,L_G h_1\rangle \le \langle f,L_G f\rangle\) and \(\langle h_2,L_G h_2\rangle\le \langle f,L_G f\rangle\). On the other hand, \(\|f\|_2^2=\|h_1\|_2^2+\|h_2\|^2\). Hence, we can choose \(h\) to be the function \(h_1\) or \(h_2\) with larger norm.