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

• 欢迎关注WX公众号，每周发布论文解析：PaperShare,
  点我关注

标题

A NEW PERSPECTIVE ON “HOW GRAPH NEURAL NET- WORKS GO BEYOND WEISFEILER-LEHMAN?”
（括号内的内容是个人见解，难免偏颇，望请指正）

主题

1. 理论上刻画了Message-Passing GNN 比WL-test 的表达能力更强。（当然，这是基于判断不同graph结构的测试上的结论，GNN还有另外一个表达能力就是学习节点等特征的能力。）
2. 基于以上理论，提出了GraphSNN，在多个区分图结构的数据集上取得了SOTA。

框架

定义：local isomorphism on neighborhood sub-graphs.

即在neighborhood sub-graphs 上的同构，就叫做邻居子图局部同构。（暂且这么翻译吧。。）

那么什么是neighborhood sub-graphs（邻居子图）呢？见上图：$G_1$中$v$的邻居子图$S_v$就是中间的$\{v_1\dots v_4\}$，包括$v$自己。

那么什么是overlap子图，比如，假设节点$v_1$的邻居子图为$S_{v1}$，那么，$S_{v1}$和$S_v$重叠的部分，即绿色椭圆部分，定义为$S_{v{v}_1}=S_v\cap S_{v_1}$，即含了$\{v1,v2,v\}$。再加上$S_{v{v}_2},S_{v{v}_3},S_{v{v}_4}$，即为over-subgraphs。

同理，可得出$G_2$的overlab subgraphs。

(Ok，再回到上面的图。上图中，首先分别计算出$G1,G2$中的节点$v,u$的overlap子图，然后用GMP(graph message passing)框架学习出两个节点的embedding：$h_v,h_u$，完事儿。)

接下来作者定义了对于任意两个邻居子图$S_i,S_j$的三种同构类型：

1. subgraph-isomorphism: $S_i{\simeq }_{subgraph}{S}_j$

邻居子图是同构的；$v_1,v_2\in S_i$是相邻的，有且仅有当$g(v_1),g(v_2)\in S_j$也是相邻的，并且$h_{v_1}=h_{g(v_1)}$, $h_{v_2}=h_{g(v_2)}$

关于同构的定义其实很简单（即，对于任意两个图$G_1,G_2$, 存在一个bijective mapping，$g:G_1\to G_2$, 使得$g(i)=j$, $i\in Vertex(G_1),j\in Vertex(G_2)$，详见：等下补充下同构，WL-test相关知识）。

2. overlap-isomorphism: $S_i{\simeq }_{overlap}{S}_j$

即对于overlap子图中的每一个对overlap子图是subgraph-isomorphism的，即，$S_{iv}{\simeq }_{subgraph}{S}_{ju}$.

3. subtree-isomorphism: $S_i{\simeq }_{subtree}{S}_j$

只要求节点$i,j$到其邻居节点构成的图同构，并且$h_v=h_u$，$v\in \hat{N}(i)$, $u\in \hat{N}(j)$.

见图：