The Second Largest Eigenvalue

Or, why the most interesting number in a spectrum is almost never the first one.

During my time at Microsoft Research India in 2021 and 2022, I worked on graph neural networks, and somewhere between debugging message passing layers and reading spectral graph theory papers, I kept running into the same quantity: the second largest eigenvalue of a graph operator. At first it seemed like a technical curiosity, but the more I looked, the more I realized that the gap between the first and second eigenvalue, the spectral gap, quietly controls the behavior of an astonishing number of systems. Random walks mix because of it, clusters exist because of it, quantum phases of matter are classified by it, and even the depth-related pathologies of GNNs trace back to it. This post is my attempt to collect those threads in one place, with the actual mathematics rather than just the slogans.

1. Setting up notation

Let $G = (V, E)$ be an undirected graph on $n = |V|$ vertices. I will write $A \in \mathbb{R}^{n \times n}$ for its adjacency matrix, $D = \mathrm{diag}(d_1, \dots, d_n)$ for the diagonal degree matrix, and define two Laplacians: $$L = D - A, \qquad \mathcal{L} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}.$$

All of these matrices are real and symmetric, so by the spectral theorem they have real eigenvalues and an orthonormal basis of eigenvectors. I will order eigenvalues of $A$ as $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$ and eigenvalues of $L$ (or $\mathcal{L}$) as $0 = \mu_1 \le \mu_2 \le \dots \le \mu_n$. For a $d$-regular graphA graph is $d$-regular if every vertex has exactly $d$ neighbors, so every row of $A$ sums to $d$ and $D = dI$. The cycle is $2$-regular and the complete graph $K_n$ is $(n-1)$-regular. Regularity is what lets us pass freely between the adjacency and Laplacian pictures, since the two matrices then differ only by a shift and a sign flip. these viewpoints coincide, since $L = dI - A$ implies $\mu_k = d - \lambda_k$.

The single most useful identity in this whole subject is the quadratic form of the Laplacian.The expansion is a small but instructive computation. Writing out $x^\top L x = x^\top D x - x^\top A x = \sum_i d_i x_i^2 - 2\sum_{(i,j) \in E} x_i x_j$, note that the degree $d_i$ counts the edges incident to vertex $i$, so the first sum distributes exactly one copy of $x_i^2$ to each edge touching $i$. Grouping by edges, each edge $(i,j)$ collects $x_i^2 + x_j^2 - 2x_i x_j = (x_i - x_j)^2$. The Laplacian quadratic form is therefore a sum of squared disagreements across edges, which is why it measures the smoothness of $x$ over the graph. For any $x \in \mathbb{R}^n$, $$x^\top L x = \sum_{(i,j) \in E} (x_i - x_j)^2.$$

This is nonnegative, which shows $L \succeq 0$, and it vanishes exactly when $x$ is constant on each connected component. The all-ones vector $\mathbf{1}$ is always in the kernel, so $\mu_1 = 0$ always. The first eigenvalue is therefore boring by construction. Everything interesting starts at $\mu_2$.

Proposition (connectivity). $\mu_2 > 0$ if and only if $G$ is connected.

Fiedler called $\mu_2$ the algebraic connectivity for this reason, and the associated eigenvector is called the Fiedler vector.The Fiedler vector is any eigenvector attaining $\mu_2$. It assigns a signed real number to every vertex, and because it must be orthogonal to the constant vector, some vertices receive positive values and others negative ones. The sign pattern tends to split the graph along its weakest seam, which is precisely why thresholding this vector is a sensible partitioning algorithm. The proposition already hints at the theme of this post: $\mu_2 = 0$ means the graph is disconnected, so by continuity, $\mu_2$ small should mean the graph is nearly disconnected. Making that intuition quantitative is the content of Cheeger's inequality.

One more tool I will use repeatedly is the variational characterization of eigenvalues.The Courant–Fischer theorem characterizes every eigenvalue of a symmetric matrix as an optimum of the Rayleigh quotient $x^\top L x / x^\top x$ over nested subspaces. The smallest eigenvalue is the unconstrained minimum, and the $k$-th smallest is the minimum after forcing $x$ to be orthogonal to the first $k-1$ eigenvectors. The practical payoff is one-sided: plugging in any feasible test vector immediately yields an upper bound, with no need to solve the eigenproblem. By the Courant–Fischer theorem, $$\mu_2 = \min_{x \perp \mathbf{1},\; x \ne 0} \frac{x^\top L x}{x^\top x}.$$ This turns eigenvalue bounds into an optimization game: any test vector orthogonal to $\mathbf{1}$ gives an upper bound on $\mu_2$.

2. Graph theory: Cheeger's inequality and expanders

Define the conductance of a vertex set $S \subseteq V$ with volume $\mathrm{vol}(S) = \sum_{i \in S} d_i$ as $$\phi(S) = \frac{|E(S, \bar S)|}{\min(\mathrm{vol}(S), \mathrm{vol}(\bar S))}, \qquad \phi(G) = \min_{\emptyset \ne S \subsetneq V} \phi(S),$$ where $E(S, \bar S)$ is the set of edges crossing the cut. Small $\phi(G)$ means the graph has a sparse bottleneck.One line of intuition for conductance: $\phi(S)$ is essentially the probability that a random walk currently at a random vertex of $S$ (chosen proportionally to degree) leaves $S$ in the next step. A set with small conductance is a room with narrow doors, easy to wander around in and hard to exit. The Cheeger inequalityThe intuition behind Cheeger's inequality is that the eigenvalue problem for $\mu_2$ is a continuous relaxation of the discrete sparsest cut problem. The upper bound says the relaxation can only do better than any actual cut, which is what the test vector proof makes literal. The hard direction says the relaxation does not cheat too much: an eigenvector with small Rayleigh quotient can be rounded into a genuine cut whose conductance is at most $\sqrt{2\mu_2}$, and the square root is the price paid for passing from the continuous object back to a discrete one. relates this combinatorial quantity to the second eigenvalue $\mu_2$ of the normalized Laplacian $\mathcal{L}$: $$\frac{\phi(G)^2}{2} \le \mu_2 \le 2\,\phi(G).$$

The easy direction is the upper bound, and the proof is a nice illustration of the test vector trick, so let me do it for the $d$-regular case, where $\mathrm{vol}(S) = d|S|$ and $\mu_2 = \frac{1}{d}\min_{x \perp \mathbf{1}} \frac{x^\top L x}{x^\top x}$.

Claim. For $d$-regular $G$, $\mu_2 \le 2\phi(G)$.

The hard direction, $\phi(G) \le \sqrt{2\mu_2}$, is proved by taking the actual second eigenvector, sorting vertices by their coordinate values, and showing that one of the resulting sweep cuts must be good. I will not reproduce it here, but it is worth knowing that the proof is constructive: it is exactly the spectral partitioning algorithm used in practice.

Graphs where $\mu_2$ is bounded away from zero are called expanders, and they are in a precise sense the best-connected sparse graphs possible. There is a limit to how large the gap can be: the Alon–Boppana theorem says that for any $d$-regular graph, $\lambda_2 \ge 2\sqrt{d-1} - o(1)$ as $n \to \infty$. Graphs achieving $\lambda_2 \le 2\sqrt{d-1}$ are called Ramanujan graphs, and their explicit construction by Lubotzky, Phillips, and Sarnak is one of the great applications of number theory to combinatorics.

Why do we care how large the gap is? One answer is the expander mixing lemma: for a $d$-regular graph with $\lambda = \max(|\lambda_2|, |\lambda_n|)$, and any $S, T \subseteq V$, $$\left| \, |E(S,T)| - \frac{d\,|S||T|}{n} \right| \le \lambda \sqrt{|S||T|}.$$ The term $d|S||T|/n$ is what a random graph would give, so a small second eigenvalue certifies that the graph behaves pseudorandomly. This is the engine behind derandomization results and expander codes in theoretical computer science.

3. Markov chains: the second eigenvalue as a clock

Now for the appearance of $\lambda_2$ that I find most fundamental. Let $P$ be the transition matrix of an irreducible, aperiodic, reversible Markov chain on $n$ states with stationary distribution $\pi$, meaning $\pi(i) P(i,j) = \pi(j) P(j,i)$.The condition $\pi(i)P(i,j) = \pi(j)P(j,i)$ is called detailed balance. It says that at stationarity, the probability flow from $i$ to $j$ exactly equals the flow from $j$ to $i$, so a film of the stationary chain looks statistically identical when played backwards. Its algebraic consequence is what we exploit: $P$ becomes self-adjoint in the $\pi$-weighted inner product, guaranteeing a real spectrum and an orthonormal eigenbasis. Metropolis–Hastings chains are reversible by construction. Reversibility makes $P$ self-adjoint with respect to the inner product $\langle f, g \rangle_\pi = \sum_i \pi(i) f(i) g(i)$, so its eigenvalues are real and satisfy $$1 = \lambda_1 > \lambda_2 \ge \dots \ge \lambda_n > -1.$$

The lazy random walk on a graph, $P = \frac{1}{2}(I + D^{-1}A)$, is the canonical example, and its eigenvalues relate to the normalized Laplacian by $\lambda_k = 1 - \mu_k / 2$.

Define $\lambda_\star = \max(|\lambda_2|, |\lambda_n|)$, the second largest eigenvalue in absolute value. The claim is that $1 - \lambda_\star$, the absolute spectral gap, sets the relaxation clock of the chain.

Theorem (spectral bound on mixing). For a reversible chain as above, started at state $x$, $$\left\| P^t(x, \cdot) - \pi \right\|_{TV} \le \frac{1}{2} \sqrt{\frac{1 - \pi(x)}{\pi(x)}} \; \lambda_\star^t.$$

The consequence is that the mixing time satisfies $$t_{\mathrm{mix}}(\varepsilon) \le \frac{1}{1 - \lambda_\star} \log\!\left(\frac{1}{\varepsilon \sqrt{\pi_{\min}}}\right),$$ and a matching lower bound $t_{\mathrm{mix}}(\varepsilon) \ge \left(\frac{1}{1-\lambda_\star} - 1\right) \log \frac{1}{2\varepsilon}$ also holds. So up to a logarithm, the mixing time is the inverse spectral gap. Every time you run MCMC, whether it is Gibbs sampling in a graphical model, Metropolis–Hastings in Bayesian inference, or a diffusion sampler, the honest answer to the question "how long do I need to run this" is "one over your spectral gap, roughly." When the underlying state space has a bottleneck, Cheeger's inequality tells us the gap is small, and the chain gets stuck. Slow mixing and near-disconnectedness are two descriptions of the same eigenvalue.

The same quantity governs the humble power method. If $M$ is symmetric with $\lambda_1 > |\lambda_2|$ and top eigenvector $v_1$, and we iterate $x_{t+1} = M x_t / \|M x_t\|$ from any $x_0$ with $\langle x_0, v_1 \rangle \ne 0$, then writing $x_0 = \sum_k c_k v_k$ in the eigenbasis gives $$M^t x_0 = \lambda_1^t \left( c_1 v_1 + \sum_{k \ge 2} c_k \left(\frac{\lambda_k}{\lambda_1}\right)^{\!t} v_k \right),$$ so the error decays geometrically at rate $|\lambda_2| / \lambda_1$. PageRank is exactly this iteration on the Google matrix, and the damping factor $\alpha = 0.85$ is there precisely to guarantee $|\lambda_2| \le \alpha$, giving a convergence rate that is uniform over the entire web graph. The second eigenvalue is, quite literally, the reason your search results load.

4. Machine learning: clustering, embeddings, and GNNs

Spectral clustering is the algorithmic converse of everything above. Suppose we want to partition a similarity graph into two balanced clusters by minimizing the ratio cut $\frac{|E(S,\bar S)|}{|S|} + \frac{|E(S,\bar S)|}{|\bar S|}$. Encoding a partition by the same two-valued vector I used in the Cheeger proof, one can check that this objective equals $x^\top L x$ up to normalization, while the constraints become $x \perp \mathbf{1}$ and fixed $\|x\|$. The combinatorial constraint that $x$ takes only two values is what makes the problem NP-hard, so we relax it and solve $$\min_{x \perp \mathbf{1},\; \|x\| = 1} x^\top L x,$$ whose solution, by Courant–Fischer, is exactly the Fiedler vector with optimal value $\mu_2$. In practice we take the first $k$ nontrivial eigenvectorsThe trivial eigenvector is the one attached to the eigenvalue $0$, namely the constant vector $\mathbf{1}$ for $L$, or $D^{1/2}\mathbf{1}$ for $\mathcal{L}$. It is the same for every connected graph and carries no structural information, so spectral embeddings discard it. The nontrivial eigenvectors are the remaining ones, and the heuristic from the connectivity proposition explains their role: a graph with $k$ good clusters is a perturbation of a graph with $k$ components, which would have $k$ eigenvalues equal to zero, so the perturbed graph has $k$ small eigenvalues whose eigenvectors approximately encode cluster membership., embed each vertex as a row of the resulting $n \times k$ matrix, and run $k$-means. The reason this works is that when the graph has $k$ well-separated clusters, the bottom of the Laplacian spectrum has $k$ small eigenvalues followed by a gap, and the eigenvectors are approximately indicators of the clusters, a statement made precise by the Davis–Kahan perturbation theorem. The size of the eigengap $\mu_{k+1} - \mu_k$ is what you check to choose the number of clusters, and it also controls the stability of the recovered embedding.

The same spectral gap showed up constantly in my GNN work, usually as a villain. Two well-known pathologies of deep message passing networks are oversmoothing and oversquashing, and both are spectral gap statements. For oversmoothing, note that each propagation step multiplies features by an operator like $\tilde{A} = \tilde{D}^{-1/2}(A + I)\tilde{D}^{-1/2}$, whose spectrum lies in $(-1, 1]$ with top eigenvalue $1$. After $\ell$ layers the component of the features along any non-top eigenvector shrinks by a factor $|\lambda_2(\tilde{A})|^\ell$, so representations collapse toward the top eigenspace, which encodes only degree information, at a geometric rate set by the second eigenvalue. Ironically, a large spectral gap makes oversmoothing faster. Oversquashing runs the other way: on graphs with small spectral gap, information between distant vertices must pass through bottlenecks, commute times scale like $1/\mu_2$, and gradients between the relevant nodes get exponentially compressed. Recent graph rewiring methods explicitly add edges to increase $\mu_2$, effectively performing surgery on the second eigenvalue to help the network communicate. The design tension of GNN depth is, in large part, a negotiation between these two faces of the same number.

5. Physics: the gap as a phase diagram

In quantum mechanics the object of study is a Hamiltonian $H$, a self-adjoint operator whose eigenvalues $E_0 \le E_1 \le \dots$ are the allowed energies of the system. The lowest eigenvalue $E_0$ is the ground state energy, and the quantity everyone cares about is the spectral gap $$\Delta = E_1 - E_0,$$ the distance to the second eigenvalue. A family of Hamiltonians $H_n$ on systems of growing size is called gapped if $\Delta_n \ge c > 0$ uniformly in $n$, and gapless otherwise. This distinction is essentially the definition of a quantum phase: gapped phases have exponentially decaying correlations and stable ground states, while a closing gap signals a quantum phase transition, with the critical point exhibiting scale-invariant, power-law correlations. The reason my tensor network detour keeps meeting this material is exactly here, since MERA-type ansätze are built to capture the critical, gapless case where correlations decay polynomially.

The gap is also a computational resource. The quantum adiabatic theorem says that if you evolve a system slowly under a time-dependent Hamiltonian $H(s)$ that ends at a problem Hamiltonian whose ground state encodes your answer, the evolution time needed to stay in the ground state scales like $$T = O\!\left( \max_s \frac{1}{\Delta(s)^2} \right)$$ up to factors involving $\|\dot H\|$. Adiabatic quantum computing and quantum annealing succeed or fail based on how small the gap gets along the interpolation path, which is a perfect physical analogue of the MCMC story: in both cases the second eigenvalue is the clock, and bottlenecks in the landscape close the gap.

There is a final result that I find genuinely startling. Cubitt, Perez-Garcia, and Wolf proved in 2015 that the spectral gap problem is undecidable: there is no algorithm that, given a translationally invariant local Hamiltonian on a lattice, decides whether the thermodynamic limit is gapped or gapless. The distance between the first and second eigenvalue is not merely hard to compute; for general quantum systems it is beyond the reach of computation entirely.

6. Closing thoughts

Let me try to say what I think the unifying principle is. The top eigenvalue and its eigenvector describe the equilibrium of a system: the stationary distribution of a walk, the constant function on a graph, the ground state of a Hamiltonian. The second eigenvalue measures how strongly the system commits to that equilibrium. When the gap is large, deviations die geometrically fast, walks mix, expanders expand, adiabatic algorithms run quickly, and GNN features smooth out. When the gap is small, structure survives: clusters persist, chains remember their starting point, phases become critical, and correlations reach across the whole system. Whether that structure is a feature you are mining, as in spectral clustering, or an obstacle you are fighting, as in MCMC, the mathematics is identical.

So my advice, learned somewhere between a GNN training run and a spectral graph theory textbook, is simple. When you meet a new system described by a self-adjoint operator, do not stop at the first eigenvalue. The first eigenvalue tells you where the system is going. The second one tells you everything about how it gets there.

References and further reading

1. F. Chung, Spectral Graph Theory, AMS, 1997.
2. D. Levin, Y. Peres, E. Wilmer, Markov Chains and Mixing Times, AMS, 2017.
3. S. Hoory, N. Linial, A. Wigderson, "Expander graphs and their applications," Bulletin of the AMS, 2006.
4. U. von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, 2007.
5. T. Cubitt, D. Perez-Garcia, M. Wolf, "Undecidability of the spectral gap," Nature, 2015.
6. J. Topping et al., "Understanding over-squashing and bottlenecks on graphs via curvature," ICLR, 2022.