GIN은 graph isomorphism network의 줄임말로, WL test와 같은 강력한 expressive power를 가지고 있기 때문에 가장 널리 쓰이는 GNN 구조 중 하나이다. 이번 글에서는 GIN이 무엇인지와 함께 GNN의 expressive power가 어떻게 정의되는지에 대해서 알아보겠다.
Motivation
GIN의 motivation을 설명하기 위해서는 GNN의 expressive power가 무엇인지에 대한 정의가 필요하다. Message passing neural network (MPNN)의 정의에서 살펴보았듯이, GNN의 layer는 aggregate (message) function과 combine (update) function으로 구성된다.
이러한 aggregate와 combine function을 어떻게 정의하느냐가 GNN 구조 설계의 핵심이고, aggregate function을 얼마나 표현력이 좋은 function으로 정의하느냐가 GNN의 expressive power를 결정한다고 할 수 있다. GNN의 aggregation function은 보통 현재 노드의 이웃 노드들의 multiset을 input으로 받아서 이를 현재 노드의 representation으로 표현한다.
GCN, GraphSAGE 등 기존 연구들에서는 aggregate function을 mean, max 등의 표현력이 낮은 함수로 정의하였고, 이는 GNN의 expressive power를 낮게 만들 수밖에 없었다.
Expressive power에 대한 직관적인 이해를 위해 예시와 함께 살펴보겠다. 예를 들어, 다음과 같은 그래프들이 있다고 하자. 우리의 목표는 두 다른 그래프에 속해 있는 노드 v, v'의 representation을 구별하는 것이다.
GNN에서는 위에서 언급했듯이 현재 노드의 이웃들의 representation을 aggregate하여 현재 노드의 representation을 표현한다. 예를 들어, 노드의 feature를 one-hot vector로 표현한다고 하자. 우리의 예시에서는 파란색이 (1,0,0), 초록색이 (0,1,0), 빨간색이 (0,0,1)이라고 하겠다. 첫 번째 예시 그래프처럼 모든 이웃 노드의 feature가 같다고 하자. 이러한 경우에는, aggregate function이 mean일 때에도 두 그래프가 모두 (1,0,0), max일 때에도 (1,0,0)으로 두 그래프를 구별할 수 없다. 다음으로, 두 번째 예시 그래프를 살펴 보자. Aggregation function이 mean이라면 노드 v의 representation은 (0,0.5,0.5), v'은 (0,0.33,0.66)으로 둘의 구별이 가능하다. 하지만 aggregation function이 max라면 노드 v의 representation은 (0,1,1), v'의 representation도 (0,1,1)로 둘의 구별이 불가능하다. 마지막으로, 세 번째 예시 그래프의 경우에는 mean과 max가 두 노드 v와 v'에 대해 각각 (0,0.5,0.5), (0,1,1)의 같은 representation을 보이기 때문에 둘의 구별이 불가능하다.
이렇게 기존에 사용해오던 mean, max aggregation은 각 노드들에 대해 적절한 representation을 도출하는데에는 한계가 있었고, 이에 GIN이 등장하게 되었다.
정의
WL test를 만족하는 GNN
위에서 언급한 것처럼 우리는 현재 노드의 이웃 노드들의 multiset을 input으로 받는 aggregation function의 expression power를 올리는 것을 목적으로 한다. 그리고 가장 이상적인 GNN은 WL test처럼 다른 구조를 가지는 그래프를 다른 representation으로 매핑할 수 있어야 한다. 이를 위해서는 다음과 같은 두 가지 조건이 만족되어야 한다.
첫 번째 조건은 다음과 같이 aggregation과 update function, 즉 현재 노드의 embedding과 이웃 노드들의 multiset의 embedding이 일대일 함수(injective function)여야 한다는 점이다.
여기서 일대일 함수란, 서로 다른 input을 서로 다른 output으로 매핑하는 것을 말한다. 예를 들어, 다음 그림과 같은 함수는 일대일 함수가 아니다. 즉, 다른 구조를 가지는 서로 다른 이웃 노드들과 현재 노드를 input으로 받았으면 이들은 항상 다른 embedding으로 매핑하는 것이다.
두 번째 조건은 노드 feature들의 multiset을 input으로 받는 graph-level readout function이 일대일 함수여야 한다. 즉, node feature의 multiset이 다른 두 그래프는 서로 다른 embedding으로 매핑되어야 한다는 것이다.
GIN의 구조
GIN은 위의 두 조건을 만족하도록 설계되어야할 것이다. 이를 위해 우리는 aggregation function으로 sum을 사용한다. 그 이유는 sum은 multiset을 input으로 받았을 때 각 multiset에 대해 unique한 embedding을 매핑할 수 있는 function이기 때문이다. 예를 들어, 다음과 같은 input node들이 있다고 하자.
이들을 aggregate한다고 할 때, 아래 그림과 같이 sum은 mean이나 max보다 훨씬 뛰어난 expression power를 가질 것이다. 예를 들어, 노드의 feature를 one-hot vector로 표현한다고 하자. 우리의 예시에서는 파란색이 (1,0), 빨간색이 (0,1)이라고 하겠다. 그러면 sum은 어떤 노드의 개수가 input으로 들어오든 이들을 모두 구별할 수 있을 것이다. 하지만 mean은 (파란색 4개, 빨간색 2개)가 들어오든 (파란색 2개, 빨간색 1개)가 들어오든, 심지어는 (파란색 100개, 빨간색 50개)가 들어오든 모두 같은 embedding으로 매핑할 것이다. 또한 max는 더 심하게 빨간색과 파란색이 포함되어 있기만 하면 이들을 모두 같은 embedding으로 매핑할 것이다. 그러므로 우리는 sum이 mean, max에 비해 가장 강한 expression power를 가짐을 알 수 있다.
그래서 GIN은 aggregation function으로 sum을 사용한다. 우선 GIN의 aggregation과 update function부터 살펴보겠다. 이는 다음과 같이 정의된다.
이 때, MLP가 사용되는 이유는 MLP는 적절한 개수 이상의 layer를 가지고 있으면 어떤 함수든 표현할 수 있기 때문이다.
다음으로, GIN의 graph-level readout function은 다음과 같이 정의된다. 즉, 모든 노드의 representation을 각 layer별로 구해서 이들을 concat하는 것이다.
결과
이 연구에서는 GIN의 성능을 graph classification 실험을 통해서 측정하였다. 그 결과는 다음과 같다. Y축이 accuracy이기 때문에 더 위에 있을수록 성능이 좋은데, GIN이 WL subtree kernel만큼은 아니지만 학습을 거듭할수록 그에 준하는 결과를 보여줌을 알 수 있다.
이번 글에서는 graph isomorphism network (GIN)에 대해 알아보았다. 다음 글에서는 또 다른 기본적인 GNN인 GraphSAGE에 대해 알아보겠다. 독감 때문에 강제 격리 + 재택 근무.. 오전까지 좀 컨디션이 안 좋았는데 저녁으로 고기 먹구 좀 괜찮아져따
References
Xu, K., Hu, W., Leskovec, J., & Jegelka, S. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations 2019 (ICLR 2019).
최근댓글