8. Graph Neural Networks

tobigs-gnn1213·2021년 3월 5일
4

CS224W Review

목록 보기
8/18
post-thumbnail

작성자 : 이재빈

Contents

  1. Intro
  2. Deep Learning for Graphs
  3. Graph Convolutional Network
  4. Graph Attention Network
  5. Application

Keyword : Deep Learning on Graph , Neighborhood Aggregation , GNN , GCN , GAT

0. Intro

Node Embedding

7강에서는 Node Embedding 에 대해 공부했습니다.
embedding node ($z_u$, $z_v$) 사이의 관계가 original network node ($u$, $v$) 사이의 관계 (Similarity) 를 가장 잘 표현해 주는 encoder ($ENC(⋅)$) 를 찾는 방법을 배웠습니다.

From "Shallow" to "Deep"

이 때 Shallow Encoder (Lookup table) 를 공부했습니다.
Shallow Encoder는 single layer ($f$) 로 구성되어 있으며, 이를 통해 node embedding 을 진행하고 ($u$ → $z_u$), similarity (${z_v}^T z_u$) 를 계산합니다.

Limitations of Shallow Embedding

  1. $O(|V|)$ parameters are needed
    • parameter 개수 = # of nodes
      node 끼리 parameter 를 공유하지 않습니다.
    • 각 node 들은 unique embedding 값을 가지게 됩니다.
  2. Inherently "transductive"
    • I have to re-embed everything
    • train 과정에서 보지 않은 node/embedding 을 generalize 할 수 없습니다.
  3. Do not incorporate node features
    • node attribute feature 를 사용하지 않습니다.

Deep Graph Encoders

따라서 위의 한계를 극복하고자, multiple layer 로 구성된 Deep Encoder 를 고려하게 됩니다.

Challenges

Graph NetworkDeep Neural Network 구조에 통과시켜서, node embedding (good prediction) 을 만들어 내고 싶지만, 이는 쉽지 않습니다.

단순하게 Deep Learning을 적용하기에는, 실제 Network가 매우 복잡하기 때문입니다.

  • 현존하는 ML/DL ToolBoxImage (Grids = Fixed Size Graph) & Text (Sequences = Line Graph) 에 특화되어 있습니다.
  • Network는 위상학적으로 매우 복잡한 구조를 가지고 있습니다.
  • node들은 고정된 순서 & 기준점이 없습니다.
  • dynamic 하며, Multimodal features를 갖는 경우도 있습니다.

A Naive Approach

Adjacency matrixFeature vector 를 concat 해서 Deep Neural Network 의 input 으로 넣는 방법 또한 적용이 어렵습니다.

Issues

  1. $O(N)$ : parameter 개수 (node + feature) 가 많아집니다.
  2. different size 의 graph 에 적용할 수 없습니다.
  3. node 의 순서가 바뀌면, 의미가 달라질 수 있습니다.
    • Adj node 의 ordering 이 shuffle 될 수도 있습니다.
    • 2 additional feature node 를 어디에 넣어야 할지 모호해집니다.

idea : Convolutional Networks

Convolutional 연산의 원리는 위와 같습니다.
sliding window 통해 얻은 정보를 다 더하여, output 을 도출합니다.

$(f \ast g)(t) = \int_{a}^{b} f(\tau) g(t-\tau) , d\tau$

neighborhood 의 message 를 collect 하여, node 의 message 와 combine 하고, 이를 통해 new valueproduce 하고자 합니다.

이러한 과정을 가장 잘 수행할 수 있는 연산 방법이 ConV 이기 때문에,
Convolutional 을 graph 에 적용해서, informationaggregate 하고자 합니다.


1. Deep Learning for Graphs

Setup

graph $G$ 에 대하여,

  • $V$ : vertex set = node 집합
  • $A$ : Adjacency matrix = 인접행렬
  • $X$ : Node Feature matrix

Graph Convolutional Networks

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

node i 에 대한 prediction 을 하고 싶을 때,

  1. node computation graph 를 결정하고,
  2. neighborhood information 을 propagate 하고 aggregate 합니다.

Aggregate Neighbors

Key idea

Local Network Neighborhoods 정보를 기반으로 node embedding 을 진행합니다.

  • node B 는 A, C 로 부터, node A 는 B, C, D 로 부터 정보를 얻습니다.
  • Graph 에서는 4~5 level 이상의 Layer를 쌓지 않는데, (Ch2 MSN 예시에서도 path length = 6.6 이었듯이) Depth 6 정도면 graph 내의 모든 node 를 방문할 수 있기 때문입니다.

Intuition 1

Neural Network 를 통해 neighborhood informationaggregate 합니다.

Intuition 2

neighborhood 가 computation graph 를 결정합니다.
모든 node들은 자기 자신만의 Neural Network Architecture 를 갖고 있으며, 각자의 neighborhood에 근거하여 computation graph를 정의합니다.

Neighborhood Aggregation

Neighbors 로 부터 정보를 모아 Average 한 뒤, Neural Network 를 적용합니다.

Models

Deep Layer Model

Model의 depth는 자유롭게 설정할 수 있습니다.

  • Node는 각 layer에서 embedding 값을 가지게 됩니다.
  • Layer-0에서의 node A의 embedding 은 $X_A$ 가 됩니다.
  • Layer-K에서의 embedding 은, Layer-0 에서 시작하여 Hidden Layer를 거쳐 K번 전달된 정보에 대한 값을 가지게 됩니다.

Deep Encoder


정보가 전달되어 embedding 값을 가지게 되는 과정을 수식적으로 표현하면 위와 같습니다.

  • W : Average of neighbor's previous layer embeddings
  • B : Message myself from the previous layer

Training the Model

위의 식에서, Train의 대상은 Weight Matrix 인 WB 입니다.
WB 비율을 통해, friend / own property 중 어디에 더욱 주목할 지 결정합니다.

  • W ↑ , B ↓ : Neighbor 정보 더욱 많이 고려
  • W ↓ , B ↑ : 이전 레이어의 자신의 정보를 더욱 많이 고려

embedding 값은 어떠한 loss function에도 적용 가능하며,
Stochastic Gradient Descent 를 통해 Weight를 update 합니다.


Loss Function은 Task에 따라 달라집니다.

1. Unsupervised Training

Task : graph structure 를 고려한 node embedding

  • node u 와 node v 가 similar 할 때, $y_{u,v} = 1$ 이 됩니다.
  • CE : Cross Entropy
  • DEC : Decoder (ex. inner product)
  • Loss Function : Random Walks, Graph Factorization, Node Proximity in the Graph

2. Supervised Training

Task : node classification

  • Cross Entropy Loss
  • $y_v$ : ground-truth label
  • Positive node 라면 $\sigma({z_v}^T\theta)$ 값이 커지고, Negative node 라면 $1 - \sigma({z_v}^T\theta)$ 값이 커지게 됩니다.

Overview

Parameter Sharing

The same aggregation parameters are shared for all nodes
new nodes & new graphs 에 대해서도, generalize 가능합니다.

Summary

Generate node embeddings by aggregating neighborhood information

Graph Neural Network

Layer에서 Neighborhood 와 자기 자신의 messageAggregate 하여 embedding 을 만들고, 이를 전달하여 최종 target node의 embedding 을 만드는 것입니다.


2. Graph Convolutional Network (GCN)

Matrix Formulation

k-1 hidden layer에서 information aggregation을 통해 k hidden layer 로 전달하는 Neighborhood Aggregation 식은 위와 같습니다.

$A$ (인접행렬)은 node 연결 여부에 대한 정보(0/1)를 담고 있는 행렬입니다.
따라서 $AH^{(l)}$ 는 node i 와 relationship이 있는 state 값만 더한 값으로 update 한다는 의미입니다.
여기에 $D^{-1}$을 곱해 row normalized matrix 를 만들어 냅니다.

Neighborhood Aggregation 식을 vector form 으로 표현하면 위와 같습니다.


Graph Convolutional Networks

idea

  1. neighborhood aggregate 에는 $W_k$ 를 사용하였고, previous self embedding 에는 $B_k$ 를 곱했는데 → GCN 에서는 neighbor 와 self 모두에 대해 동일한 parameter 인 $W_k$ 를 사용합니다.

  2. 인접행렬($A$)을 사용하게 되면 자기 자신으로의 연결을 고려하지 않게 되므로 → self-connection을 추가한 $\hat{A} = A + I_N$ 행렬을 사용합니다.

  3. 단순히 neighborhood 정보의 평균 ($D^{-1} A$)을 구하지 않고 → neighborhood aggregation 에 symmetric normalization ($D^{-1/2} A D^{1/2}$)을 적용하여 계산합니다.

$f(H^{(l)}, A) = \sigma ({\hat{D}}^{-\frac{1}{2}}\hat{A}{\hat{D}}^{\frac{1}{2}}H^{(l)}W^{(l)})$

  1. graph 에서 $\hat{A}$, $\hat{D}$ 를 얻습니다.
  2. 각 node에 연결된 edge 개수에 대해 normalization 을 진행합니다.
  3. l번째 hidden state 인 $H^{(l)}$ 을 곱합니다.
  4. 학습 가능한 parameter $W^{(l)}$ 을 곱합니다.
  5. activation function $\sigma$ 를 거쳐 비선형성을 학습합니다.

Output : 인접 노드들의 가중치 $\ast$ feature vector $\ast$ W의 합
즉, GCN은 특정 node의 representation으로, 해당 node에 연결되어 있는 node들을 가중합하는 방법입니다.


GraphSAGE

idea

  1. Concatenate neighbor embedding & self embedding
  2. 다양한 Aggregation 방법론을 적용합니다.

  • GCN : neighbor 과 self 의 message 를 더합니다.

    GraphSAGE : neighbor 과 self 의 message 를 concat 합니다.

  • Aggregation 방법은 여러 가지가 있습니다.


3. Graph Attention Network (GAT)

각 neighborhood node들의 중요도를 같다고 보지 않고 ($\neq \frac{1}{|N(v)|}$), attention coefficients $e_{vu}$ 를 적용해 neighborhood node 마다 가중치를 다르게 적용합니다.

Attention Mechanism in NLP

출력 값을 예측할 때, encoder의 모든 입력 단어들의 정보(확률값)를 다시 한번 참고하여 손실했던 정보를 반영합니다.

  1. $e^t = [{s_t}^T h_1, {s_t}^T h_2, ... , {s_t}^T h_N]$
    encoder 에서 나온 hidden state 에, 현재 시점 t에서의 decoder hidden state 값을 dot product 연산을 통해 구합니다.
  2. $a^t = softmax(e^t)$
    attention distribution 을 구합니다.
  3. $a_t = \sum\limits_{i=1}^N a_i^t h_i$
    encoder의 hidden state와 Attention Weights를 곱하고, Weighted Sum 합니다.
  4. $v_t$ = concat($a_t$, $s_t$)
    attention value 와 decoder hidden state 값을 concat 한 후, 최종 layer 를 통과하여 output 을 계산합니다.

Attention Mechanism in Graph

PROCESS

$e_{vu}$ 를 통해서 노드 $u$에서 노드 $v$로 가는 message importance 를 계산합니다.

각 node 의 hidden state 값이 concat 되고, linear 를 거쳐 attention coefficient $e_{vu}$ 가 계산됩니다.

softmax 함수 를 거치고, 이를 통해 나온 값 $\alpha_{vu}$ 을 곱해 가중합 하여 $h_v^{(l)}$ 을 계산합니다.

Multi-head attention 을 통해 값을 여러 개 도출하여, 이를 aggregate 해서 최종 output을 계산합니다.
✔︎ Multi-head attention : 서로 다른 attention mechanism을 여러 번 계산하여, input을 여러 관점(head)에서 해석


Allows for (implicitly) specifying different importance values to different neighbors

Experiments

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


4. Application

Pinterest

Graph 를 이용해서 더 나은 Recommendation 결과를 도출합니다.

PinSAGE

visual 로만 구분하면, fence 와 bed 를 제대로 구분할 수 없게 됩니다.
따라서 Image 와 이를 한 곳에 모아 놓은 Pinsnode 로 하여, bipartite graph 를 구축해 좀 더 나은 추천 결과를 도출합니다.

node v image 를 embedding 하여, similar 한 node u 를 찾고, node u의 neighbor 를 추천해 줍니다.

Graph 적용 시 훨씬 좋은 추천 결과를 보인다고 합니다.


Reference

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
profile
2021 투빅스 GNN 스터디

7개의 댓글

comment-user-thumbnail
2021년 3월 14일

Lecture 8 Graph Neural Networks에서는 Graph의 Node Embedding을 위한 방법으로 Neural Network를 적용한 방법의 구조와 특징에 대해 다룹니다.

GNN 기본 구조

GNN은 그래프와 정점의 속성 정보를 입력으로 받습니다. 그래프는 인접 행렬 $V * V$의 A이며, 각 정점 𝑢의 속성(Attribute) 벡터는 $m$ 차원 벡터 $X_u$ 입니다. 이 때, 정점의 속성의 예시로는 온라인 소셜 네트워크에서 사용자의 지역, 성별, 연령, 프로필 사진 등과 논문 인용 그래프에서 사용된 키워드에 대한 one-hot 벡터 등이 있습니다.

GNN은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻습니다. 대상 정점의 임베딩을 얻기 위해 이웃 정점과 이웃의 이웃 정점의 정보를 우측과 같이 도식화할 수 있습니다. 여기서 주의할 점은 2단계 이웃 정점의 정보를 집계하는 과정에서 단계를 무시하고 독립적으로 이웃의 정보를 중복으로 집계했음을 알 수 있습니다.

각 이웃의 정보를 집계하는 단계를 층, Layer 라고 하며, 각 층마다 임베딩을 얻습니다. 즉, 이전 층의 이웃 정보를 집계하여 임베딩을 얻게 되는데, 0th-layer인 입력층의 임베딩으로는 정점의 속성 벡터를 사용합니다.

결론적으로 임베딩 벡터를 얻고자 하는 대상 정점 마다 이웃의 상태가 다르기 때문에 집계되는 정보가 상이합니다. 이렇게 대상 정점 별 집계되는 구조를 계산 그래프, Compuation Graph라고 합니다.

집계 함수

하지만 서로 다른 대상 정점 간에도 층 별 집계 함수는 동일합니다. 여기서 주의해야할 점은 해당 정점이 가지고 있는 이웃의 크기가 다르기 때문에 각 층별로 공유하는 함수는 가변적인 입력에 대한 처리가 필요합니다.

그렇기 때문에 각 층별로 적용되는 집계 함수는 이웃 정점의 정보의 평균을 계산하고 신경망에 적용하는 단계를 거치게 됩니다. 이 때, 정보의 평균을 계산하는 단계는 가변적인 입력의 크기를 동일하게 만들어주기 위한 과정입니다.

손실 함수

GNN의 손실함수의 목표는 정점 간 거리를 보존하는 것 입니다. 그래프에서 정점 간 유사도를 계산하는 방법을 정의함에 따라 손실함수 또한 다양한 접근법으로 정의될 수 있습니다.

다시 정리하자면, GNN은 손실함수를 기준으로 loss를 줄여나감으로써 집계가 발생하는 각 layer의 weight를 업데이트함으로써 단순 정점 임베딩 벡터가 아닌 주어진 그래프를 통해 generalization된 임베딩 모델?을 얻을 수 있게 됩니다.

이 때, 학습에 사용할 대상 정점은 모든 정점이 아닌 일부 정점만을 사용할 수 있으며, 선택된 정점들의 계산 그래프를 통해 weight를 업데이트할 수 있습니다.

  • 학습을 통해 만들어진 weight와 설계된 구조로 학습에 사용되지 않은 정점의 임베딩 계산이 가능함
  • 학습 이후에 추가된 정점의 임베딩 계산이 가능함
  • 학습된 GNN을 새로운 그래프에 적용 가능하기도함

그래프 합성곱 신경망, Graph Convolutional Network, GCN

GCN의 집계 함수를 GNN의 집계 함수와 비교하게 되면 크게 2부분에서 차이가 발생합니다. 수식적으로 형태 자체가 크게 변하지는 않았지만 정보를 집계하는 작은 차이가 큰 성능의 향상으로 이뤄지기도 했습니다.

  • 학습 파라미터인 weight 부분입니다. GNN에서는 집계가 이뤄지는 부분과 이전 층의 임베딩에서 각각 parameter가 존재했지만 GCN에서는 하나의 paramter로만 학습이 진행됩니다.

  • 정규화 방법의 변화입니다. GNN에서는 정점 𝑣의 연결성만 고려했다면 GCN에서는 정점 𝑢, 𝑣 연결성의 기하평균을 사용했습니다.

GraphSAGE

GraphSAGE의 집계 함수는 AGG 함수와 concat에서 차이가 발생합니다.

  • 집계 함수로 통과한 벡터와 이전 층의 벡터와 concat하게 된 후에 activation function을 통과하게 됩니다.

  • AGG라는 새로운 기능이 추가되었는데 이전 층의 이웃 벡터를 입력함으로써 집계가 이뤄지는 부분입니다. 이 때 다양한 집계 함수가 사용될 수 있습니다.

답글 달기
comment-user-thumbnail
2021년 3월 15일

이번 강의는 Node Representation의 방법으로, Deep Nerual Network를 사용하는 방법에 대해서 배웠습니다. 앞선 7강에서는 Graph의 구조를 활용하여, Node Representation을 하는 방법을 배웠습니다. 이 과정에서 Node의 특징 (Feature X)를 제외하고, 오직 Graph의 구조를 통해서만 학습하였습니다. 해당 8강에서는 Node의 특징 (Feature X)를 활용하여 Node Representation하는 방법에 대해서 배웠습니다.

INTRO

Deep Learning을 사용하여 Graph를 학습하는 방법은 정말 Basic하게 각 노드의 인접행렬과 Node의 특징 Vector들을 concat하여 Feature로 활용하는 것입니다. 하지만, 방법에는 단순하게도, 차원이 매우 커진다는 점과 Graph 특성상 차원이 달라질 수 있다는 점이 한계로 존재합니다.

이러한 문제점들 해결하기 위해서 Convolution의 연산원리 도입하여 정보들을 합치는 작업을 수행합니다.

Deep Learning for Graphs & Graph Convolutional Network (GCN)

node i 에 대한 prediction 을 하고 싶을 때,

  1. node computation graph 를 결정하고,
  2. neighborhood information 을 propagate 하고 aggregate 합니다.

앞선 강의자료에서 나와있듯이, 해당 과정이 전부입니다. node computation graph를 설정하고, computation graph에서 나타나는 인접노드들의 해당 정보들을 종합하여 Node에 대해서 정의하게 됩니다. 해당 정보들을 종합하는 과정에서 Nerual Network를 사용하여 학습하게 되며, 여기서 중요한 점은 인접노드들의 정보 반영비율과 이전 시점에서의 자신의 정보 반영비율을 모두 학습시킬 수 있다는 것입니다. 이는 위의 강의자료의 Deep Encoder 부분을 통해서 파악해볼 수 있습니다.

해당 학습 또한, 여타 Deep Learning과 같이 Matrix Formula로 나타낼 수 있으며, 다음과 같이 표기할 수 있습니다.

앞에서 언급하였듯이, 인접노드들의 정보와 자기 자신에 대한 정보를 학습하게 되는 형식입니다.

앞선 정보들을 취합하는 과정에서 단순히 평균을 사용하여 취합할 수도 있지만, Pool, LSTM과 같은 Nerul Network를 사용하여 여러가지 방법들을 통해 이웃노드들의 정보를 취합할 수 있습니다.

Graph Attention Network (GAT)

Attention Mechiansm을 활용하여 역시 정보들을 취합할 수 있으며, NLP에서의 Attention과 동일한 원리라고 생각하시면 됩니다. 이웃노드들이 있을 때, 어떠한 노드들에 더 집중을 할 것인지를 학습하게 되며, Attention Weight를 구할 때, 단순히 Concat하여 해당 연산과정을 거칩니다.

좋은 강의 잘들었습니다. 감사합니다.

답글 달기
comment-user-thumbnail
2021년 3월 16일

이번 강의는 갓재빈님께서 Graph Neural Network라는 주제로 GCN,GAT등 graph 도메인에서의 deep neural network에 대해 강의를 진행해 주셨습니다.

Node embedding은 original graph의 node사이의 유사도와 embedding space로 embedding된 node사이의 유사도가 최대한 같도록 학습합니다. 지난강의에서 Shallow Encoder를 배웠지만, 이는 단순히 look-up table이기 때문에 parameter수가 매우 많고 node끼리 parameter를 공유하지 않는다는 단점이 있었습니다. 또한 train 과정에서 보지 않은 node/embedding 을 generalize 할 수 없고 node feature를 사용하지 않았습니다. 이러한 문제를 해결하기 위해 Deep Graph Encoder가 제안되었습니다.

Deep Learning for Graphs

Local Network Neighborhoods 정보를 기반으로 node embedding 을 진행합니다.

오른쪽 그림이 computation graph. 네모난 상자가 각각 neural network의 hidden layer
Nerual Network를 통해 neighborhood의 정보를 aggregation합니다. 모은 정보들을 Average합니다. 이후 Deep Learning과 같이 weight를 곱하고 activation function을 지나 다음 layer로 넘겨줍니다.

단, graph 도메인에서는 layer를 4~5개 이상을 사용하지 않습니다. (MSN예시에서 보았던것과 같이 depth가 약 6이면 모든 node로 도달할 수 있기 때문입니다.)

각 node들의 feature정보들의 embedding vector가 데이터가 되어 입으로 사용됩니다($X_{n_i}$).

  • $\mathbb{h}_v^0=x_v$ : initial 0-th layer embedding은 node의 feature입니다. (데이터가 입력으로 들어갑니다.)
  • $\mathbb{h}v^k=\sigma(W_k \sum{u \in N(v)}{h_u^{k-1} \over {|N(v)|}}+B_kh_v^{k-1})$
  • $z_v=h_v^K$ : embedding after K layers of neighborhood aggregation

The same aggregation parameters are shared for all nodes

parameter
$W \rightarrow$Average of neighbor's previous layer embeddings(높을수록 neighborhood정보 많이 고려)
$B \rightarrow$ Message myself from the previous layer(높을수록 이전 레이어의 자신의 정보 많이 고려)

Loss

  • if unsupervised learning -> node embedding based graph structure
    $L = \sum_{z_u,z_v}CE(y_{u,v},DEC(z_u,z_v))$
  • if supervised learning -> node classification :
    $L = \sum_{v \in V} {y_vlog(\sigma(z_v^T \theta))+(1-y_v)log(\sigma(1-z_v^T \theta))}$

Graph Convolution Networks

Basic GNN과 다른 점

  • GNN : neighborhood aggregation과 previous self embedding에 다른 parameter 적용
    $\rightarrow$neighborhood와 self embedding 두 동일한 parameter적용
  • GNN : 인접행렬을 사용하면서 자기 자신으로의 연결을 고려하지 못함
    $\rightarrow$ f-connection을 추가한 $\hat{A} = A + I_N$ 행렬을 사용
  • GNN : 단순히 neighborhood 정보의 평균 $D^{-1} A$ 사용($\sum_{u\in N(v)}{h_u^{k-1} \over {|N(v)|}}=H^{l+1}=D^{-1}AH^{(l)}$)
    $\rightarrow$ neighborhood aggregation 에symmetric normalization ($D^{-1/2} A D^{1/2}$)을 적용

$f(H^{(l)},A) = \sigma(\hat{D}^{-1\over2}\hat{A}\hat{D}^{-1\over2}H^{(l)}W^{(l)})$
notation $\hat{D}=\tilde{D},\hat{A}=\tilde{A}$
$\hat{A},\hat{D}$에 대한 설명 :Yeongmin's Blog : Graph Convolutional Networks Review

GCN의 output은 인접 노드들의 가중치 * feature vector * W의 합입니다. GCN은 특정 node의 representation으로, 해당 node에 연결되어 있는 node들의 가중합을 하는 방법입니다.

GraphSAGE

GCN이 neighbor과 self의 message를 더했다면, GraphSAGE에서는 neighbor과 self의 message를 concate합니다.

  • GCN : $\mathbb{h}_v^k=\sigma(Sum({m^{(l)}_u,u \in N(v)}) \rightarrow \mathbb{h}v^k=\sigma(W_k \sum{u \in N(v)}{h_u^{k-1} \over {|N(v)|}}+B_kh_v^{k-1})$
  • GraphSAGE : $\mathbb{h}_v^k=\sigma(W^{(l)}CONCAT(h^{l-1},AGG{h^{(l-1)}_u,\forall u \in N(v)})$
    $AGG$ : Mean or Pool or LSTM

Graph Attention Network (GAT)

각 neighbor의 중요도를 다르게 보도록 attention을 적용합니다.

$\mathbb{h}v^k=\sigma( \sum{u \in N(v)}\alpha_{vu}W_kh_u^{l-1}$
$\alpha_{vu}$ : attention weights

GNN의 개념을 확실히 알 수 있는 좋은 강의였습니다. 감사합니다! S2갓재빈도덕책S2

1개의 답글
comment-user-thumbnail
2021년 4월 12일

이번 강의에서는 이번 스터디의 꽃 GNN 그 자체를 배웠습니다.
저번 강의에서는 graph에서 node를 임베딩하는 법을 배웠습니다. word2vec처럼 look-up table을 활용한 방법이 있는데, 이는 일반화 능력 부족과 node feature의 부재 등의 단점이 있었습니다. 그래서 전지전능하신 neural net으로 해결할 수 있습니다. naive하게 접근해본다면 인접행렬과 feature vector를 concat하여 fc를 바로 태우는 방법이 있으나 역시 일반화가 어려우며 node 순서에 영향을 받을 수 있다는 단점이 있습니다. 그래서 CNN의 convolution 연산을 차용하여 GCN이 개발되었습니다. convolution은 쉽게 말해서 주변 이웃의 feature 정보를 취합하여 학습을 진행한다는 점인데 graph에서도 edge로 연결되어있는 이웃이 있다는 점에서 비슷합니다. GCN에서의 aggregator를 보면 target 노드로부터 k-layer에 걸쳐(일반적으로 2층) aggreagtion을 진행하여 최종 임베딩을 업데이트합니다. 이 때 일반적인 CNN과 달리 매 학습마다 computation graph의 구조가 달라진다는 점이 특징입니다. aggregation은 주로 average를 사용하고 자기 자신의 feature를 잊지않기위해 k-1 step의 자신의 feature를 더하게 됩니다.
여기서 더 나아가 graphSAGE는 다양한 aggregation function을 시도하였습니다. 순전파시 neighbor info와 self message를 concat하고 aggregation에서 average, pool, lstm 등의 방법을 적용하기도 했습니다. GAT에서는 attention을 사용하였습니다. 두 노드 간의 attention score를 계산하여 학습하는 방법으로 두 방향의 score를 concat하여 normalize후 weighted sum을 하고 neural net에 태웁니다. 여기서 multi-head attention을 첨가하여 다양한 시각의 모델을 학습시킬 수도 있습니다.
띵강 감사합니다!

답글 달기