ICLR 2022 | GNN | GraphSNN (二)

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

---

定理

定理一：≃subgraph\simeq_{subgraph}≃subgraph​ => ≃overlap\simeq_{overlap}≃overlap​ => ≃subtree\simeq_{subtree}≃subtree​,反过来不可，=>代表推出。

定理二：假如一个GNN 有满足多层，而且能够将Si,SjS_i,S_jSi​,Sj​映射为不同的embeddings的时分，则GNN和WL-1 适当，有且仅当 Si≃subtreeSjS_i \not \simeq_{subtree} S_jSi​≃subtree​Sj​。

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

注：这里的kernel function:$w$即用来结构邻接矩阵$A$，比如Avu=w(Sv,Svu)A_{vu}=w(S_v, S_{vu})Avu​=w(Sv​,Svu​)，而$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).