谱图论：Laplacian算子及其谱性质

1 Laplacian 算子

给定无向图G=(V,E)，我们在上一篇博客《谱图论：Laplacian二次型和Markov转移算子》中介绍了其对应的Laplacian二次型：

E[f]=12⋅Eu∼v[(f(u)−f(v))2]

这里f:V→R为图的顶点标签，u∼v表示服从均匀分布的随机无向边(u,v)∈E。直观地理解，Laplacian二次型刻画了图的“能量”（energy）。E[f]的值越小，也就意味着f更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。

事实上，我们可以做进一步地等价变换：

E[f]=12⋅Eu∼v[(f(u)−f(v))2]=⟨f,f⟩−Eu∼v[f(u)f(v)]=⟨f,f⟩−⟨f,Kf⟩=⟨f,If−Kf⟩=⟨f,(I−K)f⟩

这K为我们在上一篇博客中提到的MarKov转移算子，它满足：(Kf)(u)=Ev∼u[f(v)]。

对于最后一个等式而言，我们称算子

L=I−K

为图G的 （归一化）Laplacian算子。

注 对于d-正则图G而言，我们有

L=I−1dA=1d(dI−A)

这里A为G的邻接矩阵，dI−A被称为非归一化Laplacian算子，或直接被简称为Laplacian算子。

和K一样，L也是定义在函数空间F={f:V→R}上的线性算子，按照以下规则将f∈F映射到Lf∈F，满足

Lf(u)=f(u)−Ev∼u[f(v)]，

通过研究L，我们就能把握Laplacian二次型E[f]=⟨f,Lf⟩的特性，从而把握图G的特性，这是谱图理论中至关重要的一点。

接下来再来看我们熟悉的那个示性函数例子。

例 设图顶点的子集S⊆V, 0-1示性函数f=IS用于指示顶点是否在集合S中，即：

f(u)={1 if u∈S0 if u∉S

则我们有：

⟨f,Lf⟩=E[f]=Pru∼v[u∈S,v∉S]⟨f,f⟩=Eu∼π[f(u)2]=Pru∼π[u∈S]=vol(S)

直观地理解，这里Pru∼v[u∈S,v∉S]表示“伸出”S的边占总边数的比例；vol(S)表示S的“体积”。则上述两式的比值

⟨f,Lf⟩⟨f,f⟩=Pru∼v[v∉S∣u∈S]=Pr[pick a random u∈S⏟proportional to the degree, do  1 step, that you get out of S]∈[0,1]

表示从集合S中的“逃出”概率。我们将这个比值称为S的电导（conductance）（我们在博客《图数据挖掘：重叠和非重叠社区检测算法》中介绍过，当时是用来衡量社区划分的质量，这个值越小说明划分得越好），用Φ[S]表示。

2 再论Laplacian二次型的极值

有了L，那么最小化/最大化E[f]的问题就可以进行进一步的研究了。考虑下列优化问题：

maxE[f]=⟨f,Lf⟩=12Eu∼v[(f(u)−f(v))2]⏟continous func. f: Rn→Rs.t.‖f‖22=⟨f,f⟩=Eu∼π[f(u)2]=1⏟compat set, ellipsoid in Rn(⇔Var[f]=1)

存在一个极大值点φ:V→R，它满足：

Lφ=λφ for some λ∈R，

也即Lφ∥φ。此外，该极大点也可以被有效地找到。

推论

E[φ]=⟨φ,Lφ⟩=⟨φ,λφ⟩=λ⟨φ,φ⟩=λ∈[0,2]

事实

E[φ]=Eu∼π[φ(u)]=Eu∼π[φ(u)⋅1]=0⇔⟨φ,1⟩=0⇔φ⊥1Var[φ]=1

下面我们来证明为什么E[f]的极大值点φ满足Lφ∥φ。

证明 我们采用反证法，即假设极大值点φ满足Lφ∦，如下图所示：

由于L\varphi \nparallel \varphi，那么我们可以现在L\varphi与\varphi之间的垂线方向上取f = \varphi + \varepsilon \psi（\varepsilon\neq 0是一个很小的数，\psi为单位向量），根据勾股定理有\lVert f \rVert^2_2 = 1 + \epsilon^2。则：

\begin{aligned} \mathcal{E}[f] = \langle f, Lf \rangle &\overset{(1)}{=} \langle \varphi + \varepsilon \psi, L\varphi + L\varepsilon \psi \rangle \\ & \overset{(2)}{=} \langle \varphi, L \varphi \rangle + \underbrace{\varepsilon \langle \phi, L \psi \rangle + \varepsilon \langle \psi, L \varphi \rangle}_{L \text{ is self-adjoint}} + \varepsilon^2 \langle \psi, L \psi \rangle\\ & \overset{(3)}{=} \langle \varphi, L \varphi \rangle + \underbrace{2\varepsilon \langle \psi, L \varphi \rangle}_{>0} + \mathcal{O}(\epsilon^2) \\ & > \langle \varphi, L \varphi \rangle \end{aligned}

（其中等式(3)用到了自伴算子的定义）而这与\varphi为极大值点相矛盾。因此，\mathcal{E}[f]的极大值点\varphi满足L\varphi \parallel \varphi。

3 Laplacian算子的谱性质

在上一小节，我们已经证明了\varphi是一个极大值点。现在我们不采用\varphi及所有与\varphi平行的解，而将解限制在与\varphi相正交的子空间中。这样，优化问题就变为了：

\text{Max } \underbrace{\langle f, Lf \rangle}_{\text{continous func. }} \quad \text{s.t.} \underbrace{\lVert f \rVert^2_2 = \langle f, f \rangle = 1}_{\text{compat set}},\quad f\perp \varphi

求解该优化问题可以采用与之前相同的思路，也即存在极大值点\varphi^{\prime}满足：

L \varphi^{\prime}=\lambda^{\prime} \varphi^{\prime} \quad \text { for some } \lambda^{\prime} \leqslant \lambda，\text{and } \mathbb{E}[\varphi^{\prime}] = 0 (\Leftrightarrow \langle \varphi^{\prime}, \mathbf{1} \rangle = 0)

这里\lambda^{\prime} < \lambda的原因是\lambda已经对应了极大值点，而我们添加了新的约束使f\nparallel \varphi，故这里\lambda^{\prime}对应的是第二大的极值点。

重复这个步骤，不断寻找第3大，第4大……的极大值点，并使其与之前找到的所有极大值点正交，直到找到最后一个（第n大的）极大值点。在这个过程中得到的极大值点都会\perp于\mathbf{1}（\mathbf{1}为全1向量），而最后一个极大值点即为所剩的\mathbf{1}向量本身，此时有

L\mathbf{1}=0

由此可见最后一个特征值（最小的特征值）为0。

通过上面所述的步骤，我们可以找到Laplacian算子的n个相互正交的规范化特征向量（范数为1）及其对应的特征值。而这事实上和我们在线性代数课程中所学过的谱定理密切相关。

谱定理 若T为一个实向量空间V上的自伴算子，则V有一个由T的特征向量组成的规范正交基（orthonormal basis）\varphi_1, \varphi_2, \cdots, \varphi_{n}，每个特征向量分别对应于实特征值\lambda_1, \lambda_2, \cdots, \lambda_{n}。

我们前面证明过Markov转移算子K是自伴的，则L = I - K也是自伴的（事实上，又由于\langle f, Lf \rangle \geqslant 0，L还是半正定的）。于是，关于图G的Laplacian算子就有以下定理：

定理 给定G及其Laplacian算子L，则存在规范正交基（函数）\mathbf{1} \equiv \varphi_1, \varphi_2, \cdots, \varphi_{n}及实数0=\lambda_1 \leqslant \lambda_2\leqslant \cdots \leqslant \lambda_{n} \leqslant 2 满足：

L\varphi_i = \lambda_i \varphi_i

我们将\lambda_2和更广泛的\lambda_k（k为一个较小的值）称为低频（low-frequency） 特征值，而将\lambda_n称为高频（high-frequency） 特征值。

事实上，除了讨论Laplacian算子L之外，我们也可以讨论Markov转移算子K的特征向量及特征值。由L = I - K，我们有

K \varphi_i = (I - L) \varphi_i = I \varphi_i - L\varphi_i = \varphi_i - \lambda_i \varphi_i = (1 - \lambda_i) \varphi_i,

则K拥有特征向量\varphi_i及其相伴的特征值 \kappa_i = 1 - \lambda_i，且-1\leqslant \kappa_{n}\leqslant\cdots\leqslant \kappa_2 \leqslant \kappa_1 = 1。

定义 给定f: V\rightarrow \mathbb{R}和正交基\varphi_1, \varphi_2, \cdots \varphi_{n}，那么f能够唯一地表示为\varphi_i的一个线性组合：

f = \hat{f}(1) \varphi_1 + \hat{f}(2) \varphi_2 + \cdots \hat{f}(n) \varphi_{n},\quad \hat{f}(i)\in \mathbb{R}

这个性质会为我们带来许多新的结论。

命题 将L应用于f，就得到了：

Lf = \underbrace{\lambda_1 \hat{f}(1) \varphi_1}_{0} + \lambda_2 \hat{f}(2) \varphi_2 + \cdots + \lambda_{n} \hat{f}(n) \varphi_{n}，

可以看到，L应用于f可以转换为分别去应用于正交基。为了方便，我们常常会使用如下所示的记号：

\widehat{Lf}(i) = \lambda_i \hat{f}(i)

此外，我们也可以使用规范正交基来简化我们内积和范数的表示。

命题 给定另一个函数

g = \hat{g}(1)\varphi_1 + \cdots + \hat{g}(n)\varphi_{n}，

则f和g的内积

\langle f, g\rangle = \sum_{i, j}\hat{f}(i)\hat{g}(j)\langle \varphi_i, \varphi_j \rangle = \sum_{1\leqslant i \leqslant n}\hat{f}(i)\cdot \hat{g}(i)

推论

根据内积我们可以诱导出范数

\lVert f \rVert^2_2 = \langle f, f\rangle = \sum_{1\leqslant i \leqslant n}\hat{f}(i)^2，

f的均值可表示为：

\mathbb{E[f]}=\mathbb{E}_{u\sim \pi}[f(u)] = \langle f, \mathbf{1}\rangle=\langle f, \varphi_1 \rangle = \widehat{f}(1)

可以看到，f沿规范正交基的展开式中的第一项就是均值乘单位向量：

f = \underbrace{\hat{f}(1)}_{\mathbb{E}[f]} \underbrace{\varphi_1}_{\mathbf{1}} + \hat{f}(2) \varphi_2 + \cdots \hat{f}(n) \varphi_{n}, \quad \hat{f}(i) \in \mathbb{R}，

f的方差可表示为：

\begin{aligned} \text{Var}[f] & = \mathbb{E}[f^2] - \mathbb{E}[f]^2 \\ & = \sum_{1\leqslant i \leqslant n} \left[\hat{f}(i)^2\right] - \hat{f}(1)^2 \\ &= \sum_{1< i \leqslant n} \hat{f}(i)^2 \end{aligned}

（注意第1项\hat{f}(1)^2 - \hat{f}(1)^2抵消掉了）

Laplacian二次型\mathcal{E}[f]可表示为：

\begin{aligned} \mathcal{E}[f] &= \langle f, Lf \rangle \\ &= \sum_{i, j}\lambda_i \hat{f}(i)\hat{f}(j)\langle \varphi_i, \varphi_j \rangle\\ &= \sum_{1 < i\leqslant n}\lambda_i \hat{f}(i)^2 \end{aligned}

（注意第1项由于\lambda_1=0就消失了）

参考

[1] CMU 15-751: TCS Toolkit
[2] Bilibili: CMU计算机科学理论(完结)—你值得拥有的数学和计算机课)
[3] Spielman D. Spectral graph theory[J]. Combinatorial scientific computing, 2012, 18: 18.
[4] Axler S. Linear algebra done right[M]. springer publication, 2015.

• 1 Laplacian 算子
• 2 再论Laplacian二次型的极值
• 3 Laplacian算子的谱性质
• 参考

__EOF__