一、图的拉普拉斯矩阵

1. 拉普拉斯算子

这里简单介绍一下散度的概念：散度（divergence）用于表征空间各点矢量场发散的强弱程度。散度描述的是向量场里一个点是汇聚点还是发源点。值为正时表示该点为发源点，值为负时表示该点为汇聚点，值为零时表示该点无源。散度在物理上的含义可以理解为磁场、热源等。在笛卡尔坐标系中，矢量 的散度表示为：

那么拉普拉斯算子作为梯度的散度，则在笛卡尔坐标系中定义为：

也就是表示为函数 在各个维度上的二阶偏导数的和。

接下来来看一下拉普拉斯算子直观上表示什么含义，以一维空间为例：

接着来看二维空间的例子：

                                                           卷积核

那么我们可以认为：拉普拉斯算子是所有自由度上进行微小变化后所获得的增益。

2. 图的表示

一个网络（无向图）由节点与节点之间的边组成。每个节点是有值的，我们用 来表示节点的值：

3. 图的拉普拉斯矩阵

可以将拉普拉斯算子推广到网络（无向图）中，对于有 个节点的网络，我们想要获得一个节点关于其邻居节点（自由度）的增益，然而每个节点的邻居个数不一定是相同的，一个节点的最大自由度为 。

那么拉普拉斯算子在所有的节点上的作用结果就是：

4. 拉普拉斯矩阵的谱分解

拉普拉斯矩阵的谱分解（Laplace Spectral Decomposition）就是拉普拉斯矩阵的特征分解：

对于无向图来说，拉普拉斯矩阵是实对称矩阵，而实对称矩阵一定可以用正交矩阵进行正交相似对角化：

5. 拉普拉斯矩阵的性质

拉普拉斯矩阵有一些性质如下：

①对称性。

②由于其对称性，则它的所有特征值都是实数。

③对于任意向量 ，有：

这一性质利用拉普拉斯矩阵的性质很容易可以得到：

                                            图的平滑度

上图中的两个网络，第一个网络的节点标签差异较小（更平滑），因 此较小，而第二个网络节点标签差异较大（不平滑），因此 较大。因此 可以用来刻画网络的平滑度（越小越平滑）。

多说一句，这一点可以用在半监督学习中，大概的思路是构建有标签和无标签数据的无向图，节点就是每一个数据样本，边是节点间的相似度（使用径向基函数等来度量的相似度），为了使模型为无标签数据标注的标签更平滑，可以将 作为训练模型的一个正则项。感兴趣的同学可以参考：半监督学习|深度学习（李宏毅）（九）。

图的拉普拉斯矩阵的应用是多种多样的，本文只介绍一些学习图神经网络（主要是图卷积网络GCN）的一些基础知识。图的拉普拉斯矩阵还可以应用在谱聚类方法中，这是一种聚类方法，也可当做一种降维方法，感兴趣的同学可以参考：谱聚类|机器学习推导系列（二十）。

二、图傅里叶变换

本章节需要了解傅里叶变换的相关知识，可以参考这篇文章：傅里叶级数与傅里叶变换。

1. 回顾傅里叶变换

对于连续非周期函数 的傅里叶变换，其公式为：

2. 亥姆霍兹方程与傅里叶变换

亥姆霍兹方程的公式为：

因此我们可以看出，傅里叶变换的基函数其实就是拉普拉斯算子的特征函数，而 就代表了拉普拉斯算子的特征值。

3. 从傅里叶变换到图傅里叶变换

对于傅里叶变换，存在卷积定理：在适当条件下，两个信号的卷积的傅立叶变换是他们的傅立叶变换的点积，换句话说就是时域卷积等于频域相乘。为了能够应用卷积定理来处理卷积，所以可以将两个信号 和 首先进行傅里叶变换再相乘，从而得到卷积结果，这样做的好处在于可以降低算法的时间复杂度。用公式表达卷积定理就是：

对于网络来说，直接进行卷积是困难的，因为网络不具备图像那样规则的网格结构，因此考虑应用图傅里叶变换将网络的空域信息映射到频域来应用卷积定理完成卷积操作。

图傅里叶变换是使用类比的方式直接定义的，并非经过严格推导，类比的方法如下：

①拉普拉斯算子与拉普拉斯矩阵：拉普拉斯算子的作用是能够得到一个点在某些自由度上微扰以后获得的增益，而拉普拉斯矩阵能够获得网络中的每个节点微扰以后从它的邻居节点上获得的增益，也就是说：拉普拉斯矩阵之于网络就相当于拉普拉斯算子之于函数。

②拉普拉斯算子的特征函数与拉普拉斯矩阵的特征向量：傅里叶变换的基函数 是拉普拉斯算子的特征函数，那么同样的图傅里叶变换的基向量就是拉普拉斯矩阵的特征向量 。

③拉普拉斯算子的特征值与拉普拉斯矩阵的特征值：傅里叶变换的频率 是拉普拉斯算子的特征值，那么同样的图傅里叶变换的频率就是拉普拉斯矩阵的特征值 。

总而言之，这个类比的过程如下：

既然对于函数来说拉普拉斯算子的特征值和特征函数能够用于函数的傅里叶变换，那么对于网络来说拉普拉斯矩阵的特征值和特征向量就能够用于网络的傅里叶变换。换句话说，傅里叶变换是以拉普拉斯算子的特征函数为基进行投影，那么图傅里叶变换就以拉普拉斯矩阵的特征向量为基进行投影，因此图傅里叶变换定义为：

参考资料

ref:【GCN】万字长文带你入门 GCN——公众号：阿泽的学习笔记

ref:图傅里叶变换