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。
智能推荐
稀疏编码的数学基础与理论分析-程序员宅基地
文章浏览阅读290次，点赞8次，收藏10次。1.背景介绍稀疏编码是一种用于处理稀疏数据的编码技术，其主要应用于信息传输、存储和处理等领域。稀疏数据是指数据中大部分元素为零或近似于零的数据，例如文本、图像、音频、视频等。稀疏编码的核心思想是将稀疏数据表示为非零元素和它们对应的位置信息，从而减少存储空间和计算复杂度。稀疏编码的研究起源于1990年代，随着大数据时代的到来，稀疏编码技术的应用范围和影响力不断扩大。目前，稀疏编码已经成为计算...
EasyGBS国标流媒体服务器GB28181国标方案安装使用文档-程序员宅基地
文章浏览阅读217次。EasyGBS - GB28181 国标方案安装使用文档下载安装包下载，正式使用需商业授权, 功能一致在线演示在线API架构图EasySIPCMSSIP 中心信令服务, 单节点, 自带一个 Redis Server, 随 EasySIPCMS 自启动, 不需要手动运行EasySIPSMSSIP 流媒体服务, 根..._easygbs-windows-2.6.0-23042316使用文档
【Web】记录巅峰极客2023 BabyURL题目复现——Jackson原生链_原生jackson 反序列化链子-程序员宅基地
文章浏览阅读1.2k次，点赞27次，收藏7次。2023巅峰极客 BabyURL之前AliyunCTF Bypassit I这题考查了这样一条链子：其实就是Jackson的原生反序列化利用今天复现的这题也是大同小异，一起来整一下。_原生jackson 反序列化链子
一文搞懂SpringCloud，详解干货，做好笔记_spring cloud-程序员宅基地
文章浏览阅读734次，点赞9次，收藏7次。微服务架构简单的说就是将单体应用进一步拆分，拆分成更小的服务，每个服务都是一个可以独立运行的项目。这么多小服务，如何管理他们？(服务治理 注册中心[服务注册 发现 剔除])这么多小服务，他们之间如何通讯？这么多小服务，客户端怎么访问他们？(网关)这么多小服务，一旦出现问题了，应该如何自处理？(容错)这么多小服务，一旦出现问题了，应该如何排错?(链路追踪)对于上面的问题，是任何一个微服务设计者都不能绕过去的，因此大部分的微服务产品都针对每一个问题提供了相应的组件来解决它们。_spring cloud
Js实现图片点击切换与轮播-程序员宅基地
文章浏览阅读5.9k次，点赞6次，收藏20次。Js实现图片点击切换与轮播图片点击切换<!DOCTYPE html><html> <head> <meta charset="UTF-8"> <title></title> <script type="text/ja..._点击图片进行轮播图切换
tensorflow-gpu版本安装教程（过程详细）_tensorflow gpu版本安装-程序员宅基地
文章浏览阅读10w+次，点赞245次，收藏1.5k次。在开始安装前，如果你的电脑装过tensorflow，请先把他们卸载干净，包括依赖的包（tensorflow-estimator、tensorboard、tensorflow、keras-applications、keras-preprocessing），不然后续安装了tensorflow-gpu可能会出现找不到cuda的问题。cuda、cudnn。..._tensorflow gpu版本安装
随便推点
物联网时代 权限滥用漏洞的攻击及防御-程序员宅基地
文章浏览阅读243次。0x00 简介权限滥用漏洞一般归类于逻辑问题，是指服务端功能开放过多或权限限制不严格，导致攻击者可以通过直接或间接调用的方式达到攻击效果。随着物联网时代的到来，这种漏洞已经屡见不鲜，各种漏洞组合利用也是千奇百怪、五花八门，这里总结漏洞是为了更好地应对和预防，如有不妥之处还请业内人士多多指教。0x01 背景2014年4月，在比特币飞涨的时代某网站曾经..._使用物联网漏洞的使用者
Visual Odometry and Depth Calculation--Epipolar Geometry--Direct Method--PnP_normalized plane coordinates-程序员宅基地
文章浏览阅读786次。A. Epipolar geometry and triangulationThe epipolar geometry mainly adopts the feature point method, such as SIFT, SURF and ORB, etc. to obtain the feature points corresponding to two frames of images. As shown in Figure 1, let the first image be and th_normalized plane coordinates
开放信息抽取(OIE)系统（三）-- 第二代开放信息抽取系统(人工规则, rule-based, 先抽取关系)_语义角色增强的关系抽取-程序员宅基地
文章浏览阅读708次，点赞2次，收藏3次。开放信息抽取(OIE)系统（三）-- 第二代开放信息抽取系统(人工规则, rule-based, 先关系再实体)一.第二代开放信息抽取系统背景 第一代开放信息抽取系统(Open Information Extraction， OIE， learning-based, 自学习, 先抽取实体)通常抽取大量冗余信息，为了消除这些冗余信息，诞生了第二代开放信息抽取系统。二.第二代开放信息抽取系统历史第二代开放信息抽取系统着眼于解决第一代系统的三大问题: 大量非信息性提取（即省略关键信息的提取）、_语义角色增强的关系抽取
10个顶尖响应式HTML5网页_html欢迎页面-程序员宅基地
文章浏览阅读1.1w次，点赞6次，收藏51次。快速完成网页设计,10个顶尖响应式HTML5网页模板助你一臂之力为了寻找一个优质的网页模板，网页设计师和开发者往往可能会花上大半天的时间。不过幸运的是，现在的网页设计师和开发人员已经开始共享HTML5，Bootstrap和CSS3中的免费网页模板资源。鉴于网站模板的灵活性和强大的功能，现在广大设计师和开发者对html5网站的实际需求日益增长。为了造福大众，Mockplus的小伙伴整理了2018年最..._html欢迎页面
计算机二级 考试科目,2018全国计算机等级考试调整，一、二级都增加了考试科目...-程序员宅基地
文章浏览阅读282次。原标题：2018全国计算机等级考试调整，一、二级都增加了考试科目全国计算机等级考试将于9月15-17日举行。在备考的最后冲刺阶段，小编为大家整理了今年新公布的全国计算机等级考试调整方案，希望对备考的小伙伴有所帮助，快随小编往下看吧！从2018年3月开始，全国计算机等级考试实施2018版考试大纲，并按新体系开考各个考试级别。具体调整内容如下：一、考试级别及科目1.一级新增“网络安全素质教育”科目(代..._计算机二级增报科目什么意思
conan简单使用_apt install conan-程序员宅基地
文章浏览阅读240次。conan简单使用。_apt install conan