초 간단 논문리뷰 | Graph Neural Networks란

Components of Graph Network

http://web.stanford.edu/class/cs224w/

 

A Comprehensive Survey on Graph Neural Networks

• paper: https://arxiv.org/pdf/1901.00596.pdf

image classification, natural language understanding 등 기존 tasks의 데이터는 Euclidean space에서 표현했다. 하지만 application 수가 증가하며 생성된 데이터는 non-Euclidean domains이고 이는 object 사이에 복잡한 관계를 갖는 graph로 표현된다.

 

1. Introduction

graphs는 불규칙적일 수 있다. 다양한 순서가 없는 node를 가질수도, node에 연결된 nieghbors의 숫자도 다를 수 있다. 따라서 graph domain에는 다르게 적용해야한다.

graph 데이터를 다루기위해 기존의 딥러닝 CNNs, RNNs, autoencoder 방법으로부터 새로운 일반화를 통한 응용한 연구가 진행되어왔다. 예를 들어 graph convolution은 2D convolution의 일반화가 될 수 있다. 2D convolution과 유사하지만 graph convolution은 node’s neighborhood 정보의 weight average를 가진다.

 

** manifolds: 국소적으로는 유클리드 공간과 닮았지만 대역적으로는 위상 공간이다.

 

2. BackGround & Definition

outlines the background of graph neural networks, lists commonly used notations, and defines graph-related concepts.

A. Background

A brief history of graph neural networks (GNNs)

이전 연구들은 recurrent graph neural networks의 카테고리였다. 고정된 point에 도달할때 까지 neighbor information을 전파하는 방법으로 target node’s representation을 학습한다. 하지만 이 프로세스는 컴퓨팅 비용이 비싸며 이 문제를 극복하기 위한 노력이 증가해왔다.

2009년에는 RNN(message passing)의 아이디어를 상속하면서 구조적으로 non-recursive layer를 합성하여 graph mutual dependency를 해결하는 RecGNNs(Micheli et al.) 방법이 제안되었다.

CV 도메인에서 CNN의 성공으로 graph를 데이터를 병렬적 개발하기 위한 convolution이 재정의되었다. ConvGCNNs(Bruna et al.(2013)) 은 spectral-based 접근법과 spatial-based 접근법으로 주요하게 나눠진다.

 

Graph neural networks vs. network embedding

network embedding의 목적은 low-dimensional vector로 representation을 생성하고 network topology structure와 node content information을 모두 보존하여 classification, clustering, recommendation등을 쉽게 수행할수 있도록 하는 것이다. matrix factorization, random walks 방법(non-deep learning method)을 사용한다. (예시, support vector machines for classification)

GNNs은 딥러닝 모델이며 end-to-end graph와 연관된 task를 해결하는 것이 목적이다. GNNs는 다양한 task를 위한 neural network model의 그룹이며 다양한 network embedding을 포함하고 있다.

 

Graph neural networks vs. graph kernel methods

GNNs과 유사하게 graph kernels는 mapping function을 이용하여 graphs or nodes를 vector space로 임베딩할 수 있다. mapping function이 learnable하기보다는 deterministic하다는 점이 다르다.

 

B. Definition

Definition 1 (Graph):

$G=(V,E)$, $V$: nodes, $E$: set of edges

$v_i \in V, e_{ij} = (v_i, v_j) \in E$

neighborhood of a node $N(v) = {u\in V|(v,u) \in E}$

 

adjacency matrix $A$ is $n \times n$ matrix 

http://web.stanford.edu/class/cs224w/

** 인접 행렬: edges의 관계를 표현

$\begin{cases} A_{ij} = 1 ,\ if\ e_{ij} \in E \ A_{ij} = 0,\ if\ e_{ij} \notin E \end{cases}$

 

node attributes matrix $X \in R^{n\times d}$

node feature attribute $x_v \in R^d$

 

edge attribute $X^e \in R^{m\times c}$

edge feature attribute $x_{v,u}^e \in R^c$

 

Definition 2 (Directed Graph):

directed(방향이 있는) graph는 node로부터 다른 node로 향하는 edges가 있는 것이다. adjacecy matrix가 대칭적인 경우에만 undirected graph이다.

 

Definition 3 (Spatial-Temporal Graph):

$G^{(t)} = (V,E,X^{(t)}), X^{(t)} \in R^{n\times d}$ : node attributes matrix도 고려!

spatial-temporal graph는 node attributes가 시간에 따라 dynamic하게 변화하는 attributed graph이다.

 

3. Categorization and Frameworks

clarifies the categorization of graph neural networks

 

A. Taxonomy of Graph Neural Netowrks (GNNs)

Recurrent graph neural networks (RecGNNs): GNN의 개척자라고 볼 수 있다.

RecGNN의 목적은 recurrent neural architectures로 node representation을 학습하는 것이다. graph의 node은 stable equilibrium(=변화하지 않는 안정된 상태)에 도달할 때까지 neighbor와 정보를 교환한다고 가정한다.

 

Convolutional graph neural networks (ConvGNNs): grid data로 부터 graph data로 convolution 연산을 일반화한다.

주된 아이디어는 feature $x_v$ 와 neighbors’ features $x_u$(where $u \in N(v)$)를 조합하여 node $v$’s features $x_u$를 생성하는 것이다. RecGNNs와 달리 ConvGNNs는 high-level node representation을 추출하기 위해 multiple graph convolutional layers를 쌓는다.

Figure 2a shows a ConvGNN for node classification.

Figure 2b demonstrates a ConvGNN for graph classification.

 

Graph autoencoders (GAEs): unsupervised learning framework이다.

node/graph를 latent vector space로 인코딩하고 encoded information으로부터 graph data를 재구성한다. network embedding과 graph generative distribution을 학습하는데 유용한다.

Figure 2c presents a GAE for network embedding.

 

Spatial-temporal graph neural networks (STGNNs): hidden patterns를 학습하는 것이 목적이다.

핵심 아이디어는 spatial dependency와 temporal dependency를 한번에 고려하는 것이다.

Figure 2d illustrates a STGNN for spatial-temporal graph forecasting.

 

B. Frameworks

mechanisms

• Node-level outputs relate to node regression and node classification tasks. With a multi-perceptron or a softmax layer as the output layer, GNNs are able to perform node-level tasks in an end-to-end manner.
• Edge-level outputs relate to the edge classification and link prediction tasks. two nodes’ hidden representations로 the label/connection strength of an edge 예측할 수 있다.
• Graph-level outputs relate to the graph classification task. graph level에서 compact representation를 얻을 수 있다.

Training Frameworks

Many GNNs (e.g., ConvGNNs) can be trained in a (semi-) supervised or purely unsupervised way within an end-to-end learning framework, depending on the learning tasks and label information available at hand.

• Semi-supervised learning for node-level classification
• Supervised learning for graph-level classification
• Unsupervised learning for graph embedding