GNN, GCN

GNN(Graph Neural Network)

Graph representation

GCN(Graph Convolutional Network)

 

---

GNN(Graph Neural Network)

GNN이란?

Influential users form Twitter Social Graph

: 기존 neural network의 input으로 사용되던 data(ex. image, sequential vector, ...)와 다르게 input data의 구조가 graph(ex. social graph, analysis graph, 3D graph, ...)의 형태일 경우에 직접 사용되는 neural network를 의미한다. vertex, edge, graph level에서의 prediction에 사용 가능하다. 발표된 논문으로는 Recurrent GNN, Spatial Convolutional network, Spectral Convolutional newtork로 구분 가능하다. 

 

GNN의 핵심은 node(vertex)가 edge(neighbor)에 의해 정의된다는 것이다. 따라 다음 sector에서 언급하겠지만, 모든 node는 각각의 feature를 설명하는 state로 표현된다. 

 

1) Recurrent GNN

Banach Fixed-Point Theorem

: k가 크면, x에 mapping T를 k번 적용한 값과 k+1번 적용한 값이 거의 같다는 의미인 위 theorem을 기초로 만들어 졌다.

 

An illustration of node state update based on the information in its neighbors

위 graph를 아래의 식을 사용하여 node' state를 update한다. 

 

l_n: node n's feature

l_{co[n]}: node n's edges' feature

l_{ne[n]}: node n's neighbors' feature

x_{ne[n]): node n's neighbors' state

 

k iteration을 통한 update 후, 마지막 state(x_n)과 feature(l_n)을 사용하여 결과값(o_n)을 출력한다. 

 

 

2) Spatial Convolutional network

: image classification과 detection과 같은 problem에 많이 사용되는 CNN과 비슷하다. CNN에서 Convolution의 아이디어는 learnable filter를 통해 중심 pixel의 주변 pixel을 합치는 것이다. 이 아이디어에서 주변 pixel 대신, 연결된 점의 특징을 적용한 것이다. graph convolution은 vertex domain에서의 graph filtering에 따르면, node neighborhood를 포함한 graph signals들의 aggregation로 일반화될 수 있다. classic-CNN based model, propagation-based model, other related general frameworks 등으로 분류된다. 

 

classic-CNN based model

: CNN에서 image와 같은 gird-like data에 대한 처리에는 다음의 특징이 존재한다. 

a. neighboring pixles for each pixel의 개수가 고정되어 있다. 

b. image를 스캔하는 spatial order가 자연적으로 결정되어 있다. 

 

그러나 graph data에 대해서는 위 두가지 모두 결정된 상태가 아니다. 이러한 issue를 해결하기 위해, graph 내 locally-connected된 지역을 추출하여 node-ordering을 하여 fixed-length seuqence로 만들고 각 nodes' neighbor을 fixed-sized vector로 표현하거나, fixed-size learnable set of filter를 재구성하는 등의 시도를 통해 활용한다. 

 

propagation-based model

: vertex domain에서 neighboring nodes로부터 node representation을 재구성한다. p'th layer에서의 node를 표현하기 위해, graph diffusion process, universe patch operator 등을 사용하여 node를 표현한 뒤 propagate & aggregate를 기존과 같이 CNN을 진행한다. 

 

other related general frameworks

: 위에 언급한 두가지 방식에 해당되지 않는 model로, node's attribute와 edges' attribute를 input으로 하는 function을 구성 하는 등의 방식을 사용한다. 

 

3) Spectral Convolutional network

: graph signal processing theorem을 기반으로 고안되었으며, 제안되는 두 층으로 된 신경망을 아래의 식으로 정리할 수 있다. 이는 아래의 GCN sector에서 언급되는 방식이다. Spectral Convolutional network와 Spatial Convolutional network는 다른 내용을 기초로 하고 있지만 결과적으로 비슷한 연산 과정을 거친다. 현재 대부분의 Convolutional GNN이 이러한 방식으로 동작한다. 

 

 

node를 어떻게 전달할지 정의하는 함수를 message-passing function이라고 하며, node update function, readout function을 차례로 거치며 GNN network를 구성하기도 한다.

 

 

GNN의 활용

1) Node Classification

: Node embedding을 통해 node를 분류하는 문제다. 일반적으로 graph의 일부만 labeling된 상황에서 semi-supervised learning을 수행한다. 대표적인 응용 영역으로는 Reddit posts, Youtube video 등이 있다. 

 

2) Link Prediction

: graph's nodes 사이의 관계를 파악하고 두 node 사이에 얼마나 relationship이 존재하는지 prediction 하는 문제다. 대표적인 응용 영역으로는 facebook friend recommendation, youtube / netflix video recommendation 등이 있다. 

 

3) Graph Classification

: graph 전체를 여러 카테고리로 분류하는 문제다. image classification과 비슷하지만 대상이 graph라고 보면 된다. 분자 구조가 graph의 형태로 제공되어 분류하거나 하는 산업 문제에 광범위하게 사용가능하며 다양한 응용이 가능하다. 

 

---

Graph representation

Graph란?

: graph는 기본적으로 node(vertex)와 edge로 구성된다. node(vertex)는 한 개의 input data, edge는 두 개의 data 간의 relationship을 의미한다. 

 

Graph의 표현

: graph 내 node 간의 모든 relationship를 data로 표현해야 하므로 data는 node 간의 relationship 정보를 표현하는 Adjacency matrix와 node 자체가 가지고 있는 feature 정보를 표현하는 Feature matrix로 나타낸다. 

 

1) Adjacency matrix

a. 좌측에 해당하는 network가 존재할 때, n개의 node를 n*n matrix로 표현한다. 

b. 생성된 Adjacency matrix 내 value는 (A_ij: node i와 node j의 relationship 여부)를 만족하는 value로 채워준다. 

 

2) Feature matrix

a. 각 input data(node 자체의 정보)에서 이용할 feature를 먼저 선택한다. 

b. Feature matrix에서 각 row는 선택한 feature에 대해 각 node가 가지고 있는 값을 의미한다. 

(ex. row1: node1의 feature value)

 

---

GCN(Graph Convolution Network)

GCN이란?

: graph network에 CNN의 convolution 개념을 적용한 것으로 CNN에서의 두 가지 특징인 Weight Sharing과 Learning local feature이 적용된다. 

 

1) Weight Sharing

Convolution layer

: CNN에서는 input data(ex. image)에 동일한 weight를 갖는 동일한 filter를 이동하면서 연산을 수행한다. 이 때, 보통 stride를 filter 크기보다 작게 설정하여 이동시키므로 중복되어 연산되는 pixel이 다수 존재하게 된다. 

 

2) Learning local features

Multi-layer perceptron

: 기존의 MLP에서는 hidden node들이 모든 input node들과 fully-connected하게 연결되어 있어서 global feature들에 의해 학습되게 된다.

 

Learning local feature

: 그러나 CNN에서는 filter가 이동하면서 local feature들과만 연산하여 activation map을 생성하므로, 각 activation map의 pixel들은 global이 아닌 local feature들에 의해서만 학습된다. 

 

따라서 위 특징 두 가지를 요약해보자면, CNN은 동일 weight의 filter를 이동하면서 local feature들에 의해 node를 학습시킨다. 이 과정에서 많은 중복 feature(=input pixel)들이 동일 weight과 연산하기 때문에 output으로 나온 activation map의 pixel들은 근처 pixel끼리의 상관관계가 높아진다. 따라서 Parallel Transition에 강해질 수 있다. (ex. Image를 1, 2칸 shift해도 성능이 우수)

 

이 특성으로 인해 CNN은 근처 data끼리 상관 관계가 높은 input data에 대해 학습이 더 잘 이루어진다. 

 

GCN에 CNN의 특징 적용

: input data인 node의 feature들을 학습할 때, edge로 연결된 local feature(neighbor node)만 적용하여 동일 weight로 연산하면서 node feature들을 update하는 방식을 사용한다. 

 

1) Graph 표현을 위해 Adjacency matrix A, Feature matrix H 생성

Adjacnecy matrix A, Feature matrix H

a) matrix A는 graph의 node가 5개이므로 5*5 shape를 갖는다. 

b) matrix H는 node 개수만큼의 row와 선택한 feature 개수만큼의 column인 5*10 shape를 갖는다. 

 

2) Hidden state는 matrix W와 bias b에 의해 update

Hidden state function(l: l'th layer)

Learn local feature

: node1이 node2, 3, 4와 인접하고 있으므로, H1 state는 H1, H2, H3, H4에서만 영향을 받아야 한다. 

 

Weight sharing

: H1 state는 동일 weight matrix를 사용하여 H1, H2, H3, H4와 연산되어야 한다. 

즉, 각각의 H state는 자신과 인접한 state들과 matrix W를 곱한 후 모두 더한 값으로 update된다. 

 

위의 식은 단순히 matrix A를 곱함으로써 일반화가 가능하다. 

matrix A를 HW에 곱하는 이유는 다음과 같다. 

a. 각각의 H state는 자신과 연결된 state에 의해서만 영향을 받는다. 

b. 이때 matrix H와 W를 곱해서 나온 HW에서의 (i, j) value는 H_i*W_j를 의미한다. 

 

matrix example

matrix W의 shape는 matrix H가 5*n이라면 n*K shape를 만족해야 한다. 여기서 K는 CNN filter의 개수이다. 

ex. filter의 개수를 64개로 하고자 한다면, matrix W의 shape는 10*64가 된다. 

 

Weight sharing

: 이때, matrix HW에서 column N은 모든 H state들에 N'th weight filter를 곱했을 경우 나온 값들이다. 

 

그러나 새롭게 update 되는 H state는 자신과 relationship이 있는 state와 동일 weight filter를 곱하여 나온 값들을 모두 더한 값이어야 한다. 즉, relationship에 대한 정보는 matrix A가 담고 있으므로 matrix A와 matrix HW를 곱하게 되면 최종 output matrix에서 (i, j)가 나타내는 value는 matrix A에서 row i와 matrix HW에서 column j를 곱한 값이다. 

 

Learning local feature

: matrix A의 row i는 node i의 relationship 정보이고, matrix HW에서 column j는 모든 H state에 j'th weight filter를 곱한 값이다. 따라서 이 둘을 행렬곱한 것은 기존이 모든 H state에 j'th weight filter를 곱하고 이 중에서 node i와 relationship이 있는 state만 더한 갓으로 update 한다는 뜻이다. 

 

결과적으로 최종 output matrix H'에서 row i는 node i와 relationship이 있는 node들을 각기 다른 weight filter와 연산해서 나온 value들이다. 

 

3) GCN을 거친 후 Readout-layer를 통해 최종적으로 classification 혹은 value를 regression

: CNN에서 conv layer들을 거친 후 마지막에 모든 nodes 정보를 취합하기 위해 FC-layer를 거친 후 softmax를 통해 classification 작업을 수행한다. 마찬가지로 GNN에서도 graph convolution layer들을 거친 후, MLP로 모든 node 정보를 취합하고 최종적으로 regression 혹은 classification을 위해 어떤 값을 결정 짓는 작업이 필요하다. 이를 GCN에서 readout-layer라고 한다. 

 

readout-layer가 필요한 이유

 

: 같은 network를 갖는 두 graph가 Adjacecncy matrix는 상이할 수 있다. 모든 node 간의 edge 정보가 같아도 회전, 대칭에 의해 matrix 내 값의 순서가 다를 수 있기 때문이다. 따라서 이런 Permutation에 대해 invariance하도록 MLP를 곱하는 readout-layer가 필요하다. 

 

---

Reference

https://medium.com/watcha/gnn-소개-기초부터-논문까지-96567b783479

GNN 소개 — 기초부터 논문까지

 

https://ganghee-lee.tistory.com/27

GNN, GCN 개념정리