原讲解视频地址，本篇是对该视频的笔记。感谢视频UP的讲解，受益颇多！

如果我们只知道一个模型是怎么做的，却不知道它为何这样做，对于我们做科研的人来说是远远不够的。我们必须知其然并且知其所以然，才能够在现有的模型基础上提出自己的想法和改进。

目录 1.GCN基础 2.谱图理论 3.傅里叶变换 4.GCN

1.GCN基础

1.1 同样都是“图”，Graph与Image有什么联系与区别呢？

Image是Graph在欧式空间中的一种特例。Graph是相较于Image来说更加广义的一种拓扑结构。Graph由点和边组成它可以表示任意的事物与事物之间的关系。而Image是表示在欧式空间中的事物与事物之间的关系。我们可以根据Image来构建对应的Graph，将每一个像素作为节点，像素之间的关系作为边。

图一两种不同的Image—>Graph表示方法

现实生活中能够建图的场景非常之多，社交关系，词汇搜索等等。

1.2 什么是图神经网络？

图神经网络就是专门用来处理图数据的神经网络架构。具体来说，会给定图的每个邻接矩阵和节点特征，通过将这两个输入进行某种图上的映射。从而得到每个节点下一层的特征。

图神经网络的聚合模式：

$GNN: H^{(l+1)} = f(A,H^l)$

合理性：比如社交网络中我们想要获得某一个用户的特征，可以搜集与他相近的人的特征，他们会具有一定的相关性。（近朱者赤，近墨者黑）

许多GNN相关的模型其实都是在设计函数“f”

1.3 GCN模型？

这里我们只讨论简单无向图（图无自环、无重边，边无方向）

$GCN:H^{l+1}=\sigma (\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^l\theta )$

公式中的 $\hat{A}$ 是邻接矩阵+单位矩阵，相当于给每一个节点添加一个自环。 $\hat{D}$ 是对角阵+单位阵。表示添加自环后每一个节点的度值。 $D$ 代表了每一个节点的度的值。对于对角阵求幂，只要对对角线上的每一个元素求幂即可。

例：

$\begin {bmatrix}4&0&0\\0&1&0\\0&0&1\end{bmatrix}^{-\frac{1}{2}}=\begin {bmatrix}4^{-\frac{1}{2}}&0&0\\0&1^{-\frac{1}{2}}&0\\0&0&1^{-\frac{1}{2}}\end{bmatrix} =\begin {bmatrix}\frac{1}{2}&0&0\\0&1&0\\0&0&1\end{bmatrix}$

$\theta$ 是可训练的参数，是对输入的feature进行线性变换。 $\sigma$ 是非线性的激活函数。

简单理解GCN在做什么：对图的邻接矩阵加了一个自环，做了对称归一化。然后用得到的结果对输入的特征进行聚合。每个节点都聚合到了自己和周边节点加权求和的feature信息。

2. 谱图理论

2.1 什么是谱图理论？

研究与图的邻接矩阵相关的一些性质的领域。将线性代数研究矩阵性质限定在了研究图的邻接矩阵的范围内。谱图理论是线性代数的子领域。

2.2 回顾：线性代数相关知识

（1）特征值与特征向量

对于一个矩阵 $A$ ，如果有 $A\overrightarrow{x}=\lambda \overrightarrow{x}$ 其中 $\lambda$ 为标量、 $|\overrightarrow{x}|\neq0$ 。就称 $\overrightarrow{x}$ 是 $A$ 的特征向量， $\lambda$ 是A的特征值。

（2）定理

如果一个矩阵是一个实对称阵，那么它一定有N个特征值，对应着N个互相正交的特征向量。

$A=U\Lambda U^T$ ，其中 $UU^T=I$ ， $\lambda$ 除了对角线上以外其他元素都是0。对角线上的元素都是一个特征值。

（3）半正定矩阵

半正定矩阵就是所有的特征值都大于等于0。

（4）二次型

给定一个矩阵A，左乘x转置，右乘x。 $\overrightarrow{x}^TA\overrightarrow{x}$ 就称为向量x对矩阵A的二次型。

（5）瑞利熵

瑞利熵就是一个向量关于矩阵A的二次型与这个向量关于单位矩阵的二次型的比值 $\frac{\overrightarrow{x}^TA\overrightarrow{x}}{\overrightarrow{x}^T\overrightarrow{x}}$ 。

为什么需要研究瑞利熵：因为其与矩阵的特征值有着密切的联系。如我们假定 $\overrightarrow{x}$ 是矩阵A的一个特征向量，那么瑞利熵就是矩阵对应的特征值。

证明如下：

$\frac{\overrightarrow{x}^TA\overrightarrow{x}}{\overrightarrow{x}^T\overrightarrow{x}}=\frac{\overrightarrow{x}^T(\lambda\overrightarrow{x})}{\overrightarrow{x}^T\overrightarrow{x}} =\frac{\lambda(\overrightarrow{x}^T\overrightarrow{x})}{\overrightarrow{x}^T\overrightarrow{x}} = \lambda$

因此瑞利熵是我们研究特征值的重要手段。

2.3 谱图理论基础

（1） $L$ 与 $L_{sym}$ （重要）

$L$ 是图的拉普拉斯矩阵， $L=D-A$ 。

$L_{sym}$ 是拉普拉斯矩阵的对称规范化， $L_{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$ 。

$L$ 与 $L_{sym}$ 都是实对称阵。因此他们都有N个特征值和N个互相正交的特征向量。可以分解为上述的 $U\Lambda U^T$ 的形式。且这两个矩阵都是半正定的，其特征值都是大于等于0的。

证明：（通过瑞利熵）

如果我们能够证明对于任何的一个向量都有 $\frac{\overrightarrow{x}^TL\overrightarrow{x}}{\overrightarrow{x}^T\overrightarrow{x}}\geq 0$ ，那么当 $\overrightarrow{x}$ 是特征向量，也即当L是特征值是也成立。

首先，分母部分肯定是恒大于等于0的，因为它是向量x的模长的形式。所以我们只需要证明分子恒大于0即可。

我们定义 $G_{(i,j)}$ ，它只有在第i行的第i列和第j行的第j列才为1，在第i行的第j列与第j行的第i列都是-1，其他位置都是0。

为什么构造 $G_{(i,j)}$ ，因为它的二次型非常有特点，对于向量x，关于 $G_{(i,j)}$ 的二次型为：

$\overrightarrow{x}^TG_{(i,j)}\overrightarrow{x} = \overrightarrow{x}^T \begin {bmatrix}0\\\vdots\\x_i-x_j\\ \vdots\\x_j-x_i\\\vdots\\0\end{bmatrix} =x_i(x_i-x_j) + x_j(x_j-x_i) = (x_i-x_j)^2$

所以 $G_{(i,j)}$ 非常有特点，它的二次型就相当于对x的第i个点和第j个点的坐标位置做差求平方。

拉普拉斯矩阵 $L=D-A=\sum_{(i,j)\in E}G_{(i,j)}$ ,因此L的二次型为：

$\overrightarrow{x}^T L\overrightarrow{x}=\overrightarrow{x}^T(\sum G_{(i,j)})\overrightarrow{x}=\sum\overrightarrow{x}^TG_{(i,j)}\overrightarrow{x}=\sum(x_i-x_j)^2\geq 0$

$\overrightarrow{x}^T L_{sym}\overrightarrow{x}= \overrightarrow{x}^T D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\overrightarrow{x}=(\overrightarrow{x}^T D^{-\frac{1}{2}})L(D^{-\frac{1}{2}}\overrightarrow{x}) = \sum(\frac{x_i}{\sqrt {d_i}}-\frac{x_j}{\sqrt {d_j}})^2 \geq0$

也就是将上式中的 $x_i$ 与 $x_j$ 换成了规范化后的 $x_i$ 与 $x_j$ 。

一个更加强的性质： $L_{sym}$ 不仅 $\geq0$ 而且 $\in [0,2]$ 。

证明：（与上述证明类似）

我们定义 $G_{(i,j)}^{pos}$ ，它在第i行的第i列和第j行的第j列，第i行的第j列和第j行的第i列都为1，其他位置为0。

可得 $G_{(i,j)}^{pos}$ 的二次型： $\overrightarrow{x}^TG_{(i,j)}^{pos}\overrightarrow{x} = (x_i+x_j)^2$ 。

定义 $L^{pos}=D+A = \sum_{(i,j)\in E}G_{(i,j)}^{pos}$ 。

可得 $L^{pos}$ 的二次型： $\overrightarrow{x}^TL^{pos}\overrightarrow{x} = \sum(x_i+x_j)^2 \geq0$ 。

同理，定义 $L_{sym}^{pos}=D^{-\frac{1}{2}}L^{pos}D^{-\frac{1}{2}}$ 。

可得 $L_{sym}^{pos}$ 的二次型： $\overrightarrow{x}^TL_{sym}^{pos}\overrightarrow{x} = \sum(\frac{x_i}{\sqrt {d_i}}+\frac{x_j}{\sqrt {d_j}})^2 \geq0$

由 $L_{sym}^{pos}=D^{-\frac{1}{2}}(D+A)D^{-\frac{1}{2}}=I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$

可得 $\overrightarrow{x}^TL_{sym}^{pos}\overrightarrow{x} =\overrightarrow{x}^T(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x} \geq0$

$\overrightarrow{x}^T\overrightarrow{x}+\overrightarrow{x}^T(D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x} \geq0$

$\overrightarrow{x}^T\overrightarrow{x}\geq-\overrightarrow{x}^T(D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x}$

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^T\overrightarrow{x}-\overrightarrow{x}^T(D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x}$

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^T(I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} )\overrightarrow{x}$