[survey paper] GNN (2018/12)

 

 

오역, 의역, 생략 및 제 맘대로 해석한 글임에 주의하세요.

부분적으로 AI가 쓴 글임에 주의하세요.

---

논문 정보:

https://arxiv.org/pdf/1812.08434

그래프 신경망(GNN)의 개념부터 다양한 모델 분류, 그리고 실제 응용 사례까지 체계적으로 정리한 논문이다.

 

[목차]

1. Introduction (서론)

2. General design pipeline of GNNs (GNN의 일반적인 설계 파이프라인)

• 2.1. Find graph structure (그래프 구조 찾기)
• 2.2. Specify graph type and scale (그래프 유형 및 규모 명시)
• 2.3. Design loss function (손실 함수 설계)
• 2.4. Build model using computational modules (계산 모듈을 사용하여 모델 구축)

3. Instantiations of computational modules (계산 모듈의 구체화)

• 3.1. Propagation modules - convolution operator (전파 모듈 - 합성곱 연산자)
  • 3.1.1. Spectral approaches (스펙트럼 접근 방식)
  • 3.1.2. Basic spatial approaches (기본적인 공간 접근 방식)
  • 3.1.3. Attention-based spatial approaches (어텐션 기반 공간 접근 방식)
  • 3.1.4. General frameworks for spatial approaches (공간 접근 방식을 위한 일반적인 프레임워크)
• 3.2. Propagation modules - recurrent operator (전파 모듈 - 순환 연산자)
  • 3.2.1. Convergence-based methods (수렴 기반 방법)
  • 3.2.2. Gate-based methods (게이트 기반 방법)
• 3.3. Propagation modules - skip connection (전파 모듈 - 스킵 연결)
• 3.4. Sampling modules (샘플링 모듈)
  • 3.4.1. Node sampling (노드 샘플링)
  • 3.4.2. Layer sampling (레이어 샘플링)
  • 3.4.3. Subgraph sampling (서브그래프 샘플링)
• 3.5. Pooling modules (풀링 모듈)
  • 3.5.1. Direct pooling modules (직접 풀링 모듈)
  • 3.5.2. Hierarchical pooling modules (계층적 풀링 모듈)

4. Variants considering graph type and scale (그래프 유형 및 규모를 고려한 변형)

• 4.1. Directed graphs (유향 그래프)
• 4.2. Heterogeneous graphs (이종 그래프)
• 4.3. Dynamic graphs (동적 그래프)
• 4.4. Other graph types (기타 그래프 유형: 하이퍼그래프, 부호 그래프 등)
• 4.5. Large graphs (대규모 그래프)

5. Variants for different training settings (다양한 학습 설정을 위한 변형)

• 5.1. Graph auto-encoders (그래프 오토인코더)
• 5.2. Contrastive learning (대조 학습)

6. A design example of GNN (GNN 설계 예시)

 

7. Analyses of GNNs (GNN 분석)

• 7.1. Theoretical aspect (이론적 측면)
• 7.2. Empirical aspect (실증적 측면)

8. Applications

• 8.1. Structural scenarios
• 8.2. Non-structural scenarios

9. Open problems

 

10. Conclusion

---

Graph neural networks: A review of methods and applications

J. Zhou et al. 2020

 

Abstract

GNN(Graph Neural Network)는 그래프의 노드 간에 전달되는 정보를 통해서, 그래프들 간의 관계를 찾아낸다.

최근 GNN의 변종들, 예를 들어 GCN(Graph Convolution Network), GAT(Graph Attention Network). GRN(Graph Recurrent Network)가 훌륭한 성능을 보여줬다.

이 논문에서는 GNN model을 설계하는 표준 pipline을 제시하고, GNN의 각 변종들에 대해 자세히 알아볼 것이며, 응용들을 구조적으로 분류할 것이며, 마지막으로 후속 연구를 위한 4가지 잠재적 문제점들을 제안한다.

 

 

1. Introduction

Graph는 객체의 집합(nodes)와 그들의 관계(edge)를 표현하는 자료 구조이다.

GNN(Graph Neural Netowrk)는 graph 구조에서 사용되는  Deep Learning 방법이다. graph를 보통 node-feature matrix나 adjacent matrix를 통해 나타낸다.

 

GNN의 역사

GNN의 초기 아이디어는 오래되었다.

  - acyclic graph에 RNN을 처음 적용함. (1998)

  - cyclic graph에 RNN과 FNN을 적용함. (2009)

결과는 성공적이었지만, 여기서 graph에 사용한 State Transition System과 수렴할 때까지 반복하는 것은, 확장성과 표현력이 제한적이었다.

 

하지만 최근 DNN이 발전하며, 특히 CNN(1998)이 나오고 나서 GNN이 재조명되었다.

CNN은 다양한 해상도의 국소적인 공간적 특징을 추출하고, 표현력이 뛰어난 표현이 되도록 재구성하는 능력을 가지고 있는데, 이 능력 덕에 많은 기계학습 분야에 breakthrough가 열렸다. CNN의 가장 중요한 핵심은 local connection과, 가중치를 공유하며, 여러 레이어를 사용하는 것이다. 하지만 CNN은 이미지(2D grid)와 텍스트(1D sequence)와 같은 정형적이고 구조화된 데이터에만 사용 가능하다.

 

하지만 이미지나 텍스트는 graph와 같은 형태로도 볼 수 있기에, CNN을 변형하면 graph에도 일반화하는 것이 가능하다.

  - CNN을 확장하여, graph나 manifold와 같은 비정형구조에서도 사용하겠다 (Geometric Deep Learning) (2017)

  - feature를 수작업으로 정의하던 전통적인 machine Learning방법을 깬 Representation Learning이 나오고 나서, Word Embedding은 최초로 Representation Learning에 graph embedding을 적용시켰다. (2013)

  -  ..등등 혁신은 이어졌다.

 

하지만 위의 방법들은 2가지 치명적인 문제점이 있었다.

1) encoder 내부의 node간의 parameter들은 공유되지 않았기 때문에, node가 많아질수록 parameter도 선형적으로 증가했다.

2) 직접적으로 embedding하는 방식은 일반화 성능이 떨어져서, 새로운 그래프를 다루기 힘들었다.

 

드디어 CNN과 graph embedding에 기반해서, graph 구조로부터 종합적으로 정보를 모을 수 있는 GNN의 변종들이 제안되었다. 

 

 

 

2.  GNN 설계의 보편적인 pipline  2020년 기준

이 논문에서 사용된 notations

 

2.2. graph type과 scale

아래의 기준은 서로 독립이다.

 Type

  - Directed / Undirected Graphs : 방향이 있나? 아니면 양방향인가?

  - Homogeneous / Heterogeneous Graphs : Node와 Edge의 type이 같은가? 아니면 서로 다른가?

  - Static / Dynamic Graphs : graph가 고정인가? 아니면 시간에 따라 변화할 수 있는가?

 Scale : 상대적이며, 기준이 계속 바뀐다.

 

2.3. Loss Function 만들기

task type과 training 환경에 맞게 Loss Function을 설계해야 한다.

graph 학습 task는 대부분 3가지로 나누어진다.

  - node-level task

node classification  :  이 node는 어떤 class인가?

node regression  :  이 node의 값(continuous)은 무엇인가?

node clustering  :  node들을 가까운 것들끼리 서로 다른 group으로 묶기.

  - edge-level task

edge classification  :  이 edge는 어떤 class인가? 

link prediction :  이 두 node사이에는 edge가 있을까? 없을까?

  - graph-level task

graph classification

graph regression

graph matching

 

참고로 Supervised Learning은 3가지로 나뉜다.

  - Supervised Learning : 훈련 시에 label이 있다.

  - Semi-supervised Learning : 훈련 시에 극소수의 node에만 label이 있고, 나머지는 없는 채로 학습한다. 

  - Unsupervised Learning : pattern을 찾는 데에 label은 주어지지 않음.

 

예를 들어 node-level semi-supervised classification 에서는, label된 training data에 cross-entrophy loss를 쓸 수 있다.  

 

2.4. 모듈을 조합해서 model 만들기

드디어 computational module을 이용해서 model을 설계할 수 있다.

자주 쓰는 module들은 아래와 같다.

  - Propagation Module : 조합된 정보가 feature 및 topological한 정보를 모두 포함할 수 있도록, node들 간의 정보를 propagation하는 데 사용된다. convolution operator와 recurrent operator가 이웃들간의 정보를 종합하고, skip connection operator는 node들의 과거 표현들로부터 정보를 모으고 over-smoothing 현상을 완화하는 데 사용된다.

  - Sampling Module : graph가 너무 크면, propagation module이 propagation을 할 때, 계산하는 이웃을 제한함으로써 계산량을 줄인다.

  - Pooling Module : 고차원의 graph의 표현이 필요할 때, node들로부터 정보를 추출한다.

 

많은 예외가 있지만, 다른 많은 GNN들이 아래와 같은 구조를 공통적으로 가진다.

 

 

 

 

---

GNN에 대한 쉬운 설명은 아래에서 찾아볼 수 있다.

https://glanceyes.com/entry/%EC%B6%94%EC%B2%9C-%EC%8B%9C%EC%8A%A4%ED%85%9C-GNNGraph-Neural-Network%EC%99%80-%EC%9D%B4%EB%A5%BC-%EC%9D%91%EC%9A%A9%ED%95%9C-NGCFNeural-Graph-Collaborative-Filtering%EC%99%80-LightGCN