Boostcamp Day 25. 2021-02-26.

Graph in AI - GNN_Basic

Contents

  • 정점 표현 학습 복습
  • 그래프 신경망 기본
  • 그래프 신경망 변형
  • 합성곱 신경망과의 비교

Intro

이번 강의에서는 정점 표현 학습(Node Representation Learning)의 방법 중 한 가지인 그래프 신경망(Graph Neural Network, GNN)에 대해서 배웁니다.

최근 딥러닝에서 촉망 받고 있는 그래프 신경망, 과연 무엇을 학습시키는 것이고 어떤 방식으로 학습이 이루어질까요? 그리고, 이전에 나온 합성곱 신경망(Convolutional Neural Network)과 어떤 점이 다른 것일까요? 그냥 합성곱 신경망을 사용하면 안될까요?

위와 같은 질문들에 대한 답변을 할 수 있다면, 누군가가 그래프 신경망에 대해 질문하여도 멋지게 대답할 수 있지않을까요? :)

이에 더하여, 라이브러리에서 그래프 신경망 모델을 가져와 학습까지 시켜보겠습니다!


정점 표현 학습 복습

그래프의 정점들을 벡터의 형태로 표현하는 것. Node Embedding(정점 임베딩)이라고도 불림. 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존하는 것을 목표로함.

  • 지금까지 소개한 정점 임베딩 방법들은 변환식(Trasductive) 방법이다.
    • Trasductive 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있다.
    • 정점을 임베딩으로 변환시키는 함수, 즉 인코더를 얻는 귀납식(Indective) 방법과 대조된다.
    • $ENV(v) = Z_v$
  • 출력으로 임베딩 자체를 얻는 변환식 임베딩 방법은 여러 한계를 갖는다.
    • 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다.
    • 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 한다.
    • 정점이 속성(Attrubute) 정보를 가진 경우에 이를 활용할 수 없다.

반면에,

  • 출력으로 인코더를 얻는 귀납식 임베딩 방법은 여러 장점을 갖는다.
    • 학습이 진행된 이후에 추가된 정점에 대해서도 임베딩을 얻을 수 있다.
    • 모든 정점에 대한 임베딩을 미리 계산하여 저장해둘 필요가 없다
    • 정점이 속성(Attrubute)정보를 가진 경우에 이를 활용할 수 있다.
      • $ENC(v)$ = 그래프 구조와 정점의 부가 정보를 활용하는 복잡한 함수
    • 오늘 학습할 Graph Neural Network는 대표적인 귀납식 임베딩 방법이다.


그래프 신경망 기본

GNN 구조

  • GNN은 Graph와 정점의 속성 정보를 Input으로 받는다.
  • GNN은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.
    • 대상 정점의 임베딩을 얻기위해 이웃들 그리고 이웃의 이웃들의 정보를 집계.
  • 각 집계 단계를 층(Layer)라고 부르고, 각 층마다 임베딩을 얻는다.
    • 각 Layer에서는 이전 층의 임베딩을 집계하여 새롭게 얻고,
    • 그럼 가장 밑에 층(0번층)은 뭘로? ` 정점의 속성 벡터`를 사용함.
  • 대상 정점 마다 집계되는 정보가 상이하다.
    • 대상 정점 별 집계되는 구조를 ` 계산 그래프(Computation Graph)`라고 부름
  • 집계함수
    • 집계 함수는 (1) 이웃들 정보의 평균을 계산하고 (2) 신경망에 적용하는 단계를 거친다.

이런식으로 $k=0$ (0번째 층)부터 마지막 층까지 임베딩을 거친다.

  • 마지막 층에서의 정점 별 임베딩이 해당 정점의 출력 임베딩이 된다.


GNN 학습

  • 여기서 $W_k$와 $B_k$가 의미하는 것은 학습 변수(Trainable Parameter)이다. 이것은 층 별 신경망의 가중치다.
    • 물론 층별 임베딩의 값들도 바뀌지만 그건 부수적인 부분이고 우리가 직접 바꾸고 집중하는 부분은 학습변수이다. 저걸 층별로 바꾸면서 학습을 진행하고 그러인해 층별 임베딩이 바뀌기는 한다.
  • 먼저 손실 함수를 결정한다. 정점간 거리를 "보존"하는 것을 목표로 할 수 있다.
    • 변환식 정점 임베딩에서처럼 그래프에서의 정점간 거리를 “보존” 하는 것을 목표로 할 수 있다.
    • 만약, 인접성을 기반으로 유사도를 정의한다면, 손실 함수는 다음과 같다.

자 이렇게 각 층별로 임베딩방법과 정점간의 거리를 보존하는 방법을 배웠는데 이것은 전부 다 분류를 하기위한 전단계이다. 정점 표현 학습은 이렇게 진행되고 그다음 우리는 분류(Classfier)를 잘 해야하는데 그것에 대한 손실함수는 따로 있다.

  • 그래서 후속 과제(Downstream Task)의 손실함수를 이용한 종단종(End-to-End)학습도 가능.
    • 분류기의 손실함수, 예를 들어 교차 엔트로피(Cross-Entropy)를, 전체 프로세스의 손실함수로 사용하여 종단종 학습을 할 수 있다.

  • Graph 신경망의 종단종 학습을 통한 분류는, 변환적 정점 임베딩 이후에 별도의 분류기를 학습하는 것보다 정확도가 대체로 높다.

  • 손실함수를 정의하고 난 뒤에는 학습에 사용할 대상 정점을 결정하여 학습 데이터를 구성한다.

  • 마지막으로 오차역전파(Backpropagation)을 통해 손실함수를 최소화 합니다.

    • 신경망의 학습 변수들을 학습하는데, 위에서 말한 Trainable Parameter($W_k, B_k$)를 조절한다.

GNN 활용

  • 학습에 사용된 정점들이 있을 것이고, 학습에 사용되지 않은 정점이 있을 것인데 학습에 사용된 정점들의 임베딩을 얻어서 똑같이 비학습정점들에게 사용한다.
  • 마찬가지로, 학습 이후에 추가된 정점의 임베딩도 얻을 수 잇다.
  • 학습된 그래프 신경망을, 새로운 그래프에 적용할 수도 있다.


그래프 신경망 변형

Graph 합성곱 신경망

  • Graph Convolutional Network, GCN
  • 이것의 집계 함수는 다음과 같다.

GraphSAGE

  • 이웃들의 임베딩을 AGG함수를 이용해 합친 후,
  • 자신의 임베딩과 연결(Concatenation) 하는 점이 독특.

  • AGG 합수로는 평균, 풀링, LSTM등이 사용될 수 있다.

lstm안에 $\pi$는 이웃들의 임베딩을 가져와서 shuffle해서 lstm에 넣어준다고 생각하면 됨.


합성곱 신경망과의 비교

CNN과 GNN의 유사성

  • 모두 이웃의 정보를 집계하는 과정을 반복한다는 점에서 유사함.
    • cnn은 이웃의 pixel을 집계하기 때문


CNN과 GNN의 차이

  • CNN에서는 이웃의 수가 균일하지만, GNN은 아님.
    • 정점 별로 집계하는 이웃의 수가 다르다.
  • Q. Graph의 인접 행렬에 CNN을 적용하면 효과적일까?
    • A. No

    • 그래프에는 합성곱 신경망이 아닌 그래프 신경망을 적용해야 한다.

    • CNN이 주로 쓰이는 이미지에서는 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높다.
    • 하지만, 그래프의 인접 행렬에서의 인접 원소는 제한된 정보를 가짐. 특히나, 인접 행렬의 행과 열의 순서는 임의로 결정되는 경우가 많음.

9강 정리

  1. 정점 표현 학습
    • 그래프의 정점들을 벡터로 표현하는것.
    • 그래프에서 정점 사이의 유사성을 계산하는 방법에 따라 여러 접근법이 구분됨
    • 그래프 신경망 등의 귀납식 정점 표현 학습은 임베딩 함수를 출력으로 얻음
  2. 그래프 신경망 기본
    • 그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻음
    • 후속 과제의 손실함수를 사용해 종단종 학습이 가능함
    • 학습된 그래프 신경망을 학습에서 제외된 정점, 새롭게 추가된 정점, 새로운 그래프에 적용 가능
  3. 합성곱 신경망과의 비교
    • 그래프 형태의 데이터에는 합성곱 신경망이 아닌 그래프 신경망을 사용해야 효과적



Further Reading

Semi-Supervised Classification with Graph Convolutional Networks

Reference

  • bootcamp AI Tech pdf .
  • NAVER Connect Foundation.