Chapter8. Graph Neural Networks

12기 이승현

Intro

Node Embeddings

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

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

Two key components

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

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

From "Shallow" to "Deep"

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

Shallow Encoders

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

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

Deep Graph Encoders

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

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

Modern ML Toolbox

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

Why is it Hard?

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

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

Idea : Convolutional Networks

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

From Images to Graphs

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

Real-World Graphs

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

A Naive Approach

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

아이디어의 한계점
- 파라미터가 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

Idea : Aggregate Neighbors

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

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

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

Deep Model : Many Layers

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

Neighborhood Aggregation

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

The Math : Deep Encoder

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

Model Parameters

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

Unsupervised Training

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

Supervised Training

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

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

Model Design : Overview

Inductive Capability

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

Graph Convolutional Networks and GraphSAGE

GraphSAGE Idea

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

Neighborhood Aggregation

Simple neighborhood aggregation:

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

Neighbor Aggregation : Variants

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

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

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

Recap : GCN, GraphSAGE

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

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

Efficient Implementation

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

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로 가는 메시지, 정보의 중요도를 가리킵니다.

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

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