[GNN] How Expressive are Graph Neural Network? (GIN model)

본 게시글은 Stanford 대학교 Jure Leskovec 교수님의

Stanford CS224W: Machine Learning with Graphs(2021) 강의를 듣고

학습을 목적으로 재구성한 글입니다

스스로 정리한 내용이라 오류가 있을 수 있습니다

 

https://web.stanford.edu/class/cs224w/

 

https://www.youtube.com/watch?v=6g9vtxUmfwM&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=15

---

이번 시간에 정리해볼 내용은

Theory of GNN에 관한 내용인데

어떤 GNN model이 어떤 task에 적합한지

어떤 GNN model이 expressive한지를 살펴본다

 

지금까지 우리가 배웠듯이 다양한 GNN model들이 제안되었다

그렇다면 이런 다양한 GNN model들 중에서

어떤 GNN model들 중에서 어떤 model이

가장 expressive할까?

 

 

 

우선 앞에서 배웠던 GNN model들을 잠깐 복습해보자

GCN은 aggregate를 평균내서 하는 mean-pool을 사용하는 방식이었다

 

 

 

GraphSAGE는 aggregation 방식이 많이 있을 수 있는 model이지만

가장 대표적으로는 최대값인 max-pool을 사용한다

 

 

 

 

그렇다면 위 ppt에서 예시 그래프를 한 번 잘 살펴보자

위 그래프에서 노드 1과 4는 degree가 2로 동일하다

하지만 접해있는 이웃 노드들이 다르기 때문에 차별화가 가능하다

하지만 1과 2는 차별화가 가능할까?

degree도 똑같고 symmetric하기 때문에 차별화가 불가능하다

 

 

그렇다면 우리의 key question은 

GNN의 Node embedding이

이런 local neighborhood structure를 제대로 인식할까?

 

 

 

위 그래프 예시에서 노드 1을 기준으로

computational graph를 생성해보자

computational graph를 2-layer로 생성하면

위와 같이 만들어진다

 

 

 

노드1과 노드2를 기준으로 각각 생성한 computational graph이다

 

 

 

GNN은 node의 ID들을 보는 것이 아니고

node feature만 보기 때문에

위의 1과 2의 computational graph는 구분할 수 없다고 한다

 

위의 예시에서는 노란색 노드는 모두

node feature가 동일하다고 가정했다

그래서 구분이 되지않는 것이다

 

 

 

보통은 local neighborhood가 다르면

computational graph도 달라진다

 

 

 

GNN의 node embedding은 rooted subtree structure를 포착하는데

한마디로 rooted subtree가 다르면 다를수록

GNN이 더욱 expressive하다는 뜻이다

 

 

 

대부분의 GNN의 subtree들은 각각 node embedding에

injective하게 mapping이 되어야한다

이게 무슨 말이냐면 각각 서로 다른 노드들의 node embedding 값들은

각각 서로 다르게 매핑이 되어야한다는 것이다

 

 

 

이렇게 각각 노드들의 subtree들이 서로 다르게 mapping 되어야

많이 expressive한 GNN이 된다

 

 

따라서 GNN에서는 모든 이웃에서의 aggregation이

injective하다면 당연히 subtree structure도 injective하게 된다

 

 

 

그렇다면 이제 강력한 GNN을 design하는 방법에 대해서 알아보자

 

 

 

 

한 노드의 이웃을 나타내는 neighbor aggregation은

multi-set 즉, 중복집합으로 표현이 가능하다

 

 

 

그렇다면 인기있는 2개의 대표적인 GNN들

GCN과 GraphSAGE를 바탕으로 case study를 해보자

 

 

 

우선 GCN부터 살펴보자

 

우선 이론적으로 GCN의 mean-pooling으로는

중복되는 node feature가 있는 multi-set을 구분하지 못한다

위 예시를 한 번 잘 살펴보자

왼쪽과 오른쪽은 엄연히 다른 case이지만

mean-pooling을 수행하면 그 값은 똑같이 나온다

 

 

 

실제로 one-hot encoding을 통해서 계산한 것을 살펴보자

이렇게 노란색 node와 파란색 node를 각각

위처럼 one-hot encoding을 수행하고

mean-pooling을 때리면 결국 최종값은 같아진다

 

 

두번째로 GraphSAGE에서의 max-pooling을 살펴보자

max-pooling도 multi-set을 구분할 수 없는 사례가 있다

위 사례를 한 번 잘 살펴보자

 

 

 

위처럼 동일하게 one-hot encoding을 수행해서

max-pooling을 수행하면 3가지 케이스 모두

노드 구성이 다르지만 최종 결과값은 동일하게 나오는 것을 확인할 수 있다

 

 

 

 

그렇다면 위에서 모든 node에 대해서 injective하게 mapping이 되어야

가장 expressive한 GNN model이라고 했는데

앞에서 GCN, GraphSAGE 모두 injective하지 못했다

 

 

 

따라서 우리의 목표는 가장 powerful한 GNN을 디자인하는 것이다

 powerful한 GNN이란 것은 앞에서 말했듯이

이웃 노드 aggregation function을 multi-set로 사용했을 때

injective하게 표현할 수 있으면 된다

 

 

 

multi-set S를 어떤 non-linear function에 넣은 다음

그 값을 다 더해서 또 다른 어떤 non-linear function에 넣어준다

 

 

 

그렇다면 위에서 나온 2가지의 non-linear function을

어떻게 모델링하면 좋을까?

우리는 이걸 MLP로 수행하려고 한다

 

그렇다면 injective하게 결과를 가져오는게 어떻게 MLP로 가능할까?

이는 Universal Approximation Theorem에 기반한다

이게 무슨 이론이냐하면

단 하나의 hidden layer를 가진 MLP로도 충분히 큰 노드수와

적절한 activation function을 사용하면

임의의 continuous function을 임의의 accuracy로 근사 가능하다는 이론이다

 

따라서 우리는 neural network에 MLP를 활용해서

inejctive multiset function을 모델링하고자 하는 것이다

 

 

이렇게 MLP로 injective function이 한 번 나오게하고

그걸 다 더한 값에 또 MLP를 적용하도록 한다

 

 

 

그렇다면 이런 injective multi-set function을 

가장 잘 활용한 표현력이 가장 좋은 GNN model을 알아보자

 

GIN(Graph Isomorphism Network)은

MLP을 사용해서 aggregation 함수를

injective하게 설계한 GNN model이다

 

 

GIN model은 우리가 강의 아주 초반에 배웠던

Weisfeiler-Lehman kernel의 neural network 버전이라고 생각하면 된다

그렇다면 이전에 배웠던 WL graph kernel을

다시 복습해보자

 

 

강의 아주 초반 node embedding 부분에서

WL kernel을 color refinement algorithm으로 배웠다

 

첫 번째 노드의 color를 c(0)(v)라고 정의할 때

 

노드의 색상을 이렇게 정의할 수 있는데

이게 어떤 뜻이냐고하면

자기 자신의 노드와, k의 이웃노드들을 합친 다음

HASH 함수를 적용해서 k+1번째 색을 추출한다

 

이 과정을 k번 거치면 c(k)(v)가 되는 것이고

이는 k-hop neighborhood를 반영하게 된다

 

 

 

위에 저렇게 2개의 그래프가 있다면

이웃 노드들을 합쳐서 아래와 같이 나타낸다

 

 

그럼 그걸 바탕으로 HASH를 이용해서

각 aggregated된 노드별로 색상을 적용한다

그래서 해당 색상을 injective하게 적용한다

 

 

 

그래서 이렇게 이웃을 aggregate하고 또 hash하는 과정을 반복해서

결과가 stable 해질 때까지 반복한다

2개의 그래프의 색을 set을 적용했을 때

색의 set이 동일하면 Ismorphic한 그래프로 간주한다

 

 

GIN model은 injective hash function을 만들기 위해서

NN을 사용한다

 

따라서 위와같은 식으로 modeling을 할 수 있는데

이웃 노드들인 c(k)(u)들에 MLP를 적용해서 모두 합한 것과

자기 자신에 MLP를 적용시킨것에 (1+입실론)을 곱한 값과 더한 다음

그것을 다니 MLP에 적용시켜주는 방식으로

injective하게 각각의 노드들을 mapping 시킨다

여기서 입실론은 학습 가능한 scalar이다

 

 

 

따라서 지금까지배운 GIN의 내용을 요약해보자

 

WL kernel과 유사하게

node vector들을 aggregation하고 hash하는 과정을

계속 반복해서 stable 될 때까지 적용하는 방식으로

injectivity를 보장한다

 

GIN iterations를 k-steps만큼 수행했으면

c(k)(v)는 k-hop 만큼의 이웃 정보를 담고있게 되는 것이다

 

 

 

위에서 설명한 내용과 동일한 내용이다

따라서 GINConv는 다른 input이 들어가면

다른 embeddings로 mapping을 시켜주는 것이다

 

 

 

GIN과 WL Graph Kernel의 차이점을 비교해보고

이번 강의 내용을 정리해보고자한다

 

GIN이 WL Graph Kernel의 nerual network 버전이다

따라서 GIN이 노드 간 유사한 점을 더 capture 가능하고

parameter가 downstreatm task로 부터 학습 가능하다는 장점이 있다

 

 

 

이렇게 GIN은 모든 노드들을 구별할 수 있는

강력한 GNN model 중에 하나로 손꼽힐 수 있지만

이 역시도 결국 node feature가 다 똑같으면

표현력이 줄어든다고 한다

 

위 2개의 그래프가 바로 그 대표적인 예시이다

 

 

이번에 강의에서 배운 내용에 대한 복습이다

 

우리는 지금까지 배운 GCN, GraphSAGE 모델들의

표현력을 살펴보았고 computational graph가

일부 case에서 동일하게 나온다는 문제를 확인할 수 있었다

 

따라서 expressivee한 GNN model은

injective하게 mapping할 수 있는 모델이고

그걸 수행하는 것이 바로 GIN model이다