重新思考图卷积网络:GNN只是一种滤波器

2019 年 6 月 3 日 新智元
重新思考图卷积网络:GNN只是一种滤波器



  新智元报道  

来源:arxiv

编辑:肖琴

【新智元导读】最新研究提出,图神经网络仅对特征向量进行低通滤波,不具有非线性流形学习特性。论文提出了一种基于图形信号处理的理论框架,用于分析图神经网络。


图神经网络已成为解决图结构数据机器学习问题的最重要技术之一。


最近关于顶点分类(vertex classification)的工作提出了深度和分布式的学习模型,以实现高性能和可扩展性。


但最近,一篇题为“Revisiting Graph Neural Networks: All We Have is Low-Pass Filters”的论文引起关注,文中提出,图神经网络仅仅是对特征向量进行低通滤波而已。



来自东京工业大学、RIKEN的两位研究人员发现,基准数据集的特征向量对于分类任务来说已经能提供很多有用信息,而图结构仅仅提供了一种对数据进行去燥的方法。


论文提出了一种基于图形信号处理的理论框架,用于分析图神经网络


作者称,他们的结果表明,图神经网络仅对特征向量进行低通滤波(low-pass filtering),不具有非线性流形学习特性论文进一步研究了它们对特征噪声的适应力,并对基于GCN的图神经网络设计提出了一些见解。


什么时候应该使用图神经网络?


图神经网络(Graph neural networks, GNN)是一类能够从图结构数据中学习的神经网络。近年来,用于顶点分类和图形同构测试的图神经网络在多个基准数据集上取得了良好的效果,并不断开创新的最先进技术性能。随着ChebNet和GCN在顶点分类方面获得成功,许多GNN变体被提出来解决社交网络、生物学、化学、自然语言处理、计算机视觉和弱监督学习方面的问题。


半监督顶点分类问题中,我们观察到,图卷积层(GCN)的参数只会导致过拟合。类似的观察在简单的架构(如SGC)和更复杂的脚骨(如DGI)中都曾被报告。


基于这种现象,Felix Wu等人提出将图神经网络简单地看作是特征传播(feature propagation),并提出了一种在许多基准数据集上具有最先进性能的高效模型。Kawamoto等人对图分区设置下未经训练的GCN-like GNNs进行了相关理论评述。


从这些先前的研究中,一个很自然的问题出现了:为什么、以及何时图神经网络在顶点分类任务中表现很好


换句话说,是否存在一个顶点特征向量的条件,使得图神经网络模型即使没有经过训练也能很好地工作?


那么,我们能否找到基准图神经网络(如SGC或GCN)失败的实际反例?


在本研究中,我们从图信号处理的角度来回答上述问题。在形式上,我们考虑了一个图的半监督学习问题。


给定一个图G = (V, E),每个顶点i∈V都有一个特征x(i)∈x,和标记y(i)∈y,其中x是d维欧氏空间R d,  Y = R用于回归, Y ={1,…, c}用于分类。任务是从特征x(i)中学习预测标签y(i)的假设。


然后,我们描述了这个问题的图神经网络解决方案,并对最常用的基准模型GCN及其简化的变体SGC的机制提供了见解。


本研究三大贡献


图信号处理(Graph signal processing, GSP)将顶点上的数据视为信号,应用信号处理技术来理解信号的特征。通过组合信号(特征向量)和图结构(邻接矩阵或邻接矩阵的变换),GSP启发了图结构数据学习算法的发展。在标准信号处理问题中,通常假设观测值包含一些噪声,并且底层的“真实信号”具有低频。这里,我们对我们的问题提出了类似的假设。


假设1:输入特征包括低频真实特征和噪声。真实特征为机器学习任务提供了足够的信息。


本研究的第一个贡献是验证了常用数据集的假设1(第3节)。图1显示了针对不同频率成分(frequency components)的特征训练的2层感知器(MLPs)的性能。在所有基准数据集中,我们看到只有少数频率成分有助于学习。在特征向量中加入更多的频率成分只会导致性能下降。反过来,当我们将高斯噪声N (0, σ2 ) 添加到特征中时,分类精度变得更糟了。


图1:频率成分的精度


最近的许多GNN都是建立在图信号处理的基础上的。最常见的做法是用(增强)规范化邻接矩阵I − L˜ 和矩阵X的特性。在图信号处理的文献中,这种操作在图上过滤信号(filters signals),而不显式地对标准化拉普拉斯矩阵进行特征分解。在这里,我们将这个增强的标准化邻接矩阵及其变体称为可互换的图滤波器(graph filters)和传播矩阵(propagation matrices)。


本研究的第二个贡献表明,将图信号与传播矩阵相乘对应于低通滤波(第4节,尤其是定理3),此外,我们还证明了观测信号与低通滤波器之间的矩阵乘积是真实信号优化问题的解析解。与最近的图神经网络设计原理相比,我们的结果表明图卷积层只是低通滤波(low-pass filtering)。因此,不需要学习图卷积层的参数。


在理论理解的基础上,我们提出了一种新的基准框架,称为gfNN((graph filter neural network, 图滤波神经网络),对顶点分类问题进行了实证分析。


gfNN由两个步骤组成:

  • 通过与图滤波矩阵的乘法实现滤波特性;

  • 通过机器学习模型学习顶点标签。


我们使用图2中的一个简单实现模型演示了框架的有效性。


图2:gfNN的一个简单实现


本研究的第三个贡献是以下定理:


定理2:在假设1下,SGC、GCN和gfNN的结果与使用真实特征的相应神经网络的结果相似。


定理7表明,在假设1下,gfNN和GCN具有相似的高性能。由于gfNN在学习阶段不需要邻接矩阵的乘法,因此它比GCN要快得多。此外,gfNN对噪声的容忍度也更高。


最后,我们将gfNN与SGC模型进行了比较。虽然SGC在基准数据集上计算速度快、精度高,但我们的分析表明,当特征输入是非线性可分的时,SGC会失败,因为图卷积部分对非线性流形学习没有贡献。为了实证证明这个观点,我们创建了一个人工数据集。


实验和结果


为了验证前面提出的观点,我们设计了两个实验。在实验E1中,我们将不同水平的白噪声加入到真实数据集的特征向量中,并比较不同基线模型的分类精度。


在实验E2中,我们研究了一个具有复杂的特征空间的人工数据集,以证明SGC等简单模型在分类时会失败。


表1给出了每个数据集的概述。


表1:用于顶点分类的实际基准数据集和合成数据集


神经网络


图4:Cora(左)、Citeseer(中)和Pubmed(右)数据集上的基准测试精度。噪声水平通过在特征值上增加白噪声的标准差来测量。


图像滤波器的去噪效果


对于每个数据集表1中,我们介绍一个白噪声N(0, 2)为特征向量?范围内(0.01,0.05)。根据定理8和定理7的含义,由于GCN的一阶去噪特性,它对特征噪声的容忍度较低。


随着噪声水平的增加,我们在图4中可以看到,GCN、Logistic回归(LR)和MLP更容易对噪声进行过拟合。另一方面,gfNN和SGC对噪声的容忍度差不多。


图过滤器的表现力


图5:基于两个圆形图案生成的500个数据样本的决策边界


表2:随机train/val/test分段的平均测试精度(5次)


总结


很少有工作涉及GCN架构的限制。Kawamoto等人采用平均场方法对一个简单的GCN模型进行了统计物理分析。他们的结论是,反向传播既不能提高基于GCN的GNN模型的准确性,也不能提高其可检测性。Li et al.在有限的标签数据设置下对多层的GCN模型进行了实证分析,指出如果标签数据太少或者叠加层太多,GCN的性能就会下降。虽然这些结果为GCN提供了很有洞察力的观点,但是它们并没有充分地回答这个问题:我们什么时候应该使用GNN?


我们的结果表明,如果假设1成立,我们应该使用GNN方法来解决给定的问题。从我们的角度来看,从GCN派生出来的GNNs只是简单地执行噪声滤波,并从去噪数据中学习


基于我们的分析,我们提出了GCN和SGC可能无法执行的两种情况:噪声特征和非线性特征空间。然后,我们提出一个在这两种情况下都能很好地工作的简单方法。


近年来,基于GCN的神经网络在点云分析、弱监督学习等领域得到了广泛的应用。随着输入特征空间的复杂化,我们提议重新审视当前基于GCN的GNNs设计。在计算机视觉中,GCN层并不是卷积层,我们需要把它看作一种去噪机制。因此,简单地叠加GCN层只会给神经网络设计带来过拟合和复杂性。


论文地址:

https://arxiv.org/pdf/1905.09550.pdf


新智元春季招聘开启,一起弄潮 AI 之巅!

岗位详情请戳:


【加入社群】


新智元 AI 技术 + 产业社群招募中,欢迎对 AI 技术 + 产业落地感兴趣的同学,加小助手微信号:aiera2015_2   入群;通过审核后我们将邀请进群,加入社群后务必修改群备注(姓名 - 公司 - 职位;专业群审核较严,敬请谅解)。

登录查看更多
26

相关内容

图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。近年来,图神经网络(GNN)在社交网络、知识图、推荐系统、问答系统甚至生命科学等各个领域得到了越来越广泛的应用。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

题目: Continuous Graph Neural Networks

摘要:

本文建立了图神经网络与传统动力系统之间的联系。我们提出了持续图神经网络(CGNN),它将现有的图神经网络与离散动力学进行了一般化,因为它们可以被视为一种特定的离散化方案。关键思想是如何表征节点表示的连续动力学,即关于时间的节点表示的导数。受现有的基于扩散的图方法(如社交网络上的PageRank和流行模型)的启发,我们将导数定义为当前节点表示、邻节点表示和节点初始值的组合。我们提出并分析了两种可能的动态图,包括节点表示的每个维度(又名特征通道)各自改变或相互作用的理论证明。所提出的连续图神经网络在过度平滑方面具有很强的鲁棒性,因此允许我们构建更深层次的网络,进而能够捕获节点之间的长期依赖关系。在节点分类任务上的实验结果证明了我们提出的方法在和基线对比的有效性。

介绍

图神经网络(GNNs)由于其在节点分类等多种应用中的简单性和有效性而受到越来越多的关注;、链接预测、化学性质预测、自然语言理解。GNN的基本思想是设计多个图传播层,通过聚合邻近节点的节点表示和节点本身的表示,迭代地更新每个节点表示。在实践中,对于大多数任务,几层(两层或三层)通常就足够了,更多的层可能导致较差的性能。

改进GNNs的一个关键途径是能够建立更深层次的网络,以了解数据和输出标签之间更复杂的关系。GCN传播层平滑了节点表示,即图中相邻的节点变得更加相似。当我们堆叠越来越多的层时,这会导致过度平滑,这意味着节点表示收敛到相同的值,从而导致性能下降。因此,重要的是缓解节点过平滑效应,即节点表示收敛到相同的值。

此外,对于提高我们对GNN的理论理解,使我们能够从图结构中描述我们可以学到的信号,这是至关重要的。最近关于理解GCN的工作(Oono和Suzuki, 2020)认为GCN是由离散层定义的离散动力系统。此外,Chen等人(2018)证明了使用离散层并不是构建神经网络的唯一视角。他们指出,带有剩余连接的离散层可以看作是连续ODE的离散化。他们表明,这种方法具有更高的记忆效率,并且能够更平滑地建模隐藏层的动态。

我们利用基于扩散方法的连续视角提出了一种新的传播方案,我们使用来自常微分方程(即连续动力系统)的工具进行分析。事实上,我们能够解释我们的模型学习了什么表示,以及为什么它不会遭受在GNNs中常见的过度平滑问题。允许我们建立更深层次的网络,也就是说我们的模型在时间价值上运行良好。恢复过平滑的关键因素是在连续设置中使用了最初在PageRank中提出的原始分布。直观上,重新开始分布有助于不忘记邻接矩阵的低幂次信息,从而使模型收敛到有意义的平稳分布。

本文的主要贡献是:

  • 基于PageRank和扩散方法,提出了两个连续递增模型容量的ODEs;
  • 我们从理论上分析了我们的层学习的表示,并表明当t → ∞我们的方法接近一个稳定的不动点,它捕获图结构和原始的节点特征。因为我们在t→∞时是稳定的,我们的网络可以有无限多个“层”,并且能够学习远程依赖关系;
  • 我们证明了我们的模型的记忆是高效的,并且对t的选择是具有鲁棒性的。除此之外,我们进一步证明了在节点分类任务上,我们的模型能够比许多现有的最先进的方法表现更好。
成为VIP会员查看完整内容
0
103

主题: Graph Neural Networks with Composite Kernels

摘要: 近年来,对图结构化数据的学习引起了越来越多人的兴趣。诸如图卷积网络(GCN)之类的框架已经证明了它们在各种任务中捕获结构信息并获得良好性能的能力。在这些框架中,节点聚合方案通常用于捕获结构信息:节点的特征向量是通过聚集其相邻节点的特征来递归计算的。但是,大多数聚合方案都将图中的所有连接均等化,而忽略了节点特征的相似性。本文从内核权重的角度重新解释了节点聚合,并提出了一个框架来考虑特征相似性。我们表明归一化的邻接矩阵等效于Kerin空间中基于邻居的内核矩阵。然后,我们提出功能聚集作为基于原始邻居的内核和可学习的内核的组成,以在特征空间中编码特征相似性。我们进一步展示了如何将所提出的方法扩展到图注意力网络(GAT)。实验结果表明,在一些实际应用中,我们提出的框架具有更好的性能。

成为VIP会员查看完整内容
0
39

图卷积运算符将深度学习的优势引入到各种以前认为无法实现的图和网格处理任务中。随着他们的不断成功,人们希望设计更强大的架构,通常是通过将现有的深度学习技术应用于非欧几里德数据。在这篇论文中,我们认为在新兴的几何深度学习领域,几何应该保持创新的主要驱动力。我们将图神经网络与广泛成功的计算机图形学和数据近似模型:径向基函数(RBFs)联系起来。我们推测,与RBFs一样,图卷积层将受益于将简单函数添加到强大的卷积内核中。我们引入了仿射跳跃连接,这是一种将全连通层与任意图卷积算子相结合而形成的新型构造块。通过实验验证了该方法的有效性,表明改进的性能不仅仅是参数数目增加的结果。在我们评估的每一项任务中,配备了仿射跳跃连接的操作人员都显著地优于他们的基本性能。形状重建,密集形状对应,和图形分类。我们希望我们的简单而有效的方法将作为一个坚实的基线,并有助于缓解未来在图神经网络的研究。

成为VIP会员查看完整内容
0
45

题目

几何图形卷积网络,GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS

关键字

消息传递神经网络,图卷积神经网络,图表示学习,深度学习

简介

消息传递神经网络(MPNN)已成功应用于各种现实应用中的图表示学习。但是,MPNN聚合器的两个基本弱点限制了它们表示图结构数据的能力:丢失了邻居中节点的结构信息,并且缺乏捕获解离图中的长期依赖关系的能力。很少有研究注意到不同观点的弱点。通过对经典神经网络和网络几何的观察,我们提出了一种新颖的图神经网络几何聚合方案,以克服这两个缺点。背后的基本思想是图形上的聚合可以受益于图形下方的连续空间。提出的聚合方案是置换不变的,由节点嵌入,结构邻域和双层聚合三个模块组成。我们还介绍了该方案在图卷积网络(称为Geom-GCN)中的实现,以对图执行转导学习。实验结果表明,Geom-GCN在各种开放的图形数据集上均达到了最先进的性能。

作者

Hongbin Pei,Bingzhe Wei,Kevin Chen-Chuan Chang,Yu Lei,Bo Yang

成为VIP会员查看完整内容
0
63
小贴士
相关资讯
图神经网络三剑客:GCN、GAT与GraphSAGE
PaperWeekly
50+阅读 · 2020年2月27日
一文读懂图卷积GCN
计算机视觉life
16+阅读 · 2019年12月21日
【论文笔记】自注意力图池化
专知
54+阅读 · 2019年11月18日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
154+阅读 · 2019年2月14日
深度 | 一文概览图卷积网络基本结构和最新进展
机器之心
17+阅读 · 2017年11月30日
基于注意力机制的图卷积网络
科技创新与创业
59+阅读 · 2017年11月8日
干货|基于图卷积网络的图深度学习
DataCanvas大数据云平台
7+阅读 · 2017年6月8日
相关VIP内容
相关论文
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang,Yuesong Zou,Jian Ma
12+阅读 · 2019年11月6日
Simon S. Du,Kangcheng Hou,Barnabás Póczos,Ruslan Salakhutdinov,Ruosong Wang,Keyulu Xu
8+阅读 · 2019年11月4日
OD-GCN: Object Detection by Knowledge Graph with GCN
Zheng Liu,Zidong Jiang,Wei Feng
4+阅读 · 2019年9月30日
Hoang NT,Takanori Maehara
7+阅读 · 2019年5月23日
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Naganand Yadati,Madhav Nimishakavi,Prateek Yadav,Vikram Nitin,Anand Louis,Partha Talukdar
9+阅读 · 2019年5月22日
Xiang Wang,Xiangnan He,Meng Wang,Fuli Feng,Tat-Seng Chua
8+阅读 · 2019年5月20日
Generative Graph Convolutional Network for Growing Graphs
Da Xu,Chuanwei Ruan,Kamiya Motwani,Evren Korpeoglu,Sushant Kumar,Kannan Achan
3+阅读 · 2019年3月6日
HyperGCN: Hypergraph Convolutional Networks for Semi-Supervised Classification
Naganand Yadati,Madhav Nimishakavi,Prateek Yadav,Anand Louis,Partha Talukdar
11+阅读 · 2018年9月7日
Petar Veličković,Guillem Cucurull,Arantxa Casanova,Adriana Romero,Pietro Liò,Yoshua Bengio
7+阅读 · 2018年2月4日
Haitham Afifi,Sebastien Auroux,Holger Karl
7+阅读 · 2017年12月18日
Top