谱扩张与 Cheeger 不等式

形式陈述 ​

设 $G=(V,E,w)$ 是有限无向图，边权 $w_{uv}=w_{vu}\ge 0$，且没有孤立点。令

$$d_u=\sum _v{w}_{uv},\mathrm{vol}(S)=\sum _{u\in S}{d}_u,$$

并记 $w(S,\overline{S})=\sum _{u\in S,v\notin S}{w}_{uv}$。非平凡割的 conductance 定义为

$$\varphi (S)=\frac{w(S,\overline{S})}{min\{\mathrm{vol}(S),\mathrm{vol}(\overline{S})\}},\varphi (G)=\underset{\varnothing \ne S⊊V}{min}\varphi (S).$$

使用归一化 Laplacian公理库图 LaplacianGraph Laplacian · Laplacian matrix用度矩阵减邻接矩阵得到的算子，以二次型衡量相邻顶点取值的不一致。

$$\mathcal{L}=I-D^{-1/2}A{D}^{-1/2},$$

令 ${\lambda }_2$ 为它的第二小特征值。图的 Cheeger 不等式是

$$\boxed{{\displaystyle \frac{{\lambda }_2}{2}\le \varphi (G)\le \sqrt{2{\lambda }_2}}}.$$

左侧证明取实现 $\varphi (G)$ 的割 $S$，构造在 $S,\overline{S}$ 上分别为常数且与 $D^{1/2}\mathbf{1}$ 正交的向量。代入 Rayleigh 商得到 ${\lambda }_2\le 2\varphi (S)$。

右侧从 ${\lambda }_2$ 的特征向量出发，把它换成顶点函数并选取适当的正部或负部。按函数值排序，对阈值集合 $S_t$ 使用离散 coarea 恒等式；再对

$$\sum _{uv}{w}_{uv}|f(u{)}^2-f(v{)}^2|$$

写成 $|f(u)-f(v)||f(u)+f(v)|$ 并用 Cauchy–Schwarz，不等式保证某个 sweep cut 满足 $\varphi (S_t)\le \sqrt{2{\lambda }_2}$。这同时给出从特征向量寻找稀疏割的算法骨架。

直觉 ​

若图有一条窄割，让向量在割的两侧近似常值，就只在少数跨割边上产生能量，因此得到很小的 Rayleigh 商和 ${\lambda }_2$。反过来，小特征值给出一个缓慢变化的低能量函数；沿其数值逐层切开，总有一层的边界相对于体积足够小。

两边常数不对称，是因为从割构造向量几乎没有损失，而从连续取值的特征向量恢复一个离散割要经过 sweep 与 Cauchy–Schwarz。定理连接的是 conductance 与 normalized Laplacian，不能把其中的 ${\lambda }_2$ 换成组合 Laplacian 或邻接矩阵谱隙后保留原常数。

例子与边界 ​

完全图 $K_n$ 的 normalized Laplacian 谱为 $0$ 一次和 $n/(n-1)$ 重数 $n-1$。对 $|S|=s\le n/2$，

$$\varphi (S)=\frac{s(n-s)}{s(n-1)}=\frac{n-s}{n-1},$$

所以 $\varphi (K_n)$ 约为 $1/2$，与常数量级的 ${\lambda }_2$ 一致。

环 $C_n$ 的 ${\lambda }_2=1-\cos \left(2\pi /n\right)=\mathrm{\Theta }(n^{-2})$，而取连续的 $\lfloor n/2\rfloor$ 个顶点得到

$$\varphi (C_n)=\frac{1}{\lfloor n/2\rfloor }=\mathrm{\Theta }(n^{-1}).$$

这展示上界中的平方根尺度确实必要。若图不连通，则某个非平凡分量割的边界为零，故 $\varphi (G)=0$ 且 ${\lambda }_2=0$。无孤立点假设使 $D^{-1/2}$ 和非平凡割体积均无歧义；若采用其他孤立点约定，必须另行修改陈述。

推论与应用 ​

对 $d$-正则图，若只取 $|S|\le |V|/2$，则

$$\varphi (S)=\frac{|{\partial }_{E}S|}{d|S|},$$

所以 conductance 正是边扩张公理库扩张图Expander graph · Expander family每个不超过半数的顶点集合都向外暴露大量边或邻点的稀疏图及其有界度图族。除以 $d$。因此一族有界度正则图具有统一正的组合扩张，当且仅当 normalized Laplacian 的 ${\lambda }_2$ 有统一正下界，常数通过 Cheeger 不等式互相控制。

sweep 证明还给谱划分算法：计算第二特征向量、按顶点值排序、检查所有前缀割，即可找到 conductance 至多 $\sqrt{2{\lambda }_2}$ 的集合。随机游走混合、谱聚类和网络瓶颈检测都建立在这条桥梁上，但其具体结论还需平稳分布、起点和误差范数等额外假设。

参考资料

• Fan R. K. Chung, Spectral Graph Theory, American Mathematical Society, 1997, Chapter 2.
• Daniel A. Spielman, Spectral and Algebraic Graph Theory, Yale lecture notes, chapters on conductance and Cheeger inequalities.