[人工智能]ICLR 2020 | 浅谈 GNN：能力与局限 |机器学习|算法|深度学习|

本文简要阐述三篇与此相关的文章，它们分别研究了基于信息传递的图神经网络 GNNmp 的计算能力， GNNs 的推理能力和阻碍 GCN 变深的问题---over-fitting 与 over-smoothing 。
本文涉及的 3 篇 ICLR 原文：

What graph neural networks cannot learn: depth vs width
What Can Neural Networks Reason About?
DropEdge: Towards Deep Graph Convolutional Networks on Node Classification

图数据在现实世界中广泛存在，图神经网络（GNNs）也在相关的机器学习任务中取得了不错的效果，但简单地“将数据给模型、希望其拟合出来可以得到预期结果”的一整套函数在某种程度上是不负责任的。更好地理解 GNNs 适合与不适合哪些问题可以帮助我们更好地设计相关模型。本文简要阐述三篇与此相关的文章，它们分别研究了基于信息传递的图神经网络 GNNmp 的计算能力、GNNs 的推理能力和阻碍 GCN 变深的问题---over-fitting 与 over-smoothing 。
What graph neural networks cannot learn: depth vs width
机器学习中一个很基础的问题是判断什么是一个模型可以学习和不能学习的。在深度学习中，已经有很多工作在研究如 RNNs、Transformers 以及 Neural GPUs 的表现力。我们也可以看到有工作在研究普遍意义上的 GNNs 相关的理论，如以图作为输入的神经网络。普遍性的表述使得我们可以更好地研究模型的表现力。
理论上，给定足够的数据和正确的训练方式，一个这种架构下的网络可以解决任何它所面对的任务。但这并不应该是一切，只是知道”一个足够大的网络可以被用来解决任何问题”无法使我们合理地设计这个网络，而另一方面，我们需要通过研究他们的局限来获取更多关于这个模型的认知。
本文研究了基于信息传递的图神经网络 GNNmp 的表达能力，包括 GCN、gated graph neural networks 等，并回答了如下问题：
（1）什么是 GNNmp 可以计算的？
本文证明了在一定条件下， GNNmp 可以计算任何可以被图灵机计算的函数。这个证明通过建立 GNNmp 和 LOCAL 之间的关系来实现。而 LOCAL 是一个经典的分布式计算中的模型，本身是具有图灵普遍性的。简言之， GNNmp 如果满足如下的几个较强的条件，即具有足够多的层数和宽度、节点之间可以相互区分，即被证明是普遍的。
（2）什么是 GNNmp 不可以计算的？
本文证明了如果乘积 dw 被限制， GNNmp 的能力会损失很大一部分。具体的，本文对于以下的几个问题展示了 dw 的下限，即检测一个图中是否含有一个指定长度的环，确认一个子图是否是联通的、是否包含环、是否是一个二分图或是否具有哈密顿回路等。

本文插图
本文展现了 GNNmp 在和合成数据上的实验结果，选取 4-cycle 分类问题，即将图根据它们是否包含有 4 个节点的回路来将其分类的问题来检验 GNNmp 的能力，目的在于验证 GNNmp 的 dw 乘积，节点数 n 和 GNNmp 解决问题的能力之间的关系。

本文插图
What Can Neural Networks Reason About?
【[人工智能]ICLR 2020 | 浅谈 GNN：能力与局限】近来，有很多关于构建可以学会推理的神经网络的尝试。推理任务多种多样，如视觉或文本问答、预测物体随时间的演化、数学推理等。神奇的是那些在推理任务中表现较好的神经网络通常具有特定的结构，而很多成功的模型均采用 GNN 的架构，这种网络可以显示的建模物体两两之间的关系，并可以逐步的通过结合某个物体和其它物体的关系来更新该物体的表示。同时，其他的模型，如 neural symbolic programs、Deep Sets 等，也都可以在特定问题上取得较好的效果。但是关于模型泛化能力和网络结构之间关系的研究仍然较少，我们自然会问出这样的问题：怎样的推理任务可以被一个神经网络学习到？这个问题的回答对我们如何理解现有模型的表现力和其局限性至关重要。本文通过建立一个理论框架来回答这个问题，我们发现如果可以在推理问题和网络之间建立良好的对应关系，那么这个问题可以被很好地解决。