全面入门:图卷积网络(GCN)的谱分析

栏目: IT技术 · 发布时间: 4年前

内容简介:加入极市专业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 卷积

【注意】:下列公式中的积分、求和上下限在遇到具体问题是会退化为具体的数字。积分上下限为无穷只是它的一般定义。

  • 一维连续卷积

卷积的名字似乎听上去让人感觉有些晦涩,其实它的计算难度并不大。我们给定两个函数和,这两个函数的卷积的计算公式如下(这个公式应该小伙伴们都在概率论中见过):

全面入门:图卷积网络(GCN)的谱分析

图1 连续卷积动图

  • 二维连续卷积(这里不太重要,理解是怎么算的就行)

和一维卷积类似,对于多元函数,二维的连续函数卷积可以表示为:

  • 一维离散卷积

将连续卷积的积分号变为求和号,就可以得到两个离散函数和一维离散卷积的公式:在此,引用一张很形象的图(结合公式)来帮助小伙伴们理解什么是一维离散卷积:

全面入门:图卷积网络(GCN)的谱分析

图2 一维离散卷积示意图

  • 二维离散卷积

这是卷积神经网络(CNN)的基础,和上述的卷积类似,对两个信号、,我们定义他的二维离散卷积公式为:

这里还是借助一个动图来看看二维的卷积是如何卷的:

全面入门:图卷积网络(GCN)的谱分析

图3 二维离散卷积

不难发现二维离散的卷积是将卷积核进行一个中心对称的翻转后,在进行对应位置相乘求和得到的。然而,实际上大家在CNN的计算中可以省去旋转的步骤,因为卷积核的参数是学来的。

3 傅里叶变换与卷积的另一种求法

由于一些信号在时域内部难以分析,我们将信号先变换到频域,再变换回时域,以便于我们的分析。  我们对一个时域信号函数做傅里叶变换:

有时候,我们在时域很难求卷积,我们就要利用下面的卷积公式求解:

这个公式告诉我们,时域卷积的傅里叶变换等于傅里叶变换的乘积。因此,我们可以这样求卷积:

其中,代表傅里叶变换的逆变换。

4 拉普拉斯算子

我们知道,一个二元函数的Nabla算子,可以表示为:那么梯度就可以表示为:下面定义拉普拉斯算子:

显然,我们可以把拉普拉斯算子视为二阶导数。

上述的拉普拉斯算子表示的是连续函数的拉普拉斯算子。那么离散情况下的拉普拉斯算子是什么呢? 我们可以用差分来近似我们的“导数”概念。对于一个离散的二元函数,它的拉普拉斯算子可表示为:

我们可以观察一下上面这个式子,它可以写成:

从直观上看,拉普拉斯算子体现的离散值之间的关系为:

全面入门:图卷积网络(GCN)的谱分析

图4 拉普拉斯算子的直观表示

根据拉普拉斯算子的定义和图4相关可视化表示,我们可以看出离散拉普拉斯算子描述的是 二维空间上与上、下、右邻居局部差异的和 。下一步我们就可以将这个概念迁移到图上去定义图的拉普拉斯矩阵。

5 拉普拉斯矩阵

离散拉普拉斯算子描述的是 二维空间上与上、下、右邻居局部差异的和 。迁移到图上,我们将拉普拉斯算子定义为与邻居结点特征信息差异的和,即:其中表示结点的邻居结点,这里的表示第个结点的特征(信号),简便起见,只有一维(看做数字、标量)。我们用表示结点之间的邻接关系:下面我们将扩充到所有结点集合进行表示:

其中表示结点的度数。

我们将每个结点的扩充到整个图上,得到:

这样我们就定义了图的拉普拉斯矩阵。的对角线元素对应着各个结点的度数,非对角线元素对应着图的邻接矩阵。我们给出一个 拉普拉斯矩阵的范例 [4]

全面入门:图卷积网络(GCN)的谱分析

图5 拉普拉斯矩阵示例

  • 性质1:拉普拉斯矩阵有 个线性无关的特征向量

原因:拉普拉斯矩阵是实对称矩阵。

  • 性质2:特征值非负

首先,我们定义图的总变差为矩阵的二次型:

所以是 半正定的矩阵 (证明手推一下难度不大)。所以它的特征值均为非负。

注意一下,这里存在一个特殊的特征值0,它对应的特征向量为,这个代入验证即可。

  • 性质3:特征向量相互正交

是实对称矩阵,它的特征向量相互正交,构成一个特征空间。

6 图傅里叶变换与图卷积

普通的傅里叶变化公式为:其中为傅里叶基。我们有:根据广义的特征方程,我们可以看出就是拉普拉斯算子的特征向量,相当于特征值,就相当于拉普拉斯矩阵。

把傅里叶变换的定义扩充到图上。传统傅里叶变换是求信号在上的投影,图傅里叶变换求的是一个信号在正交基上的投影(这里信号是一个维的列向量,表示每一个结点仅为一个数)。我们定义 图信号的傅里叶变换 为:其中,是矩阵特征分解矩阵的转置()。这里我们注意一下,的每一个列向量为的一个特征向量,的每一个行向量为的一个特征向量。这样与的乘积就实现了一个信号在正交基上的投影,图傅里叶变换完成。

接下来我们就可以很容易地实现傅里叶逆变换:这里用到了矩阵分解的性质:。

在信号处理中我们有如下的卷积公式:

应用到图上,我们定义卷积公式:

其中表示 哈达玛积 ,就是向量的对应元素相乘(不是矩阵相乘)。我们把其中的向量写成对角阵的形式,这样我们就可以把哈达玛积写成是 矩阵相乘 的形式了,即:

我们将对角阵用来表示:其实这里的对角阵就是可供学习的卷积核了。

终于!!!把图信号的卷积定义完了!

7 基于谱方法的各种Net

7.1 Spectral Graph CNN

根据上述的定义,我们知道了如何定义图上的卷积操作。那么网络的前传也就可以定义了:

其中:

  • 在此之前我们讨论的都只有一个特征信息( 通道 )。这里增加了通道数,,分别表示第层和第层的通道数。

  • 表示第层的可供学习的卷积核,是一个对角阵。

  • 表示具有个通道(信号)的个结点

该模型存在的问题主要有三:

  • 模型不是spatial localization(局部连接)的;

  • 依赖矩阵分解,前传的时候多次用到矩阵乘法,计算代价大;

  • 卷积核的规模参数收到图规模的控制,特别是对大图而言。

7.2 ChebNet

对于上述的卷积核,我们可以使用阶多项式进行拟合:

那么图卷积就变成了:

这样的操作就将参数个数减少到个,同时也不需要进行矩阵的分解了。同时就算复杂度大大下降。注意,这里的的次方就体现了局部相关特性,这和邻接矩阵次幂的含义类似,代表着阶可达。 ChebNet 引入了切比雪夫多项式对进行拟合。切比雪夫多项式的递归定义为:

的阶近似为: 其中 ,是最大的特征值,这个操作的意义是将特征值调整到的范围中,因为我们知道拉普拉斯矩阵的特征值非负,且有最小值为0(稍加推导就可以得到范围了)。这个操作可以防止梯度爆炸。

现在我们的图卷积公式就可以被进一步写成是:

下面介绍公式之间是如何进行转换的。

  • 的证明:

只要证明:对上述式子应用数学归纳法:

  1. 或时,根据切比雪夫多项式的定义,。

  1. 假设小于的时候都成立。

  • 的转换:

由此我们就得到了新的卷积公式:可以看出,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/

极市独家福利

40万奖金的AI移动应用大赛,参赛就有奖,入围还有额外奖励

全面入门:图卷积网络(GCN)的谱分析

添加极市小助手微信 (ID : cv-mart) ,备注: 研究方向-姓名-学校/公司-城市 (如:AI移动应用-小极-北大-深圳),即可申请加入 AI移动应用极市技术交流群 ,更有 每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、 干货资讯汇总、行业技术交流 一起来让思想之光照的更远吧~

全面入门:图卷积网络(GCN)的谱分析

△长按添加极市小助手

全面入门:图卷积网络(GCN)的谱分析

△长按关注极市平台,获取 最新CV干货

觉得有用麻烦给个在看啦~   


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Head First jQuery

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》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具