本文探讨了图神经网络 GNN 与 Weisfeiler-Leman 算法的联系，指出 GNN 在图同构 graph isomorphism 任务上和 Weisfeiler-Leman 算法具有同样的能力，同时二者也存在着同样的缺陷，基于此，本文提出了一种新的GNN变体： higher-order GNN，并在相关任务上验证了该方法的优越性。
Weisfeiler-Leman Algorithm and Graph Neural Networks
Weisfeiler-Leman Algorithm 是用来确定两个图是否是同构的，其基本思路是通过迭代式地聚合邻居节点的信息来判断当前中心节点的独立性Identity，从而更新整张图的编码表达 code reprsentation。有一个式子来表示更新公式：
把(1)去掉具体的例子可以参考我们之前讲的 《Graph learning》| 图传播算法（下），这里由于每轮迭代都是聚合一阶邻居节点，所以作者特称这个算法为 1-WL。
我们再来看一看 GCN 的核心更新公式：
相信对于这个式子很熟悉，我们就不做变量说明了。在GraphSage算法中，上式被抽象成：
比较上式和1-WL，我们可以发现如下几点：
1、两个方法都是在聚合邻居节点；
2、存在一套特定的GNN模型，其效果完全等价于1-WL；
3、在图的同构问题上，GNN和1-WL的能力是一样的，谁也超不过谁；
4、1-WL算法的局限性被研究的很清晰，因此在GNN有着同样的问题。
在 On the power of color refinement 一文的研究中指出 1-WL算法对图的一些基本性质难以分辨，如循环图、三角计数等，特别是三角计数问题是研究社交网络的一个关键因素。
k-dimensional Graph Neural Networks
为了解决上述问题，作者借鉴1-WL到k-WL的拓展，将GNN拓展到k-GNN，称之为 higher-order GNN。具体地：
其中s 表示由k个节点组成的subgraph，u 是这个这个子图s的邻居子图，其中邻居子图的定义如下：
也就是一个k个节点组成的subgraph，其邻居子图必须和其有且仅有 k-1个公共节点。有了这样的思路之后，我们在建模一些 graph level 的任务时，就可以考虑更多的 high order 信息聚合，如下图所示：
实验
本文的改进主要是针对GNN在 graph level上的任务，因此我们就来看看这方面的效果吧。这里，作者使用了QM9数据集，这是一个分子结构数据集，任务是通过分子的结构来确定其12项物理化学指标。实验效果如下：
可以看到本文的方法在每一项指标的预测上均有效果提升。
参考链接
项目链接：
https://github.com/chrsmrrs/k-gnn
论文链接：
https://arxiv.org/abs/1810.02244
