[머신러닝 공부] 딥러닝/GNN (Graph Neural Network)

인턴에서 GNN을 이용한 Situation Recognition을 수행하며 Graph Neural Network 야 말로 진정한 AI가 아닐까? 라는 생각이 들어 관심이 생겼다.

아래는 GNN을 이용한 상황인식을 하는데 참고한 논문 링크이다.

openaccess.thecvf.com/content_ICCV_2017/papers/Li_Situation_Recognition_With_ICCV_2017_paper.pdf

아래는 공부하기 전 지금까지 내가 이해한 GNN의 기초 개념이다.

1. 그래프는 고정된 형태가 아니고 유클리드 좌표계에 나타내기 어려워 직관적인 해석이 어렵다는 단점을 가지고 있지만

2. 관계나 상호작용을 나타낼 수 있어 이의 특성을 이용한다면 사회 관계망을 분석하거나 바이러스의 확산 같은 추상적인 개념을 다루는데 효율적으로 사용할 수 있다.

3. 이를 이미지 분석에 사용한다면 각 이미지간의 관계들을 연관지어 신뢰도 높은 관계 데이터를 도출해 낼 수 있을 것이란 것을 알 수 있었다.

---

그래프의 표현

그래프는 G = (V,E) 로 정의한다.

V는 Vertex 으로 점 집합을 뜻하고 E는 Edge set 으로 선집합을 뜻한다.


그래프는 Adjacency Matrix (인접행렬) 로 표현한다.

따라서 점의 개수가 n 일때 행렬의 크기는 n*n 이다.

만약 점들의 특징 f를 column으로 설정하였다면 크기는 n*f 가 될 것이다.

---

GNN 이전의 그래프 분석방법

1. 탐색알고리즘 (BFS, DFS)

2. 최단경로 알고리즘 (Dijkstra, A star)

3. 신장트리 알고리즘 (Prim, Kruskal)

4. 클러스터링 방법

이들을 통해서는 입력 그래프에 대한 사전 지식이 필요하다. 따라서 그래프가 여러 개 있을 때 이들의 정보를 다루기 힘들다.

---

GNN (Graph Neural Network)

점(node)이 이웃과의 연결에 의해 정의된다.
이웃과 연결을 모두 끊게 되면 그 점은 고립되고 의미가 없게된다.

만약 점이 A, B, C 특성 중 A, B의 특성을 갖고 있으면 (1,1,0) 상태로 생각할 수 있다.

이를 학습을 통해 업데이트하고 마지막 상태가 곧 예측된 상태로, 이 상태를 node embedding 이라고 부른다.

Recurrent Graph Neural Network

Recurrent GNN은

위와 같은 함수 fw를 정의하여 점의 상태를 업데이트 한다.

ln : 점 n의 feature
lco[n] : 점 n과 연결된 선들의 feature
lne[n] : 점 n과 연결된 점들의 feature
xne[n] : 점 n과 연결된 점들의 상태

업데이트 하는 과정의 일러스트이다.

An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model”.

k 번 반복 후에 x와 l을 사용하여 결과값 o를 출력한다.

Spatial Convolution Network (Non-spectral methods)

이또한 GNN의 일종이다. 이미지 분류에 쓰이는 CNN의 아이디어와 비슷하다.

CNN은 주변 픽셀을 convolution 하지만 GNN에서는 주변 노드의 특징을 convolution 하는 것이다.

Spectral Convolutional Network (Spectral methods)

이는 신호 전처리 이론에 기반을 둔 Convolution 접근법이다.
embedding vector 들의 분포를 주파수 대역으로 변환시켜 해석하는게 Spectral 방식
(=> 위에서 알아본 Spatial Convolution Network는 기존 convolution 방식과 거의 동일하고 graph convolution으로 표기하기도 한다.)

이와 같이 나타내진다.

아래와 같은 그래프가 있을 때 feature matrix와 Adjacency matrix를 생성해보자.

Example of a graph with a feature assigned to each node. Figured by the original author.

Example of the adjacency matrix and feature matrix. Figured by the original author.

이와 같은 Adjacency Matrix 와 Feature Matrix가 생성될 것이다.

이 둘을 곱한다면

1	1	1
1	1	1
1	2	2
0	1	2

이와 같은 결과 H가 도출될 것이다.

연산과정을 들여다보면 점1의 Feature는 점1과 그 이웃인 점2, 점3의 Feature를 합한 값이다. 자신의 이웃만 영향을 미칠 수 있다.

---

위에서 말한 GNN의 네트워크 중 Convolution이 들어간 두 네트워크는 사실 GCN(Graph Convolution Network)이라고 말할 수 있다.

그렇다면

GNN과 GCN의 차이는?

GCN은 Graph Network 에 CNN의 Convolution 개념을 적용한 것으로 CNN을 사용했기 때문에 보다 이미지 분류에 유용하다.

CNN의 특징은   1) Weight Sharing : 동일한 weight를 갖는 동일 filter를 이동하면서 연산, 중복 pixel이 다수 존재   2) Learn local features : 일반적인 MLP에서는 hidden node들이 모든 input node와 연결되어 있어 global feature들에 의해 학습된다.  하지만 CNN 에선 filter가 이동하면서 local feature 들과만 연산하고 activation map을 생성한다. => 중복 feature 들이 동일 weight와 연산산하기 때문에 output으로 나온 activation map의 pixel들은 근처 pixel 들과의 상관관계가 높아진다. == Parallel Translation에 강하다

이러한 CNN의 특징을 Graph Network에 적용한 것이 GCN이다.

---

GNN으로 해결할 수 있는 문제들

1. Node Classification

Node embedding 을 통해 점들을 분류하는 문제이다.

그래프의 일부만 레이블링 된 상태에서 semi-supervised learning을 한다.

Youtube 동영상 , 게시물 분류 등에 사용할 수 있다.

2. Link Prediction

그래프 점들 사이의 관계를 파악하고 그 연관성을 예측하는 문제이다.

페이스북 친구추천 등의 추천알고리즘에 사용될 수 있다.

3. Graph Classification

그래프 전체를 여러 카테고리로 분류하는 문제이다.

그래프의 노드들을 분류하는 문제로 주로 그래프는 분자구조 그래프 형태로 제공되며

주로 화학 생의학 등에서 연구한다.