GNN - 2탄 GNN 기본 개념 알아보기

2021.03.13 - [관심있는 주제] - GNN- 1탄 Graph 기본 개념 알아보기

2021.03.13 - [관심있는 주제] - GNN - 2탄 GNN 기본 개념 알아보기

 

앞 글에서는 GNN을 하는데 있어 Graph가 먼지 어디에 적용하고, 현재 왜 적용하고 싶어 하는지에 대해서 알아봤다.

이번 글에서는 GNN에 대한 기본적인 설명을 적어보려고 한다

 

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

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

여기서 나온 글에서는 3개의 큰 개념 알고리즘이 있다. 

1. Recurrent Graph Neural Network
2. Spatial Convolutional Network
3. Spectral Convolutional Network

다른 적용 관련 페이퍼들은 아래 링크를 참고하시면 된다.

github.com/thunlp/GNNPapers 

thunlp/GNNPapers

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

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

따라서 노드의 이웃과 이웃에 대한 연결이 노드의 개념을 정의합니다.

 

 

이를 염두하고, 모든 점(node)이 각각의 특징을 설명하는 어떤 상태(state)로 표현되어 있다고 생각해보자.

우리는 output(o)를 만들기 위해서 node state(x)를 사용한다.

다른 글에서 좋은 예시가 있어서 그대로 차용했다.

예를 들어, 점이 영화고 이 영화는 로맨스,범죄,공포 중에 로맨스, 범죄에 해당한다면 (1,1,0)의 상태를 가지고 있다고 생각할 수 있다. GNN은 주로 연결관계와 이웃들의 상태를 이용하여 각 점의 상태를 업데이트(학습)하고 마지막 상태를 통해 예측 업무를 수행한다. 일반적으로 마지막 상태를 ‘node embedding’이라고 부른다.

즉 노드 상태 (x)를 사용하여 출력 (o), 즉 개념에 대한 결정을 생성 할 수 있습니다. 

노드의 최종 상태 ($x_n$)는 일반적으로 "node embedding"이라고합니다.

모든 GNN의 task는 인접 노드에 대한 정보를 보고 각 노드의 "node embedding"을 결정하는 것입니다.

---

Recurrent Graph Neural Network

 

original GNN Paper에서 도입된 것 처럼, RecGNN은 Banach Fixed-Point Theorem의 가정을 기반으로 한다.

BanachFixed-Point Theorem은 다음과 같다.

 

이 글을 읽어야 도움이 될 것 같다...

simcho999.blogspot.com/2020/11/numerical-analysis-banach-fixed-point.html

[Numerical Analysis] - The Banach Fixed Point Theorem(바나흐 고정점 정리)

k가 크면, x에 매핑 T를 k번 적용한 값과 k+1번 적용한 값이 거의 같다는 의미로 이해하면 된다.

RecGNN defines a parameterized function $f_w$:

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

$f_w$ 와 $g_w$ 에 대한 설명은 다음과 같음.

---

Spatial Convolutional Network

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

간단히 말하면, 이미지에서 convolution의 아이디어는 학습 가능한 필터를 통해 중심 픽셀의 주변 픽셀을 합치는 것이다. Spatial Convolution Network의 핵심 아이디어는 이 아이디어에서 주변 픽셀 대신 연결된 점의 특징을 적용한 것이다.

 

http://dmqm.korea.ac.kr/activity/seminar/267

자세한 GCN 내부 작동은 아래 설명을 참고하면 될 듯 합니다.

ganghee-lee.tistory.com/27

GNN, GCN 개념정리

---

Spectral Convolutional Network

Spectral Convolutional Network는 그래프 신호 처리 이론을 기반으로 고안됐으며 위에 설명한 것들보다 더 수학적 기반을 가지고 있다. 이 글에서는 최대한 쉽고 간략하게 느낌적인 느낌을 설명하도록 하겠다.

‘Semi-Supervised Classification with Graph Convolutional Networks’(논문 링크, 블로그 링크)에서 두 층으로 된 신경망을 제안하는데 아래 식으로 정리할 수 있다.

By Chebyshev polynomial approximation (Hammond et al. 2011), graph convolution can be simplified to below form:

여기에서 Â 는 인접 행렬 A를 약간 변형한 것이라고 생각하면 된다. (물론, Â의 정의는 중요하고 ‘spectral’을 붙인 이유이긴 한데 논문에서 각자 읽도록 하자.)

위 식의 형태는 머신러닝에 익숙하다면 본 적이 있을 것이다. fully-connected layer 두 개를 연결한 식에선 학습 가능한 행렬 W만 있는데 위 식엔 Â 이 붙어있다. 자세한 내용은 논문을 보면 알 수 있고, 여기에선 인접 행렬의 변형과 feature matrix를 곱하는 것인지 확인해보자.

노드가 4개인 간단한 그래프를 생각해보자. 

위의 그림처럼 연결되어있고 점 옆에 있는 수들은 그래프의 feature를 나타낸다.

아래처럼 대각선을 1로 채운 인접 행렬과 feature matrix를 쉽게 얻을 수 있다.

adjacency matrix의 대각선은 일부러 1을 넣는다. 왜냐하면 각각의 노드에 self loop를 추가해야 하기 때문이다. 

이것은 feature aggregation 수행할 때, 각 노드들의 각정의 피처를 포함시키려고 하는 것입니다.

AxX를 수행하다. 

 

 

가장 오른쪽에 있는 행렬이 곱한 결과이다. 

곱한 후 [점 1]의 feature를 보자. [점 1] 자신과 이웃인 [점 2], [점 3]의 feature를 합한 값임을 알 수 있다. [점 4]는 [점 1]의 이웃이 아니므로 [점 4]의 feature는 더해지지 않았다. 인접 행렬의 성질에 의해 곱한 결과가 자신과 이웃의 feature 합이 되었다. (이 부분은 애매하다)

 

따라서, Spectral Convolutional Network와 Spatial Convolutional Network는 다른 내용을 기초로 하고 있지만 비슷한 연산 과정을 거친다.

 

현재 대부분의 Convolutional GNN이 이런 식이다. 점(node)의 정보를 공유하고 업데이트를 하는데 어떻게 전달할 것인지에 대한 연구가 많이 진행되고 있다.

GNN은  message-passing 함수와 함께 Message Passing Neural Network로 표현된다. 

 ‘Neural Message Passing for Quantum Chemistry’에서 아래 세 가지 함수를 정의하여 GNN을 Quantum Chemistry에 적용하는 연구를 했다. 자세한 정의는 생략하지만 첨자와 기호를 보면 대략 어떤 식인지 추측할 수 있다.

---

What Can GNN do?

GNN은 크게 3가지로 나눌 수 있다.

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

In node classification,

Node embedding을 통해 점들을 분류하는 문제다. 일반적으로 그래프의 일부만 레이블 된 상황에서 semi-supervised learning을 한다.

대표적인 응용 영역으로는 citation networks, Reddit posts, Youtube videos, and Facebook friends relationships.이다.

In link prediction,

그래프의 점들 사이의 관계를 파악하고 두 점 사이에 얼마나 연관성이 있을지 예측하는 문제다.

대표적인 응용 영역으로는 페이스북 친구 추천, 왓챠 플레이(유튜브, 넷플릭스) 영상 추천 등이 있다. 

예를 들어, 추천 시스템은 모델이 서로 다른 제품에 대한 사용자 리뷰 세트를 제공하는 링크 예측 문제로 취급될 수 있으며, 작업은 사용자의 선호도를 예측하고 사용자에 따라 더 관련성 있는 제품을 푸시하도록 추천 시스템을 조정하는 것입니다. 

In graph classification,

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

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

대표적인 응용 영역으로는 화학, 생의학, 물리학 연구자들과 활발히 협업을 하고 있다.

---

참조 : 

paperswithcode.com/area/graphs

 

towardsdatascience.com/spectral-graph-convolution-explained-and-implemented-step-by-step-2e495b57f801

 

www.groundai.com/project/graph-convolutional-networks-with-eigenpooling/1

 

dmqm.korea.ac.kr/activity/seminar/267

 

https://littlefoxdiary.tistory.com/16#:~:text=%EA%B7%B8%EB%9E%98%ED%94%84%20%EB%89%B4%EB%9F%B4%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%EB%8A%94%20%EA%B7%B8%EB%9E%98%ED%94%84, %EC%B5%9C%EA%B7%BC%20%EC%9D%B8%EA%B8%B0%EA%B0%80%20%EB%86%92%EC%95%84%EC%A7%80%EA%B3%A0%20%EC%9E%88%EB%8B%A4.

 

towardsdatascience.com/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

 

www.youtube.com/watch?v=zCEYiCxrL_0 

 

www.ee.iitb.ac.in/~eestudentrg/presentations/Deconvoluting_Graph_Convolutional_Networks.pdf

 

sailab.diism.unisi.it/gnn/auto_examples/PyTorch_Subgraph/main_subgraph.html

 

courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture21/sld014.html

 

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

 

www.slideshare.net/JungwonKim10/graph-neural-network