图 Laplacian 与谱图论

Matrix as Graph区分了邻接矩阵、关联矩阵与转移矩阵。谱图论进一步研究这些矩阵的特征值如何反映图的整体结构。本章先限于有限、无向、非负加权图。

零权边与连通性的约定

零权边对能量没有贡献。因此“零特征值重数等于连通分量数”必须在正权边构成的图上解释。若把一条零权边也当作真实连接，图的组合连通性会与 Laplacian 的零空间不一致。本章把零权边视为不存在，并假设无自环。

Laplacian 比邻接矩阵更直接地测量差异

设邻接矩阵为 $A$，加权度矩阵为 $D=\operatorname{diag}(d_1,\ldots,d_n)$，其中 $d_i=\sum_j a_{ij}$。组合 Laplacian 定义为

$$L=D-A.$$

对顶点信号 $\mathbf x$，第 $i$ 个分量为

$$(L\mathbf x)_i=\sum_j a_{ij}(x_i-x_j).$$

它把一个顶点与邻居的差异加总。常数信号没有差异，所以 $L\mathbf1=\mathbf0$。

关联矩阵给出同一个算子

给每条无向边任取方向，令关联矩阵 $B$ 的一列在起点取 $-1$、终点取 $1$。若边权组成对角矩阵 $W$，则

$$L=BWB^{\mathsf T}.$$

改变任意一条边的临时方向，只会让 $B$ 的对应列乘以 $-1$，乘积保持不变。方向只是记账工具，不改变无向图的 Laplacian。

逐项检查：边 $\{i,j\}$ 对应的列向外积在 $(i,i),(j,j)$ 处贡献 $w_{ij}$，在 $(i,j),(j,i)$ 处贡献 $-w_{ij}$，其余为零。对所有边求和恰好得到 $D-A$，所以关联矩阵恒等式成立。

二次型测量图信号的粗糙程度

由关联分解可得

$$\mathbf x^{\mathsf T}L\mathbf x =\sum_{\{i,j\}\in E}w_{ij}(x_i-x_j)^2\ge0.$$

因此 $L$ 对称半正定。相邻顶点取值接近时能量小，变化剧烈时能量大。这是图上的平滑性概念。

能量为零当且仅当每条边两端取值相同，所以每个连通分量上 $\mathbf x$ 为常数。于是零特征值的重数恰好等于连通分量数。

证明核与连通分量

若 $L\mathbf x=0$，其能量为零。保留的边权均为正，每个平方差都必须为零；相等关系沿路径传递，故信号在每个分量上为常数。反过来，这样的信号代入邻点差公式，直接得到 $(L\mathbf x)_i=0$。各分量的示性向量支撑不交，因而独立，并且张成所有这样的信号，所以核的维数恰为分量数。谱定理又保证这个维数等于零特征值的代数重数。

第二特征值测量最弱连接

对连通图，特征值满足

$$0=\lambda_1<\lambda_2\le\cdots\le\lambda_n.$$

$\lambda_2$ 称为代数连通度。由 Rayleigh 商，

$$\lambda_2=\min_{\mathbf x\perp\mathbf1,\,\mathbf x\ne0} \frac{\sum_{\{i,j\}}w_{ij}(x_i-x_j)^2}{\|\mathbf x\|^2}.$$

若图能沿一条弱连接分成两团，就能构造一个在两团近似常数、跨边才改变的低能量信号，使 $\lambda_2$ 较小。对应特征向量称为 Fiedler 向量，可提供二分线索。

这里还需 $n\ge2$。取第一单位特征向量为 $\mathbf q_1=\mathbf1/\sqrt n$。与 $\mathbf1$ 正交的向量展开为 $\sum_{i=2}^n c_i\mathbf q_i$，Rayleigh 商就是 $\sum_{i=2}^n\lambda_i c_i^2/\sum_{i=2}^n c_i^2\ge\lambda_2$，在 $\mathbf q_2$ 处取等号，因而得到所写的最小值。

把顶点分成非空的 $S,T$，记 $s=|S|$、$t=|T|$。在 $S$ 上取 $x_i=\sqrt{t/s}$，在 $T$ 上取 $x_i=-\sqrt{s/t}$，则 $\mathbf x\perp\mathbf1$，$\|\mathbf x\|^2=s+t=n$，能量只有跨割边贡献。若这些边的权重和为 $c(S,T)$，则

$$R_L(\mathbf x)=c(S,T)\left(\frac1s+\frac1t\right).$$

这正是二分 RatioCut 目标。去掉“坐标只能取上述两个值”的离散约束，就得到前面的 Rayleigh 最小化。因此 $\lambda_2$ 是离散目标的下界，Fiedler 向量解出了这个明确的连续松弛问题；之后的离散化步骤不保证恢复最优割。

归一化 Laplacian 处理不同度数

组合 Laplacian 会让高度顶点贡献更多。对所有度数正的顶点，可以定义

$$L_{\mathrm{sym}}=I-D^{-1/2}AD^{-1/2}, \qquad L_{\mathrm{rw}}=I-D^{-1}A.$$

$L_{\mathrm{rw}}$ 与随机游走转移矩阵相连，$L_{\mathrm{sym}}$ 则是对称矩阵，便于使用谱定理。孤立顶点使 $D^{-1}$ 不存在，必须单独处理或明确约定。

由 $L_{\mathrm{sym}}=D^{-1/2}LD^{-1/2}$，把能量公式中的向量换成 $D^{-1/2}\mathbf x$，就证明它半正定。又有

$$D^{1/2}L_{\mathrm{rw}}D^{-1/2}=L_{\mathrm{sym}},$$

所以两个归一化 Laplacian 相似，具有相同的实非负特征值。这里的换基依赖所有度数为正。

与前文列概率约定怎样衔接

$D^{-1}A$ 是行随机矩阵，适合描述起点到终点的转移概率，并作为算子作用于顶点函数。若沿用前文的列概率状态，则使用

$$P=AD^{-1},\qquad \mathbf p_{n+1}=P\mathbf p_n.$$

两者互为转置。不能把行随机矩阵直接左乘列概率后仍声称总概率守恒。无向图中，归一化度向量是该列转移矩阵的稳态；图若二分且没有自环，离散随机游走仍可能周期振荡。

具体地，记 $s_d=\sum_i d_i>0$，取 $\boldsymbol\pi=\mathbf d/s_d$，则 $AD^{-1}\boldsymbol\pi=A\mathbf1/s_d=\mathbf d/s_d$，且 $AD^{-1}$ 每列之和为一。在二分图上，每一步都把全部质量移到另一侧；若初始质量全部在一侧，该侧总质量便在零和一之间交替，直接说明可能不收敛。

从扩散到谱聚类

连续图扩散可写成

$$\mathbf x'(t)=-L\mathbf x(t), \qquad \mathbf x(t)=e^{-tL}\mathbf x(0).$$

高特征值模式衰减得快，常数模式保留。谱聚类则取若干低特征值对应向量，把每个顶点映到低维坐标，再做聚类。它利用的是松弛后的连续优化问题，最终离散分组仍需额外步骤。

有向图、负权图和超图需要不同的 Laplacian 定义。不能把本章结论不加条件地搬过去。

在正交特征基中，解为 $\sum_i e^{-t\lambda_i}(\mathbf q_i^{\mathsf T}\mathbf x(0))\mathbf q_i$。当 $t\to\infty$，所有正特征值模式消失。连通图只剩 $\mathbf1\mathbf1^{\mathsf T}\mathbf x(0)/n$，即各顶点趋向初始平均值；多个分量则分别投影到各自归一化示性向量，每个分量趋向自身的初始平均值。总信号守恒，因为 $(\mathbf1^{\mathsf T}\mathbf x)'=-\mathbf1^{\mathsf T}L\mathbf x=0$。这是组合 Laplacian 的扩散，按度数加权的随机游走具有不同的平稳归一化。

用三顶点路径把定义算一遍

取两条单位权边 $1\!-!2$ 与 $2\!-!3$。其 Laplacian 为

$$L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}.$$

直接相乘验证，向量 $(1,1,1)$、$(1,0,-1)$、$(1,-2,1)$ 的特征值分别为 $0,1,3$。第二模式描述路径两端缓慢变化，第三模式使中点与两端差异较大，因此能量更高。在扩散方程中，它们分别乘以 $1,e^{-t},e^{-3t}$。

练习

练习两节点图

求单边连接两个顶点时的 $L$ 及其特征值。

解答

$L=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$，特征值为 $0,2$，对应常数方向与差异方向。

练习连通分量与零空间

若图由两个互不相连的连通分量组成，构造 $\ker L$ 的两组独立方向。

解答

分别取两个分量的示性向量。每个向量在自己的分量上为一，其余为零，沿每条边都没有变化。

练习方向选择不影响 Laplacian

说明把 $B$ 的一列乘以 $-1$ 为什么不改变 $BB^{\mathsf T}$。

解答

该列的外积为 $\mathbf b\mathbf b^{\mathsf T}$。换成 $-\mathbf b$ 后外积仍相同。