WL 테스트는 그래프 동형성 문제 해결을 위한 강력한 방법으로 기계학습(ML)과 그래프 신경망(GNN)모델의 표현력 분석 및 성능평가에 중요한 역할을 한다.
1968년 Boris Weisfeiler와 Andrei Lehman이 개발한 알고리즘으로 대부분의 그래프에서 동형성을 빠르고 효과적으로 판단 가능하다.
-두 그래프가 동일한 구조를 가지는지 (즉, 동형인지) 판별하는 알고리즘 (NP-complete)인지 (NP-intermediate)인지 아직 미해결된 문제로, 일반적인 해결방법은 컴퓨터공학 분야에서 계산적으로 매우 복잡하다고 알려져 있다.
다음은 1차원 or k차원일때, WL 알고리즘의 작동방식이다.
hash 함수는 노드의 기존 레이블과 이웃들의 레이블을 조합하여 새로운 값을 생성
-반복적으로 노드의 레이블을 갱신하면서 그래프를 구별하는 방식
위의 과정을 거쳐 나온 두 그래프의 노드 레이블 목록을 비교하여 레이블 분포가 동일하면 두 그래프가 동형일 가능성이 높다고 판단
-일반적인 그래프 동형성 검출 문제(Graph Isomorphism Problem)를 해결하는 강력한 휴리스틱 방법
--> 여기서 말하는 휴리스틱 방법이란, 최적의 해를 보장하지는 않지만, 제한된 시간 내에 현실적으로 좋은 해답을 찾을 수 있는 문제 해결 기법이다.
예를들어, 그래프 동형성 문제의 경우 일반적인 알고리즘으로 풀려고 하면 시간이 너무 오래걸리고 TSP(Traveling Salesman problem)의 경우도 모든 경로를 검사하는(완전탐색)방법이기 때문에 시간이 너무 오래 걸리게 된다.
심리학에서 휴리스틱(Heuristic)- 발견법, 추단법 이란, 인간의 추론 및 의사결정, 문제해결 등의 특징을 설명하기 위해 사용되는 개념이다. 사람들이 문제를 해결할 때 빠르고 효율적으로 판단할 수 있도록 하는 정신적 지름길이라고 볼 수 있다.
경제학자이자 인지심리학자인 허버트 사이먼(Herbert Simon)은 인간이 합리적인 선택을 하기 위해 노력하는 동안 인간의 판단은 인지적 한계에 영향을 받는다고 제안하였다. 즉, 사람들은 선택을 해야하는 시간과 처리할 수 있는 정보의 양에 제한을 받는다.
심리학자 아모스 트버스키(Amos Tversky)와 다니엘 카네만(Daniel Kahneman)은 이러한 인지 편향에 대한 연구를 발표했는데, 그들은 이러한 편견이 사람들이 생각하는 방식과 사람들이 내리는 판단에 영향을 미친다고 주장했다. 휴리스틱은 문제해결과 의사결정 모두에서 중요한 역할을 한다. 빠른 솔루션이 필요할 때, 바로 이런 정신적 지름길을 자주 사용하기 때문이다.
출처: 라웰의 심리학 연구소
휴리스틱 방법의 종류
- 탐욕 알고리즘 (Greedy Algorithm)
- 매 순간 최적의 선택을 하여 전체적인 좋은 해를 찾는 방법
- A 탐색 알고리즘
- 현재까지의 비용과 목적지까지의 예상 비용을 함께 고려하는 탐색 방법
- 시뮬레이티드 어닐링 (Simulated Annealing)
- 물리학의 냉각과정에서 착안한 방법으로, 일정 확률로 최적해를 벗어나는 선택을 하면서 더 나은 해를 찾음
- 유전 알고리즘 (Genetic Algorithm)
- 자연 선택 개념을 적용하여 좋은 해를 점진적으로 찾는 방법
ex) 로봇의 움직임 최적화, 경로 탐색 등
WL 테스트의 작동방식을 설명하기 앞서, 그래프 동형사상이 무엇인지에 대해서 먼저 설명할까 한다.
그래프이론에서 그래프 G와 H의 동형사상은 G와 H의 정점 집합 사이의 일대일 대응이다.
두 그래프 사이에 동형이 존재하는 경우 그래프를 동형이라고 하며 아래와 같이 표시할 수 있다.
동형사상이 그래프의 자기 자신으로의 사상인 경우, 동형사상을 G의 자기 동형사상이라고 한다.
아래에 표시된 두 그래프는 서로 다른 모양으로 그려졌지만 모양은 동형이다.
Hassler Whitney가 보여준 Whitney 그래프 동형 정리는 두개의 연결 그래프가 동형인 것은 오직 그 선 그래프가 동형인 경우에만 가능하며, 단하나의 예외가 존재하는데, 세개의 정점이 있는 완전 그래프와 완전 이분 그래프는 동형이 아니지만 둘다 선그래프를 갖는다.
Whitney그래프 정리는 하이퍼그래프로 확장될 수 있다.
아래의 그림은 휘트니 정리가 예외인 그래프이다.
이 두 그래프는 동형이 아니지만, 동형 선그래프를 갖는다.
출처: 위키백과
그래프 G(V,E)와 H(V,E)가 존재한다고 할때, G에서 edge로 이웃한 모든 node들의 쌍에 대해, H에서 대응되는 각 node들의 쌍 또한 edge로 이웃해 있을 때 isomorphic하다고 표현한다.
아래의 그림을 예시로 들어보자,
그림을 보면, 각 그래프에서 같은 숫자를 가진 node들끼리 대응되기 때문에, 두 그래프는 isomorphic하다고 할 수 있다.
바로, Weisfeiler-Lehman Algorithm은 주어진 두 그래프가 isomorphic한지를 확인하는 방법이라고 볼 수 있다.
WL 알고리즘에 대한 자세한 내용을 학습하고 싶다면 아래 논문을 참고하는 것이 도움이 될 것 같다.
Reference
