ICLR'22| 如何提升任意GNN的表现能力？

2022 年 4 月 15 日 图与推荐

论文地址：https://openreview.net/pdf?id=Mspk_WYKoEH
欢迎关注小编知乎：戴鸽

消息传递是图网络中的一种常见方法了，一般来说都是传一个节点信息，但是在这篇文章中，作者认为局部子图信息也是能传信息的，并且这种信息一样能提高模型表现能力，使其能抓住更多的局部信息。另外，这个模型是可以通用到任意一个图网络上的，包括但不限于GCN，GIN。

Introduction

图网络通常采用信息传递的方式收集邻居节点信息，然后采用聚合的方法更新当前节点。然而这样的方法经常被认为不能完整的刻画一张图。因此，作者将一个图分解为多个子图来增强图网络的表达能力，并且，这种方法在任何图网络上都是能适用的。如图所示，子图分割的方法采用以一个点为中心，采样其邻居构成一个小图，这种操作参考了CNN的设计，将每个点视作一个像素，这样每个小子图都是一个kernel，因此这个方法也叫做GNN-AK（GNN As Kernel）。由于参考了CNN的做法，所以Base GNN本质上是统一的一套参数。图中的Emb(i | Sub[j])项表示每个节点的信息都是由某种子图中的信息带来的，并且，作者定义了3中聚合器来整合这些信息。

Method

首先还是将一个图表示成的形式，节点特征表示为。如果考虑为图分类任务，那么这个图对应的标签应当记为。如果将一个点看成中心，则他的k阶邻居可以记成。根据邻居节点的定义，当k为1时，就能的得到作者对于星型子图的定义：。常规情况下，信息传递会写成如下形式：

和分别表示l层的更新函数和聚合函数，表示图级别的表征。从同质图的角度出发，如果按照1-WL的思路，每个节点可以可以被设置为一种与众不同的标签，或者叫涂了一层新的颜色，即。如果再进行一次信息传递，那么实际上就是对这些节点上的标签进行一次压缩，更新为。这个过程作者将其定义成或者说是，这里指一种图的函数，因此，如果是1-WL，这个方程最后变成了。

显然，如果直接进行这样的压缩肯定会丧失图的表达能力，因此，可以假设这里的子图本身也具有一定特征，用表示子图在第l层上的隐藏属性，即。这样就可以说第l层上的图信息是受到这个子图的影响了。与之前的信息传递不同，GNN-AK这个时候就可以说是传递了更多的子图特征。

简化一下表达方式，用替换。对于节点的嵌入特征表达就可以写成，嵌入的方法可以认为是一个GNN。如果同样写成信息传递的形式，则可以写成：

如果再加入自己本身的信息，还能写成：

更进一步，还能考虑当前节点是否对存在于不同子图：

这里也可以添加一个门操作，保证只让选中的子图参与信息传递，即：

在GNN-AK的最终版本GNN-AK+中，作者将这些信息全部融合到了一起，写作：

考虑到这些节点可能在不同子图里被反复选择，造成信息冗余，因此，对整个图而言，是有一个对子图的采样的，如图所示：采样方法包括随机采样（Random Sampling），按照最远节点距离采样（Farthest Sampling）和最小重叠子图采样（Min-set-cover sampling）。

Experiment

实验方面选用了大规模的数据包括ZINK-12K，CIFAR10，一些来自OGB的数据包括MolHIV，MolPCBA和一些小规模数据包括MUTAG，TUDataset等。实验机器为RTX-A6000。具体为：在大图上的总体表现为：可以发现，加入GNN-AK+的方法只要不超计算资源，基本都能有效提高实验结果，如果GNN-AK+都超时的数据，那么其他图网络模型也大概率会超时。其运算资源上的对比如下：R表示采样子图的个数，一般要用的话取3就好了，能在较为有限的时间和资源里取得较优的表现。