GNN表达能力研究与实验分析

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

定理

定理一：${\simeq }_{subgraph}$ => ${\simeq }_{overlap}$ => ${\simeq }_{subtree}$,反过来不行，=>代表推出。

定理二：如果一个GNN 有足够多层，并且可以将$S_i,S_j$映射为不同的embeddings的时候，则GNN和WL-1 相当，有且仅当 $S_i/{\simeq }_{subtree}{S}_j$。

定理三：当一个GNN的agg策略满足下面这三个性质的，且有足够多层，并满足1）substree同构，subgraph不同构，$i$的邻居的multiset不等于$j$邻居的multiset。2）聚合函数$\Phi$是单射的；那么，该GNN就是严格的比1-WL要更具表达能力。(其实这个定义和[1] 中的WL kernel 用于subtree pattern的定义基本很像了。)

注：这里的kernel function:$w$即用来构造邻接矩阵$A$，比如$A_{vu}=w(S_v,S_{vu})$，而$A$就是决定了聚合的策略，即决定了邻居的权重。

模型

那么基于上面的理论，我们只要构造满足定理三的聚合函数$\Phi$的GNN就可以了。

这里$\gamma$是一个可学习的参数。

实验

作者做了两类实验，一类是图节点分类，另外一类是图整体分类问题。效果都很好，图分类用到了Standford的OGB，我也在跑这个benchmark。但是没有对比最新SOTA（去年7月的），比如ppa，sota已经80+了，作者是72.

总结

（亮点主要是提出了一个新的视角来分析GNN表达能力。）

分析

（个人认为本文思路很像是[1]中继承而来，但是扩展了三种isomorphism，并且计算$w$的方式也比较有新意，可以从如何构造kernel function上面去挖掘新的想法。但是如果对于是没有 ground truth topology的任务，估计效果就不会很好，比如一些link prediction的任务。）

references

[1] Shervashidze, Nino, et al. “Weisfeiler-lehman graph kernels.” Journal of Machine Learning Research 12.9 (2011).