2019年8月 – mhy12345

图的谱分解是人们研究图的一个重要方向，对于图卷积神经网络有着非常重要的作用。然而在阅读相关文献[1]时，发现其中图的谱分解涉及到图的拉普拉斯矩阵的特征值与特征向量非常难以理解，因此我花了一段时间研究了网上的资料，最终写下了这篇文章。

拉普拉斯矩阵的含义

说道拉普拉斯矩阵，不得不先提一下与之相关的另一个我们比较熟悉的数学概念：拉普拉斯算子。

$\Delta f = \nabla^2 f = \sum_{i=1}^{n} \frac{\partial^2 f}{\partial x_i^2}$

在图像处理中，拉普拉斯算子可以用于边缘检测，比如下面这张图，就是对x坐标使用了拉普拉斯算子的结果——

当然，上面的图片也可以看做以 $\left( \begin{matrix} -1 & 2 & -1 \\ -1 & 2 & -1 \\ -1 & 2 & -1 \end{matrix} \right)$ 作为卷积核的图卷积操作，这样的卷积适用于抓取横向的边缘信息。当然我们也可以设计卷积核同时抓取横向和纵向的信息 $\left( \begin{matrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{matrix} \right)$ 。这个卷积核就是上面列到的拉普拉斯算子的离散版本了。

从直观上来说，拉普拉斯反映了图像的边界信息，实际上，我们也可以理解为某一个像素点变为其向量的元素点产生的期望影响大小。（可以很容易看出，边缘拉普拉斯算子计算出来的值较大，而均匀色块计算出来的值则为零，表示一个像素变为相邻元素的期望影响为零）。从某种意义上来说，拉普拉斯算子非常成功刻画了一个像素的邻域信息。

对于图像来说，拉普拉斯矩阵就是将卷积的操作修改为矩阵，如一个 $3\times 3$ 的图像，有

$L = \left( \begin{matrix} 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \\ -1 & 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & \\ 0 & -1 & 4 & 0 & 0 & -1 & 0 & 0 & 0 & \\ -1 & 0 & 0 & 4 & -1 & 0 & -1 & 0 & 0 & \\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 & \\ 0 & 0 & -1 & 0 & -1 & 4 & 0 & 0 & -1 & \\ 0 & 0 & 0 & -1 & 0 & 0 & 4 & -1 & 0 & \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 & -1 & \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 \end{matrix} \right)$

而图的拉普拉斯算子，也可以理解为将一个节点权值变成其相邻节点权值的期望影响，对应的矩阵是 $L = D-W$ ，其中 $D$ 是图的度数矩阵， $W$ 是图的边权矩阵。有没有发现，不管是图，还是图像，拉普拉斯矩阵都是对角线为正数，其他地方为负数。

当然，图的拉普拉斯矩阵有若干不同的变种，分别为：

非标准化的拉普拉斯矩阵： $L = D-W$
标准化的拉普拉斯矩阵： $L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$
标准化的拉普拉斯矩阵： $L_{rw} = D^{-1}L = I - D^{-1}W$

拉普拉斯矩阵特征

我们令 $L = D-W$ ，则 $L$ 满足如下特征：

对于任意 $f \in \mathbb{R}^n$ ，有 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2$
L是对称的半正定矩阵
矩阵L的最小特征值为1，其对应的特征向量为 $1$
L的特征值是非负实数 $0 = \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \dots \lambda_n$
L的特征值中0的个数等同于原图的连通块数量。

对于上述特性的证明如下——

特性1：

(1) $\begin{align*} f' W f &= f' D f - f' W f \\&= \sum_{i=1}^n d_i f^2_i - \sum_{i=1}^n f_i f_j w_{ij} \\&= \frac{1}{2} \left( \sum_{i=1}^n d_i f^2_i - 2 \sum_{i,j=1}^n f_i f_j w_{ij} + \sum_{i=1}^n d_i f^2_i \right) \\&= \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2\end{align*}$

特性2：

由于度数矩阵 $D$ 和权值矩阵 $W$ 都是对称的，所以 $L=D-W$ 也是对称矩阵。同时，由于特性1，我们发现 $f'Wf \geq 0$ 对于所有 $f \in \mathbb{R}$ 成立，所以矩阵是半正定的。

特性3：

将 $1$ 带入即可验证

特性4：

可以通过特性2保证特征值非负实数，通过特性3保证存在0特征值。

特性5：

倘若希望 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2 = 0$ ，那么我们需要保证在 $w_{i,j} \neq 0$ 时， $f_i = f_j$ ，因此， $f_i = 1$ 一定是一个可能的解，但是，当图存在多个连通块时，相等关系只需要在块内满足即可，因此，可能有等同于连通块个数个正交基满足特征值为0.

上述内容可以在参考文献[2]中查看详细信息。

基于拉普拉斯矩阵的图的谱分解

在文献[1]中，定义了 $||\nabla x||_W^2 = \sum_i \sum_j W_{ij} [x(i)-x(j)]^2$ ，其实这只是上一小节里面 $f' L f$ 的另一种表现形式而已。

不过一个比较混乱的地方在于文章[1]借用 $||\nabla x||_W^2$ 生成了一系列基 $f_0, f_1, \dots, f_m$ ，满足——

(2) $\begin{align*}f_0 = \arg min _{x \in \mathbb{R}^m, ||x||=1} ||\nabla x||_W^2 = (1/\sqrt{m}) 1_m \\f_i = \arg min _{x \in \mathbb{R}^m, ||x||=1, x \perp \{v_0, v_1, \dots, v_{i-1}\}} ||\nabla x||_W^2 \end{align*}$

实际上，这些 $f_i$ 恰好是 $L$ 的特征值从小到大对应的特征向量！

证明可以这样想，若 $f$ 为 $L$ 的 $\lambda$ 特征值对应的特征向量，且 $\|x\| = 1$ ，那么 $f' W f = \lambda f' f = \lambda$ 。现在假设 $f_0, f_1, \dots, f_{i-1}$ 是L的前i-1个特征向量，我们希望证明下一个能够最小化 $||\nabla x||_W^2$ 的向量 $f_t$ 恰好是 $f_i$ 。如果存在 $f' W f < \lambda_i$ ，那么 $f$ 一定与 $f_0, f_1, \dots, f_{i-1}$ 中的某一个向量不正交。如果保证了 $f_t$ 与 $f_0, f_1, \dots, f_{i-1}$ 正交，那么任意一个非 $f_t$ 的向量，一定包含了一个特征值大于等于 $\lambda_i$ 的基，则最终一定没有 $f_i$ 优。因此，我们发现将 $L$ 的特征向量作为解是最优的。

谱分解的作用

我们可以使用傅里叶对于卷积的优化来类比图的谱分解对于图卷积的意义。原来图上面做卷积是将一个邻域内的点与一个“卷积核”做卷积，这个“卷积核”的权值个数会相对比较多一些，而谱分解就是考虑到了“时域的卷积等于频域的点积”。将图的权值矩阵映射为“不同频率的分量强度为多少”，而对这个“强度”做点积完全等效于原来的卷积。这样一方面减少运算量，另一方面还减少了（如神经网络的）待训练权值个数。

引用

[1] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[2] Von Luxburg, Ulrike. “A tutorial on spectral clustering.” Statistics and computing 17.4 (2007): 395-416.

[3] 图卷积神经网络(GCN)详解:包括了数学基础(傅里叶，拉普拉斯)

这个项目是在 CVPR论文 Separating Style and Content for Generalized Style Transfer的基础上改进而来的，是我和LJSthu在学校人工神经网络课程上面的课程作业。我们提出的模型叫做SelectorGAN，从模型效果上面来看，大幅度超越了上文中提出的state of art算法EMD，但模型本身并没有对应的paper，因此，如果希望研究汉字迁移问题，并且引用本文的模型，可以直接引用本博客。

我们的模型尝试处理这样一个问题：给定风格A的16个字体图片，以及字B的不同风格16个图片，尝试合成同时拥有字体A与风格B的图片。如下图所示，一个是ground truth，一个是模型输出，你能猜出谁是谁吗？

首先，我们找到了原文模型EMD的代码，并使用自己的数据集进行复现，得到下图的效果，其中右图是ground true，左图是模型生成结果。可以发现，在我们自己的数据集（规模和原文差不多）上面，模型完全没有paper里面配图的讲的那么好。

与之对比的，是我们提出的SelectorGAN输出如下图所示，其中，左边是ground truth ，右边是模型的输出结果。最明显的区别是我们的模型不容易生成全黑或者全白的无意义图片，几乎所有文字都是清晰可辨的。

在介绍我们的模型之前，我们先分析了当前state of art模型的缺陷。EMD模型的图例如下图所示，将16张候选图片，输入到CNN的16个channel中。这里，由于16张图片是无序不可分的，而CNN的不同Channel是有序可分的，这里就会导致交换输入图片的顺序会产生不同的结果。这其实是一个不正确的做法，倘若我们将16*1的CNN作用于16张图片修改16个为1*1的CNN分别作用于16张图片，可以将模型的参数个数降低16倍，有效降低过拟合的出现。用时，原文的欧几里得距离损失函数，也是的模型在对于生成图片没有信心时，直接输出全部空白，或者全部黑色，而正常图片也存在模糊边界的问题。这一系列问题到这了EMD模型实际跑的并没有文章中说的那么厉害。

我们的模型SelectorGAN为了解决上述的问题，引入了若干个特殊的机制。首先，为了解决生成图像模糊的问题，我们不在使用回归模型训练，而是使用生成模型进行创造。具体来说，我们使用了GAN。

我们使用的GAN实际上是魔改版的 CycleGAN and pix2pix，使用了GAN后，我们发现生成模型可以很好的理解诸如字体宽度，字体边界曲率等信息，并加以模仿。

接下来，我们发现，将原文中16个风格和16个字体结合生成的效果，与1个风格1个字体结合生成效果无区别。上图就是用1对1的方式生成的16张候选图片。

1对1的生成还会出现另一个比较麻烦的东西，就是生成器容易通过增删笔画的方式欺骗判别器。

通常，当原字体与目标字体长款比差距较大时，Generator认为增添笔画可以糊弄Discriminator，而且实际上它成功了。

对于上述的问题，我们发现，我们现在有整整16张候选图片。我们希望能够设计出一个评分模型Selector实现字体的选择。这个Selector应该怎么设计呢？

一个直观的想法是直接使用Discriminator的输出当做Selector，因为Discriminator觉得“真的”的图片往往真的很像答案。但是这样做并不好，因为Discriminator输入的是一堆“真的或者假的”图片，但是实际上，即使是假的图片，不考虑原来输入的话，在风格上都是无懈可击的。这时Discriminator并不能很好的判断出输出的好坏。

基于上面的考虑，我们额外设计了一个Selector模型，作为一个评分模型，通过预测Discriminator的评分进行训练，与Discriminator不同的是，Selector同时使用原始输入图片与Generator的生成图片作为输入，且可以理解为Discriminator的滑动平均。降低了Discriminator的抖动。（当然，实验证明，将Selector评分和Discriminator评分加权平均能够获得更好的效果）