ICLR 2020 | 浅谈 GNN：能力与局限
本文简要阐述三篇与此相关的文章 ， 它们分别研究了基于信息传递的图神经网络GNNmp的计算能力 ， GNNs的推理能力和阻碍GCN变深的问题---over-fitting与over-smoothing 。
本文涉及的3篇ICLR原文：
Whatgraphneuralnetworkscannotlearn:depthvswidthWhatCanNeuralNetworksReasonAbout?DropEdge:TowardsDeepGraphConvolutionalNetworksonNodeClassification图数据在现实世界中广泛存在 ， 图神经网络（GNNs）也在相关的机器学习任务中取得了不错的效果 ， 但简单地“将数据给模型、希望其拟合出来可以得到预期结果”的一整套函数在某种程度上是不负责任的 。 更好地理解GNNs适合与不适合哪些问题可以帮助我们更好地设计相关模型 。 本文简要阐述三篇与此相关的文章 ， 它们分别研究了基于信息传递的图神经网络GNNmp的计算能力、GNNs的推理能力和阻碍GCN变深的问题---over-fitting与over-smoothing 。
【ICLR 2020 | 浅谈 GNN：能力与局限】Whatgraphneuralnetworkscannotlearn:depthvswidth
机器学习中一个很基础的问题是判断什么是一个模型可以学习和不能学习的 。 在深度学习中 ， 已经有很多工作在研究如RNNs、Transformers以及NeuralGPUs的表现力 。 我们也可以看到有工作在研究普遍意义上的GNNs相关的理论 ， 如以图作为输入的神经网络 。 普遍性的表述使得我们可以更好地研究模型的表现力 。
理论上 ， 给定足够的数据和正确的训练方式 ， 一个这种架构下的网络可以解决任何它所面对的任务 。 但这并不应该是一切 ， 只是知道”一个足够大的网络可以被用来解决任何问题”无法使我们合理地设计这个网络 ， 而另一方面 ， 我们需要通过研究他们的局限来获取更多关于这个模型的认知 。
本文研究了基于信息传递的图神经网络GNNmp的表达能力 ， 包括GCN、gatedgraphneuralnetworks等 ， 并回答了如下问题：
（1）什么是GNNmp可以计算的？
本文证明了在一定条件下 ， GNNmp可以计算任何可以被图灵机计算的函数 。 这个证明通过建立GNNmp和LOCAL之间的关系来实现 。 而LOCAL是一个经典的分布式计算中的模型 ， 本身是具有图灵普遍性的 。 简言之 ， GNNmp如果满足如下的几个较强的条件 ， 即具有足够多的层数和宽度、节点之间可以相互区分 ， 即被证明是普遍的 。
（2）什么是GNNmp不可以计算的？
本文证明了如果乘积dw被限制 ， GNNmp的能力会损失很大一部分 。 具体的 ， 本文对于以下的几个问题展示了dw的下限 ， 即检测一个图中是否含有一个指定长度的环 ， 确认一个子图是否是联通的、是否包含环、是否是一个二分图或是否具有哈密顿回路等 。
文章图片
本文展现了GNNmp在和合成数据上的实验结果 ， 选取4-cycle分类问题 ， 即将图根据它们是否包含有4个节点的回路来将其分类的问题来检验GNNmp的能力 ， 目的在于验证GNNmp的dw乘积 ， 节点数n和GNNmp解决问题的能力之间的关系 。
文章图片
WhatCanNeuralNetworksReasonAbout?
近来 ， 有很多关于构建可以学会推理的神经网络的尝试 。 推理任务多种多样 ， 如视觉或文本问答、预测物体随时间的演化、数学推理等 。 神奇的是那些在推理任务中表现较好的神经网络通常具有特定的结构 ， 而很多成功的模型均采用GNN的架构 ， 这种网络可以显示的建模物体两两之间的关系 ， 并可以逐步的通过结合某个物体和其它物体的关系来更新该物体的表示 。 同时 ， 其他的模型 ， 如neuralsymbolicprograms、DeepSets等 ， 也都可以在特定问题上取得较好的效果 。 但是关于模型泛化能力和网络结构之间关系的研究仍然较少 ， 我们自然会问出这样的问题：怎样的推理任务可以被一个神经网络学习到？这个问题的回答对我们如何理解现有模型的表现力和其局限性至关重要 。 本文通过建立一个理论框架来回答这个问题 ， 我们发现如果可以在推理问题和网络之间建立良好的对应关系 ， 那么这个问题可以被很好地解决 。
文章图片
例如 ， 在Bellman-Ford算法求解任意两点间最短路径的问题上 ， 虽然可以证明MLP可以表示任何GNN可以表示的函数 ， 但GNN的泛化能力更强 ， 而后者决定了GNN的效果更好 ， 或者说 ， GNN学到了如何去推理 。 究其原因 ， GNN可以通过学习一个很简单的步骤 ， 即该算法中的松弛过程 ， 来很好地模拟Bellman-Ford算法 ， 而与此相对应地 ， MLP却必须去模拟整个for循环才可以模拟Bellman-Ford算法 。
文章图片
DropEdge:TowardsDeepGraphConvolutionalNetworksonNodeClassification
GCNs在图的很多任务上取得了SOTA的表现 ， 如节点分类 ， 社交推荐 ， 关联预测等 ， 而over-fitting和over-smoothing是两个阻碍GCNs在节点分类等任务上进一步发展的问题 。
文章图片
我们在四个数据集上验证DropEdge的效果 ， 说明其可以提高GCNs的表现里并确实具有防止over-smoothing的作用 。
文章图片
更多ICLR论文话题 ， 可通过微信“Moonnn01”加入ICLR2020交流群讨论 。
推荐阅读
- 浦东新区科技发展基金知识产权资助资金2020年度申报指南
- 上海市2020年度科技创新行动计划科普专项第二批项目申报指南通知
- 看看2020个平行进口和途乐的真实情况，预计七月将抵达香港，触及关键的价格。
- adolbook14 2020增强版正式预售，有颜值强性能，性价比之王
- 启辰星SUV2020款怎么样？来自企鹅号|《尚车快报》
- 安徽省2020年4月份“月评十佳”学雷锋志愿服务典型评选揭晓，池州一社区入选
- 经济10个关键词帮你把握2020年中国经济走势
- 石家庄市公安局桥西分局友谊派出所合力“铸盾”全力“亮剑2020”
- 环球扫描（2020.5.18-5.24）
- 解读预算报告：2020年预计为企业新增减负超2.5万亿元