[GNN] 4. GNN 개요

[GNN] 4. GNN 개요

 

 

 

1. Graph란?

- 왜 Graph?

- Graph의 종류

- Graph의 표현

- Graph Tasks

- Graph의 Motif 

 

 

2. Graph Representation Learning 

- Node Embedding

- Graph Embedding 

 

 

3. GNN 이전의 Graph 학습 

- Node Feature

• Eigenvector centrality
• Betweenness centrality
• Closeness centrality
• .....

- Link Feature

• Distance-based feature
• Local neighborhood overlap
• Global neighborhood overlap

- Graph Feature

• Graphlet kernel
• Weisfeiler-Lehman Kernel 

 

4. GNN

- Recurrent Graph Neural Networks (RecGNNs)

- Convolutional Graph Neural Networks (ConvGNNs)

• Spectral Model
• Spatial Model 

- Graph AutoEncoders (GAEs) 

• Network Embedding
• Graph Generation

- Spatial-Temporal Graph Neural Networks (STGNNs)

• CNN Based 
• RNN Based
• CNN & RNN based Model 
• Attention based Model 

 

5. GNN의 Benchmark Datasets

- Citation Networks

- Biochemical Graphs

- Social Networks 

- Others

 

 

6. GNN Library

- Pytorch Geometric

- DGL 

 

---

 

 

최근 딥 러닝의 발전은 이미지, 비디오, 언어 분야에서 많이 이루어졌다. 이 데이터들은 모두 유클리드 공간에서 표현되는 데이터들이다. 반면에 비유클리드 공간의 데이터들은 오브젝트 간의 복잡한 관계나 상호의존성등을 정의할 수 있는 그래프로 표현할 수 있다.

 

 

딥 러닝에서 가장 많이 활용되는 기법들로 CNN, RNN, autoencoder 등이 있다. 특히 이러한 기법들이 빠르게 발전한 이유중 하나는 GPU 등으로 많은 데이터에 대해서 빠른 계산이 가능해졌기 때문이다. 그리고 이러한 계산들은 특히 유클리드 데이터(이미지, 텍스트, 비디오)의 latent representations 를 추출하기 유리하다. 예를 들어서 이미지 데이터는 유클리드 공간의 격자(grid)로 표현이 가능하다. 이미지에 CNN을 활용하면 shift-invariance, local connectivity, compositionality 가 가능하다. 따라서 CNN이 이미지에서 부분적으로 중요한 feature들을 뽑아낼 수 있고, 이를 통해 전체적인 이미지 분석을 효과적으로 할 수 있다.

 

 

반면에 비유클리드 공간은 보통 그래프로 많이 표현된다. 여기서 non-euclidean data란 graph 또는 tree 구조를 가진 데이터를 말한다. Graph는 연결된 edge들이 방향성(directed)이 있거나 없거나(undirected) 순환(cyclic)되는 구조가 있다. 한편 tree는 방향성(directed)이 있는, 즉 유향 비순환(acyclic) 그래프의 한 종류로 생각하면 된다. 단, tree는 root node가 하나로 고정되어 있다. 쇼핑에서의 상품 추천, 화학에서 분자 구조, 사람들간의 관계 네트워크 등이 이에 포함된다.

 

그러나 그래프는 노드의 사이즈도 다양하고, 순서관계도 없고, 이웃의 크기도 다른 등 데이터가 규칙적이지 않다. 그래서 이를 표현하거나, 아니면 그래프로 어떤 계산을 하는 자체가 쉽지 않다. 특히 선형회귀와 같은 현재 머신 러닝에서는 기본적으로 인스턴스들이 서로 독립적이어야 한다는 전제가 있다. 하지만 그래프에서 노드는 서로 독립적이지 않고, 다른 노드들과 여러 관계를 맺고 있어서 기존 유클리드 공간에서 활용하던 머신러닝 기법들을 적용하기 어렵다.

이렇게 비유클리드 공간, 즉 그래프 분석을 위해서 최초의 GNN 논문 이후로 많은 연구가 나오게 된다.

 

 

 

- Recurrent Graph Neural Networks (RecGNNs)

- Convolutional Graph Neural Networks (ConvGNNs)

- Graph AutoEncoders (GAEs) 

- Spatial-Temporal Graph Neural Networks (STGNNs)

 

 

 

GNN은 위와 같이 크게 4개의 카테고리로 분류할 수 있다.

 

 

RecGNNs는 recurrent를 기반으로 iteration을 통해 node를 학습하는 방법을 말한다. Graph Neural Networks 가 recurrent 모델로부터 출발하였다. 그래프 자체가 시작과 끝이 있는 것이 아닌, 순환 구조이기 때문에 이 구조를 recurrent 모델을 통해 표현하고자 한 것으로 생각된다. RecGNN은 노드 표현을 RNN으로 학습하고자 하는 것에 중점을 둔다. 여기서는 노드가 stable equilibrium에 도달할 때 까지 계속해서 정보/메시지를 이웃 노드와 교환한다고 전제하였다. RecGNN은 다음에 등장하는 ConvGNN에 많은 영향을 주었다는 점에서 의미가 있다. 특히 이 메시지 패싱이라는 아이디어는 spatial-based convolutional GNN 에서도 이어졌다.

 

 

ConvGNNs은 Computer Vision에서 사용되는 CNN을 기반으로 각 node 또는 edge의 정보를 계산하는 방법을 말한다. ConvGNNs에는 크게 spectral과 spatial로 나뉜다. ConvGNN 은 convolution 이라는 연산을 일반 grid data 가 아닌, 그래프 데이터에 적용하는 방법을 정립하였다. ConvGNN 의 핵심 아이디어는 바로 노드 v를 그 노드의 feature인 x_v와 이웃 노드의 feature인 x_u​,u∈N(v)를 aggregate 하여 표현했다는 점이다. RecGNN과 다른 점은 ConvGNN은 여러개의 graph convolutional layer 를 쌓아서 노드를 고차원으로 표현했다는 점이다. ConvGNN 은 여러 종류의 GNN 모델을 설계할 때 가장 중심적으로 사용된다. 예를 들어, graph convolution 사이에 ReLU 를 두어 node classification 모델을 만들 수도 있고, convolution 을 계속 pooling 하여 softmax 를 적용하면 graph classification 모델이 된다.

 

 

GAEs는 기존 AE와 같이 graph data를 embedding하거나 graph를 생성하기 위한 방법을 말한다. GAE 는 노드나 그래프를 인코딩하고 다시 복원하는 과정에서 latent vector 를 얻는 비지도 학습이다. GAE는 네트워크 임베딩과 graph generative distributions 를 학습하기 위한 용도로 사용된다. 네트워크 임베딩에서 GAE는 latent node representation 을 학습한다.

 

 

마지막으로 STGNNs는 graph의 spatial과 temporal을 함께 고려한 방법이다. 즉, 공간과 순서를 함께 고려했다고 생각하면 이해하기 쉽다. Spatial-temporal(공간적-시간적) 그래프의 숨겨진 패턴들을 학습하기 위한 네트워크다. 교통량 예측, 사람 동작 인식, 운전 행동 예측 등 다양한 분야에서 중요한 요소가 되고 있다. STGNNs의 핵심 아이디어는 공간적인 의존성과 시간적인 의존성을 동시에 고려하는 것이다. 현재 많은 접근방식들은 graph convolution을 통해 공간적 의존성을, RNN이나 CNN을 통해 시간적 의존성을 가져가는 방식을 사용하고 있다.

 

 

 

 

GNN의 Output

 

 

- Node-level outputs

- Edge-level outputs

- Graph-level outputs

 

 

GNN을 어떻게 활용하는지 살펴보기 위해 먼저 GNN의 output에 대해 봐야 한다. GNN의 출력 형태는 고정되어있지 않고, 다음과 같이 어떤 부분에 초점을 맞추는지에 따라 달라진다.

 

노드에 대한 regression 혹은 classification 등을 처리하고자 할 때, Node-level outputs를 사용한다. RecGNNs와 ConvGNNs가 고수준의 node representation을 information propagation/graph convolution을 통해 뽑을 수 있다.


엣지에 대한 classification, 연결 예측 등에 활용되는 output이다. 두 노드의 hidden representation을 GNN의 input으로 하고, 유사도 함수 혹은 NN을 통해서 엣지의 연결 강도나 label 등을 예측할 수 있다.


그래프 수준의 output은 어떤 그래프를 분류하는 데 보통 활용된다. 그래프 수준에서의 representation을 얻기 위해 GNN에 pooling이나 readout 등을 결합해서 활용하기도 한다. 이후에 이에 대해 자세히 다루도록 한다.

 

 

 

 

GNN의 학습 방법

 

 

GNN을 지도학습, 비지도학습 등 다양한 방법으로 학습시킬 수 있다. 이는 학습 목적과 label 정보 유무 등에 따라 다음과 같은 방법 등이 있다.

 

• Semi-supervised learning for node-level classification

Graph convolutional layer를 쌓고 나서 multi-class classification을 위한 softmax layer를 연결하면 된다. 네트워크의 일부 노드들은 label이 되어있고, 다른 노드들이 label되어있지 않은 상태라고 하면, ConvGNN을 통해 unlabeled 노드에 대해 분류하는 모델을 학습시킬 수 있다.

 

• Supervised learning for graph-level classification

이를 위한 end-to-end learning은 graph convolutional layer, graph pooling layer, (readout layer)를 사용하면 된다. 여기서 graph convolutional layer는 고수준의 node representation에 필요하고, graph pooling layer는 그래프를 downsampling 하여 각 그래프를 sub-structure로 만드는데 사용한다. readout layer는 node representation들을 graph representation으로 만든다.

그래프 수준에서의 classification은 전체 그래프에 대한 클래스 label을 예측하기 위해 사용한다.

 

• Unsupervised learning for graph embedding

이 알고리즘들에서 엣지 수준의 정보를 두 가지 방법으로 활용한다.

 

첫 번째로는 autoencoder를 활용하는 방법이다. 여기서 encoder는 graph convolutional layer를 활용하여 구성되고, 그래프를 embedding 시킨다. decoder는 다시 그래프 구조를 재구성한다.

 

두 번째로, negative sampling 방법으로, 노드의 쌍의 일부는 negative로, 나머지는 positive로 샘플링하는 것이다. 그리고 logistic regression layer를 통해 postive 쌍과 negative 쌍을 구분한다.

 

그래프에서 class label 이 따로 없는 경우에는 graph embedding을 비지도학습을 통해 학습시킬 수 있다.

 

 

 

 

Reference

 

https://thejb.ai/comprehensive-gnns-1/

Graph Neural Networks 개념정리 1 - 개요

https://tootouch.github.io/research/gnn_summary/#roadmap

Graph Neural Network 찍어먹기