최근 그래프 구조 데이터를 분석하는 능력으로 딥러닝에서 촉망 받고 있는 그래프 신경망,
과연 무엇을 학습시키는 것이고 어떤 방식으로 학습이 이루어질까?
그리고, 이전에 나온 합성곱 신경망(Convolutional Neural Network)과 어떤 점이 다른 것일까?
정점 표현 학습(Node Representation Learning)의 방법 중 한 가지인 그래프 신경망(Graph Neural Network, GNN)에 대해 알아보자.
선행지식 1) Graph
Graph의 정의 및 표현방법
먼저 Graph가 뭔지 알아보자.
Graph 란 vectices(꼭짓점)과 edges(간선) 2가지 구성요소로 이루어진 데이터 구조를 말한다.
일반적으로 그래프는 G=(V,E) 로 정의하며,
V는 점(=Node)들의 집합을 뜻하고 E는 Edge set으로 두 점을 잇는 선(=Edge) 들의 집합을 뜻한다.
노드에는 일반적으로 데이터의 정보가 담겨 있고, 엣지에는 데이터 간의 관계 정보가 포함되어 있다.
아래 그래프는 G=({1,2,3}, {{1,2}, {2,3}, [1,3}}) 으로 정의할 수 있다.
그래프는 주로 인접행렬 (Adjacency matrix) A로 표현된다.
그래프가 n개의 node를 가진다면 인접행렬 A의 크기는 n×n 이며, i노드와 j노드가 연결되어 있으면
Aij=1 아니면 Aij=0 의 성분을 가진다.
ML에서 그래프를 다룰땐 점들의 특징을 묘사한 feature matrix로 표현하기도 하는데, feature의 개수가 f일때 feature matrix의 차원은 n×f이다.
Graph를 분석하기 어려운 이유
1) 그래프는 Euclidean space상에 있지 않다. 이는 정형 데이터나 이미지처럼 우리에게 익숙한 좌표계로 표현할 수 없다는 것을 의미한다.
2) 그래프는 고정된 형태가 아니다. 아래 예시를 보면, 두 그래프는 다르게 생겼지만 인접행렬은 같다.
이 경우 두 그래프를 다르게 볼 것인가, 같게 볼 것인가?
3) 그래프는 사람이 해석할 수 있도록 시각화 하는 것이 어렵다. 아래 예시처럼 점의 개수가 수백, 수천개 이상인 그래프를 얘기하는 것.
기존 CNN과 RNN계열의 모델과 다르게 이런 형태의 데이터를 처리할 수 있는 새로운 모델이 필요하며, 그것이 바로 Graph Neural Network
선행지식 2) Node Representation (=Node Embedding)
많은 분류기, 알고리즘 등은 벡터로 표현된 instance를 입력으로 받는다.
따라서 그래프의 정점(Node)을 벡터로 표현해야 하며, 그 표현 방법을 Node Representation (=node embedding) 이라고 한다.
Node Embedding
- node embedding은 vector 형태의 표현 그 자체를 의미하기도 한다.
- node가 표현되는 vector space를 Embedding Space 라고 부른다.
node representation learning의 in/output
Node Embedding을 통해 그래프의 정점(Node) 를 어떻게 벡터로 표현하는지를 알아보자.
Embedding 방식
우선 Embedding 방식에는 2가지가 있다.
1) Transductive method (변환식 방법)
2) Inductive method (귀납식 방법)
각각에 대해 좀 더 자세히 알아보자.
1) Transductive method (변환식 방법)
: node 각각에 대해 임베딩 벡터를 얻는 것. 학습의 결과로 정점의 임베딩 자체를 얻는다는 특징이 있음
ex. Node2Vec, Deepwalk 등
(참고-Nede2Vec)
Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)를 사용한다.
여기서 SBRW는 현재 정점 뿐만 아니라 직전에 머문 정점까지 고려하여 다음 정점을 선택하는 방식을 말한다.
직전 정점의 거리를 기준으로 케이스를 구분하여 차등적인 확률을 부여한다.
예를 들어 직전 정점 : 𝑢, 현재 정점 : 𝑣일 때, 다음 도달할 정점의 확률은 위와 같은 원리로 차등 부여한다. 𝑥의 경우는 𝑢에서 1이고, 𝑢와 𝑣의 거리도 1이므로 거리가 유지되는 방향이다. 비슷한 원리로 𝑣에서 바라봤을 때, 𝑢는 이전 정점과 가까워지는 방향이고, 𝑦는 멀어지는 방향이다.
이 세 가지 방향을 구분하여 확률을 차등 적용하고, 이 방식은 사용자가 지정 가능하다. 이 방식에 따라 전혀 다른 임베딩이 된다.
임베딩에 따른 Node2Vec 예시
아래의 두 예시는 Node2Vec으로 임베딩 수행 후, K-means 군집 분석을 수행한 결과이다.
멀어지는 방향에 높은 확률을 부여한 경우 위와 같은 모습으로 군집이 결정된다.
정점의 역할(bridge, leaf 등)이 같은 경우에 임베딩이 유사하게 된 모습이다.
가까워지는 방향에 높은 확률을 부여한 경우
같은 군집에 속한 경우 임베딩이 유사한 모습을 보인다.
2) Inductive method (귀납식 방법)
: 각 정점을 임베딩으로 변화시키는 함수, 즉 encorder 자체를 얻음
Ex. Latent Factor Model, GNN 등
Transductive method (변환식 방법)의 한계
1. 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다.
2. 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 한다.
3. 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없다.
이런 단점을 극복한 것이 Inductive 임베딩 방식이며, 오늘 살펴볼 그래프 신경망(Graph Neural Network)는 대표적인 inductive 방식의 한 종류이다.
Node embedding에 대한 더 자세한 내용은 아래 참고
(참고) - Network Embedding과 GNN의 차이
GNN 연구에 있어서 Network embedding은 밀접한 관련이 있다. 하지만 둘 사이의 개념은 차이가 있다.
Network embedding 은 네트워크 노드를 낮은 차원의 벡터로 표현하는 것이다. Network embedding 은 노드를 표현하는 차원을 줄이면서도 노드 구조와 노드들의 내용을 보존할 수 있도록 하는데 중점을 둔다. 반면에 Graph Neural Networks 의 목적은 그래프 표현 자체가 아니고 그래프를 이용해서 어떤 업무를 수행하거나, 문제를 푸는 것에 있다.
즉, 어떤 문제를 풀기 위해서 GNN은 문제를 푸는 모델 자체가 되는 반면, Network embedding 은 이 임베딩을 통해 표현된 값들을 바탕으로 문제를 푸는 여러가지 모델을 적용하는 개념이라는 점에서 가장 큰 차이가 있다.
지금까지 GNN을 이해하기 위한 선행 지식에 대해 알아보았다.
그럼 이제부터 GNN 에 대해 알아보자.
1. General GNN(graph neural network)
1-1. GNN이란?
GNN은 이름에서도 알 수 있듯이 그래프 데이터에 사용되는 뉴럴 네트워크를 말한다.
GNN의 목적은 이웃노드들 간의 정보를 이용해서 해당 노드를 잘 표현할 수 있는 특징 벡터를 잘 찾아내는 것이다. 이렇게 찾아낸 특징 벡터를 활용해 다양한 task를 수행할 수 있으며, 대표 예시로 Node classification이 있고 이 외에도 Graph classification, Link Prediction, clusterling 등이 있다.
GNN 관련 개념 알고리즘은 크게 3개로 나눠질 수 있다.
1. Recurrent Graph Neural Network - ex. original GNN
2. Spatial Convolutional Network - ex. GCN
3. Spectral Convolutional Network
각각에 대해서는 2장에서 자세하게 알아보자.
GNN의 핵심은 점이 이웃과의 연결에 의해 정의된다는 것이다.
만약 어떤 점의 이웃과 연결을 다 끊으면 그 점은 고립되고 아무 의미를 갖지 않게 된다. 따라서 노드의 이웃과 이웃에 대한 연결이 노드의 개념을 정의한다.
이를 염두하고, 모든 점(node)이 각각의 특징을 설명하는 어떤 상태(state)로 표현되어 있다고 생각해보자.
우리는 output(o)를 만들기 위해서 node state(x)를 사용한다.
만약 점이 A, B, C 특성 중 A, B의 특성을 갖고 있으면 (1,1,0) 상태로 생각할 수 있다.
이를 학습을 통해 업데이트하고 마지막 상태가 곧 예측된 상태로, 이 상태를 node embedding 이라고 부른다.
아래 예시를 통해 이해해보자.
예를 들어, 점이 영화고 이 영화는 로맨스,범죄,공포 중에 로맨스, 범죄에 해당한다면 (1,1,0)의 상태를 가지고 있다고 생각할 수 있다. GNN은 주로 연결관계와 이웃들의 상태를 이용하여 각 점의 상태를 업데이트(학습)하고 마지막 상태를 통해 예측 업무를 수행한다. 일반적으로 마지막 상태를 ‘node embedding’이라고 부른다.
즉 노드 상태(x)를 사용하여 task를 수행하기 위한 출력(o) 을 생성하는 것이며,
모든 GNN의 task는 인접 노드에 대한 정보를 보고 각 노드의 "node embedding"을 결정하는 것이다.
1-2. Survey
GNN에 대한 survey paper 2가지를 참고했다.
각각 인용수 3000회, 1800회를 넘은 페이퍼라 참고하면 좋을 듯 하다.
1. A Comprehensive Survey on Graph Neural Networks - IEEE, 2020
Roadmap
'Comprehensive Survey on Graph Neural Networks' Survey paper에서 소개하는 논문은 학습 방법만 따지면 대략 48개의 paper를 소개한다. 물론 각 방법마다 자세하게 설명하는 것은 아니라 핵심 내용만 소개하거나 이전 방법에서 개선된 점만 소개한다. 아래 그림은 해당 survey paper에서 분류한 GNN 학습 방법을 연도별 그리고 방법별로 나타낸 그림이다.
그림 3. Survey paper에서 소개하는 방법들에 대한 연도와 분류별 Roadmap
2. Graph neural networks: A review of methods and applications - AI Open, 2020
https://arxiv.org/pdf/1812.08434.pdf
General design pipeline for GNN model
'Graph neural networks: A review of methods and applications' paper에서 제시하는
일반적인 GNN 모델 설계시 파이프라인은 다음과 같다.
computational modules
또한, 모델 개발 시 computational modules를 사용해 시작할 수 있다.
computational modules은 크게 Propagation Module, Sampling Module, Pooling Module 3가지로 나위며, 대표적인 모듈은 아래와 같다.
또한 GNN을 Graph type과 scale에 따라서도 아래와 같이 나눌 수 있다.
1-3. Motivation
CNNs, RNNs, 그리고 딥러닝의 autoencoders 에서 영감을 받아 그래프 데이터를 처리하는 방법이 급속도로 발전되고 있다.
GNN의 아이디어는 Convolutional Neural Network(CNN)에서 시작되었으며, CNN은 아래와 같은 특징을 가지고 있다.
- local connectivity
- shared weights
- use of Multi-layer
위와 같은 특징 때문에 CNN은 spatial feature를 계속해서 layer마다 계속해서 추출해 나가면서 고차원적인 특징을 표현할 수 있으며, 이런 특징은 마찬가지로 graph 영역에도 적용할 수 있다.
Local Connectivity
위 그림을 보면, CNN과 GNN의 유사한 점을 확인할 수 있다. 먼저, graph도 한 노드와 이웃노드 간의 관계를 local connectivity라 볼 수 있기 때문에, 한 노드의 특징을 뽑기 위해서 local connection에 있는 이웃노드들의 정보만 받아서 특징을 추출할 수 있다. 즉, CNN의 filter의 역할과 유사하다.
Shared Weights
또한 이렇게 graph 노드의 특징을 추출하는 weight은 다른 노드의 특징을 추출하는데도 동일한 가중치를 사용할 수 있어(shared weight), computational cost를 줄일 수 있다.
Use of Multi-layer
CNN에서 multi layer 구조로 여러 레이어를 쌓게 되면 초반에는 low-level feature위주로 뽑고, 네트워크가 깊어질수록 high level feature를 뽑는다. graph같은 경우에 multi-layer구조로 쌓게되면 초반 layer는 단순히 이웃노드 간의 관계에 대해서만 특징을 추출하지만, 네트워크가 깊어질수록 나와 간접적으로 연결된 노드의 영향력까지 고려된 특징을 추출할 수 있게 된다.
그렇다면, 위와 같은 특성을 가지려면 GNN은 어떻게 인풋 그래프에 대하여 연산을 해야하는지 알아보자.
1-4. Structure of graph neural network
그래프 신경망은 그래프와 정점의 속성 정보를 입력으로 받는다.
특히 여기서 그래프를 입력으로 받을 때 인접행렬(Adjacency Matrix)를 입력으로 받는다.
또 다른 input인 속성정보는 각 정점 𝑢의 속성(attribute) 벡터 𝑋𝑢로 받는다.
여기서 𝑋𝑢는 𝑚차원 벡터이며, 𝑚은 속성의 수를 의미한다.
정점의 속성 예시는 다음과 같다.
- 온라인 소셜 네트워크에서 사용자의 지역, 성별, 연령, 프로필 사진 등
- 논문 인용 그래프에서 논문에 사용된 키워드에 대한 원-핫 벡터
- PageRank 등의 정점 중심성, 군집 계수(Clustering Coefficient) 등
그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.
아래 그림에서 대상 정점의 임베딩을 얻기 위해 Neighborhoods 그리고 neighborhoods of neighborhoods의 정보를 집계한다.
대상 정점 A의 임베딩을 얻기 위해서 A의 이웃, 그리고 그 이웃의 이웃 노드들을 집계함으로써 A의 임베딩을 얻을 수 있다.
여기서 각 집계의 단계를 Layer로 정의하고 각 층마다 임베딩을 얻는다.
이때, 대상 정점을 얻기 위한 첫 번째 과정으로, 위 그림과 같이 0번 층에서 2번층(대상 정점) 방향으로 임베딩을 진행(집계)한다. 또한, 0번 층, 즉 입력 층의 임베딩으로는 정점의 속성 벡터를 사용한다.
그런데, 여기서 대상 정점이 무엇이냐에 따라서 대상 정점 별 집계되는 정보가 상이하다.
주어진 graph에 대한 모든 정점들에 대하여 대상 정점 별 집계되는 구조를 계산 그래프(Computation graph)라고 부른다.
이러한 계산 그래프에서의 서로 다른 대상 정점간에도 Layer에 따른 집계 함수는 공유한다.
서로 다른 층에서는 서로 다른 집계함수를 사용하는 것이 일반적이다.
하지만, 위 그림과 같이 같은 집계함수(예를들어 layer1 에서 layer2로 가는 집계함수)을 살펴보면, 집계함수는 같지만 input node가 각각 3개, 2개임을 볼 수 있다. 즉 가변적으로 입력의 크기를 처리해야한다.
이처럼 서로 다른 구조의 Computation graph를 처리하기 위해서 어떤 형태의 집계함수가 필요할까?
가변적으로 변하는 입력 데이터로부터 동일한 input 사이즈를 가지는 집계함수를 구성하기 이를 위해서는 크게 2가지 과정을 거친다.
- Neighbor node의 평균을 계산
- 신경망에 적용
집계함수가 구성되는 위의 두 과정을 수식으로 나타내면 다음과 같다.
이 과정을 진행 후 0번째 층에서의 임베딩(입력 속성 정보)부터 마지막 층까지를 진행한 뒤 출력 임베딩으로 해당 정점 별 임베딩을 계산한다.
이때, 그래프 신경망의 학습 변수(Trainable Parameter)는 층 별 신경망의 가중치인 𝐖𝑘와 𝐁𝑘가 된다. 나머지 hidden state들도 학습 과정에서 바뀌긴 하지만, 직접적으로 학습이 되는 파라미터는 위와 같다고 할 수 있다.
1-5. Training of GNN
학습을 정의하기 위해서는 Loss function을 결정해야하며, node embedding에서의 loss function의 목표는 정점간의 거리를 "보존"하는 것이다.
만약 인접성을 기반으로 유사도를 정의한다면 손실함수는 다음과 같이 정의할 수 있다.
또한, 후속 과제(Downstream Task)의 손실함수를 이용한 end-to-end 학습도 가능하다.
예를들어 node classification이 최종 목표인 경우를 생각해보자.
1. 그래프 신경망을 이용하여 정점의 임베딩을 얻고
2. 이를 분류기의 입력으로 사용한 뒤
3. 각 정점의 유형을 분류한다.
위와 같은 과정으로 node classification을 진행하려 한다.
여기서의 목표는 각 정점의 임베딩 공간에서의 유사도를 그래프에서의 유사도로 근사시키는 것이 목적이 아니라 해당 임베딩 벡터를 사용하고, 분류기를 통과한 뒤 분류 정확도를 높이는 것이다. 좋은 그래프 임베딩 공간을 찾는 것도 중요하지만, 이 경우 분류의 정확성을 높이는 것이 더 중요하기 때문이다.
이 경우 분류기의 성능을 더 좋게하는 loss function을 사용해야만 하고, 위의 경우에(분류 task)는 아래 식과 같이 Cross Entropy를 사용한다. node embedding을 진행하는 식과는 상이하지만, 궁극적으로는 정점의 실제 class와 해당 정점의 임베딩 벡터, 그리고 분류기의 학습 변수를 사용하여 loss를 정의하는 것을 확인할 수 있다.
node classification에서의 loss function
node classification에서의 학습 과정
단순히 Classifier에서만 역전파를 계산하는 것이 아니라 node embedding 가장 첫 layer까지 진행하며 학습하게 된다.
transductive node 임베딩을 학습한 이후에, 분류기를 별도로 학습하는 방식과 그래프 신경망 end-to-end 학습을 통한 분류를 비교하였을 때에는 일반적으로 end-to-end 분류가 훨씬 높은 정확도를 보여주었다.
아래 GCN은 graph convolutional network로써 대표적인 그래프 신경망을 이용한 end-to-end 학습 방식 중 하나이다.
손실함수를 정의한 이후에는 학습에 사용할 대상 정점을 결정하여 학습 데이터를 구성한다.
모든 정점을 사용할 필요가 없는 이유는 Computation graph에서 Layer가 동일할 때 집계함수가 같고, 이를 모두 공유하기 때문에 일부 대상 정점을 선택하여 계산 그래프를 구성한다.
마지막으로 역전파를 통해 Loss function을 최소화한다. 구체적으로, 역전파를 통해 신경망의 학습 변수들을 학습하게 된다.
1-6. Usage of graph neural network
이렇게 학습된 신경망을 적용하여, 학습 이후에 추가된 정점의 임베딩도 얻을 수 있다. 온라인 소셜 네트워크 등 많은 실제 그래프는 시간에 따라서 변화한다.
새로운 정점이 추가되었을 때, 그래프 신경망을 적용하여 새 정점에 대한 임베딩을 계산할 수 있다.
심지어 학습된 그래프 신경망을, 새로운 그래프에도 적용할 수 있다. 예를 들어, A종 단백질 상호 작용 그래프에서 학습한 그래프 신경망을 B종 단백질 상호작용 그래프에 적용할 수도 있다.
지금까지 GNN에 대한 전반적인 내용을 알아보았다.
다음으로 앞서 소개했던 GNN 알고리즘 3가지에 대해 각각 어떤 특성이 있는지 조금 더 자세하게 알아보자.
다음 글 : GNN 알고리즘 - (1) Recurrent GNN
GNN 알고리즘-(1)Recurrent GNN
Recurrent Graph Neural Network Original Graph Neural Network GNN(graph neural network)은 Scarselli et al.의 The Graph Neural Network Model에서 처음 등장했다. https://ieeexplore.ieee.org/document/4700287 이 논문은 GNN을 이용
didi-universe.tistory.com
GNN 알고리즘 - (2) Spatial Convolutional Network
이전 글에서는 GNN 알고리즘 중 하나인 Recurrent GNN에 대해 알아보았다. 이전 글 : GNN 알고리즘 - (1) Recurrent GNN GNN 알고리즘-(1)Recurrent GNN Recurrent Graph Neural Network Original Graph Neural Network GNN(graph n
didi-universe.tistory.com
GNN 알고리즘-(3)Spectral Convolutional Network (Spectral methods)
그래프 신호 전처리 이론에 기반을 둔 Convolution 접근법으로, 위에 설명한 것들보다 더 수학적 기반을 갖고 있다. embedding vector 들의 분포를 주파수 대역으로 변환시켜 해석하는게 Spectral 방식
didi-universe.tistory.com
참고자료
GNN / Basic Graph neural network
GNN 키워드 줍줍하기
ydy8989.github.io
https://dbstndi6316.tistory.com/250
[머신러닝 공부] 딥러닝/GNN (Graph Neural Network)
인턴에서 GNN을 이용한 Situation Recognition을 수행하며 Graph Neural Network 야 말로 진정한 AI가 아닐까? 라는 생각이 들어 관심이 생겼다. 아래는 GNN을 이용한 상황인식을 하는데 참고한 논문 링크이다.
dbstndi6316.tistory.com
https://thejb.ai/comprehensive-gnns-1/
Graph Neural Networks 개념정리 1 - 개요
기존에 Graph 개념을 충분히 알고 있고, 알고리즘을 통해 많이 활용해봤지만 Graph Neural Networks 에 대한 개념을 잡기가 쉽지 않았다. 처음 접근할 때 가장 어려웠던 점은
thejb.ai
'AI > GNN' 카테고리의 다른 글
| GNN 알고리즘-(3)Spectral Convolutional Network (Spectral methods) (0) | 2022.04.14 |
|---|---|
| GNN 알고리즘 - (2) Spatial Convolutional Network (2) | 2022.04.13 |
| GNN 알고리즘-(1)Recurrent GNN (0) | 2022.04.13 |
댓글