GNN 개념, 관련 기본 지식

Index

• What is GNN? (brief)
• What can we do with GNN
• About Graph
• About GNN (Types of GNN)

 

What is GNN? (brief)

GNN ( Graph Neural network ) 이란 ?

    - 그래프에 직접 적용할 수 있는 신경망으로 그래프 데이터를 직접 분석할 수 있다.

    - 핵심은 점이 이웃과의 연결에 의해서 정의된다는 것이다.

GNN 예시

What can we do with GNN

1. Node Classification
2. Link Prediction
3. Graph Classification

 

Node Classification

• Node embedding을 통해 점들을 분류하는 문제다.
• 일반적으로 그래프의 일부만 레이블 된 상황에서 semi-supervised learning을 한다.
• 대표적인 응용 영역으로는 인용 네트워크, Reddit 게시물, Youtube 동영상이 있다.

 

Link Prediction

• 그래프의 점들 사이의 관계를 파악하고 두 점 사이에 얼마나 연관성이 있을지 예측하는 문제다.
• 대표적인 예로 페이스북 친구 추천, 왓챠플레이(유튜브, 넷플릭스) 영상 추천 등이 있다.
• Ex) 영화와 유저가 점이고 유저가 영화를 봤으면 선으로 연결을 해준 그래프를 생각할 수 있다.
• 선으로 연결되지 않은 영화, 유저 쌍 중에 연결될 가능성이 높은 쌍을 찾아서 유저가 영화를 감상할 가능성이 높다고 예측할 수 있다.

 

Graph Classification

• 그래프 전체를 여러가지 카테고리로 분류하는 문제이다.
• 이미지 분류와 비슷하지만 대상이 그래프라고 생각하면 된다.
• 분자 구조가 그래프의 형태로 제공되어 그걸 분류하는 산업 문제에 광범위하게 적용할 수도 있다.

분자 구조를 그래프로 변환하고 GNN을 거치면 138개의 향기를 예측할 수 있다고 한다.

 

About Graph

1. Graph Definition
2. Why use graphs?
3. Limitations of Existing Graph Analysis Methods

 

Graph Definition

• 그래프란?
• 그래프는 점들과 그 점들을 잇는 선으로 이루어진 데이터 구조이다.
• 관계나 상호작용을 나타내는 데이터를 분석할 때 주로 쓰인다.
• 대표적인 예로는 페이스북 친구관계, 왓챠플레이(유튜브, 넷플릭스) 유저-영상 감상여부 등이 있다.
• 일반적으로 그래프는 G=(V,E)로 정의하며 여기서 V는 점 집합이고 E는 두 점을 잇는 선 집합이다.

 

사진과 같은 그래프는 G=({1,2,3},{{1,2},{2,3},{1,3}})으로 정의할 수 있다.

 

흔히 생각하는 그래프                                                                  그래프의 정의에 따라 이것도 그래프라고 부를 수 있다.

 

정의에 따르면 다음도 그래프라고 이야기할 수 있다.

그렇다면 딱 보기에도 너무 복잡해 보이는 데이터인 그래프를 사용하는 이유는 무엇일까?

 

Why use Graphs?

1.

• 관계, 상호작용과 같은 추상적인 개념을 다루기에 적합하다.
• 그래프를 그려보면 이런 추상적인 개념을 시각화 할 때 도움이 된다.
• 사회적 관계를 분석할 때 기초가 되기도 한다.

2.

• 복잡한 문제를 더 간단한 표현으로 단순화하기도 하고 다른 관점으로 표현하여 해결할 수도 있다.

3.

• 소셜 네트워크, 미디어의 영향, 바이러스 확산 등을 연구하고 모델링 할 때 사용할 수 있다.
• 소셜 네트워크 분석은 데이터 과학에서 그래프 이론을 사용하는 가장 잘 알려진 분야일 것이다.
• 최근 뉴스에서 코로나19 확산, 이동경로를 나타내고 분석할 때 자주 등장한다.

 

Limitations of Existing Graph Analysis Methods

전통적인 방법은 주로 알고리즘 기반 방법이다.

이런 알고리즘의 한계는 알고리즘을 적용하기 전에 입력 그래프에 대한 사전 지식이 필요하다는 점이다.

그렇기 때문에 그래프 자체를 연구하는 것이 불가능하고, 그래프 레벨에서의 예측이 불가능하다.
여기에서 말하는 ‘그래프 레벨’은 그래프에 속하는 점이나 선에 대한 정보를 다루는 것이 아니라 그래프가 여러개 있을 때 그래프의 정보를 다루는 것을 말한다.

 

따라서 우리는 이러한 한계를 극복하기 위해 그래프에 직접 적용 가능한

Graph Neural Network(GNN)을 사용한다.

 

About GNN (Types of GNN)

GNN은 이름에서도 알 수 있듯이 그래프에 직접 적용할 수 있는 신경망이다.

점 레벨에서, 선 레벨에서, 그래프 레벨에서의 예측 작업에 쓰인다.

GNN의 핵심은 점이 이웃과의 연결에 의해 정의된다는 것이다.

만약 어떤 점의 이웃과 연결을 다 끊으면 그 점은 고립되고 아무 의미를 갖지 않게 된다. 

(이름을 불러주었을 때 꽃이 된다면, 연결될 때 점이 된다.)

이를 염두하고, 모든 점이 각각의 특징을 설명하는 어떤 상태로 표현되어 있다고 생각해보자. 예를 들어 점(dot)이 영화이고 이 영화는 로맨스,범죄,공포 중에 로맨스,범죄에 해당한다면 (1,1,0)의 상태를 가지고 있다고 생각할 수 있다.

GNN은 주로 연결관계와 이웃들의 상태를 이용하여 각 점의 상태를 업데이트(학습)하고 마지막 상태를 통해 예측 업무를 수행한다.

일반적으로 마지막 상태를 ‘node embedding’이라고 부른다.

 

Types of GNN

1. Recurrent Graph Neural Network
2. Spatial Convolutional Network
3. Spectral Convolutional Network(요즘 잘 안씀)

Recurrent Graph Neural Network

 

오리지날 GNN 논문‘The Graph Neural Network Model’ 에서 소개되었듯이 Recurrent GNN은 Banach Fixed-Point Theorem을 기초로 만들어졌다.

Recurrent GNN은 입력과 출력이 아래와 같은 함수 f_w를 정의하여 점의 상태를 업데이트 한다.

l_{n}는 점 n의 feature, l_{co[n]}은 점 n과 연결된 선들의 feature, x_{ne[n]}은 점 n과 연결된 점들의 상태   l_{ne[n]} 은 점 n 과 연결된 점들의 feature 를 의미한다 .

k번 반복을 통한 업데이트 후 마지막 상태(x_n)와 특징(l_n)을 사용하여 결과값(o_n)을 출력한다.

 즉, o_n = g_w(x_n, l_n)이 된다.

 

Spatial Convolutional Network

Spatial Convolutional Network의 아이디어는 이미지 분류와 이미지 영역 구분에 많이 쓰이는 Convolutional Neural Network(CNN)의 아이디어와 비슷하다.

이미지에서 convolution의 아이디어는 학습 가능한 필터를 통해 중심 픽셀의 주변 픽셀을 합치는 것이다.

Spatial Convolution Network의 핵심 아이디어는 이 아이디어에서 주변 픽셀 대신 연결된 점의 특징을 적용한 것이다.

 

 

그래프는 주로 인접행렬로 표시된다.

- 인접행렬이란? 

 

Adjacency matrix

• 정의

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다.

인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있다.

 

adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

cf) 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수 있다.

 

• 예시

다음과 같은 그래프가 있는 경우, 이 그래프의 연결 관계를 인접 행렬로 나타낸다면 인접 행렬은 다음과 같다.

 

 

 

 

 

그렇다면, 위의 그래프처럼 간선에 방향이 있는 유향 그래프가 아닌, 간선에 방향이 없는 무향 그래프의 경우에는 어떻게 될까요?

노드 i에서 노드 j로 가는 간선이 있다는 말은 노드 j에서 노드 i로 가는 간선도 존재한다는 의미가 되겠죠? 따라서, 인접 행렬이 대각 성분(adj[i][j]에서 i와 j가 같은 원소들)을 기준으로 대칭인 성질을 갖게 됩니다. 위의 그래프의 간선들을 방향이 없는 간선으로 바꿔주면 아래와 같은 인접행렬을 갖게 됩니다.

 

 

출처: https://sarah950716.tistory.com/12 [주니어 개발자의 대나무숲:티스토리]

 

 

 

 

참고 사이트 : https://medium.com/watcha/gnn-%EC%86%8C%EA%B0%9C-%EA%B8%B0%EC%B4%88%EB%B6%80%ED%84%B0-%EB%85%BC%EB%AC%B8%EA%B9%8C%EC%A7%80-96567b783479

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

참고 사이트 : https://sarah950716.tistory.com/12

[그래프] 인접 행렬과 인접 리스트