Graph Neural Networks (GNN) / 그래프 뉴럴 네트워크 기초 개념 정리

그래프 뉴럴 네트워크는 그래프 구조에 대해 직접적으로 작동하는 뉴럴넷으로, 그래프 노드 사이의 상관성을 모델링한다. 따라서 그래프 분석(graph analysis)이 필요한 분야들 - ▲소셜 네트워크 분석, ▲ 추천 시스템 ▲ 지식 그래프 등에서 최근 인기가 높아지고 있다.

그래프 (graph)란?

그래프 G는 방향성이 있거나(directed) 없는(undirected) 엣지(edge)로 연결된 노드(nodes=verticles)들의 집합이다. 여기서 노드와 엣지는 일반적으로 풀고자 하는 문제에 대한 전문가의 지식이나 직관 등에 의해 구성된다. 

예를 들어 분자 속 원자들, 소셜 네트워크의 사용자, 교통 시스템에서 도시들, 뇌에 있는 뉴런들 등 연구자가 그래프의 노드와 엣지를 정의할 수 있다.

그래프 뉴럴 네트워크 (GNN)

GNN의 기본은 그래프에 있는 노드 사이의 관계를 모델링하고, 그에 대한 representation을 생성하는 것.

 

그래프 뉴럴 네트워크의 작동 원리를 이해하기 위해 다음과 같은 예시를 생각해보자

 

"SNS 사용자의 네트워크 관계가 그래프로 주어질 때 해당 유저의 영향력을 예측하기"

이를 수행하기 위해서는 임의의 구조의 그래프 G가 들어왔을 때 그를 하나의 representation으로 표현해야 한다.

즉, F(G) = embedding 으로 변환할 수 있는 함수 F를 찾는 것이 목표이다. 

그래프를 임베딩할 수 있는 데에 사용할 수 있는 대표적인 아키텍쳐는 RNN(Recurrent Neural Networks)다.

RNN은 체인으로 연결된 구조 데이터에 사용할 수 있는 특별한 구조로, 이전 타임 스텝의 hidden과 현 타임 스텝의 인풋을 결합하여 현재의 hidden representation을 생성하는 것이 특징이다. 

<Recurrent Neural Networks>

RNN을 이용해 그래프 뉴럴 네트워크를 구성하기 위해서는 다음의 두 가지를 먼저 생각해야 한다

 

1. 각각의 노드를 embedding 하기 

   - 노드 하나하나는 RNN unit으로 사용되기 때문

   - 이 예시에서는 사용자의 나이, 성별, 활동 기간 등의 설명 변수를 벡터로 만들어 임베딩할 수 있다.

 

2. 엣지 타입에 따른 뉴럴 네트워크 정의하기 

   - 그래프에는 다양한 엣지 타입이 있을 수 있는데, 종류에 따라 네트워크를 다르게 구성한다.

   - 예를 들어 SNS에서 '친구(friends)' 관계와 '팔로우(follow)' 관계가 있다면, 이 둘은 다른 weight를 사용하는 네트워크로 표현하는 것이다.

 

이제 각 노드를 recurrent unit으로 생각해보자.

각각의 노드는 가장 인접한 노드를 (t-1) 시점으로 보고 recurrent unit을 사용해 새로운 히든을 생성할 수 있다.

 

예를 들어 아래 그림에서 가운데에 있는 노드에 대해 가장 인접한 노드 ①에 대해 NN_1을 사용해 정보를 결합, 새로운 representation (파란색 블록으로 표시)을 생성해낼 수 있다.

같은 방식으로 가장 인접한 네 개의 노드에 대해 RNN을 적용하면 네 개의 히든을 얻게 된다. 노드 사이의 순서를 무시한다면, 이 네 히든을 더하여(sum) 가운데 노드에 대한 새로운 representation을 생성할 수 있다. 이렇게 생성된 representation은 이제 한 단계 인접해 있는 노드의 정보를 포함한 representation이 된다.

같은 방식으로 모든 노드에 대해 한 단계 인접해 있는 노드와 RNN으로 정보를 결합하게 되면, 이제 모든 노드는 각자의 인접한 노드의 정보를 알고 있는 representation을 가지게 된다.

그래프에 대한 최종 임베딩은 업데이트된 노드 representation을 합(sum)하여 생성할 수 있다. 이 경우에도 노드의 순서 정보는 무시된다.

 

이 예시에서는 한 단계 인접한, 즉 (t-1) 스텝만 고려한 RNN을 예시로 했지만, 두 단계, 세 단계 인접한 노드들까지 고려할 수도 있다. 즉, GNN에서 몇 개의 타임 스텝 k를 고려할지는 네트워크의 하이퍼파라메터로 설정하게 된다. 더 많은 타임 스텝을 고려한 임베딩은 더 많은 노드의 정보를 가지게 된다.

---

(참고) 그래프 활용의 유용성

1. 그래프는 유연한 데이터 구조를 가지고, 다양한 데이터 구조로 일반화가 가능

- 이에 따라 데이터를 그래프 구조로 표현할 때 문제를 새로운 관점에서 바라볼 수 있음

- 예를 들어 얼굴 인식 문제를 다음과 같이 여섯 가지 다양한 형태의 그래프로 표현할 수 있다

Antonakos et al., CVPR, 2015 - Figure 2: (a) complete graph (b) chain per area (c) chain and compete per area (d) chain and complete per area with connections between them (e) minimum spanning tree (f) empty graph

- 또한 사전 지식을 이용해 데이터에 바이어스를 주는 것도 가능하다.

  예를 들어 포즈 추정 문제에서 인간 관절 움직임에 대한 해부학적 지식을 모델에 주는 식.

 

2. 데이터 그 자체가 자연스럽게 그래프로 표현되는 경우가 있음

- 분자 구조, 소셜 네트워크 등 

 

3. 기존에는 어려웠던 문제들; 암 치료제 개발/ 뇌 커넥텀에 대한 이해/ 에너지 물질 발견 등에 활용 가능

---

참고 자료:

https://www.youtube.com/watch?v=cWIeTMklzNg

https://towardsdatascience.com/a-gentle-introduction-to-graph-neural-network-basics-deepwalk-and-graphsage-db5d540d50b3

https://medium.com/@BorisAKnyazev/tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-1-3d9fada3b80d

http://snap.stanford.edu/proj/embeddings-www/files/nrltutorial-part2-gnns.pdf

https://theaisummer.com/Graph_Neural_Networks/

---