WL test
https://gyazo.com/5386b3c91440a8742269364ea7e071f2
正式名称: The Weisfeiler-Lehman Isomorphism Test
1. 各ノード$ iに適当なラベル$ C_i = 1を割り当てる
2. 隣接するノードの多重集合$ L_iをノードに記録する
3. 多重集合$ L_iをハッシュに通して新たな$ C_iを得る ($ C_i \leftarrow hash(L_i))
4. 以上を繰り返して, ノードの分割 $ \{C_i\}が収束したら停止
5. 2つのグラフが同じ $ \{C_i\}を持たないなら同型ではない
6. 同じ $ \{C_i\}を持つならほぼ同型の可能性が高い (要出典)
→絶対に同型とは言えないみたい?
例えば下の例だと, $ \{C_2\}と$ \{C_3\}とでノードの分割方法が変わってないので収束しているといえる→停止
https://gyazo.com/966e7f9655827a923bbe63933ea4176c
https://gyazo.com/b76f9fffb6bcbc2fd39edbabbcf7d853https://gyazo.com/7d38b95d282daad97254c45c8c662605
https://gyazo.com/6509467dc12f6474dd135275d8c82aa1https://gyazo.com/e3f532d028fce3a8f019821ebfbcb41f
https://gyazo.com/757c44678f1f13f2635f2137b0c9c43dhttps://gyazo.com/28737cb4928c2cc0f925c8931b66dedf
https://gyazo.com/5cbc13d884c5095758901d07568681fd