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,
and are graphs with same structure while 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也肯定一样。
这个证明通过归纳法推得。
v1.5.2