ICLR 2020 | 小桃无主，轻带晚鸦---从逻辑表达视角看GNN

GNN 可以表现什么可以解决什么问题，是否有改进余地，在建模网络数据时，这种形式的模型是否是最优的，其它可能的方向是什么确实值得进一步的思考。在本次 ICRL 中确实看到了一些研究这些问题的文章，他们在相关理论上上下求索，给出了一些有意思的结论，独具一种出水芙蓉，清雅绝尘之美。下面是一篇研究 GNN 逻辑表达能力的文章。

原文：The Logical Expressiveness of Graph Neural Networks

GNNs 经常被和检测图同构的 Weisfeiler-Lehman（WL）算法联系起来，具体地，WL 检测通过为图中的每个节点逐步地构造标签，并通过比较两个图中的节点标签来判断二者是否同构，而 GNNs 通过聚合邻居的特征向量并和本节点的特征向量结合起来的过程与此相似。我们称这种 GNNs 为 aggregate-combine GNNs，即 AC-GNNs。研究发现，如果两个节点在 WL 检测中的标签相同则他们通过 AC-GNNs 产生的节点向量也是相同的。因为存在 AC-GNNs 可以产生WL检测的结果，从而 AC-GNNs 被认为和 WL 检测一在区分节点方面一样强大。但这并不是说 AC-GNNs 捕捉到每一种节点分类器的模式，一个简单的反例为这种分类器将所有节点分类为 true 当且仅当这个图中有孤立节点。

从而 AC-GNNs 可以捕捉到怎样的节点分类器呢？以及是否存在一种 GNN 可以捕捉到 AC-GNNs 所不可以捕捉到的分类器呢？

作者在逻辑分类器的层面回答了这些问题，使用 FOC₂ 逻辑度量（详见原文）AC-GNNs 的表现力，同时，FOC₂ 和 WL 检测的关系如下：一个图中的两个节点可以被 WL 测试分到一类当且仅当他们严格满足一个相同的一元 FOC₂ 式子。

从而作者说明

（1）一种特定种类的 FOC₂ 可以被 AC-GNNs 表达，这种逻辑称为分级模态逻辑；

（2）使用一种非常简单的方式，即允许全局 readouts，每一层同时也计算一个整个图的全局特征向量并将其和局部的聚合结合。这种 GNNs 被称为 ACR-GNNs。

为展现理论上证明的 ACR-GNNs 的表现力和 AC-GNNs 与 ACR-GNNs 的区别，作者选择在合成数据集上进行实验，具体如下：一个展现 ACR-GNNs 可以学习到而 AC-GNNs 不能学习到的一个简单的 FOC₂ 节点分类器的实验和一个涉及到更加复杂的 FOC₂ 分类器去学习更多直接相关的 readout 函数的实验。

近期精彩集锦（点击蓝色字体跳转阅读）：

公众号对话框回复“2020科技趋势”，获取《2020科技趋势报告》完整版PDF！

公众号对话框回复“AI女神”，获取《人工智能全球最具影响力女性学者报告》完整版！

公众号对话框回复“AI10”，获取《浅谈人工智能下一个十年》主题演讲PPT！

公众号对话框回复“GNN”，获取《图神经网络及认知推理》主题演讲PPT！

公众号对话框回复“AI指数”，获取《2019人工智能指数报告》完整版PDF！

公众号对话框回复“3D视觉”，获取《3D视觉技术白皮书》完整版PDF！

点击阅读原文，一键直达 ICLR 2020 专题！