Weisfeiler-Lehman Algorithm

A SHORT TUTORIAL ON THE WEISFEILER-LEHMAN TEST AND ITS VARIANTS 를 바탕으로 작성되었습니다.

Weisfeiler-Lehman Algorithm (WL test)는 그래프의 동형을 판단하는 Colour refinement algorithm의 일종이다.
https://en.wikipedia.org/wiki/Colour_refinement_algorithm

1-WL (Classical WL)

• mapping function은 permutation에 불변해야한다.

• WL test의 통과가 동형임을 보장하진 않는다.
• 동형이 아님을 판단하는데 의미가 있다.
• 묘사에서는 빠졌지만 주변 노드뿐만 아니라 해당 노드 자체의 label도 고려해야한다.
• label set의 partition이 mapping 전과 후가 동일해질때까지 반복한다.

$k$-WL