[GNN] Graph Neural Networks - 1

 

 

 

 

이전 글에서 Node를 어떻게 벡터화 시키는 지에 관해서 공부하였다.

Node를 벡터화 시켰다면 딥러닝의 방식을 진행할 수 있을까?

 

 

 

 

 

하지만 그래프 분야는 image나 text와 같은 데이터보다 훨씬 복잡한 형태를 가지고 있다.

 

 

 

 

 

단순히 그래프에서 인접 노드 간의 정로를 가진 매트릭스를 input으로 넣는 것을 어떨까?

 

하지만 노드의 수의 제곱 이상의 데이터가 생성되기 때문에 파라미터가 너무 많아진다.

거기에 노드를 단순히 우리가 정한 임의의 순서대로 구별해 두었기 때문에 진행 중에 순서가 뒤바뀌면 알 수가 없어진다.

 

 

 

 

GNN는 CNN(Convolution Neural Network)의 idea를 가져온다.

 

CNN은 이미지 데이터를 convolution 연산으로, 중심 노드의 반경(window)으로부터 특징을 잡아간다.

이때 sliding window의 크기에 따라 주변의 노드를 반영하게 된다.

 

 

 

하지만 graph는 image처럼 노드가 격자 방식으로 분포하지 않는다.

 

따라서 중심 노드로 부터 이어진 이웃 노드들을 하나의 윈도우로 뭉치게 만들자.

 

 

 

A는 자신의 이웃인 B,C,D로부터 정보를 받는다.

B는 자신의 이웃인 A,C

C는 A,B,E,F,

D는 A에게 받는 식이다.

 

결국 모든 노드들이 이웃에게 받는 데이터를 표현하면 다음과 같이 만들 수 있다.

 

여기서 D 노드가 만드는 computation graph를 살펴보면 다른 노드들과 구조가 많이 다르지만, 

E와 F는 구조가 비슷한 것을 확인해 볼 수 있다.

 

 

 

 

 

지금은 이웃 노드만 고려했지만, 더 많은 층까지 고려할 수 있을까?

 

더 깊은 층까지 고려한다면, 말단 노드 츠인 Layer-0은 node의 특징인 input 데이터를 사용하고

이후, Layer-k까지는 이웃 노드로부터 information을 받도록 만들면 된다.

 

각 Layer는 층이 되므로 k만큼의 층을 쌓을 수 있다.

 

 

 

이때 정보를 조합하는 역할을 하는 Aggregation(그림에서 box들)은 어떻게 구현해야 할까?

Aggregation function은 일단, permutation invariant를 만족 해야 한다.

permutation invariant의 의미는 입력 벡터 요소들의 순서와 상관 없이 동일한 결과를 내야한다는 것이다.

예를 들어 input이 A,B 순서로 들어오든 B,A 순서로 들어오든 aggregation의 결과는 동일해야 한다.

 

 

 

 

기본적인 접근은 이웃들이 전달해준 message의 평균을 신경망에 반영하는 것이다.

h(k+1)을 구하기 위해 이전 층의 h(k)를 사용한다.

각 층이 신경망이기 때문에 최종적인 출력은 비선형 함수를 통해 만들어준다.

 

K층까지 모두 구했다면 이 값이 최종적인 node embedding의 값이 된다.

 

이때 층마다 학습이 되는 것이 weight matrix인 W와 B이다.

최종적인 node embedding이 완료가 되면, SGD를 통해 가중치들이 학습된다.

 

 

 

 

 

각각의 층에서의 Aggregation된 embedding vector들을 한데 모아서 Matrix를 만들 수 있다.

 

 

이 H 매트릭스에 node v에 대한, 인접 매트릭스(A)를 곱해주면, v의 이웃에 대한 embedding matrix를 구할 수 있다.

 

~A는 sparse matrix로 효율적인 연산이 가능해진다.

 

 

 

 

 

이제 각 노드의 embedding인 z를 라벨로 사용해 지도 학습을 시킬 수 있다.

예를 들어 drug를 노드들로 나타내면 해당 약이 safe한지, toxic 한지를 라벨링 시킬 수 있을 것이다.

 

 

 

비지도 학습에서는 node u와 v의 유사도를 통해서 embedding을 가지게 할 수 있다. 

유사도는 이전글에서 확인했던 Random walks 방식들을 통해서 구할 수 있다.

 

 

각 층의 파라미터는 공유되므로 새로운 노드가 들어와도 적용 가능하다.

즉, 일반화를 시킬 수 있다.

 

 

 

 

참조

강의 자료: http://web.stanford.edu/class/cs224w/index.html

 

강의 영상: https://www.youtube.com/watch?v=JAB_plj2rbA&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn

 

참조 게시글: https://velog.io/@tobigsgnn1415/6.-Graph-Neural-Networks-1-GNN-Model