Laplacian Matrix 拉普拉斯矩阵

1 Laplacian Matrix 拉普拉斯矩阵

1.1 Laplacian Operator 拉普拉斯算子

引用文章的一句话来引入拉普拉斯矩阵：

谱图理论是图论与线性代数相结合的产物，它通过分析图的某些矩阵的特征值与特征向量而研究图的性质。拉普拉斯矩阵是谱图理论中的核心与基本概念，在机器学习与深度学习中有重要的应用。

拉普拉斯矩阵是谱聚类算法以及图神经网络（GNN）中的核心技术。正好最近正在学习这两方面的内容，所以把介绍拉普拉斯矩阵相关的文章进行梳理与总结，只列出常用的关键性质及应用，其他部分会提供文章连接以供参考。

拉普拉斯矩阵（Laplacian Matrix）其实是通过微积分中的拉普拉斯算子（Laplacian Operator）引入的。拉普拉斯算子作用于多元函数

的结果为所有自变量的非混合二阶偏导数之和

而当拉普拉斯算子作用于一个二元函数时，则可以通过下式进行近似：

其实就是在四个方向上对函数求差分，在一个图上就可以用如下图所示的方法来近似：

图片来自文章

详细推导请见文章。

1.2 Laplacian Matrix 拉普拉斯矩阵

在图论中，我们一般将一个图表示为%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-47%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%221064%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%222120%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-56%22%20x%3D%222510%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%223279%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-45%22%20x%3D%223724%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%224489%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=G%20%3D%20%28V%2C%20E%29&id=S2XBB)的二元组，其中和%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-45%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%221042%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-7B%22%20x%3D%222098%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%222599%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-75%22%20x%3D%222988%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%223561%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%224006%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%224491%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2223%22%20x%3D%224881%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-75%22%20x%3D%225159%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%225732%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%226177%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2208%22%20x%3D%226940%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-56%22%20x%3D%227885%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-7D%22%20x%3D%228655%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=E%20%3D%20%5C%7B%28u%2C%20v%29%20%7C%20u%2C%20v%20%5Cin%20V%5C%7D&id=s4IZL)分别是图的节点和边集合。在图结构的分析与计算中，矩阵扮演了最重要的图信息存储的角色。可以说，在计算机中，图就是被存储在矩阵中的，即图可以用特殊的矩阵进行表示。

1. 邻接矩阵

其中如果 直接有边，则 就是这两个节点之间的权重；一般谱聚类中都假定我们形成的图是无向图，则 ， 则是一个对称矩阵。

1. 节点度矩阵

其中，即与节点相连所有边的权重之和。同时可以注意到，节点度矩阵是一个对角阵。

拉普拉斯矩阵就被定义为节点度矩阵和邻接矩阵的差：

2 拉普拉斯矩阵的性质

2.1 矩阵性质

1. 是对称阵，则两个不同的特征向量相互正交
2. 对任意向量

有

其中可以用来作为对 个节点的特征向量，比如就代表了节点的属性值。
这样就是一个半正定矩阵，具有一些不错的性质。对于上式证明如下：

我们可以看到，如果是代表节点信号强度的向量（如代表节点信号强度），则则可以看作是图中所有节点的加权平滑程度（或总体差异）的度量。

1. 因为是半正定矩阵，所以所有的特征值都大于等于 0。有一个特征值是 0，且对应的特征向量是全 1 的向量，这一点不难证明。

2.2 拉普拉斯矩阵与离散傅里叶变换

拉普拉斯一个非常重要的应用就是与离散傅里叶变换进行联动。

将拉普拉斯矩阵的特征值从大到小进行排序

对应的特征向量分别为

其实就代表了傅里叶变换中从大到小的个频率，而就是对应这个频率的基底。

图片来自视频截图

将所有特征值组成对角阵

将所有的特征向量组成矩阵

值得注意的是，因为是对称阵，所以是线性无关且相互正交的；同时令都是标准向量（如果是的特征向量，那么仍是的特征向量），就是一组中的标准正交基，则就是正交阵，且

进而

根据矩阵的对角化，可以得到

根据我们在傅里叶变换中提及的信号分析与合成的理论，一个时域信号转换到频域上就可以表示为（傅里叶变换）

而反变换，将频域再转换回时域上，就可以用下式进行计算（傅里叶逆变换）

所以

至于什么拉普拉斯矩阵的特征值代表频率，特征向量就是对应的基底，李宏毅机器学习课程中的解释是：因为正余弦函数是傅里叶变化的基底，而离散傅里叶变换其实是在不同频率的正余弦函数上进行等时间间隔进行采样。在频率越高的基底上采样，则相邻两次采样的信号强弱差距就越大，如下图所示：

图片截取自视频

而拉普拉斯矩阵的特征值所对应的特征向量也呈现出相邻两个分量的差距逐渐变大的趋势：

因此可以将拉普拉斯矩阵的特征值看作是 DFT 中的基底的频率，而对应的特征向量就是基底。

这么解释，总觉得有点草率，毕竟是直观的感觉，而没有理论的证明。因此我也查阅了在谱图领域最早介绍拉普拉斯矩阵与傅里叶变换关系的论文，其实论文里面也是这么说的，是基于观察得出的判断。论文链接和截图在下面给出

The Emerging Field of Signal Processing on Graphs, p.3.

3 拉普拉斯矩阵的归一化形式

1. 对称归一化

其中。这也是最常用的一种归一化形式。
对于这种归一化的由来，可以从谱聚类算法中找到一定的解答。

1. 随机漫步归一化