[CS224W] 8. Graph Neural Networks

업로드가 조금 늦어졌습니다. ㅎㅎ 8강은 성실함의 대명사 이재빈님께서 리뷰하셨습니다. Graph에 Neral Network, GNN을 적용하는 강의 입니다. 크게 Graph에 Deep learning을 적용하는 개요와, Neighborhood aggregation을 배우고 NN을 이용하는 GNN, GCN, GAT 모델들을 알아봅니다.

목차

0. Intro
1. Basics of Deep Learning for Graphs
2. Graph Convolutional Network (GCN)
3. Graph Attention Network (GAT)
4. Application

 

0. Intro

Node Embedding

먼저 7강에서 node embedding에 대해서 배웠습니다. 본래의 network node u와 v 사이의 관계를 가장 잘 표현 하는 embedding 값을 찾는 것이 핵심이었습니다 이 때 그래프를 임베딩 벡터로 잘 찾아주는 encoder ENC(・)를 잘 만드는 것이 목표인데, 오늘은 이 Encoder 역할을 Neural Network 에게 시켜서 해결할 것입니다. 

 

기존 Shallow Embedding의 문제점은 (ⅰ) node 갯수만큼의 parameter 가 필요하고(node 들 끼리 파라미터 공유가 안되어서 각 node들이 unique embedding 값을 가지기 때문에) (ⅱ) transductive해서 train 과정에서 보지 않은 unseen data를 표현할 수 없으며 (ⅲ) node에 대한 정보를 담고 있는 node attribute feature를 사용하지 않는다는 점이었습니다.

 

이를 GNN은 어떻게 해결하나 알아봅시다. 

 

 

Graph Neural Network의 Challenges

대강 왼쪽과 같은 프로세스로 처리 될텐데, 이 때 네트워크가 이미지 처럼 그리드 모양으로 표현되지도 않고, Text나 음성처럼 sequence적인 데이터도 아니여서 문제가 생깁니다. 그래프는 더 복잡한 구조를 가지고 있습니다.

또한 CS22W 초반에 배웠듯이 고정된 순서나 기준이 있는 것도 아니여서 시각화할 때마다 다른 모양의 그래프가 나오기도 합니다. dynamic, multimodal features를 갖는 경우도 있다고 합니다. 

 

A Naive Approach

가장 단순한 접근은 그래프의 adjacency matrix를 feature vector와 concat 해서 Deep Neural Network에 input으로 넣는 방법입니다. 이 방법도 파라미터가 많고 다른 사이즈나 노드 순서가 달라지면 사용이 불가능해지기 때문에 문제 입니다. (사용하지 않습니다.)

 

그래서 이런 단순한 접근 보다는 앞으로 살펴볼 GNN, GCN, GAT 등의 모델이 나왔습니다. 

 

---

 

1. Basics of Deep Learning for Graphs

(모호한데) 강의에서는 그래프에 Deep Learning을 적용하는 것이 Graph Convolution Networks라고 합니다. 2. GCN에서는 GCN의 모델 중에 하나인 Graph SAGE를 중점적으로 가르칩니다. 따라서 그래프에 Deep learning을 적용하는 Graph Convolution Network에 대해 먼저 살펴보겠습니다. 

 

Setup

• graph G
• vertex(node) set V
• adjacency matrix A (assume binary)
• node feature X (indicator vectors 와 Vector of constant는 고려하지 않음)

 

Graph Convolution Networks [Kipf and Welling, ICLR 2017]

핵심 아이디어는 "node의 이웃이 계산된 그래프를 결정한다" 입니다. node feature를 계산하기 위해서 그래프 전반에 걸쳐서 정보를 전파하는 법을 배우는 것입니다. 

node i 에 대한 prediction을 하고 싶을 때 다음의 과정을 따릅니다. 

• node computation graph를 결정하고,
• neighborhood information을 propagte 하고 aggregate합니다. 

이는 구조를 캡쳐하고 이웃의 기능 정보도 바로 가져오는 것으로, 단일 노드를 분류하는 것보다 훨씬 낫다고 합니다. 

이 전반적인 과정을 자세하게 살펴보겠습니다.

크게 Aggregate Neighbors에 대한 아이디어, Deep Model, Neighborhood Aggregation, Deep Encoder, Training model, Model parameters, Unsupervised Training & Supervised Training, Inductive Capability라는 소제목으로 설명합니다. 

 

 

Idea : Aggregate Neighbors (그림과 같이 보세요)

• local network neighborhoods를 기반으로 node embedding을 생성하는 방법입니다.
• 노드 정보를 집계하는데, neural networks를 사용해서 이웃들로 부터 정보를 aggregate(집계)합니다. 
• 네트워크 이웃들이 computation graph를 정의합니다. 
  • 모든 노드들이 자기만의 Neural Network Architecture를 갖고 있으며, 각자의 neighborhood에 근거해서 computiation graph를 정의합니다. (그림)

 

 

노드 A에 대한 feature를 A의 이웃 노드 정보를 NN으로 수집해서 나타냄

네모박스가 가각의 Neural Network

 

(왼) 평균이 순서 불변의 함수이기 때문에(순서 상관없는 함수) 집계함수로 주로 사용됨 / (오) 모든 노드에 대해 각각 computation graph가 생성된 모습

 

Deep Model : Many Layers

기본적으로 모델의 depth는 자유롭게 설정할 수 있습니다. 그래프에는 hop이라는 단위가 있습니다. 일종의 거리 개념인데, 이 hop의 크기와 layer 갯수가 비례하기 때문에 Layer-K를 사용해서 embedding 했다는 것은 K-hop만큼의 노드정보를 가져왔다는 뜻이 됩니다.

 

 

Neighborhood Aggregation

이웃에서 정보를 집계하여 가져오는 단계를 말합니다. 이웃에서 집계한 정보를 average해서 NN에 적용합니다.

 

Deep Encoder : The Math

Deep Encoder를 수식적으로 나타내면 다음과 같이 정리됩니다.

• h : embedding 값
• h_v : v에 대한 embedding 값 -> [이웃에 대한 정보 집계 하는 부분] + [이전 레이어의 v에 대한 embedding 값]
• z_v : 모든 레이어를 거친 최종 embedding 값
• 그래프에서 모델이 깊어진다는 것은 직관적으로 더 큰 네트워크, 더 많은 정보를 집계하는 것을 의미함

 

수식 추가 설명

 

Training Model 

그렇다면 embedding 값을 생성하도록 모델을 학습시키는 방법은 무엇일까요? 학습시키기 위해서 embedding 하는 것에 대한 loss function 또한 정의할 필요가 있습니다.

위의 수식에서 W,B가 학습이 필요한 weight 파라미터 였습니다. W는 이웃 노드들로부터 집계한 정보에 대한 가중치, B는 지금 보고 있는 노드의 이전 레이어에서의 임베딩 정보에 대한 가중치이기 때문에 이를 조절함으로써 이웃정보에 집중할지, 자신의 own property에 주목할지가 결정됩니다. 따라서 이 가중치를 학습시키는 수식은 다음과 같습니다.

 

Loss function은 Task 에 따라 달라지며, SGD 방법을 통해 Weight를 update해서 학습시킵니다. 1강에서 배웠듯이 자기 자신의 정보를 잃지 않기 위해서 자기 자신에 대한 self-edge를 볼 수 있습니다.

 

Unsupervised Training & Supervised Training

그래프에서 Unsupervised Trainnig과 Supervised Training은 뭘까요? 다음과 같습니다.

• Unsupervised Training
  • 지금까지 배웠던 방법들이 unsupervised 방법
  • 그래프 구조 자체만을 사용
  • similar nodes have similar embeddings
  • ex) Random walks, Graph factorization, Node proximity in the graph
• Supervised Training
  • supervised task를 수행하기 위해서 모델을 직접적으로 학습시키는 방법
  • ex) node classification
  • 그림 참고

약물 네트워크에서 A 약물이 안전한지 독인지 판단하는 node classification, 이 때 이 node classification은 위와 같은 cross-entropy loss function을 사용하는 Supervised Training을 수행합니다.

 

Inductive Capability

위에서도 inductive Capability, 직역하면 귀납적 능력입니다. 본문에서는 "The same aggregation parameters are shared for all nodes" 라고 설명합니다. CNN의 특징이기도 한, 이렇게 파라미터를 공유하는 특징을 가지고 있기 때문에  unseen node 정보에 대해서도 어느정도 알 수 있다고 합니다. 

따라서 한가지 그래프에 대해서 학습을 하고, node embedding하는 법을 배워서 새로운 그래프에 대해서 일반화 시킬 수 있습니다.

->  protein interaction graph에서 유기체 A에 대해서 학습하고 embedding 값을 만들었다면, 처음보는 유기체 B에 대해서도 데이터만 있다면 embedding값을 만들어낼 수 있습니다.

-> 따라서 Reddit, Youtube, Google Scholar 모두 unseen data에 대한 적용으로 이러한 방법을 사용하고 있었다고 합니다.

 

 

Overview

정확히 짚고 넘어가기 위해서 model design에 대한 overview(process)를 한번 다시 보겠습니다.

 

Summary

Graph Neural Network는 이웃 정보를 집계해서 노드에 대한 embedding을 하는 방법입니다. 학습 진행 후에 추가 임베딩이 가능하고, 속성 정보를 저장해서 이용가능 하다는 장점이 있습니다. 

이제 GNN 모델 두 가지를 알아보겠습니다.

 

---

 

2. Graph Convolution Network (GCN)

GraphSAGE [H amilton et al., NIPS 2017]

이웃정보를 잘 집계해서 전달하는 것이 임베딩에 중요하다는 것을 알았습니다. 그럼 이제 이웃정보를 잘 집계하는 방법은 무엇이 있을까요? 이 집계함수의 사용을 좀 더 잘하기 위해서 여러가지의 집계함수(AGG)를 사용해보고, 자신에 대한 정보 또한 따로 보관한다는 것이 GraphSAGE의 핵심입니다.

앞서 살펴봤던 SImple neighborhood aggregation과 GraphSAGE를 비교하면 위와 같습니다. 단순 average가 아니라 다양한 AGG(집계함수)를 사용할 것이고, 이를 자신에 대한 정보를 단순 합산하는 것이 아니라 Concat합니다. 이는 자신에 대한 정보를 따로 보관한다는 의미입니다. 

 

사용될 수 있는 여러가지 집계함수 예시

 

GCN에 대한 추가적인 행렬계산을 원하신다면 추천드립니다. https://velog.io/@tobigs-gnn1213/8.-Graph-Neural-Networks#graph-neural-network

 

---

 

3. Graph Attention Network (GAT)

 

지금까지 simple neighborhood aggregation에서는 모든 이웃 노드를 동일한 중요도로 보고있었습니다. 각 노드마다 중요도를 다르게 해서 이웃 정보를 더 잘 집계하는 방법이 있을까요?

 

 

Attention weight를 사용해봅시다!

 

 

Attention Mechnism

노드 u와 노드 v사이의 어텐션 계수 e_vu를 계산해서 가중치 a_vu를 다르게 줍니다. 

1. 노드 A, B에 대한 어텐션 계수는 e_AB로 나타냅니다. 노드 B -> 노드 A 일 때 중요도를 나타냅니다. 

 

2. 각 노드의 임베딩 값들을 concat해서 e_AB가 계산됩니다.

 

3. softmax function을 사용해서, 어텐션 계수 e들에 대한 분포를 만들고 확률값 처럼 a_AB를 만들어줍니다. 

 

 

 

 

 

 

 

이렇게 하면 위의 h_v를 simple 방법과 비교했을때, 이웃을 집계하고 있는 것은 동일하지만 a_vu를 사용해서 weight를 다르게 주고 있다는 것을 알 수 있습니다. 

Attention Mechanism 사용시에 a를 구하는 방법은 다양한데 attention layer를 사용할 수도 있고 , 추정해서 사용할 수도 있습니다. weight matrix와 같이 훈련시킬 수도 있다고 합니다.

 

Multi-head Attention

Multi-head attention으로 확장하면 다음과 같습니다.

multi-head로 여러 값을 도출하여 다시 aggregate(보통 concat이나 add사용) 해서 최종 output을 사용합니다. 

 

 

Properties of Attention Mechanism

• 다른 이웃에는 다른 중요도를 부여할 수 있다.
• 계산적 이점
  • ttention mechanism으로 그래프의 엣지에 대해 병렬처리가 가능하고 aggregation 도 모든 노드에 대해 병렬처리가 가능하다.
• 저장효율
  • sparse matrix 계산이 O(V+E) 이상의 공간을 필요로 하지는 않는다. 여전히 linear한 복잡도를 가진다.
  • 그래프 크기에 상관없이 일정한 갯수의 파라미터만 사용한다.
• local 포착가능
  • only attends over local network neighborhoods
• Inductive capability
  • edge-wise mechanism을 공유한다.
  • 그래프 구조에 의존하지 않는다.

 

MLP 보다는 Random Walk 가,

이보다는 GCN 과 GAT 가 훨씬 성능이 좋다고 합니다.

 

 

 

---

 

4. Application : PinSAGE

잘 구분 못하는 울타리와 침대

 

적용사례로는 PinSAGE 를 보겠습니다. 앞선 강의들에서 그래프 모델의 재미있는 사용예시로 보여줬던 Pinterest의 추천시스템 입니다. 

Graph : dynamic (모델의 retrainig 없이 새로운 노드에도 대응가능해야함), rich node features (각각이 content고 이미지임)

Task : Graph를 이용한 더 나은 Recommendation 결과 도출

Goal : 핀터레스트 그래프에서 노드에 대한 임베딩 생성

Idea : 근처 노드를 보고 정보를 가져오자 (비주얼적으로만 하려니깐 울타리랑 침대를 잘 구분못한다. -> 얘네가 같이 있는 정보도 좀 봐야겠다. 그래프에서는 얘네가 떨어져있겠지...)

적용

node를 각 이미지로 하고 노드 v를 node embedding을 해서 유사한 노드 u를 찾고 노드 u의 이웃을 추천해줍니다.

 

결과

결과를 잘 살펴보면 정말 비주얼적인 부분에 의존하지 않고 핵심을 잘 파악해서 추천하는 것을 알 수 있습니다. 이 때 Pixie 모델도 그래프 베이스의 모델입니다. 

08-GNN Pixie is a purely graph-based method that uses biased random walks to generate ranking scores by simulating random walks starting at query Pin. Items with top scores are retrieved as recommendations [Eksombatchai et al., 2018]

•  

 

 

 

 

Reference

Stanford CS224W 2019
스터디 8강 리뷰 자료 velog.io/@tobigs-gnn1213/8.-Graph-Neural-Networks#3-graph-attention-network-gat

8. Graph Neural Networks

 

스터디 8강의 참고자료

Reviews

1. Tobigs Graph Study : Chapter8. Graph Neural Networks
2. 데이터 괴짜님 Review : CS224W - 08.Graph Neural Networks
3. snap-stanford Review : Graph Neural Networks

---

CS224 Winter 2021

1. Lecture 6. Graph Neural Networks - 1: GNN Model
2. Lecture 7. Graph Neural Networks - 2: Design Space

---

GCN

1. Paper : Semi-Supervised Classification with Graph Convolutional Networks
2. Review : Graph Convolutional Networks
3. PyTorch Code : tkipf/pygcn
4. reference links
5. GraphSAGE : Inductive Representation Learning on Large Graphs

---

GAT

1. Paper : Graph Attention Networks
2. PyTorch Code : Diego999/pyGAT
3. reference links

---

etc.

1. 컨볼루션(Convolution) 이해하기
2. jihoon님 Review : Graph Neural Network
3. Deep Learning on Graphs with Graph Convolutional Networks
4. Interpretation of Symmetric Normalised Graph Adjacency Matrix?
5. lee-ganghee님 Review : GNN, GCN 개념정리
6. wikidocs : 어텐션 메커니즘 (Attention Mechanism)
7. Yeongmin님 GCN Paper Review : Graph Convolutional Networks Review