Weisfeiler-Lehman 알고리즘 (WL 알고리즘)은 두 그래프가 isomorphic한지를 검사하는 알고리즘으로, 이 테스트 결과가 다르면 두 그래프는 isomorphic하지 않다고 결론내릴 수 있다. 이번 글에서는 WL 알고리즘에 예시와 함께 대해 알아보겠다.
알고리즘
WL 알고리즘은 아래와 같은 순서로 진행된다.
- 각 노드에 initial label을 부여한다. initial label은 무엇이 되어도 상관없으나, 노드의 degree를 label로 사용하거나, 단순히 모두 같은 label을 부여하는 방식을 사용한다.
- 각 노드의 neighborhood의 label의 multiset에 대한 hash 결과를 해당 노드의 label로 사용한다. 이 때, hash 함수로는 unique한 multiset을 unique한 label로 매핑하는 어떤 함수를 사용해도 상관없다.
- 2번 단계를 label의 구성이 바뀌지 않을 때까지 혹은 K번 반복한다.
- 두 그래프의 node label 구성을 비교한다.
예시
알고리즘만 봐서는 직관적으로 이해가 되지 않기 때문에, 이를 예시와 함께 살펴보겠다. 다음과 같은 두 그래프가 있다고 하자.
우선, 각 노드에 initial label을 부여한다. initial label은 각 노드의 degree로 한다.
다음으로, 각 노드의 neighborhood의 label multiset을 구한다. 이는 다음 그림과 같다.
다음으로, 도출된 multiset을 새로운 label로 매핑한다. 우리는 ${2^2,3}$을 4, ${3^2}$를 5, ${2,3}$를 6으로 매핑한다. 그 결과는 다음과 같다.
이는 이전 단계의 initial label이 부여된 그래프와 노드의 분할이 다르다. 예를 들어, graph 1의 노란색 노드와 두 개의 파란 노드가 initial label 단계에서는 같은 label을 가지고 있었지만, 이 단계에서는 다른 label을 가진다. 그러므로 우리는 이 그래프에 대해서 앞선 과정을 한 번 더 반복한다. 각 노드의 neighborhood의 label multiset을 구한다. 이는 다음 그림과 같다.
다음으로, 도출된 multiset을 새로운 label로 매핑한다. 우리는 ${4,5,6}$을 7, ${4^2}$를 8, ${4,6}$를 9로 매핑한다. 그 결과는 다음과 같다.
이는 이전 단계의 initial label이 부여된 그래프와 노드의 분할이 같다. 그러므로 여기에서 알고리즘을 종료한다. 이 때, graph 1과 graph 2의 노드 구성이 2개의 7, 1개의 8, 2개의 9로 같기 때문에, 이 두 그래프는 WL test를 통과했다고 할 수 있다. 이 예시에서는 두 그래프가 isomorphic하지만, WL test를 통과한다고 하더라도 두 그래프가 isomorphic하지 않을 수 있다.
이번 글에서는 WL 알고리즘이 무엇인지에 대해 알아보았다. WL 알고리즘은 그래프 형태로 표현된 분자 구조들이 서로 일치하는지를 비교하거나, 회로설계를 할 때 두 개의 다른 회로가 서로 일치하는지 등을 판별할 때에 사용될 수 있다.
References
https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/
최근댓글