GCN过平滑问题-程序员宅基地
简介
尽管GCN为图数据的学习带来了一种全新的方式，然而Li Q等人在Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning中、Xu K等人在Representation Learning on Graphs with Jumping Knowledge Networks中都明确指出了GCN模型无法像视觉任务中的CNN模型一样深度堆叠，一旦使用多层GCN，相关任务的效果会急剧下降，这使得某些任务中，GCN的能力非常有限。
实验测试
我在上次的节点分类任务基础上，不断增加GCN，实验结果如下图所示（从左至右、从上至下GCN层数逐渐增加）。可以看到，2-3层的GCN区分效果最好，5-6层的GCN，7种节点已经逐渐混合在一起，很难区分了。
上面这个例子，可以发现，在使用多层GCN之后，节点的区分性越来越差，节点的表示向量趋于一致，这就使得以GCN为基础的后续学习任务难以进行。这个现象称为多层GCN的过平滑（Over-smooth）问题。
理论解释
众所周知，GCN可以看作是一个低通滤波器（具体论证见Revisiting Graph Neural Networks: All We Have is Low-Pass Filters这篇文章），这种特性会造成信号变得更加平滑，这是GCN的内在优势，然而，过犹不及，多次进行这种信号平滑操作会使得信号趋于一致，这就丧失了节点特征的多样性。过平滑问题的理解可以从频域和空域两个角度出发，下面分别展开。
频域角度
从GCN的频率响应函数 p ( λ ) = 1 − λ ~ i p(\lambda)=1-\tilde{\lambda}_{i} p(λ)=1−λ~i中能看得明白些。
lim k → + ∞ L ~ s y m k = lim k → + ∞ ( I − L ~ s ) k = lim k → + ∞ ( V ( 1 − Λ ~ ) V T ) k = lim k → + ∞ V [ ( 1 − λ ~ 1 ) k ( 1 − λ ~ 2 ) k ⋱ ( 1 − λ ~ N ) k ] V T \begin{aligned} \lim _{k \rightarrow+\infty} \tilde{L}_{\mathrm{sym}}^{k} &=\lim _{k \rightarrow+\infty}\left(I-\tilde{L}_{s}\right)^{k} \\ &=\lim _{k \rightarrow+\infty}\left(V(1-\tilde{\Lambda}) V^{\mathrm{T}}\right)^{k} \\ &=\lim _{k \rightarrow+\infty} V\left[\begin{array}{lll} \left(1-\tilde{\lambda}_{1}\right)^{k} \\ & \left(1-\tilde{\lambda}_{2}\right)^{k} \\ & & \ddots \\ & & & \left(1-\tilde{\lambda}_{N}\right)^{k} \end{array}\right] V^T \end{aligned} k→+∞limL~symk=k→+∞lim(I−L~s)k=k→+∞lim(V(1−Λ~)VT)k=k→+∞limV⎣⎢⎢⎢⎢⎢⎢⎡(1−λ~1)k(1−λ~2)k⋱(1−λ~N)k⎦⎥⎥⎥⎥⎥⎥⎤VT
由于 ( 1 − λ ~ i ) ∈ ( − 1 , 1 ] \left(1-\tilde{\lambda}_{i}\right) \in(-1,1] (1−λ~i)∈(−1,1]，当且仅当 i = 1 i=1 i=1时， 1 − λ ~ 1 = 1 1-\tilde{\lambda}_1 = 1 1−λ~1=1，，由于其他的特征值都大于0（假设全连通图，仅存在一个特征值为0），因此上式取极限之后的结果如下式。
lim k → + ∞ L ~ sym k = V [ 1 0 ⋱ 0 ] V T \lim _{k \rightarrow+\infty} \tilde{L}_{\text {sym }}^{k}=V\left[\begin{array}{llll} 1 & & & \\ & 0 & & \\ & & \ddots & \\ & & & 0 \end{array}\right] V^{\mathrm{T}} k→+∞limL~sym k=V⎣⎢⎢⎡10⋱0⎦⎥⎥⎤VT
若设图信号为 x \boldsymbol{x} x，则有下面的结果，其中 v 1 \boldsymbol{v}_{1} v1是 L ~ s \tilde{L}_s L~s的最小频率 λ ~ 1 = 0 \tilde{\lambda}_1 = 0 λ~1=0对应的特征向量， x ~ 1 \tilde{x}_1 x~1表示信号 x \boldsymbol{x} x在对应频率 λ ~ 1 \tilde{\lambda}_1 λ~1的傅里叶系数。
lim k → + ∞ L ~ sym k x = V [ 1 0 ⋱ 0 ] V T x = ⟨ x ⋅ v 1 ⟩ v 1 = x ~ 1 v 1 \lim _{k \rightarrow+\infty} \tilde{L}_{\text {sym }}^{k} x=V\left[\begin{array}{llll} 1 & & & \\ & 0 & & \\ & & \ddots & \\ & & & 0 \end{array}\right] V^{\mathrm{T}} \boldsymbol{x}=\left\langle\boldsymbol{x} \cdot \boldsymbol{v}_{1}\right\rangle \boldsymbol{v}_{1}=\tilde{x}_{1} \boldsymbol{v}_{1} k→+∞limL~sym kx=V⎣⎢⎢⎡10⋱0⎦⎥⎥⎤VTx=⟨x⋅v1⟩v1=x~1v1
由于 L ~ s D ~ 1 / 2 1 = D ~ − 1 / 2 L D ~ − 1 / 2 D ~ 1 / 2 1 = D ~ − 1 / 2 L 1 = D ~ − 1 / 2 0 = 0 \tilde{L}_s \tilde{D}^{1 / 2} \mathbf{1}=\tilde{D}^{-1 / 2} L \tilde{D}^{-1 / 2} \tilde{D}^{1 / 2} \mathbf{1}=\tilde{D}^{-1 / 2} L \mathbf{1}=\tilde{D}^{-1 / 2} \mathbf{0}=\mathbf{0} L~sD~1/21=D~−1/2LD~−1/2D~1/21=D~−1/2L1=D~−1/20=0，即 L ~ s ( D ~ 1 / 2 1 ) = 0 \tilde{L}_{s}\left(\tilde{D}^{1 / 2} \mathbf{1}\right)=\mathbf{0} L~s(D~1/21)=0。这是由于拉普拉斯矩阵 L L L存在值全为1的特征向量，其对应特征值为0。因此， v 1 = D ~ 1 / 2 1 \boldsymbol{v}_{1}=\tilde{D}^{1 / 2} \mathbf{1} v1=D~1/21是 L ~ s \tilde{L}_s L~s在 λ ~ 1 \tilde{\lambda}_1 λ~1处的特征向量，该向量是一个处处相等的向量。所以，如果对一个图信号不断进行平滑操作，图信号就会变得处处相等，也就没有可区分性了。
空域角度
Representation Learning on Graphs with Jumping Knowledge Networks这篇论文中，作者从空域角度解释了为什么多层GCN效果不好的原因。空域来看，GCN的本质是在聚合邻居信息，对于任意一个节点，节点特征每更新一次，就多聚合了更高一阶的邻居节点的信息。将最高邻居节点的阶数称为该节点的聚合半径，可以发现，随着GCN的层数增加，节点的聚合半径也在变大，一旦达到某个阈值，，该节点可覆盖的节点就会和全图节点一致。如果层数很多，每个节点覆盖的节点都会收敛到全图节点，这与哪个节点是无关的。这会导致每个节点的局部网络结构的多样性大大降低，对于节点自身特征的学习很不好。
上图是论文中的一个实验结果图，a和b分别是对不同的方块节点进行信息聚合，可以看到，四层GCN后尽管两个节点的聚合半径一致，但是覆盖到的节点是差距很大的，但是对b再进行一次聚合后发现其覆盖节点迅速增加到达图的中心区域。此时，两个方块节点聚合的节点网络趋于一致，对其区分会很困难。
如何应对过平滑，论文中基于聚合半径和模型层数的关系提出了自适应性聚合半径的学习机制，其实现非常直观，就是通过增加跳跃连接来聚合模型的每层节点的输出，聚合后的节点特征拥有混合性的聚合半径，上层任务可对其进行选择性的监督学习，这样，对于任意一个节点而言，既不会因为聚合半径过大而出现过平滑的问题，也不会因为聚合半径过小，使得节点的结构信息不能充分学习。
上图是论文中这种学习机制的示意图，4层图模型的输出都会通过跳跃连接与最终的聚合层相连，聚合可以采用拼接、最大池化等方法，聚合层的输出才是整个模型真正的输出，送入相应任务进行学习。
补充说明
过平滑是GCN存在的一个严重2问题，也是制约其性能的关键，通过不同的方法解决过平滑问题为图网络的发展提供了契机。本文涉及的代码开源于Github，欢迎star或者fork。
智能推荐
Failed to discover available identity versions when contacting http://controller:35357/v3. 错误解决方式_caused by newconnectionerror('<urllib3.connection.-程序员宅基地
文章浏览阅读8.3k次，点赞5次，收藏12次。作为 admin 用户，请求认证令牌，输入如下命令openstack --os-auth-url http://controller:35357/v3 --os-project-domain-name default --os-user-domain-name default --os-project-name admin --os-username admin token issue报错Failed to discover available identity versions whe._caused by newconnectionerror('
学校机房统一批量安装软件的方法来了_教室电脑 一起装软件-程序员宅基地
文章浏览阅读4.5k次。可以在桌面安装云顷还原系统软件，利用软件中的网络对拷功能部署批量对拷环境，进行电脑教室软件的批量对拷安装与增量对拷安装。_教室电脑 一起装软件
消息队列（kafka/nsq等）与任务队列（celery/ytask等）到底有什么不同？_任务队列和消息队列-程序员宅基地
文章浏览阅读3.1k次，点赞5次，收藏7次。原文链接：https://www.ikaze.cn/article/43写这篇博文的起因是，我在论坛宣传我开源的新项目YTask（go语言异步任务队列）时，有小伙伴在下面回了一句“为什么不用nsq？”。这使我想起，我在和同事介绍celery时同事说了一句“这不就是kafka吗？”。那么YTask和nsq，celery和kafka？他们之间到底有什么不同呢？下面我结合自己的理解。简单的分析一..._任务队列和消息队列
Java调KT类_java 调用kt 对象-程序员宅基地
文章浏览阅读1.5k次。1，MyUtuils.kt将被调用的文件class MyUtils { fun show(info:String){ println(info) }}fun show(info:String){ println(info)}2，Java文件调用该类，ClientJava.javapublic class ClientJava { public static void main(String[] args) { /** _java 调用kt 对象
UDP报文最大长度_最大请求报文大小-程序员宅基地
文章浏览阅读6.6k次，点赞4次，收藏4次。在进行UDP编程的时候,我们最容易想到的问题就是,一次发送多少bytes好? 当然,这个没有唯一答案，相对于不同的系统,不同的要求,其得到的答案是不一样的,我这里仅对 像ICQ一类的发送聊天消息的情况作分析，对于其他情况，你或许也能得到一点帮助: 首先,我们知道,TCP/IP通常被认为是一个四层协议系统,包括链路层,网络层,运输层,应用层. UDP属于运输层_最大请求报文大小
Windows CMD命令行程序中 无限死循环 执行一段命令_cmd装比代码无限循环-程序员宅基地
文章浏览阅读10w+次，点赞14次，收藏18次。代码如下：for /l %a in (0,0,1) do echo hello,world粘贴在cmd命令行窗口中，回车即可无限死循环输出hello，world。如果需要停止，可以按ctrl+c中断。解析通用形式：for /l %variable IN (start,step,end) DO command [command-parameters] 该集表示以增量形式从start到end的一个数字序列。具体到第一段代码，如果是 (0,0,1) 就是从0开始，每次增_cmd装比代码无限循环
随便推点
MyBatis 多表映射及动态语句
主要梳理mybatis多表及动态使用
Qt 多线程基础及线程使用方式-程序员宅基地
文章浏览阅读2.9w次，点赞98次，收藏777次。文章目录Qt 多线程操作2.线程类QThread3.多线程使用：方式一4.多线程使用：方式二5.Qt 线程池的使用Qt 多线程操作应用程序在某些情况下需要处理比较复杂的逻辑， 如果只有一个线程去处理，就会导致窗口卡顿，无法处理用户的相关操作。这种情况下就需要使用多线程，其中一个线程处理窗口事件，其他线程进行逻辑运算，多个线程各司其职，不仅可以提高用户体验还可以提升程序的执行效率。Qt中使用多线程需要注意：Qt的默认线程为窗口线程（主线程）：负责窗口事件处理或窗口控件数据的更新；子线程负责后台的业_qt 多线程
GQA分组注意力机制
【代码】GQA分组注意力机制。
android 耗电分析与性能优化-程序员宅基地
文章浏览阅读218次。1.官方的建议1.1 电池续航时间优化（Optimizing Battery Life）参考文章：优化电池使用时间已有中文的详细说明，此处做简要说明：（1）监控电池电量和充电状态(Monitoring the Battery Level and Charging State）通过系统广播，获取充电状态和电池电量的变化来调整数据更新等操作；如在充电时，更新数据及应用，在低电量时，减少更新频..._com.tencent.mm:exdevice
pytorch基础 神经网络构建-程序员宅基地
文章浏览阅读818次，点赞14次，收藏9次。计算e1=2.718，e5=148.413，e3=20.086，e1+e5+e3=171.217。“人/B 们/E 常/S 说/S 生/B 活/E 是/S 一/S 部/S 教/B 科/M 书/E ”给一段文字做分词标注，标注每个字对应的标号。图中是双向的三层 RNNs，堆叠多层的RNN网络，可以增加模型的参数，提高模型的拟合。双向的 RNN 是同时考虑“过去”和“未来”的信息，输入（黑色点）沿着黑色的实线箭。比如标签0将表示为([1,0,0,0,0,0,0,0,0,0])，标签3将表示为。
怎样实现c#生成的exe文件脱离Halcon的安装环境运行_c#如何免安装halcon12-程序员宅基地
文章浏览阅读513次，点赞9次，收藏10次。无法加载DLL"halconxl": 找不到指定的模块。（异常来自HRESULT:0X8007007E）。在exe安装目录中中添加halconxl.dll文件继续运行就了。_c#如何免安装halcon12