内容简介:加入极市专业CV交流群,与同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总,行业技术交流。关注
加入极市专业CV交流群,与 1 0000+来自港科大、北大、清华、中科院、CMU、腾讯、百度 等名校名企视觉开发者互动交流!
同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总,行业技术交流。关注 极市平台 公众号 , 回复 加群, 立刻申请入群~
本文授权转自大家都叫我0号,https://zhuanlan.zhihu.com/p/124727955, 未经允许,不得二次转载。
本文简要介绍了信号处理的一些概念,介绍了图卷积的定义和各种谱方法下的GNN,最后分析了GCN过平滑的原因。大约5千余字,里面有一些公式比较复杂,可能需要手推一下~~。
1 Introduction
某的上一篇文章 图表示学习极简教程 [1] 介绍了图嵌入(Graph Embedding)、图神经网络(GNNs)的一些发展。 图表示学习极简教程 [2] 对GCN、GraphSAGE、GAT等模型进行了介绍,这些介绍都是从 空域 的角度对图卷积进行分析,也就是说GNNs每层的网络就是对邻居结点的聚合操作。这样的idea似乎很好理解,也很好想到。其实,这些方法的背后蕴含着许多信号分析的重要背景。 近日听了 ICT沈老师相关知识 [3] 的讲授后,某自认为对图卷积网络的谱分析有了更进一步的理解。下面就开始进入正题吧。 【注】:如果读者已经了解过卷积、傅里叶变换的相关概念,可以对部分章节选择性跳过。
2 卷积
【注意】:下列公式中的积分、求和上下限在遇到具体问题是会退化为具体的数字。积分上下限为无穷只是它的一般定义。
-
一维连续卷积
卷积的名字似乎听上去让人感觉有些晦涩,其实它的计算难度并不大。我们给定两个函数和,这两个函数的卷积的计算公式如下(这个公式应该小伙伴们都在概率论中见过):
-
二维连续卷积(这里不太重要,理解是怎么算的就行)
和一维卷积类似,对于多元函数,二维的连续函数卷积可以表示为:
-
一维离散卷积
将连续卷积的积分号变为求和号,就可以得到两个离散函数和一维离散卷积的公式:在此,引用一张很形象的图(结合公式)来帮助小伙伴们理解什么是一维离散卷积:
-
二维离散卷积
这是卷积神经网络(CNN)的基础,和上述的卷积类似,对两个信号、,我们定义他的二维离散卷积公式为:
这里还是借助一个动图来看看二维的卷积是如何卷的:
不难发现二维离散的卷积是将卷积核进行一个中心对称的翻转后,在进行对应位置相乘求和得到的。然而,实际上大家在CNN的计算中可以省去旋转的步骤,因为卷积核的参数是学来的。
3 傅里叶变换与卷积的另一种求法
由于一些信号在时域内部难以分析,我们将信号先变换到频域,再变换回时域,以便于我们的分析。 我们对一个时域信号函数做傅里叶变换:
有时候,我们在时域很难求卷积,我们就要利用下面的卷积公式求解:
这个公式告诉我们,时域卷积的傅里叶变换等于傅里叶变换的乘积。因此,我们可以这样求卷积:
其中,代表傅里叶变换的逆变换。
4 拉普拉斯算子
我们知道,一个二元函数的Nabla算子,可以表示为:那么梯度就可以表示为:下面定义拉普拉斯算子:
显然,我们可以把拉普拉斯算子视为二阶导数。
上述的拉普拉斯算子表示的是连续函数的拉普拉斯算子。那么离散情况下的拉普拉斯算子是什么呢? 我们可以用差分来近似我们的“导数”概念。对于一个离散的二元函数,它的拉普拉斯算子可表示为:
我们可以观察一下上面这个式子,它可以写成:
从直观上看,拉普拉斯算子体现的离散值之间的关系为:
根据拉普拉斯算子的定义和图4相关可视化表示,我们可以看出离散拉普拉斯算子描述的是 二维空间上与上、下、右邻居局部差异的和 。下一步我们就可以将这个概念迁移到图上去定义图的拉普拉斯矩阵。
5 拉普拉斯矩阵
离散拉普拉斯算子描述的是 二维空间上与上、下、右邻居局部差异的和 。迁移到图上,我们将拉普拉斯算子定义为与邻居结点特征信息差异的和,即:其中表示结点的邻居结点,这里的表示第个结点的特征(信号),简便起见,只有一维(看做数字、标量)。我们用表示结点之间的邻接关系:下面我们将扩充到所有结点集合进行表示:
其中表示结点的度数。
我们将每个结点的扩充到整个图上,得到:
这样我们就定义了图的拉普拉斯矩阵。的对角线元素对应着各个结点的度数,非对角线元素对应着图的邻接矩阵。我们给出一个 拉普拉斯矩阵的范例 [4] :
-
性质1:拉普拉斯矩阵有 个线性无关的特征向量
原因:拉普拉斯矩阵是实对称矩阵。
-
性质2:特征值非负
首先,我们定义图的总变差为矩阵的二次型:
所以是 半正定的矩阵 (证明手推一下难度不大)。所以它的特征值均为非负。
注意一下,这里存在一个特殊的特征值0,它对应的特征向量为,这个代入验证即可。
-
性质3:特征向量相互正交
是实对称矩阵,它的特征向量相互正交,构成一个特征空间。
6 图傅里叶变换与图卷积
普通的傅里叶变化公式为:其中为傅里叶基。我们有:根据广义的特征方程,我们可以看出就是拉普拉斯算子的特征向量,相当于特征值,就相当于拉普拉斯矩阵。
把傅里叶变换的定义扩充到图上。传统傅里叶变换是求信号在上的投影,图傅里叶变换求的是一个信号在正交基上的投影(这里信号是一个维的列向量,表示每一个结点仅为一个数)。我们定义 图信号的傅里叶变换 为:其中,是矩阵特征分解矩阵的转置()。这里我们注意一下,的每一个列向量为的一个特征向量,的每一个行向量为的一个特征向量。这样与的乘积就实现了一个信号在正交基上的投影,图傅里叶变换完成。
接下来我们就可以很容易地实现傅里叶逆变换:这里用到了矩阵分解的性质:。
在信号处理中我们有如下的卷积公式:
应用到图上,我们定义卷积公式:
其中表示 哈达玛积 ,就是向量的对应元素相乘(不是矩阵相乘)。我们把其中的向量写成对角阵的形式,这样我们就可以把哈达玛积写成是 矩阵相乘 的形式了,即:
我们将对角阵用来表示:其实这里的对角阵就是可供学习的卷积核了。
终于!!!把图信号的卷积定义完了!
7 基于谱方法的各种Net
7.1 Spectral Graph CNN
根据上述的定义,我们知道了如何定义图上的卷积操作。那么网络的前传也就可以定义了:
其中:
-
在此之前我们讨论的都只有一个特征信息( 通道 )。这里增加了通道数,,分别表示第层和第层的通道数。
-
表示第层的可供学习的卷积核,是一个对角阵。
-
表示具有个通道(信号)的个结点
该模型存在的问题主要有三:
-
模型不是spatial localization(局部连接)的;
-
依赖矩阵分解,前传的时候多次用到矩阵乘法,计算代价大;
-
卷积核的规模参数收到图规模的控制,特别是对大图而言。
7.2 ChebNet
对于上述的卷积核,我们可以使用阶多项式进行拟合:
那么图卷积就变成了:
这样的操作就将参数个数减少到个,同时也不需要进行矩阵的分解了。同时就算复杂度大大下降。注意,这里的的次方就体现了局部相关特性,这和邻接矩阵次幂的含义类似,代表着阶可达。 ChebNet 引入了切比雪夫多项式对进行拟合。切比雪夫多项式的递归定义为:
的阶近似为: 其中 ,是最大的特征值,这个操作的意义是将特征值调整到的范围中,因为我们知道拉普拉斯矩阵的特征值非负,且有最小值为0(稍加推导就可以得到范围了)。这个操作可以防止梯度爆炸。
现在我们的图卷积公式就可以被进一步写成是:
下面介绍公式之间是如何进行转换的。
-
的证明:
只要证明:对上述式子应用数学归纳法:
-
或时,根据切比雪夫多项式的定义,。
-
假设小于的时候都成立。
-
的转换:
由此我们就得到了新的卷积公式:可以看出,ChebNet解决了7.1中Spectral Graph CNN存在的3个问题。
7.3 平时看到的GCN——ChebNet的一阶近似
我们对ChebNet进行一阶近似,即。我们可以得到下面的公式:
对进行正则化,得到正则化后的表示:正则化后的拉普拉斯矩阵特征值不超过2,所以将的最大特征值近似为为2,。将带入,,可以转换成:
其中,值得注意的是,这里的是一个标量。我们将:,分别表示输入输出的通道数。网络层与层时间的传递公式可以表示为:在这个公式中,结合上一篇文章 图表示学习极简教程 [5] ,我们可以看出这个模型是对邻居结点的聚合(1-hop),当网络加深到K层的时候就会将聚合关系扩充到K跳。
8 GCN——一个低通滤波器
8.1 为什么叫它低通滤波器?
我们有(这里其实有一点不太严谨的地方,不影响阅读,详细可参考一下 从 Graph Convolution Networks \(GCN\) 谈起 [6] )。我们知道, 特征值的范围 是0~2。所以有:可以看出,它的 特征值范围 为。在信号与系统中,我们可以将信号转换到频域,通过频率响应函数滤波,再将信号转换到时域完成滤波的操作。这里的频率响应函数为。不难看出,它对信号进行了低通滤波。
8.2 GCN的大问题——Over Smoothing
根据实验,我们的GCN一直无法像CNN那样将网络做深,很大的一个原因就是 过平滑 (Over smoothing)。那么这种现象为什么会产生?
在GCN堆叠层的过程中,矩阵被乘了次。我们看看它展开会是什么样子:
其中的只有在当时,有。其余情况下绝对值都不超过1。所以有:
这时:
这里有:(表示全1向量)。如果在往下乘,会出现一项:
信号在往下乘的时候就会出现处处相等的情况,所有的结点特征就会趋于一致,过平滑由此产生。
另外,有一种更为容易理解的方法。一层的GCN是对一阶邻居信息的聚合,k层对应的就是k-hop。相信大家听过 六度空间理论 ,几乎每一个结点的聚合都可以做到很快就把几乎全图进行覆盖。
联系我:Data_LH_ChenAToutlook.com.(AT改为@) 炼丹时间半年多,初涉该领域,如有理解不当或错误的地方欢迎指正。
一些很优秀的参考资料(可下滑)
[1]图表示学习极简教程: https://zhuanlan.zhihu.com/p/112295277
[2]图表示学习极简教程: https://zhuanlan.zhihu.com/p/112295277
[3]ICT沈老师相关知识: https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1zp4y117bB
[4]拉普拉斯矩阵的范例: https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/Laplacian_matrix
[5]图表示学习极简教程: https://zhuanlan.zhihu.com/p/112295277
[6]从 Graph Convolution Networks (GCN) 谈起: https://zhuanlan.zhihu.com/p/60014316
[7]图神经网络在线研讨会2020丨图表示学习和图神经网络的最新理论进展和应用探索: https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1zp4y117bB
[8]Graph Convolutional Network图卷积网络基础理论: https://zhuanlan.zhihu.com/p/100250297
[9]深入浅出图神经网络: https://link.zhihu.com/?target=https%3A//detail.tmall.com/item.htm%3Fspm%3Da230r.1.14.1.21e24bf49k0WwP%26id%3D610178053512%26cm_id%3D140105335569ed55e27b%26abbucket%3D9
[10]图卷积网络 GCN Graph Convolutional Network(谱域GCN)的理解和详细推导: https://link.zhihu.com/?target=https%3A//blog.csdn.net/yyl424525/article/details/100058264
[11]拉普拉斯矩阵: https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/Laplacian_matrix%23Incidence_matrix
[12]从 Graph Convolution Networks (GCN) 谈起: https://zhuanlan.zhihu.com/p/60014316
[13]Convolutional Neural Networks on Graphswith Fast Localized Spectral Filtering: https://link.zhihu.com/?target=https%3A//arxiv.org/abs/1606.09375
[14]Wavelets on Graphs via Spectral Graph Theory: https://link.zhihu.com/?target=https%3A//arxiv.org/abs/0912.3848
[15]Spectral Networks and Deep Locally ConnectedNetworks on Graphs: https://link.zhihu.com/?target=https%3A//arxiv.org/abs/1312.6203
[16]SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS: https://link.zhihu.com/?target=https%3A//arxiv.org/pdf/1609.02907.pdf
[17]Graph Convolutional Networks: https://link.zhihu.com/?target=https%3A//tkipf.github.io/graph-convolutional-networks/
-END -
*延伸阅读
极市独家福利
40万奖金的AI移动应用大赛,参赛就有奖,入围还有额外奖励
添加极市小助手微信 (ID : cv-mart) ,备注: 研究方向-姓名-学校/公司-城市 (如:AI移动应用-小极-北大-深圳),即可申请加入 AI移动应用极市技术交流群 ,更有 每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、 干货资讯汇总、行业技术交流 , 一起来让思想之光照的更远吧~
△长按添加极市小助手
△长按关注极市平台,获取 最新CV干货
觉得有用麻烦给个在看啦~
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 图卷积实战——文本分类
- 详解基于图卷积的半监督学习(附代码)
- 论文盘点:基于图卷积GNN的多目标跟踪算法解析
- 何时能懂你的心——图卷积神经网络(GCN)
- 何时能懂你的心:图卷积神经网络 (GCN)
- 图卷积网络到底怎么做,这是一份极简的Numpy实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Head First jQuery
Ryan Benedetti , Ronan Cranley / O'Reilly Media / 2011-9 / USD 39.99
Want to add more interactivity and polish to your websites? Discover how jQuery can help you build complex scripting functionality in just a few lines of code. With Head First jQuery, you'll quickly g......一起来看看 《Head First jQuery》 这本书的介绍吧!