> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter8..md).

# Chapter8. Graph Neural Networks

## Intro

### Node Embeddings

* Intuition : Input으로 들어온 그래프를 d 차원으로 Mapping을 하는데 그래프 안의 비슷한 노드끼리 더 가깝게 임베딩을 하는 함수 F를 배웁니다.

![](/files/-M5CG5cPtFs3EyVUCjnT)

* 따라서 목표는 **임베딩에서의 유사도가 네트워크 내에서의 유사도가 되도록 노드를 매핑하는 것**입니다. 아래 그림에서는 코사인 유사도가 됩니다. 

![네트워크 상에서의 유사도와 인코딩은 정의되어야 합니다.](/files/-M5CGbHgdrY2dQIwV3i-)

### Two key components

* `Encoder` : 노드를 저 차원의 벡터로 매핑합니다.

![](/files/-M5CGvv7DMW6f1BwHvIx)

* `Similarity function` 은 Input 네트워크에서의 관계를 임베딩 공간에서의 관계로 매핑하는 것을 정의합니다. 즉 u, v 노드가 유사할 수록 임베딩 공간에서의 u, z의 코사인 유사도는 증가합니다.

![](/files/-M5CHGbQOwwuOXL2v4fI)

### From "Shallow" to "Deep"

* Embedding을 시각화하면 아래와 같습니다.

![](/files/-M5CHbDV9z3_H1XeW0VR)

### Shallow Encoders

* 데이터 변환의 한 Layer로 구성되어 있습니다.
* 이 Single hidden Layer 는 node u를 임베딩하여 z로 매핑합니다.

![](/files/-M5CIBHlTi0RgRsm_CIa)

![](/files/-M5CIGAnz4ZkqA6RX8Ao)

* 이 알고리즘의 한계는 다음과 같습니다.
  * 우리가 추정하려는 파라미터의 개수는 네트워크 내의 점의 개수, O(|V|)와 똑같습니다. 그리고 노드 사이의 어떤 파라미터도 공유하지 않으며 모든 노드는 자신만의 유일한 임베딩을 가집니다.
  * 학습 과정에서 보지 못한 노드의 임베딩을 만들 수 없습니다. (=transductive)
  * 노드 피처들을 통합하지 못합니다. 

### Deep Graph Encoders

* Graph Neural Network에 기반한 Deep Encoder를 배우게 됩니다.

![](/files/-M5CIoB7jgm7QDm28Ykp)

* 이러한 딥 인코더들은 전 강의의 노드 유사도 함수와 결합가능합니다!

![](/files/-M5CJ3oIYis_kZoqkLCQ)

### Modern ML Toolbox

* 간단한 형태의 데이터에 특화되어 있습니다. (=Boring Graph ? ㅜ)

![](/files/-M5CJC8EhVsRvwe1pJkA)

### Why is it Hard?

Network들은 더 복잡하기 때문입니다. 

* 그리드와는 다르게 위상학적으로 복잡한 구조를 가집니다.
* 이미지, 텍스트와는 다르게 고정된 노드, 참조할 수  있 노드가 없습니다.
* 또한 그래프를 Resize? 하긴 어렵습니다.
* 동적이고 Multimodal한 피처들을 가집니다.

### Idea : Convolutional Networks

이미지에서 CNN의 목표는 노드들의 피처나 특징들을 남겨 합성곱, 필터를 일반화하는것입니다.

![](/files/-M5CJsrQKsIXTjy7TCJa)

### From Images to Graphs

아래 Graph 그림에서 가운데 점을 i라고 하면 주위 점들로부터 정보를 모으고 합치는 과정을 거치게 됩니다. 아래 그림은 3x3 필터를 가지고 있을 때 이미지, 그래프에 적용하는 방법입니다. 이미지는 필터에 합성곱을 해서 1개의 피처에 압축하는 반면, Graph 인접한 점들로부터 정보를 모으게 됩니다. 

 

![](/files/-M5CKOb9OJNXU-Z6FGwv)

![](/files/-M5CKBguJOXsPr7cQFNs)

### Real-World Graphs

실제 세계에는 더 많은 종류의 그래프가 있습니다.

![](/files/-M5CKbIvy2JEL024yQVZ)

### A Naive Approach

* 인접행렬과 피처들을 결합, concat한뒤에 이를 뉴럴 네트워크에 넣는 방식입니다.

![](/files/-M5CTAXBDjp5vqcCI9ev)

* 아이디어의 한계점
  * 파라미터가 N개, 데이터의 개수만큼 필요합니다.
  * 그래프의 크기가 다르면 사용할 수 없습니다.
  * 노드 순서가 바뀌면 또 이상해집니다..임베딩 벡터의 의미가 바뀌게 되는 단점이 생깁니다.
  * Q. 휴리스틱하게 학습시킬 수 있지 않을까?
    * Ans : 가능은 하지만 일반적이진 않습니다. 

## Basics of Deep Learning for Graphs

### Content

* Local network neighborhoods
  * Describe aggregation strategies 
  * Define computation graphs
* Stacking multiple layers
  * Describe the model, parameters, training
  * How to fit the model?
  * Simple example for unsupervised and supervised training

### Setup

* 그래프 G가 주여졌을 때
  * V는 정점들의 집합입니.
  * A는 인접행렬이며, 0 또는 1이라고 가정합니다.
  * X는 node 피처들의 행렬입니다. R(m \* V)
  * Node features:
    * Social networks : User profile, User image
    * Biological networks: Gene expression profiles, gene functional information
    * No features

### Graph Convolutional Networks

Computation Graph를 정의해서 노드가 주어졌을 때 노드에 대한 예측을 만드는것이 목표입니다. 노드들의 이웃들을 계산 그래프로 정의합니다. 아래 그림을 예로 들면 노드 i가 주어졌을 때 주위 노드로부터 어떻게 정보를 모으는지 배웁니다.

*Learn how to propagate information across graph to compute node features*

![](/files/-M5CU_XATRd718Xm6Cof)

### Idea : Aggregate Neighbors

* Key idea : 부분 네트워크 이웃들로부터 노드 임베딩을 생성합니다. node A는 node B, C, D로부터 정보를 얻습니다. node B 는 node A, C와 연결되어 있으므로 또다시 이로부터 정보를 얻습니다. 
* Q. 언제 학습을 멈출지 알 수 있을까요?
  * Ans : Depth는 그리 크지 않습니다. 케빈 베이컨 게임을 떠올리면 그 답을 쉽게 알 수 있습니다.
* 박스는 우리가 정보를 모을 신경망의 일종입니다. 단 이때 노드의 번호순서는 고정되어야 합니다. 그 이유는 정보를 모으는 과정에서 뒤죽박죽이 될 수 있습니다. 

![](/files/-M5CUonBOKMLdkKH3VhM)

* Intuition : 뉴럴넷을 이용해서 이웃 노드들로부터 정보를 모읍니다.

![](/files/-M5CV1Z_cxE9oM63vU7m)

* 네트워크 Neighborhood가 computation graph을 정의합니다. 노드마다 다른 신경망 구조를 가지는 것이 특징입니다. 색깔별로 구조가 다릅니다. 

![](/files/-M5CVDOnN7NN4D34KNtF)

### Deep Model : Many Layers

* Model은 자유로운 깊이를 가질 수 있습니다.
  * 노드들은 각 layer에서 임베딩을 가집니다.
  * node u에서의 layer-0 임베딩은 feature Xu입니다.
  * Layer-K에서는 K만큼 떨어진 노드로부터 정보를 얻습니다.
* 예를 들면 Layer-0에서 A, C로부터 피처를 Aggregation 하여 비선형 변환 후 노드 B에 전달합니다. 

![](/files/-M5CVbyIOIqU72yDbMb-)

### Neighborhood Aggregation

* Basic approach : 이웃 노드로부터 정보들을 모아서 뉴럴넷을 적용합니다. Aggregation 할 때의 합, 평균 등은 노드의 순서가 중요하지 않는 것이 특징입니다. 

![](/files/-M5CWHSo8sQ9fMSOoa_N)

### The Math : Deep Encoder

k-1번째 iteration의 주위 노드들의 정보를 평균내고 이를 현재 자기 자신의 임베딩으로 Weight sum하는 과정을 거쳐 k번째 자기자신의 임베딩을 얻습니다.

![](/files/-M5CWTmDE9EpdHdM-H5E)

### Model Parameters

W 행렬과 B행렬을 우리가 loss function, 확률적 경사 하강법을 통해 학습을 할 수 있습니다. 이를 vector 형식으로 쓰면 다음과 같습니다.

![](/files/-M5CXCgVjijQPFAS-yRU)

### Unsupervised Training

* 비지도 학습을 할 시에는
  * 그래프 구조만을 사용하게 됩니다.
  * 비슷한 노드들이 비슷한 임베딩을 가지게 니다.
* 비지도 학습의 손실함수는 아래와 같습니다.
  * `Random walks`
  * `Graph factorization`
  * `Node proximity in the graph`

### Supervised Training

지도학습을 위해 직접적으로 학습합니다. (node classification)

![](/files/-M5CXqfvn3qS_Zdfx-wJ)

정점 v의 노드 임베딩과 v의 라벨을 통해 지도학습이 가능합니다.

![](/files/-M5CXxbeYAnrX_KOJEI8)

### Model Design : Overview

![](/files/-M5CYH__Po5KO10R5lW-)

![](/files/-M5CYKSF9P6rYBVdQGqh)

![](/files/-M5CYOtlloTlnDOOGeu8)

### Inductive Capability

* 모든 노드들에 대한 같은 Aggregation 파라미터가 적용됩니다.
  * 모델의 파라미터 수는 V보다 조금 작기 때문에 보지 않은 노드들에 대해서도 일반화가 가능합니다.(sublinear)

![](/files/-M5CZZ0yZONBWOe71YCx)

![](/files/-M5CZjckSyL2KMIPtTWs)

![](/files/-M5CZnPbsirzCWG64ONV)

## Graph Convolutional Networks and GraphSAGE

### GraphSAGE Idea

어떻게 하면 비슷한 것 끼리 더 잘 Aggregation , 모을 수 있을까요? 첫번째 방법은 L2 Normalization을 Aggregation function에 적용하는 것입니다.

![](/files/-M5C_hu1ZaBqK6m5OtPE)

### Neighborhood Aggregation

* `Simple neighborhood aggregation`:

![](/files/-M5C_r6CrZvE9Bs_t12U)

* `GraphSAGE` : Aggregation 한 것과 자기자신을 임베딩한것을 더하는게 아니라 concat 합니다.

![](/files/-M5Ca55-yrWDeE2Ee7QQ)

### Neighbor Aggregation : Variants

* `Mean` : 이웃 노드들로부터 정보를 얻은 후 평균을 냅니다.

![](/files/-M5CakPsYSYNtkiZdG9d)

* `Pool` : 이웃 노드들의 임베딩을 바꾸고 symmetric 벡터를 용합니다.

![](/files/-M5CaxJWQuI3CXiJaOib)

* `LSTM` : 이웃노드들 섞어서 LSTM을 적용합니다.

![](/files/-M5Cb4gX8HPSCdi7u6Xq)

### Recap : GCN, GraphSAGE

GCN, GraphSAGE는 모두 이웃 노드들로부터 임베딩을 새로 만드는 것입니다. 노드들은 뉴럴넷을 사용하여 그들의 이웃들로부터 정보를 모읍니다.

* `Graph convolutional networks`
  * 정보를 모으고 뉴럴넷에 쌓습니다. - Average neighborhood information
* `GraphSAGE`
  * Aggregation 함수를 일반화합니다.

![](/files/-M5CbcNSf8E5ml_OFjaK)

### Efficient Implementation

* `GCN, GraphSAGE`는 희소행렬에 대하여 효율적으로 연산이 가능합니다.

![](/files/-M5Cbrwa5x_uco9aXPPr)

### More on Graph Neural Networks

![](/files/-M5Cc18yMIAmOrPjIeJN)

## Graph Attention Networks

### Simple Neighborhood Aggregation

* Graph convolutional operator:
  * 이웃 노드들로부터 정보, 메시지를 모읍니다. N(v)
  * 1/N(v) 는 노드 u에서 v로가는 중요도, `weighting factor(importance)`를 나타냅니다.
  * 이는 그래프의 구조적인 특징을 명확히 정의합니다. 하지만 모든 노드가 이 중요도가 같다고 볼수는 없습니다. 

### Graph Attention Networks

* 그래프의 각 노드의 다른 이웃 노드들의 중요도를  다르게 표현합니다.
* 노드의 임베딩을 Attention 전략에 따라 계산합니다.

### Attention Mechanism

* `attention coefficients` e(vu) 를 통해서 노드 u, v사이의 정보 중요도를 계산합니다. e(vu)는 노드 u에서 노드 v로 가는 메시지, 정보의 중요도를 가리킵니다.

![](/files/-M5Cp6Jkk_z8bCuARn7Y)

* `Normalize coefficients` 를 이용해서 다른 이웃들간 정보량을 계산할 수 있습니다.

![](/files/-M5CpWaoZRg6R2uH3Fon)

*  `Attention mechanism` a
  * The approach is agnostic to the choice of a, 정하기 나름입니다. 
  * Parameters of a are trained jointly, 파라미터들은 서로 독립이 닙니다. 
* `Multi-head attention` : Stabilize the learning process of attention mechanism
  * Attention operations in a given layer are independently replicated R times
  * Outputs are aggregated

### Properties of Attentional Mechanism

![](/files/-M5Cq5hk8wIPHvzD7wav)

### GAT Example : Cora Citation Net

![](/files/-M5CqE0at_vrCGXtnt3_)

## Example Application

### Application : Pinterest

![](/files/-M5CqT1WE8j-5K_aeQb9)

![](/files/-M5CqY_ffMiaBqoUrLN0)

### Pinterest Graph

![](/files/-M5CqgtcXeecUxLJFfHc)

### Pinsage: Overview

![](/files/-M5CqmtPjfmtnbqeQqbz)

### Embedding Nodes

![](/files/-M5CqrclELfQKRgBLVxM)

### Task Overview

![](/files/-M5CqzAwi4P-rFqxcuGZ)

### PinSAGE Training

![](/files/-M5Cr3IkhUxVh8AsPWYg)

### PinSAGE Efficiency

![](/files/-M5CrCgclZ6SfUJiHQdD)

### PinSage : Key Innovations

![](/files/-M5CrKBZfxWx4mNHuGT1)

![](/files/-M5CrN2laOgPBUvI04to)

### PinSage : Experiments

![](/files/-M5CrTRCCo66xtqG9ejg)

### Example Pin Recommendations

![](/files/-M5Cr_od7wady9ZE1GJZ)

### PinSAGE Recommendations

![](/files/-M5CrfkXXJZ0yZtaaaDm)

![](/files/-M5CriGcUBPPpWlILmAs)

## General Tips and Practical Demos

### General Tips

![](/files/-M5CrqYIHEvcI59M8Odb)

### Debugging Deep Networks

![](/files/-M5Cryu1XqoYFglgQZ7T)

### Demo : Human Disease Network

![](/files/-M5Cs3togfgowFicGz9W)

### Demo : Protein Interation Prediction

![](/files/-M5Cs9qQ6FYVzFsnBegs)