머신러닝&딥러닝

Graph Neural Network (GNN)

에스더 2021. 12. 9. 15:28

Graph Theory

하나의 그래프는 objects과 entities사이의 쌍 관계를 분석하기 위한 수학적 구조로 활용되며, nodes(vertices or points)와 nodes들이 이어진 edges(links or lines), 두가지 요소로 구성되어 있다. 한 그래프의 edges가 방향성을 가지고 있는가, 가지고 있지 않는가로 directed graph와 undirected graph로 나뉠 수 있고, 만약 그래프의 모든 nodes들이 모든 다른 nodes과 연결되어 있다면 이 그래프는 complete graph라고 불린다.

 

 

그래프 $G$는 $G=(V, E)$로 나타내어질 수 있고 이 때, $V$와 $E$는 각각 a set of nodes와 edges를 의미한다.

그래프를 신경망에 넣기 위해서는 주로 메트릭스 형태의 features로 변형한다. 어떤 한 그래프 nodes의 개수를 N, 각 node의 feature 개수를 F라고 한다면, 주로 그래프는 $N \cdot N$ adjacency matrix, $A$, 로 표현되지만, $N \cdot F$ 크기의 feature matrix or node attributes, $X$, 로 표현되는 경우도 많다. 가끔은 nodes가 아닌 edges의 관점에서, $N_{\text{edges}}$가 edges의 개수이고 $S$가 edges의 feature 개수일 때, $N_{\text{edges}} \cdot S$ 사이즈의 Edge attributes matrix, $E$, 로 표현되기도 한다.

Difficulties to Analyse Graphs - 그래프를 분석하는 것을 어렵게 하는 요인

1. 그래프가 Euclidean space에 존재하는 것이 아님

2. 그래프의 형태가 고정되어 있는 것이 아님

3. 사람이 해석하기 용이하도록 시각화 (visualisation)하는 것의 어려움

그럼에도 불구하고 그래프가 유용한 이유는

Relationships이나 interaction과 같은 추상적인 개념을 다루기에 용이함

어떠한 문제를 더 간단히 표현하거나 다른 관점에서 표현하여, 복잡한 문제를 해결하는 데에 도움을 줌

ex) Social Network, Fraud patterns, Power consumption patterns 등

 

An Undirected Graph / A Directed Graph / A Completed Graph 

 

Graph Neural Network

GNN에서 각각의 node들은 자신의 이웃 nodes와 그들과의 연결로 정의된다. 만약 한 node가 아무런 이웃 nodes와 그들과의 연결을 가지고 있지 않다면 이 node는 아무런 정보를 갖고 있지 않은 셈이다. 그래프에서 한 node를 state($x$)라고 할 때, GNN은 이 state($x$)로 output($o$)을 만들어 낸다. 이 과정을 $n$번 반복함으로써 생성되는 node의 최종 state($x_n$)을 node embedding이라고 한다. 모든 GNN의 과제는 이웃하는 nodes들의 정보들을 통하여 각 node의 node embedding을 결정하는 것이다.

 

Message Passing Neural Network로서의 GNN

모든 GNN은 feature들을 전달하고 nodes를 업데이트 한다는 점에서 massage-passing (or node update & readout) 함수를 갖는 Message Passing Neural Network (Gilmer et al., 2017)라고도 표현된다.

 

A Massage Passing Funtion: $M_t:m^{l+1} = M_t(H^l,A)$

A Node Update Function: $U_t: H^{l+1} = U_t(H^l,m^{l+1})$

A Readout Funtion: $R_t$ (for graph classification): $y = R(H^l)$

GNN의 세가지 종류

Recurrent Grapn Neural Networks (RecGNN)

Spatial Convolutional Networks

Spectral Convolutional Networks

 

 

 

Recurrent Graph Nerual Networks (RecGNN)

RecGNN은 Banach Fixed-Point Theorem을 가정한다.

$(X, d)$가 complete metric space이고 $(T:X→X)$가 contraction mapping 일 때, $T$는 a unique fixed point, ($x^\ast$), 를 갖고 모든 $x\in X$ 에 대해, $\lim_{n \to \infty}T_n(x) = x^\ast$로 나타낼 수 있다.

따라서, $x$에 mapping $T$를 $k$번 반복한다면, $x^k$는 $x^{(k-1)}$와 거의 동일하다.

$$x^k = T(x^{(k-1)}), \text{ where }k \in (1,n)$$

 

RecGNN은 아래와 같은 parameterised function $f_w$를 통해 nodes를 업데이트 한다.

$${\bf x}_n = f_{\bf w}({\bf l}_n, {\bf l}_{co[n]}, {\bf x}_{ne[n]}, {\bf l}_{ne[n]})$$

${\bf l }_n$: 현재 node $\small[n]$의 features

${\bf l}_{co[n]}$: node $\small [n]$의 edges

${\bf x}_{ne[n]}$: 이웃하는 nodes들의 state

${\bf l}_{ne[n]}$: 이웃하는 nodes들의 features

 

An Example of Node State Update based on the Information in its Neighbours (Scarsellli et al., 2009)

 

이 과정을 $k$번 반복한 이후, 최종 node state는 각 noded에 대한 결정을 할 수 있는 output인 ${\bf o}_n$을 생성한다.

$${\bf o}_n = g_w({\bf x}_n, {\bf l}_n)$$

 

GNN Application

Node Classification

Node Classification의 task는 그래프의 모든 node에 대하여 node embedding을 예측하는 것이다. 보통 이러한 과제들은 그래프의 일부만 labeled되어 있는 semi-supervised의 방식으로 진행되며, citation networks, Reddit posts, Youtube videos와 Facebook friends relationship 등이 이러한 분류가 적용된 사례들이다.

 

Link Prediction

Link Prediction의 과제는 그래프의 entities 사이의 관례를 이해하고 두 entities 사이에 connection이 있는지를 예측하는 것이다. 추천 시스템은 Link Prediction을 활용한 예들 중 하나인데, 이 때 모델은 각기 다른 대상에 대한 사용자들의 후기를 통하여 사용자의 선호도를 예측하고 사용자에게 더 알맞는 대상을 추천해 주도록 시스템을 조정한다.

 

Graph Classification

Graph Classification은 그 이름에서 알 수 있듯이 그래프 자체의 분류를 뜻한다. 여러가지 산업군에서 다양하게 활용되고 있는 분류 방법이다. 주로 Chemistry, Biomedical, Physics 등의 분야에서 활용되기도 하는데, 모델은 분자 구조를 받아 이를 각기 다른 카테고리로 분류한다.

 

 

 

 

 

Reference