题目: From Stars to Subgraphs: Uplifting any GNN with local structure awareness
作者：Lingxiao Zhao(Carnegie Mellon Uni.), Wei Jin, Leman Akoglu, Neil Shah
本文来自MIND Lab，链接https://mp.weixin.qq.com/s/k63U5CR_NEP2Ji6e7iAH2A
一、本文介绍
MPNN作为GNN的一种，通过递归地聚合某结点星状图邻居的表示信息，以生成该结点的表示信息。MPNN的表达能力上界是1-WL test。本文提出了一种能提升任意MPNN模型表达能力的通用框架GNN-AK(GNN As Kernel)。实现的途径是将MPNN模型中的星状图替换为如k-egonets的子图结构。即某结点的表示将通过其导出子图而不是与其直接相连的邻居所组成的子图(即星状图)来计算。本文通过理论证明，GNN-AK表达能力强于1&2-WL，不弱于3-WL。
二、问题描述
与1-WL表达能力相当的GNN还不够强大，因为无法捕捉某些结构性信息，比如像圆圈和三角形之类的motif。鉴于k-WL的表达能力严格大于1-WL，目前的许多工作寻求将k-WL整合并设计为更强大的GNN。然而现有的大部分工作为了达到k-WL的表达能力，使用了O(k)阶张量。这导致这些工作在大规模的图上难以应用并扩展。现有的其他工作也缺乏可泛化性。
本文提出的模型拟提高任意GNN的表达能力。思路是将常见的MPNN中的star graph替换为灵活定义的subgraph，并将injective aggregator替换为GNN。换句话说，本模型利用GNN来计算某结点所处的子图，来生成该结点的新表示。将GNN作为base model计算每个子图而不是整个输入图是本文的一个创新点。
本文的贡献总结如下：
1、提出了GNN-AK(&GNN-AK+)框架，通过使用GNN对子图编码，提升任意GNN的表现力；
2、提供了理论支撑：GNN-AK的表现能力强于1&2-WL，不弱于3-WL；
3、高效的实现方式。设计了能够节约内存和时间开销的子图采样方法；
4、SOTA的实验结果。
三、模型方法
3.1 From stars to subgraphs
首先，MPNN通过下式计算图的嵌入
：
其中，
是一开始的feature，L是层数，
分别是第l层的update和aggregation函数。当以及POOL函数都是injective时，MPNN达到最大表达能力，与1-WL相当。
值得注意的是，1-WL有个bug之处在于，无法区分两个unlabeled(所有结点拥有相同的label)的不同构正则图。这也显示出采用星状图的MPNN表达能力有限。因此，本文提出将
泛化到subgraph上，比如egonet
以及k-hop egonet
，本文称这种方法为Subgraph-1-WL。
由于HASH可能是non-trivial的，导致总时间开销大，因此用1-WL作为弱化版的HASH。
注意：HASH和1-WL都是对一个subgraph进行操作的。
将GNN作为HASH便得到了GNN-AK：
3.2 通过理论进行表达能力分析
原因是MPNN内部的各函数都是injective的，所以MPNN表达能力=1-WL。
其中1-WL和2-WL被认为表达能力相同。
3.3 具体实现
GNN-AK：
通过GNN计算结点v的subgraph中各节点i的embedding，通过POOL函数得出整个子图的表示作为结点v的表示，成为subgraph encoding。
GNN-AK+：
提出了context encoding，将结点v所在的所有根结点不同的子图的embedding整合成multiset，用POOL函数计算得到v的表示。
对式(5)添加基于distance to centroid变量的门控函数，变为：
最终每层的GNN-AK+被定义为：
其中FUSE是串联或求和函数，
是第l层i到j的距离，
是将门控函数引入式(3)得到的。
3.4 SUBGRAPHDROP
四、实验&结果
GNN-AK表达能力的验证、子图计数问题和图性质回归
通过SubgraphDrop验证模型的泛化性
五、结论
本文介绍了GNN-AK和GNN-AK+，通过在输入图的导出子图上部署GNN作为kernel，以做到提升任意GNN的表达能力。并提供了理论证明。同时设计了SubgraphDrop，减少了子图采样的运行时间和内存占用。在数据集上的实验取得了SOTA的表现，并具有良好的泛化性。
OpenReview链接为：
https://openreview.net/forum?id=Mspk_WYKoEH
