Intuition behind eigenvalues of an adjacency matrix

Question

I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a start of an intuition regarding the second eigenvalue of the adjacency matrix.
Usually, in graph theory, most of the concepts we come across of are quite simple to intuit, but in this case, I can't even come up with what kind of graphs would have a second eigenvalue being very low, or very high.
I've been reading similar questions asked here and there on the SE network, but they usually refer to eigenvalues in different fields (multivariate analysis, Euclidian distance matrices, correlation matrices ...).
But nothing about spectral partitioning and graph theory.

Can someone try and share his intuition/experience of this second eigenvalue in the case of graphs and adjacency matrices?

Answer 1

The second (in magnitude) eigenvalue controls the rate of convergence of the random walk on the graph. This is explained in many lecture notes, for example lecture notes of Luca Trevisan. Roughly speaking, the L2 distance to uniformity after $t$ steps can be bounded by $\lambda_2^t$.

Another place where the second eigenvalue shows up is the planted clique problem. The starting point is the observation that a random $G(n,1/2)$ graph contains a clique of size $2\log_2 n$, but the greedy algorithm only finds a clique of size $\log_2 n$, and no better efficient algorithm is known. (The greedy algorithm just picks a random node, throws away all non-neighbors, and repeats.)

This suggests planting a large clique on top of $G(n,1/2)$. The question is: how big should the clique be, so that we can find it efficiently. If we plant a clique of size $C\sqrt{n\log n}$, then we could identify the vertices of the clique just by their degree; but this method only works for cliques of size $\Omega(\sqrt{n\log n})$. We can improve this using spectral techniques: if we plant a clique of size $C\sqrt{n}$, then the second eigenvector encodes the clique, as Alon, Krivelevich and Sudakov showed in a classic paper, Finding a Large Hidden Clique in a Random Graph.

More generally, the first few eigenvectors are useful for partitioning the graph into a small number of clusters. See for example Chapter 3 of lecture notes of Luca Trevisan, which describes higher-order Cheeger inequalities.

Answer 2

(Disclaimer: This answer is about eigenvalues of graphs in general, not the second eigenvalue in particular. I hope it is helpful nevertheless.)

An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e., a vertex labeling). An eigenvector of the adjacency matrix, then, is an element of $f \in \mathbb{R}^n$ such that there is $\lambda \in \mathbb{R}$ (i.e., an eigenvalue) with $A f = \lambda f$, $A$ being the adjacency matrix of $G$. Note that $A f$ is the vector associated with the map which sends every vertex $v \in V$ to $\sum_{u \in N(v)} f(u)$, $N(v)$ being the set of neighbors (i.e., vertices adjacent to) $u$. Hence, in this setting, the eigenvector property of $f$ corresponds to the property that summing over the function values (under $f$) of the neighbors of a vertex yields the same result as multiplying the function value of the vertex with the constant $\lambda$.

Answer 3

I think for most things it's more productive to look at the Laplacian of the graph $G$, which is closely related to the adjacency matrix. Here you can use it to relate the second eigenvalue to a "local vs global" property of the graph.

For simplicity, let's suppose that $G$ is $d$-regular. Then the normalized Laplacian of $G$ is $L= I - \frac1d A$, where $I$ is the $n\times n$ identity, and $A$ is the adjacency matrix. The nice thing about the Laplacian is that, writing vectors as functions $f: V\to \mathbb{R}$ like @dkaeae, and using $\langle \cdot, \cdot \rangle$ for the usual inner product, we have this very nice expression for the quadratic form given by $L$: $$ \langle f, Lf\rangle = \frac{1}{d} \sum_{(u,v) \in E}{(f(u) - f(v))^2}. $$

The largest eigenvalue of $A$ is $d$, and corresponds to the smallest eigenvalue of $L$, which is $0$; the second largest eigenvalue $\lambda_2$ of $A$ corresponds to the second smallest eigenvalue of $L$, which is $1 - \frac{\lambda_2}{d}$. By the min-max principle, we have

$$ 1 - \frac{\lambda_2}{d}=\min\left\{\frac{\langle f, Lf\rangle}{\langle f, f\rangle}:\sum_{v \in V}{f(v)} = 0, f \neq 0\right\}. $$

Notice that $\langle f, Lf\rangle$ does not change when we shift $f$ by the same constant for every vertex. So, equivalently, you can define, for any $f:V \to \mathbb{R}$, the "centered" function $f_0$ by $f_0(u) = f(u) - \frac{1}{n}\sum_{v \in V}{f(v)}$, and write

$$ 1 - \frac{\lambda_2}{d}=\min\left\{\frac{\langle f, Lf\rangle}{\langle f_0, f_0\rangle}: f \text{ not constant}\right\}. $$

Now a bit of calculation shows that $\langle f_0, f_0\rangle = \frac{1}{n}\sum_{\{u,v\}\in {V\choose 2}}{(f(u) - f(v))^2}$, and substituting above and dividing numerator and denominator by $\frac{n}{2}$, we have

$$ 1 - \frac{\lambda_2}{d}=\min\left\{\frac{\frac{2}{nd} \sum_{(u,v) \in E}{(f(u) - f(v))^2}}{\frac{2}{n^2}\sum_{\{u,v\}\in {V\choose 2}}{(f(u) - f(v))^2}}: f \text{ not constant}\right\}. $$

What this means is that, if we place every vertex $u$ of $G$ on the real line at the point $f(u)$, then the average distance between two independent random vertices in the graph (the denominator) is at most $\frac{d}{d - \lambda_2}$ times the average distance between the endpoints of a random edge in the graph (the numerator). So in this sense, a large spectral gap means that what happens across a random edge of $G$ (local behavior) is a good predictor for what happens across a random uncorrelated pair of vertices (global behavior).