本博客记录了本人对于该文的一点理解，仅供自己学习GNN、GCN使用。
平移不变性：平移是一种几何变换，表示把一幅图像或一个空间中的每一个点在相同方向移动相同距离。比如对图像分类任务来说，图像中的目标不管被移动到图片的哪个位置，得到的结果（标签）应该是相同的，这就是卷积神经网络中的平移不变性。平移不变性意味着系统产生完全相同的响应（输出），不管它的输入是如何平移的。
平移不变性依赖于CNN的卷积和池化两步操作
空间域与频率域为我们提供了不同的视角。在空间域中，函数自变量（x,y）被视为二维空间中的一个点，数字图像f(x,y)即为一个定义在二维空间中的矩形区域上的离散函数；换一个角度，如果将f(x,y)视为幅值变化的二维信号，则可以通过某些变换手段（如傅里叶变换、离散余弦变换、沃尔什变换和小波变换等）在频域下对图像进行处理了因为在频率域就是一些特性比较突出，容易处理。比如在空间图像里不好找出噪声的模式，如果变换到频率域，则比较好找出噪声的模式，并能更容易的处理。
具体名词解释如下：
二者关系：
空间域与频率域可互相转换。在频率域中可以引用已经很成熟的频率域技术,处理的一般步骤为：①对图像施行二维离散傅立叶变换或小波变换,将图像由图像空间转换到频域空间。②在频率域中对图像的频谱作分析处理,以改变图像的频率特征。即设计不同的数字滤波器,对图像的频谱进行滤波。
空间域处理的应用可以参考：
频率域处理主要用于与图像空间频率有关的处理中。如图像恢复、图像重建、辐射变换、边缘增强、图像锐化、图像平滑、噪声压制、频谱分析、纹理分析等处理和分析中。
对于图结构的数据，从最早的基于深经网络框架的GNN到将卷积引入图数据中，说实话卷积还真是个好东西。引入卷积的这类算法又被分为谱方法（spectralapproaches）和非谱方法（non-spectralapproaches）两类。谱方法是基于图的谱表征，通过图拉普拉斯算子的特征分解，在傅里叶域中定义的卷积运算需要进行密集的矩阵计算和非局部空间的滤波（计算）。在此基础上，GCN很有效地对节点的一阶邻域进行处理，从为避免复杂的矩阵运算。但是GCN依赖于图的结构信息，这就导致了在特定图结构上训练得到的模型往往不可以直接被使用到其他图结构上。非谱方法是直接在图上进行卷积而不是在图的谱上。这种方法的挑战之一是如何找到一个或者定义一个运算来处理可变大小的邻域并保证参数共享机制。
这里引入了一个新的概念——散度，这里简单介绍下：
散度（Divergence）是向量分析的一个向量算子，将向量空间上的向量场（矢量场）对应到一个标量场。散度描述的是向量场里一个点是汇聚点还是发源点。值为正时表示该点为发源点，值为负时表示该点为汇聚点，值为零时表示该点无源。散度在物理上的含义可以理解为磁场、热源等。
回到正文，我们看下拉普拉斯算子在n维空间中的笛卡尔坐标系的数学定义：
数学表示为各个维度的二阶偏导数之和。
以一维空间为例：
也就是说二阶导数近似于其二阶差分，可以理解为当前点对其在所有自由度上微扰之后获得的增益。这里自由度为2，分别是+1和-1方向。
再以二维空间为例子：
看到上面可能大家会很可能很陌生，但是这个就是图像中的拉普拉斯卷积核：
此时共有4个自由度(1,0),(-1,0),(0,1),(0,-1)，当然如果对角线后其自由度可以为8。
对此我们可以进行归纳：「拉普拉斯算子是所有自由度上进行微小变化后所获得的增益」。
图拉普拉斯矩阵可以定义为：
其中，D为度矩阵，W为邻接矩阵（对于有权图，W为有权邻接矩阵）。
考虑归一化后的拉普拉斯矩阵：
拉普拉斯矩阵的谱分解就是矩阵的特征分解：
对于无向图来说，拉普拉斯矩阵是实对称矩阵，而实对称矩阵一定可以用正交矩阵进行正交相似对角化：
因为L是半正定矩阵，我们还可以有：
拉普拉斯的谱分解具有以下几点性质：
傅立叶变换分为傅立叶级数和连续傅立叶变换，我们先说傅立叶级数。
傅立叶级数适用于周期性函数，它能够将任何周期性函数分解成简单震荡函数的集合（正弦函数和余弦函数），举个例子，比如说下图：
左边是一个周期函数，右边是将周期函数分解成多个简单震荡函数，所以这个周期函数用数学公式可以表达为：
这个就是我们所说的频域（FrequencyDomain），其和时域是等价的，不过是从另外一个角度去描述信号。我们把它放在一起看一下：
给出傅立叶级数的公式：
还可以将其稍作变换：
这里介绍下傅立叶变换后的基为正交基，因为有个知识点后面还会用到。
我们知道判断两个向量是否正交可以用向量点乘求和等于0来判断，这种方法我们称为点积（内积）：
与向量点积不同的是，函数是连续的，假设现在有两个函数f和g，f的周期为2n，我们也想用上述连续累加的方式来使得函数内积和向量内积的概念一致，而积分正是函数累加的概念，所以我们有：
对于上面我们说的傅立叶变换后的正交基，我们容易得到：
容易证明上述标准基为正交基。
在数学里，希尔伯特空间（HilbertSpace）是有限维欧几里得空间的一个推广，是一个完备的内积空间，其定义了一个带有内积的完备向量空间。在希尔伯空间中，一个抽象元素通常被称为向量，它可以是一个复数或者函数。傅立叶分析的一个重要目的是将一个给定的函数表示成一族给定的基底函数的和，而希尔伯特空间为傅立叶分析提供了一种有效的表述方式。
可能大家看到这里要爆炸了，不过不用担心，我们只需要记住上面「两个函数的内积形式」即可。
现实中大部分函数都是非周期的，如果涉及到非周期性函数该怎么办呢？
在介绍非周期性函数之前，我们先简单介绍下欧拉公式。
根据欧拉公式，我们可以写成：
其中，e为自然对数的底数。
所以坐标轴上的点现在有了两种表示方式：
回到正题，考虑非周期函数的傅立叶变换。
以上就是我们所说的傅立叶变换（FourierTransform，FT）。同样的我们也存在逆变换：
于是，我们便实现了将信号拆成多个正弦信号，再把正弦信号逆变换为原来信号的过程。
简单介绍下傅立叶变换的应用吧，省得看了那么多不知道他能干什么。
一个很经典的例子就是：分离、降噪。如果男生和女生一起说话，该如何分离出两者的声音呢？答案就是对这一段声音（时域）做傅立叶变换转换到频率，而男女生的声音频率不同，在频域中，低频为男生，中频为女生，高频可能为噪音，我们可以根据需要去除中频和高频的信号，并将其进行逆变换，这样便分离出了男生的声音。
我们之前提到，我们在图上定义卷积操作，遇到的困难主要是空域不具备“平移不变性”，难以定义一个合适的卷积核。要想解决这个问题，有两种思路，一种是设法直接在空域定义卷积，另一种方法是先将空域转化到谱域，在谱域上定义卷积操作，最后再将结果转化回空域。图傅立叶变换就是用于完成图的空域与谱域之间的转化。
回顾下拉普拉斯谱分析：
我们类比一下：
是不是长得非常像，所以我们也有了网络图上的傅立叶变换：
考虑矩阵乘法：
我们也可以得到傅立叶逆变换：
现在有了图傅立叶变换，又有了离散卷积操作，那么我们想：既然无法直接在空域进行卷积，可否将图信号映射到频域后再做卷积操作。
所以我们有：
第一代的卷积神经网络也就是刚刚我们给出的公式：
这和论文中给出的公式是一样的：
我们也称之为SpectralGNN。
这边补充一点，在这篇论文中，作者还给出了一个基于空域的「深度局部连接网络」（DeepLocallyConnectedNetworks），我们可以简单看一下：
每一层变换定义为：
虽然看起来很简单，但是优点在于它不需要很强的前提假设，其只需要网络具有局部邻域结构，甚至不需要很好的Embedding向量。
但这种结构下有一个很大的缺点：「没有办法实现共享参数」。
作者针对这种问题提出了我们所看到第一代图卷积神经网络。