Isomorphic graph는 노드의 ordering의 차이로 인해 다르게 표현되지만 완전히 같은 구조를 가지고 있는 그래프들을 말한다. 이번 글에서는 graph isomorphism이 무엇인지에 대해 알아보고, 이것이 graph representation을 표현할 때 어떻게 활용될 수 있는지에 대해 알아보겠다.
정의
Isomorphic graph는 위에서 언급했듯이, 노드의 ordering의 차이로 인해 다르게 표현되지만 완전히 같은 구조를 가지고 있는 그래프들을 말한다. 예를 들어, 다음과 같은 두 그래프가 있다고 하자.
두 그래프를 비교해 보면 다르게 생긴 것처럼 보인다. 하지만, 각 노드가 연결된 구조를 살펴보면 두 그래프가 정확히 같은 구조를 가지고 있는 것을 알 수 있다. 각 노드가 가지고 있는 색깔이 같으면 같은 노드라고 생각해보자. 그럼 빨간색 노드 (h, 2)는 두 그래프에서 모두 파란색 (a, 1), 분홍색 (b, 6), 하늘색 (d, 3)과 연결되어 있다. 다음으로, 초록색 노드 (g, 5)는 파란색 (a, 1), 분홍색 (b, 6), 노란색 (c, 8)과 연결되어 있다. 이렇게 각 노드를 각 색깔에 대응시키면, 그래프가 가지는 연결 구조가 모두 같음을 알 수 있다. 이렇게 노드 ordering을 일치시킴으로써 두 그래프가 같은 구조를 가지고 있으면, 이들을 isomorphic graph라고 한다.
이를 식으로 표현하려면 어떻게 해야할까? 그래프의 adjacency matrix를 A, node feature를 X라고 할 때, 다음 식을 만족하는 permutation matrix P가 존재한다면 우리는 그래프 1과 2가 isomorphic하다고 말할 수 있다.
즉, 어떤 permutation을 통해 adjacency matrix를 같게 만들 수 있고, 이 permutation으로 node feature matrix까지 같게 만들 수 있다면 우리는 두 그래프를 isomorphic하다고 표현할 수 있는 것이다.
검증
Graph isomorphism의 정의는 간단하다. 하지만 두 그래프가 isomorphic한지의 여부를 검증하는 것은 꽤나 어려운 문제이다. 우리의 목적은, 위에서 언급한 graph isomorphism 식을 만족하는 P를 찾는 것이다. 이를 식으로 표현하면 다음과 같이 표현할 수 있다.
우리가 원하는 최적의 P는 위의 식을 0으로 만들어줄 것이다. 그러므로 우리는 graph isomorphism test 문제를 위 식을 minimize하는 P를 찾는 optimization 문제로 바꿀 수 있다. 즉, 모든 존재할 수 있는 permutation matrix에 대해서 위 식을 0으로 만들 수 있는 P를 찾는 것이다. 모든 permutation matrix를 전부 search해야하기 때문에 이의 complexity는 $O(|V|!)$가 된다.
활용
Graph isomorphism은 graph representation의 성능을 평가할 때 사용되기도 한다. 즉, 우리가 도출한 graph representation이 graph isomorphism을 test하는 데에 얼마나 잘 사용될 수 있는지를 평가해서 graph representation (z)의 성능을 평가하는 것이다. 이를 식으로 표현하면 다음과 같다.
즉, 두 그래프의 representation이 같은 것과 두 그래프가 isomorphism한 것이 서로 동치이면 우리는 그래프의 representation이 완벽하게 학습되었다고 평가하는 것이다.
이번 글에서 우리는 graph isomorphism이 무엇이고, 이것이 graph representation의 성능을 평가할 때 어떻게 활용될 수 있는지에 대해 알아보았다. 이번 글에서 다룬 모든 permutation matrix를 모두 대입해보는 검증 방법 이외에도, WL algorithm 등의 더 효율적인 graph isomorphism 검증 방법이 존재한다. 다음 글에서는 WL algorithm에 대해서 알아보겠다.
References
1. https://en.wikipedia.org/wiki/Graph_isomorphism
2. Hamilton, W. L. Graph Representation Learning.
최근댓글