<aside> 💡

프로젝트를 위해 공부했던 GIN에 대해 정리하고자 한다. 이번 포스팅은 'How Powerful are Graph Neural Networks?' 논문의 내용을 바탕으로 참고 자료와 함께 정리한 내용이다.

</aside>

0. Preliminaries

Isomorphism graph

• 노드 ordering 차이로 다르게 표현되지만 같은 구조를 가지고 있는 그래프
• 즉, 어떠한 permutation을 통해 adjacency matrix를 같게 만들수 있고, 이 permutation으로 node feature matrix 까지 같게 만들수 있다면 두 graph의 관계를 isomorphic 하다고 표현함
• 존재할 수 있는 모든 permutation matrix에 대해서 위 식을 0으로 만들 수 있는 $P$를 찾는 것으로 검증

$$ PA_1P^T=A_2\,and\,PX_1\,=\,X_2 $$

$$ min_{P\in \mathcal{P}}||PA_1P^T-A_2||+||PX_1-X_2||= 0 $$

                                             [ figure 1 ] Example Isomorph graphs 

WL(Weisfeiler-Lehman) Test

• 두 graph가 isomorphic(동치) 인지 검증하는 방법
• 검증 결과가 같다면 두 그래프는 isomorphic 하다 말할 수 있음
• 각 노드에 initial label을 부여하고, multiset에 대한 hash 결과를 해당 노드의 label 재할당
• label의 구성이 바뀌지 않을 때까지 혹은 $K$번 반복 수행

                                                                           (** 출처 : [The Weisfeiler-Lehman Isomorphism Test](<https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/>))

Graph isomorphism for evaluating graph representation

• 두 그래프의 representation이 얼마나 isomorphism 한지 바탕으로 graph representation 평가

$$ z_\mathcal{G_1}= z_\mathcal{G_2}\;if \;and \;only\;if\;\mathcal{G_1}\;is\;isomorphic\;to\;\mathcal{G_2} $$