[CS224W] 6. Graph Neural Network

Cherish·2023년 2월 5일

CS224W

목록 보기

6/7

📁 Review

✔️ Node embedding

그래프에서 유사한 노드들이 함수 f 를 거쳐 d 차원으로 임베딩 되었을 때, 임베딩 공간 내에서 가까이 위치하도록 만드는 것
Encoder : 각 노드를 저차원 벡터로 매핑
Similarity fuction : 원래 그래프 내에서의 노드 간 유사도와 임베딩 공간에서 노드 벡터의 내적값이 유사하도록 만드는 함수
Shallow Encoding (embedding lookup)
- 임베딩 행렬에서 노드의 임베딩 벡터를 각 column에 담아 단순히 벡터를 읽어오는 방식
- 노드 간에 파라미터를 공유하지 않기 때문에 노드 개수가 증가하면 행렬의 크기도 커진다
- 훈련 과정에서 보지 못한 노드는 임베딩을 생성할 수 없다.
- 노드의 feature 정보는 포함되지 않는다.

🔨 Tasks of GNN

Node calssification
Predict a type of a given node
Link prediction
Predict whether two nodes are linked
Community detection
Identify densely linked clusters of nodes
Network similarity
How similar are two (sub)networks

🔨 Deep Graph Encoders

노드의 유사도는 랜덤워크나 딥워크와 같이 이전의 개념과 동일하지만 Encoder의 구조가 달라진다. 단순히 look-up만 하는 임베딩 방식의 한계를 극복하기 위해 다중 레이어로 구성된 encoder를 활용한다.

✔️ Differences

complex topological structure

No fixed node ordering or reference point

Often dynamic & multimodal feature

local 개념이 불분명하고 뒤집거나 회전시켜도 변하지 않는다.

멀어보이는 노드도 실제로는 짧은 경로로 연결되어있을 수 있다.

📁 DNN (Deep Neural Network)

✔️ Notation

V : 노드들의 집합

A : 인접행렬(binary)

X : node feature 행렬

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

✔️ Issues

O(|V|) parameters
Not applicable to graphs of different sizes
Sensitive to node ordering

📁 GCN ( Graph Convolutional Network)

GCN은 CNN의 아이디어를 그래프에 접목한 개념이다.
왼쪽 그래프에서 A 노드에 대해 2 hop node까지 계산그래프를 생성한 것이 오른쪽 그림이다. 오른쪽 가장 위를 보면 A와 C 노드에서 정보가 B로 흘러간다. A와 C 노드에 해당하는 임베딩 벡터를 입력으로 하여 정보가 합쳐져 레이어를 통과한다. 이렇게 B로 모아진 정보는 기존 B의 임베딩 벡터와 연산이 이루어진다. 타깃이 된 A 노드 역시 이웃노드 B,C,D로부터 정보를 받아 연산이 이루어진다.
-> 각 노드마다 이웃 노드로 부터 정의된 computation(계산) 그래프의 모습이다.
각 노드 별로 모델 구조가 다르다. E와 F 노드의 경우 동일한 계산 그래프를 가지고 있기 때문에 동일한 모델을 통해 처리될 수 있다.

Layer-k embedding : k hop 만큼의 이웃노드 정보를 가져와 임베딩 한 것

✔️ Neighborhood aggregation

이웃 노드로부터 정보를 집계하는 방식은 네트워크 마다 상이하다. 집계하는 함수는 permutation invariant (입력 데이터 순서에 영향을 받지 않는) 함수여야 하며, 기본적인 방식은 정보를 average 하는 기법을 사용한다.

0번째 layer = node feature로 초기화

(k+1)번째 layer = k번째 layer 임베딩에 weight matrix를 곱하고 이웃노드들의 hidden state의 평균을 weight matrix에 곱하여 더한다. 그 후 non-liearity를 부여.

L번 layer을 거친 임베딩 결과 = Zv

W : weight matrix for neighborhood aggregation

B : weight matrix for transforming hidden vector of self

W,B는 layer 마다 상이하며, 같은 layer에서는 모든 node들이 동일하다.

📁 How to train a GNN

✔️ Goal : Node embedding Zv
✔️ input : Graph

✔️ Unsupervised setting ( 비지도 학습 )

Node의 레이블이 없는 경우

그래프 구조를 supervision으로 사용

✔️ Supervised setting [Node classification]

실제 라벨과 node embedding 결과갑과의 loss function을 정의하여 학습시킬 수 있다.

✔️ GNN Model Design

neighborhood aggregation function 정의
임베딩 벡터에 대한 loss function 정의
노드 집합을 배치 학습 등을 통해 학습
필요한 노드에 대해 임베딩 벡터 생성

GNN이 달성한 성과

계산 그래프의 구조와 관계없이 layer에 따라 Wl, Bl이 공유된다.

학습에 사용되지 않았던 노드들도 임베딩 벡터를 효과적으로 생성할 수 있다(Inductive Capability)

기존에 존재하는 그래프를 이용해 GNN을 학습시키고 새로운 노드를 추가할 때에도 추가 학습없이 임베딩 벡터를 생성할 수 있다.

기존에 look up만 사용한 방식에서 학습에 사용되지 않은 데이터를 임베딩하지 못하거나 노드 변수를 충분히 활용하지 못하는 문제점에서 탈피.