我这篇博客，目的是为了打下理解 GCN 的基础，介绍图傅里叶变换和图卷积。图傅里叶变换主要参考 [0] 这个讲义的前半部分。
先说一下 [0] 这篇讲义吧。这是一篇关于图的信号处理方法的讲义，我觉得对于 GCN 的理解非常有用，一眼看上去也还挺硬核，于是决定先看它。这篇讲义介绍了 ① 图信号处理的挑战 ② 各类定义图的谱域的方法 ③ 对于图信号的各种操作 ④ 高维图的局部多尺度变换方法。本博客只介绍 ①②，③④ 以后再说。
这个讲义我看的比较吃力（跳步真的太多了喂！），查阅了比较多的文章，都有写引用。建议阅读我所有引用的文章，对理解很有帮助。后面的图卷积相对还没有那么难理解，直接看我写的就好啦。
1 简介
在图结构中，边权可以被看做是点之间的相似度，连接与否取决于实际问题的物理意义或从数据中推断；图中的数据可以被视为有限的样本集合，也就是把每个顶点的数据当做一次采样。我们就把顶点上的这些“采样”叫做图信号（graph signal），下图就是一个 peterson 图上信号的例子，高度代表顶点上的值：
在图信号上的数据处理任务包括滤波（filtering）、降噪（denoising）、修复（inpainting）和压缩（compressing）。
1.1 图信号处理的主要挑战
有 $N$ 个顶点的图上的信号，可以像 $N$ 次采样的离散时间信号一样，用长为 $N$ 的向量表示。但是，如果用传统的信号处理方法来处理图信号，就会忽略了图的不规则结构的信息依赖。另外，很多传统信号处理中的基本概念在图信号处理问题上也存在问题：
- 模拟信号 $f(t)$ 的平移，$f(t-3)$ 即可。但是，图信号的 $f(t-3)$ 操作代表什么呢？倒是可以把所有顶点从 $1$ 到 $N$ 标号，然后令 $f(t-3):=f(mod(t-3,N))$，但这似乎没啥意义。这种图的结构是不规则的，因此不具有平移不变性。（所以怎么卷积？怎么参数共享？）
- 谱域信号的平移，乘个 $e^{jw}$ 即可。但是，图信号是离散的，且不均匀的，因此并不太能“在谱域平移”
- 离散信号的下采样，每 x 个取一个即可。但是，不规则结构的图信号怎么下采样？
除此之外，当图中数据很多时，信号处理要求只采用 localized 的操作（就比如 CNN，就是只在卷积核里有 localized 的卷积，只跟邻居发生关系），但是图结构怎么定义邻居呢？
综上所述，图上的信号处理存在的挑战主要就是 localize。
2 谱图理论
在图的信号处理领域，谱图理论被用来定义图傅里叶变换的频谱和坐标变换（basis expansion）（我搜了一下，就是把线性不可分的数据转换到另一个空间，使之线性可分，这个新的空间的基就叫做 expansion basis，详见 [2]）
2.1 有权图和图信号
我们定义一个无向、连通、有权图 $G = \{\mathcal{V},\mathcal{E},W\}$，其中顶点集 $\mathcal{v}$ 的大小 $|\mathcal{V}|= N$，边集 $\mathcal{E}$，邻接矩阵 $W$。如果一个图有多个连通分量，就拆成多个上述的图。
邻接矩阵的一项 $W_{ij}$ 通常代表边的权重。如果没有显式地定义，通常按照如下式子定义：
$$W_{ij}= \begin{cases} exp(-\dfrac{[dist(i,j)]^2}{2\theta^2})& \text{if } dist(i,j)\le \mathcal{k} \\ 0& \text{otherwise} \end{cases} $$当然，也可以把顶点连接到 $k$ 个最近的邻居。
定义图的顶点的一个函数 $f:\mathcal{V}\rightarrow \mathbb{R}$，可以表示成一个向量 $f\in \mathbb{R}^N$，向量的第 $i$ 个分量表示第 $i$ 个顶点的函数值。
2.2 图拉普拉斯矩阵
图拉普拉斯矩阵 $L:=D-W$ 是一个差分算子（difference operator，可见百度百科）。对于任何信号 $f\in\mathbb{R}N$，都满足：
$$(Lf)(i) = \sum_{j\in\mathcal{N}_i}W_{ij}[f(i) – f(j)]$$其中，$\mathcal{N}_i$ 是和顶点 $i$ 有直接相邻边的点集。更普遍地，用 $\mathcal{N}(i,k)$ 表示跟顶点 $i$ 的距离 $\le k$ 的点集。
要理解上面这个式子，首先要知道，函数的拉普拉斯算子为：
$$\triangledown^2f=\dfrac{\partial^2f}{\partial x^2} + \dfrac{\partial^2f}{\partial y^2}$$即梯度的散度。再看下 [4] 的“图(Graph)上热传播模型的推广”部分即可理解。
由于 $L$ 是实对称矩阵，所以有 $N$ 个非负特征值，这组特征值 $\sigma(L) = \{\lambda_0,\lambda_1,…,\lambda_{N-1}\}$ 就叫做谱。
如果想深入了解拉普拉斯矩阵，建议阅读 [9]（虽然我也还没有认真读）
2.3 图傅里叶变换
经典的傅里叶变换：
$$\hat{f}(\xi):=\langle f,e^{2\pi i\xi t}\rangle = \int_\mathbb{R}f(t)e^{-2\pi i \xi t}dt$$其中 $\xi$ 是频域的变量。不了解傅里叶变换的可以先看一下 [7]。这里我们可以把傅里叶变换看做将函数 $f(t)$ 向基函数 $e^{-2\pi i \xi t}$ 投影，傅里叶变换的结果 $\hat{f}(\xi)$ 就是在 $\xi$ 对应的基上的坐标（详见[6]）。
从上面第一个等号看出，傅里叶变换本质上是函数和一个复指数的内积。而这个复指数就是上文说的基，也正是拉普拉斯算子的特征向量：
$$-\triangle(e^{2\pi i\xi t}) = -\frac{\partial^2}{\partial t^2}e^{2\pi i\xi t} = (2\pi\xi)^2e^{2\pi i\xi t}$$看了 [4] 才知道，$\triangle$ 这个符号代表对各个坐标二阶导数的加和，其实就是拉普拉斯算子 $\triangledown^2$！又看了 [5]，终于理解：原来上面等式中，第一个等号是带入拉普拉斯算子的定义 $\triangledown^2f=\partial^2f/\partial x^2 + \partial^2f/\partial y^2$，第二个等号是求出二阶导。对比第一项和最后一项发现，$e^{2\pi i\xi t}$ 就是 $\triangledown^2$ 的特征向量。
我们知道了傅里叶变换的本质，是求函数与正交基（$e^{2\pi i\xi t}$）的内积。那么类似地，推广到图，图上的拉普拉斯矩阵就是离散化的拉普拉斯算子，图上的正交基就是拉普拉斯矩阵的特征向量。因此我们可以定义，图的函数 $f\in\mathbb{R}^N$（上文说过，用 $N$ 维向量表示）的傅里叶变换 $\hat{f}$ 为：
$$\hat{f}(\lambda_l):=\langle f,u_l\rangle = \sum_{i=1}^Nf(i)u_l^*(i)$$其中，$u_l(i)$ 表示第 $l$ 个特征值的第 $i$ 个分量。那么在特征值（或者说频率） $\lambda_l$ 处对应的坐标，就是函数与 $\lambda_l$ 对应的特征向量 $u_l$ 进行内积运算。看了 [8] 才明白，由于上述的内积运算是在复数空间定义的，因此用的是 $u_l$ 的共轭。
图傅里叶反变换：
$$f(i) = \sum_{l=0}^{N-1}\hat{f}(\lambda_l)u_l(i)$$这里再插一句我的理解：用机器学习的话说，图傅里叶变换，就是一个空间变换的过程，将原始数据转换到高维特征空间。这个空间的基就是拉普拉斯矩阵的特征值，求傅里叶变换的目的就是求原函数在这组基下的坐标。
对了，读到这里你可能会有这样的疑问：“为什么图拉普拉斯矩阵就是离散拉普拉斯算子呢？这俩形式差那么多，为啥名字差不多呢？” 这是因为，在某点处计算离散拉普拉斯算子，表示进行微小扰动后的总增益，即
$$\triangle f = \triangledown^2f=\sum_{i=1}^n\dfrac{\partial^2f}{\partial x_i^2}=\sum_{i=1}^n f”(x_i)$$而对于图来说，顶点 $i$ 处的微小扰动，到达各点会有一个 $w_{ij}$ 的权重，权重为零则是无相邻的边，无法直接到达。因此计算图上的总增益，为：
$$\triangle f_i = \sum_{j=1}^nw_{ij}(f_i-f_j) = d_if_i -\sum_{j=1}^nw_{ij}f_j$$ $$\triangle f = \left( \begin{array}{c} \triangle f_1\\ \vdots\\ \triangle f_n \end{array} \right) = (D-W)f = Lf$$因此计算这俩，都是同一个目的。故图拉普拉斯矩阵就是离散拉普拉斯算子（详见 [6]）。
在传统傅里叶变换中，频率低（$\xi$ 小）的正弦分量，波动慢；频率大的波动快。在连通图中也是同理，图拉普拉斯矩阵零特征值对应的特征向量 $u_0$ 是常量（直流分量），且在每个顶点都是 $\frac{1}{\sqrt{N}}$（我在网上查的说是 $(1,1,…,1)^T$，差不多，不计较了）。小特征值对应的特征向量，在图上传播的“很慢”。我这里还是用谱聚类的切图理解的，小特征值的特征向量就是更 bottleneck 的地方，传播的也就更“慢”。
作者举了个🌰，说如果两个顶点之间的边权较大，那么这俩点处，在谱域的这个小特征值对应的特征向量（就是一个基）上的坐标，会非常可能相似。这个乍一看很难理解，但是可以把它类比到传统信号的傅里叶变换上：“图上两点边权大”就是距离近（[3] 推导里看到的），“特征向量上坐标相似”就是在频域的分量差不多。整句话转换过来就是，在时域相隔很近的两处对信号采样，这两个值在频域上，低频分量可能非常接近。这是因为相距很近，低频分量“波动慢”，变化就小。
那与之相反，图拉普拉斯矩阵的大特征值对应的特征向量，在图上“波动”的就更剧烈；大边权的两点，在大特征值对应的特征向量上，可能相去甚远（因为高频信号变得快）。
这张图的横坐标是在不同大小的特征值对应的分量，纵坐标对应的是图上的过零边（zero crossing），即连接的两个顶点，一个信号是正数，一个信号是负数。这张图表明，频率越高，过零边越多。这是因为相邻两点在高频分量的变化可能更大，与上面说的结论一致。
以上就是 [0] 的前半部分，不过为了后面学习 GCN，还要在图傅里叶变换的理解上更加深入。
2.4 矩阵形式的图傅里叶变换
上文说过，傅里叶变换是将函数向基投影。那怎么找这组基呢？拉普拉斯矩阵可以进行如下的特征分解：
$$L=U\Lambda U^T$$其中 $U$ 的每一列都是 $L$ 的特征向量，构成一组基，$\Lambda$ 是对角矩阵，对角线上是 $L$ 的特征值。
上文说过，图傅里叶变换的表达式：
$$F(\lambda_l) = \hat{f}(\lambda_l)= \sum_{i=1}^Nf(i)u_l^*(i)$$那么把每个分量都写出来，就得到矩阵形式：
$$ \left( \begin{array}{c} \hat{f}(\lambda_1)\\ \hat{f}(\lambda_2)\\ \vdots\\ \hat{f}(\lambda_N) \end{array} \right) = \left( \begin{array}{cccc} u_1(1) & u_1(2) & \cdots & u_1(N)\\ u_2(1) & u_2(2) & \cdots & u_2(N)\\ \vdots & \vdots & \ddots & \vdots\\ u_N(1) & u_N(2) & \cdots & u_N(N)\\ \end{array} \right) \left( \begin{array}{c} f(1)\\ f(2)\\ \vdots\\ f(N) \end{array} \right) $$即
$$\hat{f} = U^Tf$$图傅里叶逆变换为：
$$f = U\hat{f}$$推理的过程同上，或见 [10]。
这里小结一下。图的傅里叶变换感觉并不是非常严谨的把傅里叶变换扩展到图上，而只是经过很多类比，定义成的样子。
3 图卷积
图卷积也是用卷积定理来类比，推广到图上的。
卷积定理：函数卷积的傅里叶变换是函数傅里叶变换的乘积，即对于函数 $f(t),h(t)$，满足：
$$f*h = \mathcal{F}^{-1}[\hat{f}(\omega)\hat{h}(\omega)] = \frac{1}{2\pi}\int \hat{f}(\omega)\hat{h}(\omega)e^{i\omega t}d\omega$$类推到图上，我们把图傅里叶变换的定义 $\hat{f} = U^Tf$ 代入，就可以直接得到函数 $f$ 与卷积核 $h$ 在图上的卷积：
$$(f*h)_G = U((U^Th)\odot(U^Tf))$$中间的 Hadamard product 是同形矩阵，同位置相乘。为啥是 $\odot$？详见 [10]。
另外，图卷积实际上并不是卷积了，只是“频域相乘再回来”的过程，和数学里的卷积定义不同！具体详见 [6]。
ok，有了上面这些基础，就可以开始看 GCN 啦！下篇文章见！
4 引用和拓展阅读
[0] Shuman, David I., et al. "The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains." IEEE Signal Processing Magazine 30.3 (2013): 83-98.
[1] 如何通俗地讲解傅立叶分析和小波分析间的关系？ – 咚懂咚懂咚的回答 – 知乎 很好理解，必看
[2] Lecture 4. Logistic Regression & Basis Expansion 大致知道 Basis Expansion 的概念就好
[3] 【其实贼简单】拉普拉斯算子和拉普拉斯矩阵 – Clyce的文章 – 知乎 深度好文！必看！讲解了图拉普拉斯矩阵、图拉普拉斯算子的具体理解！必看！！！
[4] 如何理解 Graph Convolutional Network（GCN）？ – Johnny Richards的回答 – 知乎 必看！也是很好的讲解了拉普拉斯算子
[5] 图卷积神经网络(Graph Convolutional Network, GCN) 从零开始，推出 GCN。必看！#TODO
[6] 图傅里叶变换 – Dwzb的文章 – 知乎 必读！很好懂！
[7] 傅里叶级数与傅里叶变换（一） 傅里叶级数与傅里叶变换（二） 傅里叶变换的基础知识
[8] 图(Graph)上的傅里叶变换 其实大部分都是从 [10] 抄的
[9] EIGENVALUES OF THE LAPLACIAN AND THEIR RELATIONSHIP TO THE CONNECTEDNESS OF A GRAPH #TODO
[10] 如何理解 Graph Convolutional Network（GCN）？ – superbrother的回答 – 知乎 # TODO，以及后面的引用文章都要读
[11] 论文笔记：The Emerging Field of Signal Processing on Graphs
5 TODO
[0] [5] [9] [10] 看完
[mathjax]