ICLR 2020|小桃无主，轻带晚鸦--从逻辑表达视角看GNN
GNN可以表现什么可以解决什么问题，是否有改进余地，在建模网络数据时，这种形式的模型是否是最优的，其它可能的方向是什么确实值得进一步的思考。在本次ICRL中确实看到了一些研究这些问题的文章，他们在相关理论上上下求索，给出了一些有意思的结论，独具一种出水芙蓉，清雅绝尘之美。
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所不可以捕捉到的分类器呢？
作者在逻辑分类器的层面回答了这些问题，使用FOC2逻辑度量（详见原文）AC-GNNs的表现力，同时，FOC2和WL检测的关系如下：一个图中的两个节点可以被WL测试分到一类当且仅当他们严格满足一个相同的一元FOC2式子。
从而作者说明
（1）一种特定种类的FOC2可以被AC-GNNs表达，这种逻辑称为分级模态逻辑；
（2）使用一种非常简单的方式，即允许全局readouts，每一层同时也计算一个整个图的全局特征向量并将其和局部的聚合结合。这种GNNs被称为ACR-GNNs。
logical1.png
为展现理论上证明的ACR-GNNs的表现力和AC-GNNs与ACR-GNNs的区别，作者选择在合成数据集上进行实验，具体如下：一个展现ACR-GNNs可以学习到而AC-GNNs不能学习到的一个简单的FOC2节点分类器的实验和一个涉及到更加复杂的FOC2分类器去学习更多直接相关的readout函数的实验。
logical2.png
相关阅读：
ICLR 2020 | PairNorm: Tackling Oversmoothing in GNNs
ICLR 2020 | NLP预训练模型的全新范式：对比学习
