The Lower Cheeger Bound by Level Sets

From Conductance to a Spectral Gap

Conductance measures how much stationary flow leaves a set relative to the stationary mass of that set. The lower Cheeger bound says that if every sufficiently small set has substantial outward flow, then functions cannot change slowly across the graph: the spectral gap must be positive. The proof converts a function into many level sets, applies conductance to each one, and then bounds the resulting edge sum by its Dirichlet energy.

Let \(G=(V,E)\) be a finite simple graph with \(n=|V|\ge 2\), \(m=|E|\), and no isolated vertices. The graph need not be connected. Consider its lazy random walk with transition probabilities \(P(x,x)=1/2\) and \(P(x,y)=1/(2\deg(x))\) when \(xy\in E\); all other transition probabilities are zero. Its stationary distribution is \(\pi(x)=\deg(x)/(2m)\). For a set \(S\subseteq V\), write \(\pi(S)=\sum_{x\in S}\pi(x)\), and let \(Q(S,\overline S)=\sum_{x\in S,\,y\notin S}\pi(x)P(x,y)\) be the stationary flow from \(S\) to its complement.

For each undirected edge \(xy\), the stationary flow in either direction is \(\pi(x)P(x,y)=1/(4m)\). Consequently, \(Q(S,\overline S)=|\partial S|/(4m)\), where \(\partial S\) is the set of edges with one endpoint in \(S\) and one outside. Since \(\pi(S)=\sum_{x\in S}\deg(x)/(2m)\), the conductance ratio can also be written as \(|\partial S|/(2\sum_{x\in S}\deg(x))\). The factor \(2\) in this denominator is a consequence of laziness.

The matrix \(P\) is reversible with respect to \(\pi\). Its eigenvalues are real; moreover \(P=(I+R)/2\), where \(R\) is the transition matrix of the non-lazy walk. The eigenvalues of \(R\) lie in \([-1,1]\), so those of \(P\) lie in \([0,1]\). By the Rayleigh quotient characterization for a reversible transition matrix, \(\gamma\) is the minimum of \(\mathcal E(f,f)/\operatorname{Var}_{\pi}(f)\) over nonconstant \(f\), where \(\operatorname{Var}_{\pi}(f)=\sum_x\pi(x)(f(x)-\sum_y\pi(y)f(y))^2\). This characterization follows by expanding \(f\) in an orthonormal eigenbasis: after removing its constant component, the energy-to-variance ratio is a weighted average of \(1-\lambda_i\), \(i\ge2\).

Level Sets and the Energy Estimate

For an edge \(xy\), put \(q_{xy}=1/(4m)\). In an edge sum below, each undirected edge is counted once. Then \(\mathcal E(g,g)=\sum_{xy\in E}q_{xy}(g(x)-g(y))^2\). If \(g\ge0\), its squared level sets are \(S_t=\{x:g(x)^2>t\}\), for \(t\ge0\). Integrating their boundary flow gives the identity \(\int_0^\infty Q(S_t,\overline{S_t})\,dt=\sum_{xy\in E}q_{xy}|g(x)^2-g(y)^2|\). Indeed, a fixed edge \(xy\) crosses \(S_t\) precisely for thresholds between the two endpoint values \(g(x)^2\) and \(g(y)^2\); the length of that interval is their absolute difference. Summing these contributions proves the identity.

Proof. First let \(g\ge0\) have support of stationary mass at most \(1/2\), meaning \(\pi(\{x:g(x)>0\})\le1/2\). Every nonempty \(S_t\) is then eligible in the definition of \(\Phi\); for an empty level set both its flow and mass are zero. Applying the conductance inequality at each threshold and integrating gives \(\int_0^\infty Q(S_t,\overline{S_t})\,dt\ge\Phi\int_0^\infty\pi(S_t)\,dt=\Phi\sum_x\pi(x)g(x)^2\). The last equality follows because a vertex \(x\) belongs to \(S_t\) for an interval of thresholds of length \(g(x)^2\).

For the lazy walk, \(\sum_{xy\in E}q_{xy}(g(x)+g(y))^2\le2\sum_{xy\in E}q_{xy}(g(x)^2+g(y)^2)=\sum_x\pi(x)g(x)^2\). Here \((a+b)^2\le2(a^2+b^2)\), and the sum of \(q_{xy}\) over edges incident to \(x\) is \(\deg(x)/(4m)=\pi(x)/2\). Cauchy–Schwarz and the level-set identity therefore give \(\Phi\sum_x\pi(x)g(x)^2\le\sqrt{\mathcal E(g,g)\sum_x\pi(x)g(x)^2}\). If \(g\) is zero everywhere, \(\mathcal E(g,g)\ge\Phi^2\sum_x\pi(x)g(x)^2\) holds directly. Otherwise divide by the positive square root of \(\sum_x\pi(x)g(x)^2\) and square to obtain the same inequality.

Now take any real-valued \(f\), and choose a weighted median \(a\) so that \(\pi(\{x:f(x)>a\})\le1/2\) and \(\pi(\{x:f(x)<a\})\le1/2\). Such a value exists: order the finitely many values of \(f\) and choose one where the cumulative stationary mass first reaches \(1/2\). Set \(g(x)=\max(f(x)-a,0)\) and \(h(x)=\max(a-f(x),0)\). Both supports have mass at most \(1/2\), so the estimate just proved applies to each. On every edge, \((f(x)-f(y))^2\ge(g(x)-g(y))^2+(h(x)-h(y))^2\): if both values are on the same side of \(a\), one part is zero at both endpoints; if they are on opposite sides, the left side is the square of the sum of the two nonnegative parts, which is at least the sum of their squares. Thus \(\mathcal E(f,f)\ge\mathcal E(g,g)+\mathcal E(h,h)\ge\Phi^2\sum_x\pi(x)(f(x)-a)^2\ge\Phi^2\operatorname{Var}_{\pi}(f)\). The last inequality holds because the weighted mean minimizes the sum of squared deviations from a constant. Taking the minimum Rayleigh quotient over nonconstant \(f\) proves \(\gamma\ge\Phi^2\), and hence also \(\gamma\ge\Phi^2/2\). \(\square\)

The stronger form here uses the lazy-walk convention for both flow and energy. For a non-lazy walk the incident edge-flow sum in the Cauchy–Schwarz estimate is \(\pi(x)\), rather than \(\pi(x)/2\); the resulting standard estimate has the factor \(1/2\). Keeping the convention consistent is essential.

Worked Level Sets and Conductance

A Normalization Pitfall

Do not use the non-lazy edge flow for a lazy walk. In the path example, \(\pi(1)=1/4\) and \(P(1,2)=1/2\), so the flow from \(1\) to \(2\) is \(\pi(1)P(1,2)=(1/4)(1/2)=1/8\). Writing \(1/4\) would omit the lazy holding probability. That error doubles \(Q(S,\overline S)\) and therefore doubles the calculated conductance. The correct endpoint-singleton ratio is \((1/8)/(1/4)=1/2\), not \(1\). Always compute the transition probability first, then multiply by the stationary mass.

The central mechanism is the passage from the level-set flow integral to the edge sum of squared-value differences, followed by Cauchy–Schwarz. The median shift ensures that every level set used in this argument has stationary mass at most one half. This is what lets conductance control the energy of both positive and negative deviations, and hence the variance of the whole function.