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

图的谱分解是人们研究图的一个重要方向,对于图卷积神经网络有着非常重要的作用。然而在阅读相关文献[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)},恰好就是左上角进行一次拉普拉斯卷积的结果。同时我们还可以通过观察矩阵发现,矩阵的对角线一个类似于“度数”的正整数值,而其他地方则类似于一个负的“邻接矩阵”。

2D图片的拉普拉斯算子卷积是图拉普拉斯算子的一个特例。

而图的拉普拉斯算子,也可以理解为将一个节点权值变成其相邻节点权值的期望影响,对应的矩阵是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的特征值从小到大对应的特征向量!

证明可以这样想,若fL\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_tf_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)详解:包括了数学基础(傅里叶,拉普拉斯)

《图谱分解的拉普拉斯矩阵中特征值与特征向量的含义》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据