Graph Isomorphsim Network Illustration

Graph Isomorphism Network 从数学理论的角度证明了，在验证graph是否同构(isomorphism)上，aggregation based gcn的能力不可能超过WL test。并以此提出了一个简单的graph isomorphism network，实现了能力范围内的最大效果。

本文是对知乎大佬论文解析的补充。

WL test

• The initial label of each node also influences the isomorphism. For example, $G_1$ and $G_2$ are graphs with same structure while $v_1^i,v_2^i$ has different labels, then the two graphs should be determined as non-isomorphism.

Lemma 2

若aggregation based gcn将异构两图map到不同的embedding(即成功分辨为不同构)，则WL test也一定可以将该两图判定为不同构。

该定理为了证明aggregation based gcn的能力不可能超过WL test，其实还有一个是

若aggregation based gcn将同构两图map到相同的embedding(即成功分辨为同构)，则WL test也一定可以将该两图判定为同构。

但这个是obvious的。。。

大概证明思路。

想象存在这样的两个异构图，使得gcn的embedding不一样，而WL test最后也无法判定（即最后output node label multiset 也一样）。

那么我们可以从WL无法判定的方向证明:

证明若WL 第i层node label一样，则gcn 第i层 node feature也肯定一样。

这个证明通过归纳法推得。