JavaScriptを有効にしてください

WL test

 ·  ☕ 1 min read



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

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

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

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










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

共有

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