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





引用: https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/4