6. Graph Neural Networks 1: GNN Model

GNN Tobigs·2021년 8월 11일
5
post-thumbnail

작성자: 김상현

0. Node Embedding

Node embedding은 graph의 node를 embedding space로 사상하는 encoder(ENC(\cdot))를 찾는 과정이다. 이때, similarity(u,vu,v) \simeq zvTz_v^Tzuz_u 을 목표로 한다.

Shallow Encoders

인코딩 방법으로 위 그림 같은 간단한 embedding-lookup 방법이 있다.

이 같은 방법에는 다음과 같은 한계(limitations)이 존재한다.

  1. O(V)O(|V|) parameters are needed
    • 노드 개수에 비례하는 parameters가 필요
  2. Inherently "transductive"
    • 학습시 보지 못한 노드는 embedding 불가
  3. Do not incorporate node features
    • 노드의 특징(features)를 고려하지 못함

Deep Graph Encoders

Shallow Encoders의 한계를 극복하기 위한 Graph Neural Network(GNN) 기반의 Deep Encoders 고려

Deep Graph Encoders는 위 그림과 같이 임의의 graph를 Deep Neural Network를 통과시켜 우리가 원하는 embedding space로 사상시키는 것


1. Basics of Deep Learning

Machine Learning as Optimization

Supervised learning: 주어진 입력 xx으로 범주 yy 예측을 목표

입력 xx 예시

  • vectors of real numbers
  • Sequences (natural language)
  • Matrices (images)
  • Graphs (potentially with node and edge features)

Supervised learning을 최적화 문제(optimization problem)로 공식화하면 다음과 같다.

minΘL(y,f(x))\min_{\Theta} L(y,f(x))

Θ\Theta: a set of parameters we optimize
L(y,f(x))L(y,f(x)): Objective function (=loss function)

참고) loss function의 종류: L2 loss, L1 loss, cross entropy, huber loss, hinge loss,...


Gradient Descent

최적화 문제를 해결하기 위해 경사하강법을 사용한다.

ΘΘηΘL\Theta \leftarrow \Theta - \eta \nabla_{\Theta} L

ΘL\nabla_{\Theta}L: gradient (기울기)
η\eta: learning rate (학습률)

수렴할때(=종료조건)까지 반복적으로 gradient의 반대 방향으로 가중치를 업데이트

gradient란?
가장 크게 증가하는 방향으로의 방향 도함수
ΘL=(LΘ1,LΘ2,...)\nabla_{\Theta}L = (\frac{\partial L}{\partial \Theta_{1}},\frac{\partial L}{\partial \Theta_{2}},...)

Gradient Descent는 한번 가중치 업데이트시 모든 데이터를 사용해야 되는 단점이 존재한다. 이를 해결하기 위해 Stochastic gradient descent(SGD)를 사용한다

Stochastic gradient descent

  • 경사하강법 수행할 때, 매 업데이트 마다 입력 데이터 xx 의 부분 집합인 mini batch를 이용해 가중치 업데이트
  • SGD를 통한 gradient는 전체 gradient의 불편추정량 -> 하지만 수렴의 정도를 보장하지는 않는다.
  • SGD를 개선한 optimizer 종류: Adam, Adagrad, Adadelta, RMSprop, ...

Multi-layer Perceptron

신경망(Neural network)은 linear transformation과 non-lineariy의 결합으로 이루어진 layer들이 쌓여진 형태이고, 이를 multi-layer perceptron이라 한다.

다층 구조의 학습을 위해 back-propagation 알고리즘을 이용하고, 비선형성을 위해 비선형함수 (e.g. sigmoid, ReLU,...)를 각 층마다 활성화 함수로 사용한다.


2. Deep Learning for Graphs

Setup

  • VV: vertex set
  • AA: adjacency matrix
  • XX \in Rm×VR^{m \times |V|}: matrix of node features
  • vv: a node in VV
  • N(v)N(v): the set of neighbors of vv

Node features

  • Social networks: 사용자 정보, 사용자 사진
  • Biological networks: 세포 정보
  • 특별한 node feature가 없는 경우: node degree, one-hot vector 등등

Naive Approach

인접행렬과 특징(features)를 결합시킨 후 deep neural net의 입력으로 사용

문제점

  • O(V)O(|V|) parameters -> data 수가 많아지면 parameter 수도 많아짐
  • 다른 크기의 그래프에 적용이 불가능
  • 노드(node) 순서에 민감

Graph Convolutional Networks(GCN)

Convolution

합성곱(convolution) 연산을 sliding window 방식에 따라 수행해 입력의 특징(feature)를 포착하는 신경망 구조

합성곱 연산의 idea: 주변 정보(neighbors)를 변환(transform)하고, 이를 결합(combine)

그래프의 구조적 특성 때문에 기존의 합성곱 연산을 적용하는데 어려움 존재

  • No fixed notion of locality or sliding window on the graph
  • Graph is permutation invariant

permutation invariant

  • f(x1,x2,x3)f(x_1, x_2, x_3) = f(x1,x3,x2)f(x_1, x_3, x_2), ff: model
  • 즉, 모델 출력에 입력 벡터의 순서가 영향을 미치지 않는 데이터를 permutation invariant 하다고 한다.

Aggregate Neighbors

합성곱 연산의 idea를 다음과 같은 방식으로 그래프에 적용한다.

  • Computation graph를 정의
  • 정보 전파(propagate) 및 변환(transform)

Key idea: Generate node embeddings based on local network neighborhoods


  • 노드들은 신경망을 이용한 이웃 노드들의 정보를 합산(aggregate)한다.
  • 모든 노드들은 노드마다의 인접 노드들에 기반해서 computation graph를 정의한다.

모델은 임의의 깊이를 갖을 수 있다.

  • 노드들은 각각의 층(layer)에서 ebedding을 갖는다.
  • Layer-0의 embedding은 해당 노드의 입력 특징(feature)이다.
  • Layer-k의 embedding은 k만큼 떨어진 노드들로부터 정보를 갖고 온다.

Neighborhood Aggregation

인접 노드의 정보를 어떻게 합산(aggregate) 하는지에 따라 네트워크가 구분된다. 즉, aggregate operator에 따라 구분된다. 주의할 점은 graph의 특성인 permutation invariant를 고려해서 aggregate operator 또한 permutation invariant한 연산이어야 한다.

기본적인 방법으로 평균을 이용하는 방법이 있다.

  1. 인접 노드들의 정보를 평균으로 합산
  2. 신경망을 적용

수식으로는 다음과 같이 표현된다.

  • hvlh_v^l: ll층(layer ll)에서 node vv의 embedding(hidden representation)

  • WkW_k: 이웃 노드 합산(aggregate)을 위한 가중치 행렬 -> trainable

  • BkB_k: 자기 자신의 변환(transform)을 위한 가중치 행렬 -> trainable

최종 layer에서의 node embedding을 loss function에 넣고 SGD를 이용해 학습을 진행한다.


Matrix Formulation

이웃 노드 정보를 합산(aggregate)하는 과정을 위와 같은 행렬 형태로 나타낼 수 있다.

  • AA: 인접행렬로 연결된 이웃 노드들의 embedding을 합(summation)하는 역할
  • D1D^{-1}: degree의 역수로 이루어진 대각 행렬로 이웃 노드 수로 나누는 역할

즉, 업데이트 과정을 위와 같이 행렬 형태로 표현할 수 있다.
A~\tilde{A}가 sparse 하므로 효율적인 sparse matrix multiplication을 사용할 수 있다.

대부분의 GNN의 aggregation 연산을 위와 같은 행렬 형태로 수행할 수 있다. 하지만 aggregation function이 복잡한 경우 불가능한 경우도 존재


Train a GNN

Unsupervised Training

inner product와 같은 similarity를 이용해 인접한 노드들은 비슷한 embedding을 갖게 하는 방법

Supervised Training

GNN을 통한 node embedding에 classification weights를 곱한 후 cross entropy loss를 적용하여 분류 문제를 해결할 수 있다.


Overview



  1. 인접 노드 합산(aggregate) 함수 정의
  2. embedding에 적용할 loss function 정의
  3. 노드 집합 학습
  4. 필요한 노드의 embedding 생성

Inductive Capability

Aggregation parameters들이 모든 노드들에 대해 공유된다. 같은 층(layer)의 신경망은 학습 가중치를 공유한다.

  • 모델의 parameter들이 노드의 개수에 준선형(sublinear)이다.
  • 보지 못한 노드(unseen node)에 일반화가 가능하다.
    • 새로운 그래프에서 일반화 가능 ex) 유기체 A의 단백질 상호작용 그래프에서 학습한 모델을 통해 새롭게 취득된 데이터인 유기체 B의 embedding을 생성
    • 새로 연결된 노드 embedding 가능 ex) Reddit, YouTube, Google Scholar

References

profile
투빅스 1415기 GNN 스터디입니다.

5개의 댓글

comment-user-thumbnail
2021년 8월 14일

[15기 황보진경 - 강의 요약]

기존의 shallow encoder를 개선하기 위해 multi-layer로 graph encoder를 만든다. 가장 간단한 방법으로는 인접행렬과 특징을 결합하여 DNN의 input으로 사용하여 임베딩을 한다. 다만 노드의 순서에 따라 임베딩이 바뀐다는 단점이 있다.

  1. Aggregate Neighbors: 네트워크의 이웃 노드들을 이용하여 computational graph를 정의한다. 이 때, 레이어(그래프의 깊이)를 달리하여 임베딩을 가질 수 있다.
  2. Neighborhood Aggregation: 이웃 노드들의 feature를 평균하여 NN을 통과시킨다. 위 과정은 행렬곱을 이용하여 나타낼 수 있다. 학습은 similarity를 이용하여 인접한 노드들이 비슷한 embedding을 갖도록 하는 unsupervised training, 노드의 라벨을 이용하여 임베딩을 하는 supervised training이 존재한다.
답글 달기
comment-user-thumbnail
2021년 8월 19일

[15기 권오현 - 강의 요약]

이번 세션은 그래프에 neural network를 어떻게 적용하는지에 대한 설명이다. 기존 그래프는 shallow encoder를 통해 node embedding을 하였는데, shallow encoder의 한계를 극복하기 위해 Deep Encoder를 제시하였다. Deep Graph Encoder는 임의의 graph를 Deep Neural Network를 통과시켜 좀더 우리가 원하는 embedding space로 사상시키는 것이다.

Deep Neural Network의 관점에서 그래프를 생각해보면 그래프의 인접행렬과 노드들의 feature를 결합시킨 후 Multi-layer perceptron에 입력으로 사용하면, 쉽게 해결할 수 있다. 하지만 data수가 많이지면 parameter 수가 많아지게 되고, 다른 크기의 그래프에 적용을 할 수 없다는 한계점을 가지고 있다. 이에 Convolution 연산을 Graph에 적용한 Graph Convolutional Network가 제안 되었다. 이미지에서 생각한 합성곱 연산을 그래프에 적용하기에는 어려움이 존재하지만 Aggregate Neigbors와 Neighborhood Aggregation을 통해 합성곱 연산을 그래프에 적용할 수 있게 된다.

Aggregate Neighbors는 노드들의 이웃 노드들의 정보를 합산 하여 노드마다 인접 노드들의 computation graph를 정의한다. 이 때 Layer의 깊이에 따라 k만큼 떨어진 노드들의 정보를 이용한 임베딩을 할 수 있다는 장점을 가진다. Neighborhood Aggregation은 인접 노드의 정보를 합산하게 되는데, 이때 평균을 이용하여 인접 노드를 합산하게 되고 합산된 결과를 신경망을 통해 학습하게 된다.

전체적인 프로세스를 정리해 보자면, 각 노드들 마다 인접 노드 합산 함수를 정의하고, embedding에 적용할 loss function을 정의한 후 노드 집합을 학습하게 된다. 이러한 GCN을 통해 그래프를 학습하게 되면, Aggregation parameters가 모든 노드들에 공유하게 되어, 보지 못한 노드에 대해 일반화가 가능하다는 장점을 가지고 있다.

답글 달기
comment-user-thumbnail
2021년 8월 19일

[15기 김재희 - 강의 요약]
딥러닝 개요와 간단하게 GNN을 소개하고 있습니다.

  1. 그래디언트 디센트
    딥러닝 모델은 관측치를 상수로 간주하고 파라미터를 최적화하는 과정을 수행합니다.
    이는 순전파 -> 손실함수 계산 -> 역전파 -> 업데이트의 과정으로 이루어집니다
    이때 비선형 함수를 사용하고, 층을 더 쌓아 목적함수를 더 복잡하게 만들 수 있습니다.
    가장 간단한 optimizer는 SGD이며, 이외에도 Adam, Adagrad 등이 있습니다.

  2. GNN
    기본적인 CNN은 사용이 어렵다.

  • locality, sliding window의 개념 정의 어려움
  • 그래프는 이미지와 같이 고정된 형태가 아닙니다.

이를 개선하고자 다음과 같이 모델을 구성합니다.

  • 각 노드의 변수를 벡터로 간주
  • 이웃 노드의 변수를 평균, 현재 노드의 변수를 선형변환하여 더함
  • 비선형 함수 통과
  • 다음 노드의 이웃 노드들에도 동일한 연산 진행

이를 통해 현재 노드의 이웃 노드로부터 정보를 단계적으로 전달 받을 수 있습니다.

이때 행렬 A~=D1A\tilde{A} = D^{-1}A 연산을 통해 행렬 연산이 가능합니다.

GNN 학습은 직접 태스크를 수행하여 이루어질 수도 있고, 랜덤워크등의 방법으로도 가능합니다.

답글 달기
comment-user-thumbnail
2021년 8월 20일

[15기 이성범]

이번 장에서는 그래프를 Neural Network로 학습하는 방법에 대하여 간단하게 알아보았다.

그래프를 embedding space로 나타내는 방법은 간단하게 Shallow Encoders가 있다. 이는 단순히 Node를 embedding space에 나타내는 embedding-lookup 방법이기 때문에 한계점을 가진다. 노드 개수에 비례하는 parameters가 필요하고, 습시 보지 못한 노드는 embedding이 불가하고, 노드의 특징(features)를 고려하지 못한다는 것이다.

따라서 이러한 한계점을 해결하고자 Graph Neural Network(GNN) 기반의 Deep Encoders가 고안되었다. Deep Encoders는 임의의 graph를 Deep Neural Network를 통과시켜 우리가 원하는 embedding space로 표햔하는 것이다. Deep Encoders는 당연히 Neural Network의 일종이기 때문에 Gradient Descent를 통하여 최적화를 진행한다.

그래프를 Deep Learning을 활용해 학습하는 가장 기본적인 방법은 그래프를 인접행렬로 나타낸 것과 각 노드의 특징을 결합시킨 행렬을 입력으로 사용하여 학습하는 방식이다. 그러나 이러한 방식은 data 수가 많아지면 parameter 수도 많아지고, 다른 크기의 그래프에 적용이 불가능하고, 노드(node) 순서에 민감하다는 단점을 가진다.

이러한 문제점을 해결하기 위해서 만들어진 방법이 바로 Graph Convolutional Networks(GCN)이다.
GCN은 이미지에 많이 활용되는 CNN의 아이디어를 그래프에 적용하여 만들어진 알고리즘이다.
GCN은 노드의 임베딩을 인접 네트워크를 활용해 생성하는 것이 Key idea이고, CNN의 합성곱 연산을 Computation graph를 정의하고 정보 전파(propagate) 및 변환(transform)을 통해 그래프에 적용한다.

우선 노드들은 신경망을 이용해 이웃 노드들의 정보를 합산하고, 모든 노드들은 노드마다의 인접 노드들에 기반해서 computation graph를 정의한다. 인접 노드의 정보를 어떻게 합산하는지에 따라서 네트워크가 구분되고, 기본적인 방법은 평균을 이용하는 것이다. 인접 노드를 합산 하는 함수가 정의 되었다면, embedding에 적용할 loss function 정의하고, 노드 집합을 학습 하고, 필요한 노드의 embedding 생성하는 방식으로 모델의 학습이 진행된다.

답글 달기
comment-user-thumbnail
2021년 8월 20일

[14기 이정은 정리]

  • 기존에 Node Embedding에 사용된 Shallow Encoders의 다양한 한계점을 극복하기 위해 Graph Neural Network(GNN) 기반의 Deep Graph Encoders가 제시되었습니다. 이는 graph를 deep neural network에 통과시켜 Embedding하는 방법입니다.
  • 가장 간단한 input은 인접행렬과 노드의 특징을 결합시킨 형태입니다. 다만, 이는 노드의 수에 따라 파라미터 수가 증가하고, 다른 크기의 그래프에는 모델을 적용할 수 없으며 노드 순서에 따라 결과가 민감하여 실제로 사용하는데 어려움이 있습니다.
  • 이를 해결하기 위해 이미지를 처리하듯이 합성곱 연산을 통해 노드의 특징을 파악하고자 하는 Graph Convolutional Networks(GCN)이 등장합니다. 이때 그래프의 no fixed하면서 permutation invariant한 구조적 특성으로 합성곱 연산에 어려움이 존재하지만 Aggregate Neighbors와 Neighborhodd Aggregation으로 해결이 가능합니다.
  • Aggregate Neighbors는 노드의 이웃 노드들의 정보를 합산하여 각 노드마다 이에 기반한 computation graph를 정의합니다. 정의된 computation graph에서 노드들은 각 층마다 embedding을 갖게 되는데, k층은 해당 노드에서 k만큼 떨어진 노드들로부터 정보를 갖고 옵니다.
  • Neighborhood Aggregation 즉, 이웃 노드의 정보를 합산할 때의 방법에 따라 네트워크가 구분되는데 가장 기본적인 방법은 평균을 이용하는 방법입니다. 이를 사용하면 모델의 파라미터는 기존보다 적어지고, 학습 시에 보지 못했던 새로운 노드에 대해서도 일반화가 가능해집니다.

GNN의 기본 배경에 대해 잘 알 수 있는 강의었습니다. 좋은 강의 감사합니다 : )

답글 달기