[딥러닝]Graph Neural Network 개요

Date: 2022.12.20 Updated: 2022.12.20

카테고리: DeepLearning

1. Graph Neural Network

1) Graph란?

그래프의 개념은 아래 링크를 참조하면 된다.

간략하게 그래프의 구조는 다음과 같이 $G = (V,E)$로 정의된다.

V는 Vertex(Node)들의 집합이다.
E는 Edge들의 집합이다.

그래프는 주로 인접행렬(Adjacenct matrix)로 표현되는데, 이 크기는 노드의 개수가 n일때, $n \times n$이다. 또한, feature matrix로 표현하기도 하는대, feature의 개수가 $f$일때, feature matrix의 차원은 $n \times f$이다.

그래프를 분석하기 어려운 이유

그래프는 우리가 익숙한 유클리드 공간에 있지 않다.
그래프는 고정된 형태가 아니다.
사람이 해석할 수 있도록 시각화 하는 것이 어렵다.\

그래프를 사용하는 이유

관계, 상호작용과 같은 추상적인 개념을 다루기에 적합하다.
복잡한 문제를 더 간단한 표현으로 단순화하기도 하고 다른 관점으로 표현하여 해결할 수 있다.
Social Network, 미디어의 영향, 바이러스 확산 분석 등에 아주 유용하다.

2) Graph Neural Network란?

기존 그래프 분석 방법

검색 알고리즘(BFS, DFS)
최단 경로 알고리즘(Dijkstra, A-star 알고리즘)
신장 트리 알고리즘(Prim 알고리즘, Kruskal 알고리즘)
클러스터링 방법(연결 성분, 클러스터링 계수)

Graph Neural Network는 말 그대로 Graph + 신경망, 즉 그래프에 직접 적용할 수 있는 신경망이다.
점 레벨, 선 레벨, 그래프 레벨에서의 예측 작업에 쓰인다. 대표적인 세 개의 큰 개념 알고리즘이 있다.

Recurrent Graph Neural Network
Spatial Convolutional Network
Spectral Convultional Network

GNN의 핵심은 노드가 이웃과의 연결에 의해 정의된다는 것이다. 만약 어떤 점의 이웃과 연결을 다 끊으면 그 점은 고립되고 아무 의미를 갖지 않게 된다. 따라서 노드의 이웃과 이웃에 대한 연결이 노드의 개념을 정의한다.

이에 따라 모든 노드가 각각의 feature를 설명하는 어던 상태(state)로 표현되어 있다고 가정하면

Output(o)를 만들기 위해 node_state(x)를 사용한다.

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

즉 노드 상태(x)를 사용하여 출력(o), 즉 개념에 대한 결정을 생성 할 수 있다. 노드의 최종 상태 $x_n$을 일반적으로 Node Embedding이라고 한다. 모든 GNN task는 인접 노드에 대한 정보를 보고 각 노드의 Node Embedding을 결정하는 것이다.

GNN의 기본은 그래프에 있는 노드 사이의 관계를 모델링하고, 그에 대한 Representation을 생성하는 것이다.

Ex)

“SNS 사용자의 네트워크 관계가 그래프로 주어질 때 해당 유저의 영향력을 예측하기”

이를 수행하기 위해서는 임의의 구조의 그래프 G가 들어왔을 때 그를 하나의 Representation으로 표현해야 한다. 즉, $F(G) = embedding$ 으로 변환할 수 있는 함수 F를 찾는 것이 목표이다.

그래프를 임베딩할 수 잇는 데에 사용할 수 있는 대표적인 아키텍쳐는 RNN(Recurrent Neural Network)이다. RNN은 체인으로 연결된 구조 데이터에 사용할 수 있는 특별한 구조로, 이전 1)Time Step의 Hidden값과 2)현재 Time Step의 Input 을 결합하여 현재의 Hidden representation을 생성하는 것이 특징이다. RNN을 이용해 GNN을 구성하기 위해서는 두 가지를 먼저 생각해야 한다.

각각의 노드를 Embedding하기
- 노드 하나하나는 RNN unit으로 사용되기 때문
- 이 예시에서는 사용자의 나이, 성별, 활동 기간 등의 설명 변수를 벡터로 만들어 임테딩할 수 있다.
엣지(Edge) 타입에 따를 Neural Network 정의하기
- 그래프에는 다양한 엣지 타입이 있을 수 있는데, 종류에 따라 네트워크를 다르게 구성한다.
- 예를 들어 SNS에서 ‘친구(friends)’관계와 ‘팔로우(follow)’ 관계가 있다면, 이 둘은 다른 weight를 사용하여 네트워크로 표현하는 것이다.

이제 각 노드를 Recurrent unit으로 생각하고 각각의 노드는 가장 인접한 노드를 (t-1) 시점으로 보아 recurrent unit을 사용해 새로운 히든을 생성할 수 있다.

위의 가장 왼쪽의 그림을 보면, 가운데에 있는 노드에 대해 가장 인접한 노드 ①에 대한 $NN_1$을 사용해 정보를 결합, 새로운 representation(파란색 블럭)을 생성해낼 수 있다.

다음으로 가운데 그림에서 같은 방식으로 가장 인접한 네 개의 노드에 대해 RNN을 적용하면 네 개의 히든을 얻게 된다. 노드 사이의 순서를 무시한다면, 이 네 히든을 더하여 더하여 가 운데 노드에 대한 새로운 representation을 생성할 수 있다. 이렇게 생성된 representation은 이제 한단계 인접해 있는 노드의 정보를 포함한 representation이 된다. 같은 방식으로 모든 노드에 대해 한 단계 인접해 있는 노드와 RNN으로 정보를 결합하게 되면, 모든 노드는 각자의 인접한 노드의 정보를 알고 있는 representation을 가지게 된다.

마지막으로, 그래프에 대한 최종 임베딩은 업데이트된 노드 representation의 합하여 생성할 수 있다. 이 경우에도 노드의 순서 정보는 무시된다. (참고로 한 단계 인접한 스텝만 고려하는 것이 아닌, 두 단계, 세 단계 인접한 노드들까지 고려하도록 설계할 수도 있다.)

3) Graph Neural Network 보충 & 정리

전통적인 머신러닝 기법들은 그래프를 각각의 태스크에 맞게 feature engineering하여 노드, 엣지, 그래프 레벨의 변수들을 생성
이러한 방식은 각 태스크마다 새롭게 feature engineering을 진행해야 하기 때문에 비효율적

태스크마다 새롭게 feature engineering 할 필요가 없는 효율적인 방법이 필요
그래프의 구조(노드, 링크, 그래프)를 벡터로 바꾸는 Feature representation(Embedding)이 그 방법
네트워크에서의 유사도가 임베딩에서의 유사도로 잘 나타낼 수 있도록 그래프의 구조를 2차원 공간에 잘 맵핑되도록 하는 작업
임베딩을 하면 많은 종류의 down stream task 수행이 가능해진다.

(1) Node Embedding

Goal : encode nodes so that similarity in the embedding space approximates similatity in graph
수식 : $similarity(u,v) \; \approx \; Z^T_vZ_u$
행렬의 내적으로 계산 유도

Framework
1. Encoder : 인코더를 통해 각 node를 low-dimensional vector로 맵핑한다. Ex) Shallow Encoding
  - Encoder is just an embedding-lookup.(룩업 테이블에서 입력으로 주어진 인덱스의 열만 출력하는 것)
  - 가장 간단한 방법으로, 각각의 노드가 개별적인 임베딩 벡터를 갖고 있게 되는 것이다. (we directly optimize the embedding of each node).
  - 그러나 이는 노드 수가 많아지게 될 경우 가지고 있어야 하는 룩업 테이블이 매우 커지게 된다는 단점이 있다.
  - 인코딩하는 다른 방법들로는 Deep walk, node2vec 등이 있다.
  - deep encoders -> GNNs
2. node similarity function을 정의한다.
  - 노드의 유사도 정의 중 하나로 random walks 가 있다. 그래프의 구조를 보존하면서 직접적으로 노드들의 좌표계를 얻는 방식이다.
  - 노드 임베딩 자체는 비지도 학습 혹은 자기지도 학습의 일종이기 때문에 노드의 레이블이나 변수들은 사용하지 않는다.
3. 디코더를 통해 임베딩을 유사도 점수로 맵핑한다. 내적(Inner Product)
4. 인코더의 파라미터를 최적화 하여 original network의 유사도가 임베딩의 유사도로 근사하도록 한다.
Shallow Encoding 함수의 문제점
1. 각 노드 별로 개별적인 인베딩 벡터를 가지다 보니 노드의 수가 매우 많아진다면 파라미터의 수가 기하급수적으로 증가
2. 학습 시 사용되지 않는 노드는 Look-up-table에 존재하기 않기 때문에 inference과정에서 사용할 수 없다.
3. 노드의 변수들이 사용되지 않는다.

정의 내려야 할 것 3가지
1. 인코더 함수: $Enc(v) = Z_v$
2. 그래프에서의 유사도 정의
3. 임베딩 공간에서의 유사도 정의
그래프에서의 유사도는 랜덤워크나 딥워크 등을 통해 정의할 수 있다. 임베딩 공간에서의 유사도는 두 벡터의 내적으로 간주했다.(이를 디코더라고 부르기도 함)

(2) Deep Graph Encoders: GNN

GNN은 그래프에 직접 적용할 수 있는 신경망이다. 점 레벨에서, 선 레벨에서, 그래프 레벨에서의 예측 작업에 쓰인다.
유사도는 랜덤워크나 딥워크와 같이 지금까지 사용한 유사도와 같지만, encodr의 구조는 달라진다.
cnn, rnn, dnn 등의 딥러닝 방법론들을 차용하여 multiple layers of non-linear transformations based on graph structre를 구성하게 된다.

GNN의 핵심은 점이 이웃과의 연결에 의해 정의된다는 것이다. 연결관계와 이웃들의 상태를 이용하여 각 점의 상태를 업데이트(학습)하고 마지막 상태를 통해 예측 업무를 수행한다. 그리고 마지막 상태가 ‘node embedding’이 된다.

GNN이 해결할 수 있는 문제

Node Classification (Node embedding을 통해 점들을 분류하는 문제)

Link Prediction (그래프의 두 점 사이에 얼마나 연관성이 있을지 예측하는 문제)

Community detection (밀집되어 연결된 노드의 클러스터들을 식별)

Network similarity (두개의 (sub)networks들이 얼마나 비슷한지)

Notation

$V$ : vertex set, 노드 집합

$A$ : adjacency matrix, 인접행렬

$v$ : V의 어떤 한 노드

$N(v)$ : 노드 v의 이웃노드 집합

$X \in R^m \times \vert V \vert$ : 노드 변수들 (노드의 변수가 없다면 indicator vectors 또는 Vector of constant 1: [1,1, … , 1] 사용)

2. Graph Convolution Networks

그래프이론과 CNN의 방법론을 접목시켜 만든 아키텍쳐, GCN이다.

1) How to propagate information across the graph to compute node features

GCN은 기존의 딥러닝 모델과 다르게 순전파의 과정이 다음의 두 과정을 거치게 된다. (손실함수 계산이나 역전파 과정은 동일하다.)

(1) 각 노드 별 계산 그래프 생성

타겟 노드 A에 대한 2 hope node 까지의 계산 그래프에 대한 그림이다. A는 이웃 노드 B , C, D 로부터 정보를 받고 각각의 이웃노드 B, C, D는 또다시 그들의 이웃 노드로부터 정보를 받는 다. 계산 그래프의 오른쪽에서 왼쪽으로 정보가 흐른다.

모든 노드에 대한 계산 그래프를 표현한 그림이다. 각 노드마다 각기 다른 형태의 계산 그래프의 형태를 갖고 있다. 넓은 형태의 계산 그래프가 존재하기도 하고 좁은 형태의 계산 그래프도 존재한다. E 와 F의 경우에는 동일한 형태의 계산 그래프를 갖고 있다. 즉 두 노드는 동일한 모델을 통해 처리될 수 있다.

(2) 순전파, Neighborhood Aggregation

각 레이어는 어떻게 이웃 노드들의 정보를 모을까? 가장 적합하면서 단순한 연산은 평균/합이다.

첫 번째 hidden layer의 입력값은 각 노드의 변수벡터 혹은 임베딩 벡터이다. 두 번째 히든 레이어부터 마지막 히든 레이어까지는 각 레이어의 이웃노드의 벡터의 평균과 이전 레이어의 해당 노드$(v)$를 선형 변환한 것을 결합하여 활성화 함수를 통과한 값이다. 파라미터는 $W_l$ 과 $B_l$ 두 행렬이 전부다. 즉 모든 계산 그래프는 동일한 가중치를 공유한다.

(3) Matrix Formulation

연산을 행렬단위로 하면 훨씬 효율적인 계산이 가능하다.

Let $H^{(l)} = [h_1^{(l)} \; \dots \; h_{\vert V \vert}^{(l)} ]^T$: $l$번째 레이어의 모든 노드들의 벡터를 concat하여 행렬로 표현할 수 있다. shape은 노드 차원
Then $\sum_{u \in N_v}h_v^l = A_v$: $H^{(l)}$: $H^{(l)}$와 인접행렬의 연산은 모든 이웃 노드 벡터들의 합이 된다.
$D_{u,v} = Deg(v) = \vert N(v) \vert, \; D_{u,v}^{-1} = \frac{1}{\vert N(v) \vert}$: $D$는 대각행렬이고 각 대각 성분은 $v$노드의 이웃노드의 수를 갖는다고 하면, 대각행렬 $D$의 역행렬은 $v$노드의 이웃노드 수의 역수가 된다.

위의 3가지를 이용하면

$$\sum_{u \in N_v} \frac{h^{(l)}}{\vert N(v) \vert} = H^{(l+1)} = D^{-1}AH^{(l)}$$

이 식을 완전히 정리하면 다음과 같다.

2) GNN의 학습 과정

(1) Unsupervised Learning(비지도 학습)

$$\mathscr{L} = \sum_{z_u, z_v}CE(y_{u,v}DEC(z_u, z_v))$$

비지도 학습에서의 손실함수는 위와 같다. 유사도는 랜덤워크 등의 방법이 사용되고, 디코더는 내적이 사용된다. $y_{u,v}$는 $u,v$노드가 유사할 경우 1, 아닐 경우는 0을 나타낸다. 디코더 또한 유사할 경우에는 1, 그렇지 않으면 0을 계산하도록 파라미터가 최적화된다.

(2) Supervised Learning(지도 학습)

지도학습에서의 손실함수는 위와 같다. 지도학습은 각 노드의 레이블을 예측하는 방식으로 손실함수를 구현한다.

3) Model Design

Define a neighborhood aggregation function Define a loss function on the embeddings Train on a set of nodes ( a batch of compute graphs) Generate embeddings for nodes as needed

GNN에서 주목할만한 점은 모든 계산그래프에서 구조에 상관 없이 파라미터가 공유된다는 점이다. 이는 학습에 사용되지 않았던 노드들도 추가학습 없이 임베딩 벡터를 효과적으로 생성할 수 있는 능력을 GNN모델은 갖추었다고 할 수 있다.

Reference

GNN : Graph Neural Network
Graph Neural Networks (GNN) / 그래프 뉴럴 네트워크 기초 개념 정리
[컨텐츠 연재] #03 Graph와 GNN 스터디, 어디까지 해봤니?

Meaningful