图卷积网络 GCN（二）图上的傅里叶变换和逆变换

背景知识

如要了解谱图卷积，首先需要学习图理论基础和图中如何进行傅里叶变换。

对于傅里叶变换，本文不再赘述。详细内容可以参考：

图上的傅立叶变换

傅立叶变换是将时域的函数转换成频域上的函数，是对于同一个函数的不同视角，数学定义如下：

$\mathcal{F}(w)=\mathcal{F}(f(t))=\int{f(t)e^{-iwt}}dt \quad\quad\quad (1)$

公式（1）表示的意义是傅立叶变换是时域信号 $f(t)$ 与基函数 $e^{-iwt}$ 的积分。

为什么选择 $e^{-iwt}$ 作为基函数？原因有二：

$e^{-iwt}$ 是正交函数系。
$e^{-iwt}$ 是拉普拉斯算子 $\Delta$ 的特征函数。

至于 $e^{-iwt}$ 由何种推导得来的请参考：理解傅里叶变换

先解释下拉普拉斯算子 $\Delta$ 的定义

在数学中，拉普拉斯算子（Laplacian）是由欧几里得空间中的一个函数的梯度的散度给出的微分算子，记为 $\Delta f=\nabla^{2} f=\nabla \cdot \nabla f$ ，表示 $n$ 维空间笛卡尔坐标系 $x_i$ 中所有非混合二阶偏导数之和，其数学定义为

$\Delta=\sum_{i=1}^n\frac{\partial^2}{\partial{^2x_{i}}} \quad\quad\quad(2)$

这表达式什么意思呢？以二维空间为例：

$\begin{aligned} \Delta f(x, y) &=\frac{\partial^{2} f}{\partial x^{2}}+\frac{\partial^{2} f}{\partial y^{2}} \\\\ &=[f(x+1, y)+f(x-1, y)-2 f(x, y)]+[f(x, y+1)+f(x, y-1)-2 f(x, y)] \\\\ &=f(x+1, y)+f(x-1, y)+f(x, y+1)+f(x, y-1)-4 f(x, y) \end{aligned}$

上式中每一项的系数就是拉普拉斯在二维图像中的卷积核：

再解释下 $e^{-iwt}$ 为何拉普拉斯算子 $\Delta$ 的特征函数

拉普拉斯算子的特征方程为：

$\Delta g=\lambda g \quad\quad\quad (3)$

代入函数 $e^{-iwt}$ 可得：

$\Delta e^{-iwt}=\frac{\partial ^2}{\partial^2 x_i}e^{-iwt}=\frac{\partial ^2}{\partial^2 t}e^{-iwt}=-w^2e^{-iwt} \quad\quad\quad(4)$

其中特征值 $\lambda=-w^2$ ，即 $w$ 和特征值 $\lambda$ 密切相关。

由上述证明可得结论：傅立叶变换是时域信号与拉普拉斯算子特征函数的积分。

从整体推特殊，将以上的结论推广到（离散）图中可知：图上的傅立叶变换就是时域信号与图拉普拉斯算子特征函数的求和！

对于傅里叶变换式（1），将特征函数转换为特征向量（特征函数可以认为是无限维的特征向量），将积分转换为求和，那么 $N$ 个顶点图上的傅立叶变化表达式为：

$\mathcal{F}(\lambda_l)=\widehat f(\lambda_l)=\sum_{i=1}^N f(i)*u_l(i) \quad\quad\quad(5)$

其中， $\lambda_l$ 为图拉普拉斯算子第 $l$ 个特征值， $u_{l}$ 为第 $l$ 个特征值对应的特征向量，公式（5）是
$\lambda_{l}$ 对应的傅立叶变换，对于图拉普拉斯算子，具有 $N$ 个特征值，将式 (5) 全部分量展开可得：

$\left(\begin{array}{c} \hat{f}\left(\lambda_{1}\right) \\\\ \hat{f}\left(\lambda_{2}\right) \\\\ \vdots \\\\ \hat{f}\left(\lambda_{N}\right) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \\\\ u_{2}(1) & u_{2}(2) & \dots & u_{2}(N) \\\\ \vdots & \vdots & \ddots & \vdots \\\\ u_{N}(1) & u_{N}(2) & \dots & u_{N}(N) \end{array}\right)\left(\begin{array}{c} f(1) \\\\ f(2) \\\\ \vdots \\\\ f(N) \end{array}\right) \quad\quad\quad(6)$

将公式（6）写成矩阵形式即为：

$\widehat f=U^{T}f \quad\quad\quad (7)$

此处 $U$ 为拉普拉斯谱分解的正交矩阵。

最后再来看看图中拉普拉斯算子的定义：

$L=D-W \quad\quad\quad (8)$

其中 $W$ 是邻接矩阵， $D$ 是度矩阵， $D_{i,i}$ 等于 $W$ 矩阵的第 $i$ 行的和，非对角线上元素为 0， $D$ 是个对角矩阵，这个图谱理论关于图拉普拉斯算子的的定义。详细推到过程参考：图拉普拉斯算子为何定义为 D-W

拉普拉斯矩阵是实对称矩阵，实对称矩阵一定可以用正交矩阵进行正交相似对角化（特征分解）：

$L=U\left(\begin{array}{ccc} \lambda_{1} & & \\\\ & \ddots & \\\\ & & \lambda_{N} \end{array}\right) U^{-1} =U\left(\begin{array}{ccc} \lambda_{1} & & \\\\ & \ddots & \\\\ & & \lambda_{N} \end{array}\right) U^{T} \quad\quad\quad (9)$

$U$ 为特征向量构成的正交矩阵，而正交矩阵的逆等于正交矩阵的转置： $U^{-1}=U^T$

假定 $\lambda_{1},\cdots,\lambda_{n}$ 从小到大排序，其对应的特征向量为 $u_1,\cdots, u_n$ ，特征值越小，对应的特征向量越平稳，这和傅立叶变换中频率的定义是类似的。下图是对 random sensor network 做特征值分解后的特征向量分布展示，可以看到特征值越小，对应的特征向量越平滑。

图上傅里叶逆变换

有了傅立叶变换，如何将频率函数变换为时域函数呢？这是傅立叶逆变换需要干的事情，公式如下：

$\mathcal{F}^{-1}[\mathcal{F}(w)]=\frac{1}{2\pi}\int \mathcal{F}(w)e^{-iwt}dw \quad\quad\quad(10)$

公式（10）和公式（1）类似，差一个常数系数。公式（1）积分之后是一个关于 $w$ 的函数，公式 (10) 对 $w$ 积分后是关于 $t$ 的函数，从频域变换到了时域，图上傅立叶变换类似为：

$\left(\begin{array}{c} f\left(\lambda_{1}\right) \\\\ f\left(\lambda_{2}\right) \\\\ \cdots \\\\ f\left(\lambda_{N}\right) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \\\\ \cdots & \dots & & \dots \\\\ u_{1}(1) & u_{1}(2) & \dots & u_{1}(N) \end{array}\right)\left(\begin{array}{c} \hat{f}\left(\lambda_{1}\right) \\\\ \hat{f}\left(\lambda_{2}\right) \\\\ \dots \\\\ \hat{f}\left(\lambda_{N}\right) \end{array}\right) \quad\quad\quad (11)$