【图神经网络】数学基础篇

1. 基本概念

1.1 数据分类

欧几里德结构

能够将数据转换到欧几里德空间的便是欧几里德结构化数据，如时间序列数据，图像数据，上图则是图像数据的一个例子

我们可以清晰地看到，上图的图像数据“排列整齐”，所以可以清晰地定义“距离”这个概念。

非欧结构数据

常见的非欧结构化数据有社交网络，基因，分子，大脑等等。他们的共同特点是数据“排列不整齐”，对于数据中的某个点，难以定义出其邻居节点出来，或者是不同节点的邻居节点的数量是不同的。对于非欧结构化数据，我们可以引入图来表示学习。

1.2 梯度

直观理解 ：

首先我们来回顾一下高等数学中导数的概念，一个函数在某一点的导数是这个函数在这一点附近的变化率。如果这个变化率属于某指定方向的，则是方向导数。

假设我们现在在山的某处，想要下山，天快黑了，天黑前不能下山可能会有危险，但是又不知道哪条才是最佳下山路径，该怎么办呢？这时候便到了梯度下降出场。

通过梯度计算，我们能找到最快下山的道路。梯度是一个向量，方向与最大方向导数的方向一致，模是方向导数的最大值。也就是说，只要知道了梯度，或许就能找到最快下山的路。

是下一步到的地方，是现在所在的地方，是步长，不能不宜过小或过大，太小走到天黑都还没下山，太大一脚下悬崖。

那么梯度的计算公式是怎么来的呢？这个时候就到了泰勒公式出场了

梯度下降法使用了一阶泰勒展开式：

因为我们的目标是下山，所以下一步肯定在现在所在地方的下面，用数学语言表示就是

为了满足这个要求，也得<0

为了满足上面的要求，我们设，可得，要大于0,前面加负号，是因为我们要下山(负梯度)，必定小于0，要求满足了

于是就有了

只要不断迭代计算和就可以沿着梯度的方向下山了。

形式定义 ：

设二元函数，在平面区域D上具有一阶连续偏导数，则对于每一个点P（x，y）都可定出一个向量

该函数就称为函数在点P（x，y）的梯度，记作

1.3 散度

散度 “” （divergence）可用于表针空间中各点矢量场发散的强弱程度，物理上，散度的意义是场的有源性。当，表示该点有散发通量的正源（发散源）；当表示该点有吸收能量的负源（洞或汇）；当，表示该点无源。

举个例子形象的理解，将太空中各个点的热辐射强度向量看作一个向量场，而辐射源太阳会不断向外辐射，所以其散度是大于0的，散得越多越快则散度越大。

1.4 欧拉公式

e 为自然对数的底数

2. 经典傅里叶变换

介绍完几个基础概念，可以进入傅里叶的坑了。那么傅里叶变换是干嘛的呢，简单说就是将信号从时域转化为频域

时域

随时间变换的信号则称这个信号为时域信号

频域

对信号进行时域分析时，有时一些信号的时域参数相同，但并不能说明信号就完全相同。因为信号不仅随时间变化，还与频率、相位等信息有关，这就需要进一步分析信号的频率结构，并在频率域中对信号进行描述。动态信号从时间域变换到频率域主要通过傅立叶级数和傅里叶变换。

时域和频域只是看问题的两个不同角度，下面的动图可以形象的表述：

傅里叶级数

傅里叶级数适用于任何周期函数，其作用是把一个周期函数表示成三角级数。简谐振动，单摆振动等运动都是常见的可以用周期函数表示的运动，如，但是现实中的周期信号通常是比较复杂的，那么是不是有什么方法可以将周期信号转换为三角函数？

这时候就到傅里叶出场了，给出傅里叶级数公式：

对上式进行三角变换：

便是正交基下的向量。上述公式可以表达为

正交的概念在这里很重要，正交就是两个向量的内积为零。向量如此，那函数该怎么表示和向量内积同样的概念呢，这时候就要用到积分的思想了。

将函数的连续分割成多个部分，每个部分作为一个向量，当分割的区间无限小的时候，向量的内积就可以由积分表示了：

可得

然后我们利用正交的性质，就可以很容易得出傅里叶级数的系数了。

例如我们要求，只需要两边都乘，因为正交性，其他频率都会被化掉。

一般地，有：

傅里叶级数只适用于周期函数，那么对于非周期函数呢？

傅里叶变换

首先来看一下大体思路：

1.将非周期函数看作周期无穷大的函数

2.当时，频域图变为连续的曲线

利用欧拉公式，再对函数做内积，便可得到傅里叶变换（具体推导展开比较多，此处略）

其中是一组正交基。傅里叶正变换本质是求线性组合的系数。而利用正交的性质，我们可以很容易求出对应的系数。

相应的，傅里叶变换存在逆变换：

傅里叶逆变换本质是把一个函数表示成了若干个正交基函数的线性组合

3. 图信号处理

3.1 基本概念

图信号

给定图，表示图中的节点集合，假设其长度为，图信号则是一种描述的映射，表示成向量的形式：，其中表示的是节点上的信号强度

蓝色代表信号强度，这里的图信号只有一个通道，实际的图节点可能有很多通道

下面用一个图来解释图的各类矩阵

度矩阵

度矩阵是对角阵，对角上的元素为各个顶点的度。顶点的度表示和该顶点相关联的边的数量。

邻接矩阵

邻接矩阵表示顶点间关系，是n阶方阵（n为顶点数量）。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。无向图邻接矩阵是对称矩阵，而有向图的邻接矩阵不一定对称。顶点之间有连接关系的在矩阵对应位置值为1。

关联矩阵

关联矩阵用一个矩阵来表示各个点和每条边之间的关系。

对于一个无向图G,表示在关联矩阵中点i和边j之间的关系。若点i和边j之间是连着的，则= 1. 反之，则= 0. 例如：列是边，行是点，每一行值的总和为该点的度,每一列的和为2

图函数的梯度

设图函数，关联矩阵，则图函数的梯度定义为：

3.2 拉普拉斯矩阵

拉普拉斯矩阵

是一个对角矩阵，表示的是节点的度

其中D是度(出度入度)矩阵，A是图的邻接矩阵。矩阵元素与图节点的信号值无关，而只与图的结构，即节点连接关系有关。

正则化形式

拉普拉斯矩阵是怎么来的呢？要从拉普拉斯算子说起：

拉普拉斯算子

拉普拉斯算子（Laplace Operator）是 n 维欧几里得空间中的一个二阶微分算子，函数的拉普拉斯算子被定义为函数的梯度的散度。

拉普拉斯算子也是笛卡儿坐标系中的所有非混合二阶偏导数之和：

拉普拉斯算子的意义是什么？

先从定义上简单理解，梯度的散度，某个点各个方向的梯度形成一个向量场，再结合定义是梯度的散度，结论就是拉普拉斯算子衡量了在空间中的每一点处，该函数梯度是倾向于增加还是减少

再从计算上看：

考虑一维空间的情况：

上式可理解为二阶导数近似等于其二阶差分。二阶导数等于其在所有自由度上微扰之后获得的增益。一维函数的自由度为2，分别是+1和-1两个方向。

算子退化到二维空间的情况：

上式是边缘检测中常用的拉普拉斯卷积核

由上图可以直观看到，拉普拉斯卷积核描述了中心像素点与其他四个方向的关系，此处自由度为4，如果考虑对角线的话，自由度为8。可以归纳一个结论是： 拉普拉斯算子是所有自由度上进行微小变化后所获得的增益

将拉普拉斯算子推广到图中，对于有n个节点的图，其自由度为n，邻接矩阵为A。在上面图信号处理基本概念处有定义，图表示成向量的形式：，拉普拉斯算子在图信号中怎么表示中心节点与邻居节点的差异呢？（也可以理解为节点i变化到节点j增益），即，考虑加权图的情况，则为，当节点i和节点j不直接相邻，

由拉普拉斯矩阵的推导可以得出一个结论：拉普拉斯矩阵是一个反映图信号局部平滑度的算子。

拉普拉斯矩阵中的第行实际上反应了第个节点在对其他所有节点产生扰动时所产生的增益累积。

另外还有一个有趣的地方是（证明略），也就是说，拉普拉斯矩阵是图上的拉普拉斯算子。有了这个结论，再看回上一句所说的增益累积，从拉普拉斯算子的定义（梯度的散度）上理解，就更加直观了。

下面是拉普拉斯矩阵的一些性质：

• 拉普拉斯矩阵是半正定矩阵

• 特征值中0出现的次数就是图连通区域的个数

• 最小特征值是0，因为拉普拉斯矩阵每一行的和均为0

• 最小非零特征值是图的代数连通度

• 拉普拉斯矩阵是图上的一种拉普拉斯算子

由拉普拉斯矩阵为半正定矩阵可以定义其二次型^[5]

我们称为图信号的总变差，其将各边上信号的差值求和，相当于刻画了图信号整体的平滑度。

3.3 拉普拉斯的谱分解

特征分解也叫谱分解，即把矩阵分解成特征值和特征向量表示的矩阵积

为特征值构成的对角矩阵，为特征向量构成的正交矩阵。

又因为正交矩阵的逆等于正交矩阵的转置，可得

4. 图傅里叶变换

我们要对图信号进行傅里叶变换，参考前面所讲的经典傅里叶变换，自然就可以想到要找到一组正交基。

先来回顾一下傅里叶变换

其中基为，是频率，是振幅。

对于任意一个图上 的信号，其图傅里叶变换为:

其中表示第个特征向量的第个分量。特征向量也叫做傅里叶基，为频率，结果为一组傅里叶系数。傅里叶系数本质上是图信号在傅里叶基上的投影，衡量了图信号与（特征向量）傅里叶基之间相似度。

用矩阵形式可以计算出所有的傅里叶系数：

因为是正交矩阵，所以有：

逆图傅里叶变换表明了图上任意一个图信号都可以被表征成傅里叶基的线性加权，权重即傅里叶基上的傅里叶系数。

有了图傅里叶变换定义后，再改写一下总变差：

是特征值，是图信号对应的傅里叶系数，所以上式表达的是总变差相当于权重为图的傅里叶系数的平方的所有特征值的线性组合。

4.2 特征值的意义

将拉普拉斯矩阵的特征值从小到大排列，根据拉普拉斯的谱分解，特征值越高，对应的特征向量（傅里叶基）变化越快，因此可以将特征值等价成频率。

图信号的所有傅里叶系数合起来作为信号的频谱，也可以用逆图傅里叶变换将频谱推导出时域的图信号。

上图从左到右总变差分别为 0.14   1.31  1.81

本人刚入门图神经网络，以上为最近一周的学习笔记，有些许混乱见谅，如果有错误，欢迎批评指出～

参考资料

[1]  Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs[C]//International conference on machine learning. 2016: 2014-2023.

[2] 【GNN】万字长文带你入门 GCN

[3] https://baike.baidu.com/item/%E9%A2%91%E5%9F%9F

[4] https://zhuanlan.zhihu.com/p/41455378

[5] https://www.zhihu.com/question/21665935

[6] https://zhuanlan.zhihu.com/p/81502804

[7] Discrete Regularization on Weighted Graphs for Image and Mesh Filtering

[8] https://zhuanlan.zhihu.com/p/272469300

[9] Shuman D I , Narang S K , Frossard P , et al. The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains[J]. IEEE Signal Processing Magazine, 2013, 30(3):83-98.

[10] Sébastien Bougleux, Abderrahim Elmoataz, Mahmoud Melkemi. Discrete Regularization on Weighted Graphs for Image and Mesh Filtering. 1st International Conference on Scale Space and Variational Methods in Computer Vision (SSVM 2007), May 2007, Ischia, Italy. pp.128-139, ff10.1007/978-3-540- 72823-8_12ff. ffhal-00333374f