【强基固本】GNN | GCN-谱图卷积从零开始

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—可乐不加冰

地址：https://zhuanlan.zhihu.com/p/404867066

01

Spectral-GNN（谱图卷积神经网络）

最近在学习了基本的CNN和RNN以后做了药物分子预测的课题，其中最主要使用到的就是图神经网络GNN。图神经网络虽然用到了许多CNN和RNN的思路，但是也用到了傅里叶变换和图论等相关的知识，这些相关知识大多还较为复杂。麻烦的是，绝大多数机器学习或深度学习的课程中都没有涉及GNN的内容，因此我写下这篇博文，供像我一样数学基础较差的同学学习。

02

傅里叶变换的直观理解

傅里叶变换是<信号与处理>课程当中必学的内容， 但是作为计算机系的同学可能绝大多数并没有接触过。甚至会因为平时听到身边的同学抱怨傅里叶变换有多么难，而产生了畏难心理，只因为傅里叶变换而放弃了学习谱卷积GNN。但是对于Spectral-GNN来说，傅里叶变换是绕不过去的，学习者比如迎难而上。
这部分数学推导的详细内容在博文https://zhuanlan.zhihu.com/p/400042839中，本文截取其直观理解部分。

这是一个典型的音频波形，在初中物理中我们已经学过：

波形的纵轴表示振幅，横轴表示时间，波形的疏密表示频率。

换言之，这张图是 振幅-时间 图像，而 频率 或 音色 之类的其他声音信息只能通过图的形状体现出来。

当我们希望让声音变小后再输出时，我们只需要 读取声音信号，沿着 y 轴压缩，再输出 即可。

但是，当我们希望 让声音频率降低后再输出 时，就遇到了很大的问题，因为我们如果沿x轴压缩波形，就会导致输出声音的时间变短，即本来10s的声音在频率上升以后可能只有5s，这会导致很大的问题（想想倍速播放）

当我们希望 强化声音的低音区后再输出 时，我们无法在 振幅-时间 图像上完成这一操作，因为在这个图中各个频率的声音波形杂糅在了一起（波的合成）。

我们希望能够通过采集到的 振幅-时间 图像，得到 频率-时间 图像，如下所示

这时候我们就可以任意处理频率了。例如：如果只要保留低音部分，那就把 频率大于某一阈值的部分删除 即可。

傅里叶变换就是将同一个波从以时间为横坐标转化为以频率为横坐标的变换，或者说将一个在时域的周期函数转换到频域，这种变换的反向就称为傅里叶逆变换。

(半)正定矩阵和特征分解的定义

这部分知识主要来这篇博文：https://zhuanlan.zhihu.com/p/44860862，本部分内容引用了大段原文内容。

下面我们需要直观理解一下半正定矩阵和正定矩阵的一些性质、特征分解。

这一部分是很有必要的，因为在图卷积中需要使用 图的拉普拉斯矩阵 来表示一张图，并且根据 拉普拉斯矩阵是一个半正定矩阵 这个性质对它进行特征分解，然后再进行图卷积。

在学习半正定矩阵前，先理解一些向量内积的表示。

内积

   和    都是    维列向量，则    是一个    维行向量，    计算的是向量    和向量    的内积：

半正定矩阵

【定义1-正定矩阵】给定一个大小为    的实对称矩阵 A，若对于任意长度为    的非零向量    ，有    ，则矩阵 A 是一个正定矩阵

【定义2-半正定矩阵】给定一个大小为    的实对称矩阵 A，若对于任意长度为    的非零向量    ，有    ，则矩阵 A 是一个半正定矩阵

特征分解

半正定矩阵    一定可写为如下形式：

其中    是一组 正交基 ，他们都是 列向量。

03

GCN 谱图卷积神经网络

图的拉普拉斯矩阵和拉普拉斯算子

【定义-邻接矩阵】   满足   当且仅当结点    到结点    之间有一条边；否则，   

【定义-度矩阵】    为一个对角阵，    。即    的第    个对角线元素是结点    的度。

【定义-拉普拉斯矩阵】   

图源：http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML2020/GNN.pdf

对于上图来说，度矩阵 和 邻接矩阵 分别如下所示。我们可以看到，只要图是无向图，邻接矩阵一定是对称方阵；在任何情形下，度矩阵都一定是对称方阵。

那么二者相减，拉普拉斯矩阵    一定是 对称方阵

看到这里你可能会疑惑，为什么要强调  是一个对称方阵呢？ 因为对称方阵一定可以进行特征分解，即    一定可以写成如下形式：

谱图理论——GCN的基础

GCN的正向传播公式为：   

图源：http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML2020/GNN.pdf

其中:

1.   是 列向量， 是    的特征值    对应的 经过归一化（每一个元素除以向量长度的平方根，让向量长度为1） 的特征向量，所以    是正交矩阵，故而   

2.    与    是两个域变换矩阵：

3.    先将    变换到另一个域（频域）

4.    为对    在频域中形式    进行的某一种操作（AI中称“卷积”，信号处理中称“过滤(filter)"）

5.    将频域向量    变换回原来的域

6.    为一个对角矩阵，    就是待学习的参数。此操作将    的缩放    倍。

正向传播的过程

1. 第一步：    ，将点域向量    变换到频率向量   

2. 第二步：    ，将    的第 i 个元素进行    倍的缩放操作

3. 第三步：    ，将经过缩放后的频域向量    变换回点域向量   

4. 第四步：将    经过全连接层变成与 label 形状相同的向量，并计算 loss

为何 左乘    或    表示域变换？

我们知道，属于不同特征值的特征向量相互正交（垂直），因此    构成了某一个    维空间的一组正交基。

事实上，这一组基所张成的空间，就对应这傅里叶变换的 频域

对于任意一个属于 点域 的向量    ，（点域 指    代表了点    的某些性质），那么    可以理解将    变换到频域

   是两个向量的内积，表示 把    投影到基    的方向上，    就是把  向基    做投影。

为何    张成的空间可以看作频域？

考虑上图，坐标轴上有 n 个固定点，对应于图中的n个结点。假设有一个简谐波在坐标轴上分布，那么波的频率越高，相邻结点间的波差异越大，即 n 个结点的波序列越不平滑。

而波的不平滑程度可以通过 拉普拉斯算子    来反映：

假设   是图的特征向量（即    代表了结点    的某一特征），将拉普拉斯算子加在    上以后得到

表示 图中任意两个结点特征值的差的平方和，因为    衡量   与    两点的差异大小，所以    能够反映整个序列的平滑程度

我们将拉普拉斯算子作用在某一个特征向量    上，因为    经过归一化，所以下式恒成立：

我们可以观察到    与    的一致性：特征值    越大，则    越不平滑。如果 我们将    视作波的频率，那么    就表示频率为    的波在各个结点上的分配。

例如上图四个特征值对应的特征向量，对于点域向量    ，它属于频率    的成分大小为：   

注意：    的所有元素之和不等于0，是因为我们对    进行了    正则化而非    正则化。

此处之所以说如果将    看作频率，因为这只是一种自洽理解方式，而信号处理当中的使用傅里叶变换来转换的是实实在在的波，二者是不同的。

计算 "L 的特征向量"或 "L 的多项式"代价太高，怎么办？

GCN 对图进行域变换然后再进行卷积的思想在上一部分已经解释清楚了。这部分数学性比较强，只需要知道大致思路即可，尤其是不必对切比雪夫多项式太过纠结。只要知道这种近似方式 通过 递推 计算来降低计算代价，从而提高性性能 即可。另外，我们根据特征分解的性质，来避免对   进行特征分解从而提高性能。

虽然    是矩阵    （对角线元素为特征值） 的一个任意函数，但是由于    是对角阵且    是正交阵，    可以看作    的函数：

然后我们可以对    进行    阶切比雪夫多项式（Chebyshev polynomial） 近似：

这是在 ChebNet 中提出的计算方法，GCN则则通过取    来进一步简化计算。

切比雪夫多项式为：

我们认为    是    的   次式， 则有：

注意：此处的    并不同于上一部分的    。前面的    表示第    个对角线元素，此处    表示    的系数。

上式的    阶切比雪夫近似为：

但是，这样的近似依然要求我们进行特征分解

为了不进行特征分解，最终的近似结果写成如下形式：

插图图源

http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML2020/GNN.pdf

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！