图谱分解的拉普拉斯矩阵中特征值与特征向量的含义

图的谱分解是人们研究图的一个重要方向，对于图卷积神经网络有着非常重要的作用。然而在阅读相关文献[1]时，发现其中图的谱分解涉及到图的拉普拉斯矩阵的特征值与特征向量非常难以理解，因此我花了一段时间研究了网上的资料，最终写下了这篇文章。

拉普拉斯矩阵的含义

说到拉普拉斯矩阵，不得不先提一下与之相关的另一个我们比较熟悉的数学概念：拉普拉斯算子。

$\Delta f = \nabla^2 f = \sum_{i=1}^{n} \frac{\partial^2 f}{\partial x_i^2}$

在图像处理中，拉普拉斯算子可以用于边缘检测，比如下面这张图，就是对x坐标使用了拉普拉斯算子的结果——

See the source image — 拉普拉斯算子刻画了“某一个像素点变为其相邻的元素点产生的期望影响大小”：在颜色剧烈变化的图像边缘拉普拉斯算子计算出来的值较大，而均匀色块计算出来的值则为零，表示一个像素变为相邻元素的期望影响为零

当然，上面的图片也可以看做以 $\left( \begin{matrix} -1 & 2 & -1 \\ -1 & 2 & -1 \\ -1 & 2 & -1 \end{matrix} \right)$ 作为卷积核的图卷积操作，这样的卷积适用于抓取横向的边缘信息。当然我们也可以设计卷积核同时抓取横向和纵向的信息 $\left( \begin{matrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{matrix} \right)$ 。这个卷积核就是上面列到的拉普拉斯算子的离散版本了。

从直观上来说，使用上述的拉普拉斯算子进行卷积操作计算了图像的边界信息。实际上，我们也可以理解为某一个像素点变为其相邻的元素点产生的期望影响大小。从某种意义上来说，拉普拉斯算子非常成功刻画了一个像素的邻域信息。

对于图像来说，拉普拉斯矩阵就是将卷积的操作修改为矩阵，如一个 $3\times 3$ 的图像，有

$L = \left( \begin{matrix} 2 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \\ -1 & 3 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & \\ 0 & -1 & 2 & 0 & 0 & -1 & 0 & 0 & 0 & \\ -1 & 0 & 0 & 3 & -1 & 0 & -1 & 0 & 0 & \\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 & \\ 0 & 0 & -1 & 0 & -1 & 3 & 0 & 0 & -1 & \\ 0 & 0 & 0 & -1 & 0 & 0 & 2 & -1 & 0 & \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 3 & -1 & \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 2 \end{matrix} \right)$

上述矩阵的第一行表示：图像拉普拉斯矩阵第一项值 $Lx_{(0)} = 2x_{(0)}-x_{(1)}-x_{(3)}= 2x_{(0,0)}-x_{(0,1)}-x_{(1,0)}$ ，恰好就是左上角进行一次拉普拉斯卷积的结果。同时我们还可以通过观察矩阵发现，矩阵的对角线一个类似于“度数”的正整数值，而其他地方则类似于一个负的“邻接矩阵”。

而图的拉普拉斯算子，也可以理解为将一个节点权值变成其相邻节点权值的期望影响，对应的矩阵是 $L = D-W$ ，其中 $D$ 是图的度数矩阵， $W$ 是图的边权矩阵。有没有发现，不管是图，还是图像，拉普拉斯矩阵都是对角线为正数，其他地方为负数。

当然，图的拉普拉斯矩阵有若干不同的变种，分别为：

非标准化的拉普拉斯矩阵： $L = D-W$
标准化的拉普拉斯矩阵： $L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$
标准化的拉普拉斯矩阵： $L_{rw} = D^{-1}L = I - D^{-1}W$

拉普拉斯矩阵特征

我们令 $L = D-W$ ，则 $L$ 满足如下特征：

对于任意 $f \in \mathbb{R}^n$ ，有 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2$
L是对称的半正定矩阵
矩阵L的最小特征值为1，其对应的特征向量为 $1$
L的特征值是非负实数 $0 = \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \dots \lambda_n$
L的特征值中0的个数等同于原图的连通块数量。

对于上述特性的证明如下——

特性1：

(1) $\begin{align*} f' W f &= f' D f - f' W f \\&= \sum_{i=1}^n d_i f^2_i - \sum_{i=1}^n f_i f_j w_{ij} \\&= \frac{1}{2} \left( \sum_{i=1}^n d_i f^2_i - 2 \sum_{i,j=1}^n f_i f_j w_{ij} + \sum_{i=1}^n d_i f^2_i \right) \\&= \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2\end{align*}$

特性2：

由于度数矩阵 $D$ 和权值矩阵 $W$ 都是对称的，所以 $L=D-W$ 也是对称矩阵。同时，由于特性1，我们发现 $f'Wf \geq 0$ 对于所有 $f \in \mathbb{R}$ 成立，所以矩阵是半正定的。

特性3：

将 $1$ 带入即可验证

特性4：

可以通过特性2保证特征值非负实数，通过特性3保证存在0特征值。

特性5：

倘若希望 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2 = 0$ ，那么我们需要保证在 $w_{i,j} \neq 0$ 时， $f_i = f_j$ ，因此， $f_i = 1$ 一定是一个可能的解，但是，当图存在多个连通块时，相等关系只需要在块内满足即可，因此，可能有等同于连通块个数个正交基满足特征值为0.

上述内容可以在参考文献[2]中查看详细信息。

基于拉普拉斯矩阵的图的谱分解

在文献[1]中，定义了 $||\nabla x||_W^2 = \sum_i \sum_j W_{ij} [x(i)-x(j)]^2$ ，其实这只是上一小节里面 $f' L f$ 的另一种表现形式而已。

不过一个比较混乱的地方在于文章[1]借用 $||\nabla x||_W^2$ 生成了一系列基 $f_0, f_1, \dots, f_m$ ，满足——

(2) $\begin{align*}f_0 = \arg min _{x \in \mathbb{R}^m, ||x||=1} ||\nabla x||_W^2 = (1/\sqrt{m}) 1_m \\f_i = \arg min _{x \in \mathbb{R}^m, ||x||=1, x \perp \{v_0, v_1, \dots, v_{i-1}\}} ||\nabla x||_W^2 \end{align*}$

实际上，这些 $f_i$ 恰好是 $L$ 的特征值从小到大对应的特征向量！

证明可以这样想，若 $f$ 为 $L$ 的 $\lambda$ 特征值对应的特征向量，且 $\|x\| = 1$ ，那么 $f' W f = \lambda f' f = \lambda$ 。现在假设 $f_0, f_1, \dots, f_{i-1}$ 是L的前i-1个特征向量，我们希望证明下一个能够最小化 $||\nabla x||_W^2$ 的向量 $f_t$ 恰好是 $f_i$ 。如果存在 $f' W f < \lambda_i$ ，那么 $f$ 一定与 $f_0, f_1, \dots, f_{i-1}$ 中的某一个向量不正交。如果保证了 $f_t$ 与 $f_0, f_1, \dots, f_{i-1}$ 正交，那么任意一个非 $f_t$ 的向量，一定包含了一个特征值大于等于 $\lambda_i$ 的基，则最终一定没有 $f_i$ 优。因此，我们发现将 $L$ 的特征向量作为解是最优的。

谱分解的作用

我们可以使用傅里叶对于卷积的优化来类比图的谱分解对于图卷积的意义。原来图上面做卷积是将一个邻域内的点与一个“卷积核”做卷积，这个“卷积核”的权值个数会相对比较多一些，而谱分解就是考虑到了“时域的卷积等于频域的点积”。将图的权值矩阵映射为“不同频率的分量强度为多少”，而对这个“强度”做点积完全等效于原来的卷积。这样一方面减少运算量，另一方面还减少了（如神经网络的）待训练权值个数。

引用

[1] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[2] Von Luxburg, Ulrike. “A tutorial on spectral clustering.” Statistics and computing 17.4 (2007): 395-416.

[3] 图卷积神经网络(GCN)详解:包括了数学基础(傅里叶，拉普拉斯)

图谱分解的拉普拉斯矩阵中特征值与特征向量的含义

拉普拉斯矩阵的含义

拉普拉斯矩阵特征

基于拉普拉斯矩阵的图的谱分解

谱分解的作用

引用