【ICML2021】比较消息传递框架中的图卷积网络

本文将图上定义的神经网络转换为消息传递神经网络(MPNNs)，以研究这类模型的不同分类的区分能力。我们感兴趣的是某些架构何时能够根据作为图输入的特征标签区分顶点。我们考虑了两种不同的MPNNs: 匿名MPNNs，其消息函数只依赖于所涉及的顶点的标签; 以及程度感知的MPNNs，其消息函数可以额外使用关于顶点度数的信息。前一类涵盖了流行的图神经网络(GNN)形式，其优异的能力是已知的。后者包括Kipf和Welling提出的图卷积网络(GCNs)，其区分能力未知。利用Weisfeiler-Lehman (WL)算法的辨识能力，得到了(匿名和程度感知)多神经网络辨识能力的上界和下界。我们的主要结果表明: (1) GCNs的分辨能力受到WL算法的限制，但它们可能领先一步; (ii) WL算法不能用普通的GCNs模拟，但通过在顶点和其邻居的特征之间添加一个权衡参数(Kipf和Welling提出的)可以解决这个问题。

https://proceedings.mlr.press/v139/geerts21a