关于Fourier和Laplace

2020 年 3 月 20 日 图与推荐

前言：本文是我在学习GCN过程中所作的总结梳理，主要整理了GCN中关于拉普拉斯所涉及到的知识和原理，过程中参考学习了大量优秀的资料和博客。对于一些严谨的表述，直接引用了维基百科的语言，对一些优秀博客中的描述也进行了适当的引用(已标明出处)。所涉及知识和理解仅面向机器学习领域。如有冒犯和疏漏，还请批评指正。

还想说一句：想在这里加个公式太难了

傅里叶变换

拉普拉斯变换

傅里叶变换与拉普拉斯变换的关系

图的拉普拉斯矩阵和拉普拉斯算子

参考资料

傅里叶变换

傅里叶变换(Fourier Transform)：一种线性积分变换，默认情况下为连续傅里叶变换。用于信号在时域(或空域)和频域之间的变换，在物理学和工程学中有许多应用。傅里叶变换就像化学分析，确定物质的基本成分。信号来自自然界，也可对其进行分析，确定其基本成分。[1]

傅里叶变换将时域信号变换到频域信号。因为时域有离散和连续之分，所以傅里叶变换可以粗略的分为连续傅里叶变换和离散傅里叶变换。拉普拉斯变换就是对连续傅里叶变换的扩展，使傅里叶变换成为了拉普拉斯变换中的特例。

经过傅里叶变换生成的函数称作原函数的傅里叶变换(频谱)。傅里叶变换在许多情况下是可逆的，即通过得到。通常，是实数函数，是复数函数，用一个复数来表示振幅和相位。

傅里叶变换一词既指变换操作本身，又指该操作所生成的复数函数。

傅里叶变换将可积函数 表示成复指数函数的积分形式或级数形式。其中表示时间，表示频率。

\hat f(\xi ) = \int_{ - \infty }^\infty {f(x){e^{ - 2\pi ix\xi }}dx} ,\ \xi为任意实数

逆变换(Inverse Fourier Transform)

f(x) = \int_{ - \infty }^\infty {\hat f(\xi ){e^{2\pi i\xi x}}d} \xi ,\ x为任意实数

傅里叶变换是对傅里叶级数的扩展。傅里叶级数中，复杂的周期函数可以用一系列简单的正弦、余弦波的和拟合。傅里叶变换解除了周期函数的限制，或者说傅里叶变换中的函数周期趋近于无穷。

傅里叶变换的卷积特性

若函数和在 绝对可积，则卷积函数 $f * g = \int_{ - \infty }^\infty {f(x - \xi )g(\xi )d} \xi$ 或者 $f * g = \int_{ - \infty }^\infty {f(\xi)g(x - \xi )d} \xi$ 的傅里叶变换存在，且有。卷积性质的逆形式为 ${{\cal F}^{ - 1}}\left[ {F(\omega ) * G(\omega )} \right] = 2\pi {{\cal F}^{ - 1}}\left[ {F(\omega )} \right] \cdot {{\cal F}^{ - 1}}\left[ {G(\omega )} \right]$ ，即两个函数卷积的傅里叶变换的逆变换等于各自的傅里叶逆变换的乘积乘以2 。

由卷积定理，卷积公式可以写成：。那么要想实现Graph上的卷积，只需要定义傅里叶变换就OK了。

拉普拉斯变换

拉普拉斯变换(Laplace Transform)是应用数学中的一种线性积分变换。符号表示为：。拉普拉斯变换可将一个有实数变量的函数转换为一个变量为复数的函数：

其中，和为实数。

拉普拉斯变换也可以表示为或。其中为运算符号。

拉普拉斯将一个函数表示为许多矩的叠加，而上文的傅里叶变换是弦波的叠加。

傅里叶变换与拉普拉斯变换的关系

从上文对傅里叶变换的描述中不难看出它的局限--“绝对可积”，说明了傅里叶变换只适用于那些绝对可积的函数。

傅里叶变换要求时域信号满足绝对可积条件

那么如果我们对如等不满足条件的函数乘以一个使其快速衰减的函数如，那么当函数趋近于时就会持续衰减到0，从而满足绝对可积条件[3]，使。那么新的傅里叶变换就是：

\int_{ - \infty }^\infty {f(t){e^{-\sigma t}e^{ - 2\pi it\xi }}dt}

化简后得：

\int_{ - \infty }^\infty {f(t){e^{-(\sigma + 2 \pi i \xi )t}}dt}

简写为：

$\int_{-\infty}^{\infty} f(t) e^{-s t} d t$

上面式子就是拉普拉斯变换了，当为纯虚数时就是傅里叶变换。有的资料习惯在角频率形式上推导二者之间的关系，为了遵循维基百科定义符号的连续性和傅里叶变换和逆变换的对称性，我这里就还是用了最原始的形式去表达。

图的拉普拉斯矩阵和拉普拉斯算子

在图论中，调和矩阵(harmonic matrix)，也称拉普拉斯矩阵或拉氏矩阵(laplacian matrix)；或离散拉普拉斯(discrete laplacian)，是图的矩阵表示。

拉普拉斯矩阵也是拉普拉斯算子的离散化，拉普拉斯矩阵的缩放极限是拉普拉斯算子。

缩放极限：在物理学和数学中，缩放极限(scaling limit)描述格子间距变为0的情况。

拉普拉斯矩阵（Laplacian Matrix）

对于图G = (V, E)，Laplacian Matrix定义为

L : Laplacian Matrix

D : 是顶点的度矩阵（对角矩阵）,

A : 邻接矩阵

Spectral Domain的前提条件是：无向图，此时L为对称矩阵。

上图来自Wikipedia

常用的几种Laplacian

普通形式的Laplacian

{L_{i,j}} = \left\{ \begin{array}{l}diag({v_i}){\ \ \ \ }i = j\\ - 1{\ \ \ \ \ \ \ \ \ \ \ \ \ }i \ne j{\ }and{\ }{v_i}{\ }is{\ }\\0{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }otherwise\end{array} \right.adjacent{\ }to{\ }{v_j}

表示的度

**对称归一化的Laplacian（Symmetric Normalized Laplacian）**用的多

{L^{sys}} = {D^{ - 1/2}}L{D^{ - 1/2}} = I - {D^{ - 1/2}}A{D^{ - 1/2}}

L_{i,j}^{sys} = \left\{ \begin{array}{l} 1{\qquad \qquad \qquad \qquad}i = j{\ }and{\ }diag({v_i}) \ne 0\\ - \frac{1}{{\sqrt {diag({v_i})diag({v_j})} }}{\ \ \ \ \ \ \ }i \ne j{\rm{ }}and{\rm{ }}{v_i}{\rm{ }}is{\rm{ }}adjacent{\rm{ }}to{\rm{ }}{v_j}\\ 0{\qquad \qquad \qquad \qquad}otherwise \end{array} \right.

SNL仍然是对称的。

随机游走归一化Laplacian（Random Walk Normalized Laplacian）

L_{i,j}^{rw} = \left\{ \begin{array}{l} 1{\qquad \qquad}i = j{\ }and{\ }diag({v_i}) \ne 0\\ - \frac{1}{{diag({v_i})}}{\ \ \ \ }i \ne j{\ }and{\ }{v_i}{\ }is{\ }adjacent{\ }to{\ }{v_j}\\ 0{\qquad \qquad \ }otherwise \end{array} \right.

**泛化的Laplacian（Generalized Laplacian）**用的少

无向图Laplacian Matrix性质：

半正定（特征值>=0）
特征值中0出现的次数就是图连通区域的个数
最小特征值是0，因为L = D - A中每一行的和均为0，并且最小特征值对应的特征向量是每个值全为1的向量
最小非零特征值是图的代数连通度

半正定证明（证明二次型）f^T L f >= 0：

\begin{array}{l} {f^T}Lf = {f^T}Df - {f^T}Af\\ = {f^T} * diag(d) * f - {f^T}Af\\ = \sum\limits_{i = 1}^m {{d_i}f_i^2 - \sum\limits_{j = 1}^m {\left[ {\sum\limits_{i = 1}^m {{f_j} * {a_{ij}}} } \right]{f_j}} } \\ = \sum\limits_{i = 1}^m {{d_i}f_i^2 - \sum\limits_{i,j = 1}^m {{f_i} * {f_j} * {a_{ij}}} } \\ = \frac{1}{2}[\sum\limits_{i = 1}^m {{d_i}f_i^2} - 2\sum\limits_{i,j = 1}^m {{f_i}{f_j}{a_{ij}}} + \sum\limits_{j = 1}^m {{d_j}f_j^2} ]\\ = \frac{1}{2}\sum\limits_{i,j = 1}^m {{a_{ij}}{{({f_i} - {f_j})}^2}} \end{array}

所以对于任意一个(m,1)的实向量f，都有下式成立：

{f^T}Lf = \frac{1}{2}\sum\limits_{i,j = 1}^m {{a_{ij}}{{({f_i} - {f_j})}^2}}

那么GCN中为什么要用到Laplacian Matrix？

Laplacian Matrix是对称矩阵，可以进行特征分解（谱分解）

由于卷积在傅里叶域的计算简单，为了在图上能够做傅里叶变换，需要找到图的连续的正交基，对应于傅里叶变换的基，因此需要用到Laplacian Matrix的特征向量。

关于Laplacian 和傅里叶，推荐马同学的帖子：

https://www.matongxue.com/madocs/723/

https://www.matongxue.com/madocs/473/

GCN核心Laplacian Matrix的谱分解

特征分解（Eignedecomposition）又称为谱分解（Spectral Decomposition）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有可对角化矩阵或有n个线性无关特征向量的矩阵才能特征分解。

Laplacian Matrix是半正定的（半正定矩阵本身就是对称矩阵），有如下三个性质：

对称矩阵有n个线性无关的特征向量
半正定矩阵的特征值非负
对称矩阵的不同特征值对应的特征向量相互正交，这些正交的特征向量构成的矩阵为正交矩阵

其中为列向量为单位特征向量的矩阵，i.e. u_i 为列向量。

由于U是正交矩阵，故有：

至于为什么要做特征分解，因为在Graph中，我们没必要每次都去更新全局，而是可以只关注一阶或二阶。拉普拉斯矩阵的特征分解可以达到目的。

拉普拉斯算子Laplacian Operator

在数学和物理中，Laplacian Operator是由欧几里得空间中的一个函数的梯度的散度给出的微分算子，通常写成：

Laplacian Operator是n维欧几里得空间中的一个二阶微分算子，其定义为对函数f先作梯度运算后，再作散度运算的结果。因此如果f是二阶可微的实函数，则f的Laplacian Operator定义为：

f的Laplacian Operator也是笛卡尔坐标系（直角坐标系）x_i中的所有非混合二阶偏导数：

函数f的Laplacian Operator也是该函数的海森矩阵的迹：

Laplacian Operator的物理意义是空间二阶导，准确定义是：标量梯度场中的散度，一般可用于描述物理量的流入流出，比如说二维空间中的温度传播规律，一般可以用Laplacian Operator来描述。Laplacian Matrix也叫做离散的Laplacian Operator。

这里参考学习了[6]的博客，醍醐灌顶，以下内容深受其启发。

要想明确拉普拉斯矩阵的物理意义以及为什么可以用到Graph中，可以从热传导的角度出发[6]。Graph中的每个节点的状态不仅由其本身决定，还深受其邻节点甚至更远的节点影响，且越临近的节点可能造成的影响越大。正如在热传导中，温度高的物体会将热量传递给温度低的物体。

牛顿冷却定律：一个物体所损失的热的速率与物体和其周围环境间的温度差是成正比的。一个物体和其周围处于一个不同的温度下的话，最终这个物体会和其周围达成一个相同的温度。一个比较热的物体将会冷却，因为它使其周围变温暖。一个比较冷的物体会因为其周围的高温而温度上升。当我们在考虑一个物体冷却有多快时，我们会说他冷却的速率是：单位时间内，有多少的温度改变了。它的冷却速率与该物体与周围环境的温度差成正比。

既然考虑到热传导，就需要知道每个节点（物体）周围有多少邻居，这就涉及到了邻接矩阵和度的概念。根据冷却速率与温度差成正比的表述，可以了解和的必要性和关系。关于热传导的模型推导以及如何一步步引入Graph请移步大神的帖子[6]。

那么自然而然地可以想到，热传导场景可以泛化到Graph中的特征传导或者信息传播。Graph的本质也正是信息和特征的传播。也正如GCN[7]所描述的，拉普拉斯矩阵的作用不仅是二阶导数的运算，而更具备一种加和的性质。也就是说，通过拉普拉斯矩阵，可以将图中每个节点的状态一步更新，即Message Passing和Aggregate，体现在GCN中的Aggregate，就是加和。体现在GraphSAGE中的，就是Average、LSTM，Pooling。体现在GATs中的，就是Attention。

最后引用[6]中的一句话：

所有的所有，还是“相邻”，“叠加”与“融合”三个关键词，只是解法更新、迭代、升级了。

参考资料

https://zh.wikipedia.org/wiki/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2
https://zhuanlan.zhihu.com/p/54505069
https://zhuanlan.zhihu.com/p/40783304
https://www.zhihu.com/question/22085329
https://blog.csdn.net/yyl424525/article/details/100058264?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
https://www.zhihu.com/question/54504471/answer/630639025
https://arxiv.org/abs/1609.02907