本文已参与「新人创作礼」活动，一同开启创作之路。
定理
定理一：≃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≃subtreeSj。
定理三：当一个GNN的agg战略满足下面这三个性质的，且有满足多层，并满足1）substree同构，subgraph不同构，iii的街坊的multiset不等于jjj街坊的multiset。2）聚合函数\Phi是单射的；那么，该GNN就是严格的比1-WL要更具表达能力。(其实这个界说和[1] 中的WL kernel 用于subtree pattern的界说基本很像了。)
注：这里的kernel function:www即用来结构邻接矩阵AAA，比如Avu=w(Sv,Svu)A_{vu}=w(S_v, S_{vu})Avu=w(Sv,Svu)，而AAA就是决议了聚合的战略，即决议了街坊的权重。
模型
那么根据上面的理论，咱们只需结构满足定理三的聚合函数\Phi的GNN就能够了。
这里\gamma是一个可学习的参数。
试验
作者做了两类试验，一类是图节点分类，另外一类是图全体分类问题。作用都很好，图分类用到了Standford的OGB，我也在跑这个benchmark。可是没有对比最新SOTA（上一年7月的），比如ppa，sota现已80+了，作者是72.
总结
（亮点主要是提出了一个新的视角来剖析GNN表达能力。）
剖析
（个人认为本文思路很像是[1]中承继而来，可是扩展了三种isomorphism，而且计算www的方式也比较有新意，能够从怎么结构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).
