本文得出了两个重要结论：
1. 在足够的深度、宽度、节点独立性和层表达条件下，GNN 是图灵普适（Turing universal）的；
2. 当 GNN 的深度和宽度受到限制时，它们的能力会大大降低。
为什么要研究 GNN 的局限性
机器学习中的一个基本问题是确定模型可以学习和不能学习的内容。在深度学习中，大量的研究工作都取得了正面的结果。例如，众所周知，具有足够深度和宽度的前馈神经网络可以逼近任何通用函数 。
最近，我们看到了研究图神经网络普适性的第一批结果，这些神经网络以图作为输入。针对层是线性的且输入排列是等变的深层网络，Maron 等人得出了一个不变量函数的通用近似定理。Keriven 和 Peyr'E也证明了等变函数的普适性，尽管这一次是在一个特定的浅层体系结构下。扩展到深集，Xu 等人还证明了由和聚集器组成的单图神经网络层的普适性，该结果后来由 Seo 等人扩展。这些研究从函数层面探究了 GNN 模型能学到什么，即 GNN 的普适性。
研究 GNN 的普适性使我们能够在有限的范围内把握模型的能力。理论上，只要有足够的数据和正确的学习算法，一个普适的网络就可以解决它所面临的任何任务。然而，这些结果带来的洞察也可能是有限的。知道一个足够大的网络可以用来解决任何问题，并不能在实践中指导神经网络设计。当然也不能保证该网络能够在给定的学习算法（如随机梯度下降）下解决给定的任务。
然而，通过研究模型的局限性通常更容易获得对模型的洞察。毕竟，网络所不能学到的关于特定特征的知识在应用时独立于训练过程。此外，通过帮助我们理解与模型相关的任务的难度，不可能性结果（impossibility result）有助于得出关于如何选择模型超参数的实用建议。
以图分类问题为例。训练一个图分类器需要识别是什么构成了一个类，即在同一个类而非其他类中找到图共享的属性，然后决定新的图是否遵守所学习到的属性。然而，如果可以通过一定深度的图神经网络（且测试集足够多样化）证明上述决策问题是不可能的，那么我们可以确定，同一个网络将不会学习如何正确地对测试集进行分类，这与使用了什么学习算法无关。因此，在进行实验时，我们应该把重点放在比下限更深的网络上。
本文两大结论
本文研究了图神经网络的计算能力局限。作者没有聚焦于特定的架构，这里所考虑的网络属于消息传递框架的范畴。选择该模型是因为它足够通用，能够涵盖几个最先进的网络，包括 GCN、Chebynet、门控图神经网络、分子指纹、相互作用网络、分子图卷积等。本文提出的不可能性陈述（impossibility statement）源于一种新的技术，它能使理论计算机科学的成果重新定位。这将引出涉及图的一系列决策、优化和估计问题的下界。值得注意的是，这些问题中的一些被认为是不可能的，除非 GNN 的深度和宽度的乘积超过了图的大小；即使对于看起来很简单的任务或在考虑近似值时，这种依赖性仍然很强。
具体来讲，本文主要得出了两大结论。
GAN 在什么情况下具有图灵普适性
如果满足一定的条件，GNN 就可以在其输入上计算任何可由图灵机计算的函数。这个结果不同于最近的普适性结果，后者考虑了在特定的函数类（不变和等变）和特定的体系结构上的近似（而不是可计算性）。这一主张遵循一种直接的方式，即建立 GNN 与 LOCAL的图灵等价，这是分布式计算中的一个经典模型，本身就是图灵通用模型。简而言之，如果满足以下四个强条件，GNN 就被证明是图灵普适的：（i）有足够的层；（ii）所述层有足够的宽度；（iii）节点之间互相独立；（iv）每层计算的函数具有足够的表现力。
哪些情况下 GNN 学习能力会下降
为了了解更多，作者研究了对不使用读出函数的 GNN 的深度 d 和宽度 w 进行限制的含义。具体来说，当乘积 dw 受到限制时，GNN 的能力会大打折扣。该分析依赖于一个新的引理，该引理能够将不可能性结果从 LOCAL 转换到 GNN。这种方法的主要好处是，它允许我们重新使用从理论计算机科学到图神经网络设置的几个重要下界。
设 G 为神经网络的输入。本文给出了以下问题的下界：
检测 G 是否包含特定长度的循环；
验证给定的 G 子图是否连接，是否包含循环，是否为生成树，是否为二分体，是否为一条简单的路径，是否对应于 G 的割或哈密顿循环；
近似两个顶点之间的最短路径，最小割和最小生成树；
找到最大独立集、最小顶点覆盖或 G 的着色；
计算或近似 G 的直径和周长；
表 1：主要结果总结。
图 1：给出下界的图例。
论文链接：https://arxiv.org/abs/1907.03199
