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^i_1,v^i_2$ 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也肯定一样。
这个证明通过归纳法推得。