JavaScriptを有効にしてください

WL test

 ·  ☕ 1 min read



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

  • 正式名称: The Weisfeiler-Lehman Isomorphism Test

  • グラフが同型であるかチェックするアルゴリズム

      1. 各ノード $i$に適当なラベル $C_i = 1$を割り当てる
      1. 隣接するノードの多重集合 $L_i$をノードに記録する
      1. 多重集合 $L_i$をハッシュに通して新たな $C_i$を得る ( $C_i \leftarrow hash(L_i)$)
      1. 以上を繰り返して, ノードの分割 ${C_i}$が収束したら停止
      1. 2つのグラフが[* 同じ ${C_i}$を持たないなら同型ではない]
      1. 同じ ${C_i}$を持つならほぼ同型の可能性が高い (要出典)
      • →絶対に同型とは言えないみたい?
  • 例えば下の例だと, ${C_2}$と ${C_3}$とでノードの分割方法が変わってないので収束しているといえる→停止










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

共有

YuWd (Yuiga Wada)
著者
YuWd (Yuiga Wada)
機械学習・競プロ・iOS・Web