引用: https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/
-
正式名称: The Weisfeiler-Lehman Isomorphism Test
-
-
- 各ノード $i$に適当なラベル $C_i = 1$を割り当てる
-
- 隣接するノードの多重集合 $L_i$をノードに記録する
-
- 多重集合 $L_i$をハッシュに通して新たな $C_i$を得る ( $C_i \leftarrow hash(L_i)$)
-
- 以上を繰り返して, ノードの分割 ${C_i}$が収束したら停止
-
- 2つのグラフが[* 同じ ${C_i}$を持たないなら同型ではない]
-
- 同じ ${C_i}$を持つならほぼ同型の可能性が高い (要出典)
- →絶対に同型とは言えないみたい?
-
-
例えば下の例だと, ${C_2}$と ${C_3}$とでノードの分割方法が変わってないので収束しているといえる→停止
引用: https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/4