图卷积神经网络的数学原理详解——笔记（更新中）

原讲解视频地址，本篇是对该视频的笔记。感谢视频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}$

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

$2\overrightarrow{x}^T\overrightarrow{x}\geq \overrightarrow{x}^TL_{sym}\overrightarrow{x}$

$2\geq \frac{\overrightarrow{x}^TL_{sym}\overrightarrow{x}} {\overrightarrow{x}^T\overrightarrow{x}}$

由上述证明我们得出 $L_{sym}$ 的瑞利熵是 $\leq2$ 的。因此 $L_{sym}$ 的特征值也是恒 $\leq2$ 的。

3. 傅里叶变换

傅里叶变换其实就是“去研究同一个事物在不同的域之间不同的视角”是怎样的，以及在不同的域之间进行变换。

最后编辑于：2021.08.27 21:55:32

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,496评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,407评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,632评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,180评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,198评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,165评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,052评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,910评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,324评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,542评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,711评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,424评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,017评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,668评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,823评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,722评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,611评论 2赞 353