Graph neural network review(1)

Graph 기반 deep learning 모델의 리뷰 논문. 연산 방식, 그래프 종류, 학습 방식에 따라 나누어 설명

볼 만한 논문은 [ ] 안에 기록

1. Introduction

그래프는 객체(object)간의 관계(edge)를 표현하는 자료 중 하나이며 최근에는 머신 러닝으로 그래프의 표현력을 높이기 위한 연구들이 많이 진행됨. 그래프 분석의 주요한 목적은 node-classification, link prediction, clustering

그래프는 제곱해서 거리를 구하는 유클리디안(Euclidean) 거리를 사용할 수 없다

그래프 domain을 spectral domain이라고 부른다. Spectral domain에서 그래프를 학습시키는 geometric deep learning에 대한 연구가 시작됨. [Geometric deep learning, Bronstein et al.(2017, ieee SPM)]

다른 방향으로는 node, edge, subgraph를 낮은 차원의 벡터로 표현하는 graph representation learning에 대한 연구도 시작됨.

[A Survey on Network Embedding, Cui et al(2018, ieee TKDE)]

Geometric deep learning은 domain이 다른 데이터를 어떻게 학습시킬 것인지, Graph representation learning은 하위 구조를 어떻게 표현할지를 학습하는 것

 

기존 machine learning 기법을 적용해 representation learning을 하면 두 가지 문제점이 있음.

1. 노드 간의 파라미터가 공유되지 않아서 연산적으로 비효율적

2. Direct embedding 방식은 일반화의 능력이 떨어짐

 

그래서 CNN과 graph embedding을 기반으로 그래프 정보로 부터 집단적으로 정보를 모으는(collectively aggregate information) GNN의 variants가 제안됨. 그래프는 크게 Recurrent GNN, Convolutional GNN, Graph Autoencoder, Spatial-temporal GNN으로 나눌 수 있음.

여러 그래프에 대해 딥러닝을 적용한 systematic overview [Deep learning on Graphs : A Survey, Zhang et al.(2018, ieee TKDE)]

 

이 외에도 Graph에 adversarial learning을 적용하거나, 그래프 구조가 변하는 Dynamic graph의 학습, Node나 Edge의 종류가 여러가지인 heterogeneous graph의 학습에 관한 연구 등 다양한 연구가 진행됨.

 

2. General design pipeline of GNNs

특정한 task를 위한 GNN 모델의 파이프라인

1. Find graph structure - 문제를 그래프로 표현

• Structural scenarios → 이미 구조 자체가 정의된 경우(분자, 물리적 시스템 등)
• Non-structral scenarios → 구조를 정의해야하는 경우(문장에서 단어 그래프)

2. Specify graph type and scale - 그래프의 종류와 크기를 결정

• Directed/Undirected - Edge 방향성의 유무
• Homogeneous/Heterogeneous - Node와 Edge의 종류
• Static/Dynamic - 시간에 따른 변화 유무

위의 범주들은 독립적이어서 서로 결합할 수 있음 (ex. dynamic directed heterogeneous)

3. Design loss function

• Node level task - Node classification, Node regression, Node clustering
• Edge level task - Edge classification, Link prediction
• Graph level task - Graph classification 등

Training setting

• Supervised setting - 레이블된 데이터가 존재
• Semi supervised setting - 적은 수의 레이블된 데이터가 존재
• Transductive setting - 라벨링이 되지않은 노드에 대해 라벨을 예측
• Inductive setting - 예측을 위한 라벨링이 되지않은 노드를 샘플링
• Unsupervised setting - 레이블된 데이터가 없음. 클러스터링에 이용

4. Build model using computational modules

• Propagation module - 노드 간의 정보를 전파해서 특성과 지형적(topological) 정보를 모으는 방법
• Convolutional operator
• Recurrent operator
• Skip connection - Layer가 깊어짐에 따라 representation이 과도하게 비슷해지는 over smoothing 현상 완화
• Sampling module - 그래프가 클 때 propagation module과 결합해 sampling을 하여 propagate하는 방법
• Pooling module - High level representation을 위해 노드의 정보를 추출하는 방식

GNN pipeline

 

3. Instantiations of computational modules

3.1 Propagation module

3.1.1 Spectral approach

Spectral domain은 graph signal processing과 연관된다.

L = D - A

L : Laplacian matrix, D : Diagonal matrix, A : Adjacency matrix

D의 D(i, i)는 unweighted graph에서 node i의 degree

Laplacian 예시 (unnormalized)

Laplacian matrix의 성질

• symmetric positive-semi definite matrix ∴ 대각화 가능
• eigenvalue 0은 값이 모두 1인 eigenvector와 상응한다.
• Laplacian matrix의 eigenvalue 0의 multiplicity는 graph의 connected component(≒reachability)의 개수와 같다.

Normalized laplacian (s-symmetric, rw-random walk)

위 그림의 계산 방법으로 Normalized된 Laplacian matrix를 얻을 수 있다.

Laplacian matix의 대각화(U-eigenvector)

Laplacian의 성질로 인해 대각화를 할 수 있고 U행렬은 eigenvector가 담긴 행렬, eigenvector는 graph topology를 반영하며 이는 이후 푸리에 변환에서 중요한 역할을 한다.

K는 nonzero eigenvalue의 개수, 해당 eigenvector로 클러스터링을 한 것(Spectral clustering)

Graph Fourier Transform = Spectral domain으로의 transformation

U - Laplacian matrix의 eigenvector

Euclidean space에서 convolution을 하기 어려우니 spectral domain으로 변환하여 연산하고 이를 역변환

 

Eigenvector 하나는 graph signal의 Fourier basis 라고 할 수 있음. Low frequency는 이웃 노드와 관련하여 매우 느리게 변하는 신호이고 high frequency는 이웃 노드와 관련하여 상당하게 변하는 신호. 

 

그림 2.4에서 노드의 순서가 바뀌면 eigenvector의 요소도 순서가 바뀜 ∴ Eigenvector의 값과 node간의 mapping은 permutation invariant. 작은 eigenvalue에 대응하는 eigenvector는 zero-crossing이 적음(low frequency), 큰 eigenvalue에 대응하는 eigenvector는 zero-crossing이 많음(high frequency)

 

Laplacian matrix는 연속된 시간에 대해서 이중 미분 연산자의 근사치를 제공한다. 연속 시간의 이중 미분 연산자의 고유함수는 Fourier 기저를 만드는 복소 지수함수이다. 따라서 Laplacian matrix의 eigenvector는 graph signal이 아닌 graph에 의존한다. 

출처 : https://digitalassets.lib.berkeley.edu/techreports/ucb/text/EECS-2013-209.pdf

 

https://towardsdatascience.com/graph-convolutional-networks-for-geometric-deep-learning-1faf17dee008

Graph Convolutional Networks for Geometric Deep Learning

Graph signal processing, Graph Fourier transform 관련한 글

 

하고자 하는 것 : Learnable diagonal matrix(g_w)를 통해서 smoothest한 orthonormal basis를 찾는 것 ≒ smooth한 filter를 찾는 것

 

Spectral Network - Learnable diagonal matrix(g_w)를 filter로 사용 → 연산이 비효율적 + filter가 공간적으로 localized 되어 있지 않음

 

ChebNet - g_w를 Chebyshev 다항식을 사용하여 근사

w_k는 Chebyshev coefficient, T_k는 Chebyshev polynomial

GCN - K = 1로 설정해 과적합의 문제 완화, eigenvalue의 최댓값도 2로 assume

w = w0 = -w1의 constraint(5번식 → 6번식), 기울기 폭발, 소실 문제를 막기 위한 renormalization trick(6번식)

H - convolved matrix, X- input matrix, W - weight matrix

[Semi-Supervised Classification with Graph Convolutional Networks, Kipf et al. (2017, ICLR)]

 

AGCN - Adaptive graph convolution network : Residual graph laplacian을 원래 laplacian과 더해 노드 간의 implicit relation을 학습하도록 함.

 

DGCN - Dual graph convolutional network : 두 개의 convolutional network를 사용하여 local과 global consistency 학습

첫 번째 네트워크는 GCN과 동일하고 두 번째 네트워크는 Adjacency matrix를 positive pointwise mutual information(PPMI) matrix로 대체함.

 

GWNN - Graph fourier transform을 graph wavelet transform으로 대체

Graph wavelet transform의 장점 1. Matrix decomposition이 필요 없다. 2. Sparse하고 localized 해서 더 explainable하다.

[Graph Wavelet Neural Network, Xu et al.(2019, ICLR)]

 

Spectral approach는 이론적 기반의 방법, 최근에도 이러한 이론적인 분석이 제안되고 있음. 그러나 학습된 필터가 그래프 구조에 의존하기 때문에 다른 구조의 그래프에는 사용될 수 없다.

 

3.1.2 Basic spatial approaches

Spatial approach는 graph topology에서 convolution을 바로 정의함 → 다른 크기의 이웃에도 적용하도록 하는 것, CNN의 local invariance를 유지하는 것이 중요

 

Neural FPs - Degree만큼 다른 weight를 부여, Large scale graph에 적용하기 어려움.

W - Weight matrix, N_v - Number of neighbors

DCNN - Diffusion convolutional neural network : Node의 neighbor를 표현하기 위해서 transition matrix를 사용

P* - {P, P2, ... ,Pk} power series N x K x N,   X - N x F input matrix,

P*X 연산으로 input matrix가 diffusion convolution representation으로 transform(K x F matrix) → Weight matrix(K x F)와 elementwise multiplication → Non-linear function f

 

GraphSAGE - Embedding을 샘플링을 통해 generate하고 node의 neighbor 로부터 feature를 aggregate하는 방식.

[Inductive Representation Learning on Large Graphs, Hamilton et al. (2017, NIPS)]

Fixed sized neighbor로 샘플링을 하고 aggregate function(mean, LSTM, pooling 방식이 있고 GraphSAGE는 mean 방식 이용)을 통과 →  기존 노드의 hidden state과 concat하여 weight matrix와 행렬 곱  → non linear function

 

3.1.3 Attention-based spatial approaches

Attention-based operator는 이웃에 따라 다른 weight를 부여해서 noise를 줄이고 더 나은 결과를 보임.

GAT - Graph attention network : Self-attention 으로 neighbor들의 정보를 이용해 hidden state 계산하는 방식

[Graph Attention Networks, Velickovic et al. (2018, ICLR)]

Self-attention

a - weight vector 

Multi-head attention, K - Number of independent attention heads

Attention architecture의 특징

• 병렬적으로 연산 가능해서 효율적
• Degree가 다른 node에도 적용이 가능
• Inductive learning이 용이함

 

3.1.4 General framework for spatial approaches

MoNet - Mixture model network : Non-euclidean 모델을 통합하는 spatial framework, GCNN, ACNN, GCN, DCNN 등이 MoNet의 일부 [Geometric deep learning on graphs and manifolds using mixture model CNNs, Monti et al. (2017, CVPR)]

Manifold의 한 점(point)이나 graph의 한 노드(node)가 pseudo-coordinate system의 origin.

w1(u), ... , wj(u)는 pseudo-coordinate(u)에 따른 neighbor의 weight → Dj(v)f는 이웃 노드의 정보들을 모으는 역할, u와 w를 어떻게 정의하냐에 따라 달라짐.

 

MPNN - 2가지 phase가 존재 1.Message passing phase, 2. Readout phase

[Neural Message Passing for Quantum Chemistry, Gilmer et al. (2017, ICML)]

e_vu - undirected edge(v,u)

• Message function Mt를 이용해 이웃 노드의 정보를 모으고 Update function Ut를 이용해 hidden state를 update
• Readout function R로 feature vector 계산

 

NLNN - Non-local neural network : 비전 분야에서 모든 가능한 위치에서 weighted sum을 통해 hidden state 계산하는 방식, self-attention 방식과 유사

 

Graph Network - 다른 방식보다 general한 framework, MPNN, NLNN, Interaction Networks [Interaction Networks for Learning about Objects, Relations and Physics, Battaglia et al. (2017, NIPS)], Relation Networks [A simple neural network module for relational reasoning, Santoro et al. (2017, NIPS)]

GN block이 주요 연산 unit이며 3개의 aggregate, update 함수로 이루어짐.

r_k - receiver node, s_k - sender node, E(t+1) - stacked edge vector, H(t+1) - stacked node vector, u - global attribute for graph

함수의 종류는 다른 setting이 될 수 있으며 p 함수는 입력 순서에 따라 invariant 해야하고 variable length도 가능해야함.

 

3.2 Propagation modules - recurrent operator

Convolution과의 차이 : Recurrent는 weight를 공유함.(Convolution은 그렇지 않음)

 

3.2.1 Convergence-based methods

Node, edge feature를 반복적으로 이용해 그래프의 representation을 하는 방식

Representation의 분포가 smooth하고 각 노드를 나타내기에는 less informative하기 때문에 node의 representation에는 적절하지 않음.

 

3.2.2 Gate-based methods

GRU나 LSTM과 같은 gate를 도입해 계산적인 제한과 long-term propagation 보완, convergence를 보장하지는 않음.

 

GGNN - Gated graph neural network : Function f가 contraction map(Banach's theorem과 관련하여 수렴성에 대한 내용)이어야 하고 propagation step에서 GRU(Gated Recurrent Units 사용)

[Gated Graph Sequence Neural Networks, Li et al. (2016, ICLR)]

z - update gate, r - reset gate

이외에도 Gate로 LSTM을 사용한 모델들 - Tree LSTM, Graph LSTM, S-LSTM

 

3.3 Propagation modules - skip connection

GNN architecture도 Layer가 깊어진다고 성능이 향상되는 것은 아님. ∵ Noisy한 정보 또한 전파되기 때문에 모델이 깊어질수록 representation이 서로 비슷해지는 over smoothing 문제가 발생. ResNet과 비슷하게 skip connection을 통해 over smoothing 문제 완화.

 

JKN - Jump knowledge network : 마지막 layer의 node에서 intermediate representation을 선택해 모델을 adaptive하게 설계. 

Aggregate function에서는 concatenation, max-pooling, LSTM-attention 과정이 있으며 JKN은 GCN, GraphSAGE, GAT와 결합하여 성능을 향상시킬 수 있다.

[Representation Learning on Graphs with Jumping Knowledge Networks, Xu et al. (2018, ICML)]

 

DeepGCNs - ResNet의 아이디어에서 착안하여 Residual connection과 dense connection을 결합. Vanishing gradient와 over smoothing 문제를 완화.

Deep GCN architecture

ResGCN은 바로 전 hidden state만 더해지는 방식, DenseGCN은 이전 hidden state가 모두 더해지는 방식

 

3.4 Sampling modules

 GNN 모델들은 previous layer에서 이웃의 정보를 모음. 직관적으로 해석하면 layer가 깊어질수록 이웃들이 기하급수적으로 늘어나 각 노드에 모든 이웃의 정보를 담을 수 없음 → Sampling

 

3.4.1 Node sampling

직관적인 방법은 각 노드의 이웃으로부터 일부만 sampling하여 개수를 줄이는 방법

GraphSAGE의 경우 정해진 작은 수의 이웃을 추출(2~50), Sampling variance를 줄이기 위해서 확률적으로 접근한 방법론도 존재

 

PinSage - Importance 기반의 sampling 방법 제안, 타겟 노드에서부터 시작하여 random walk를 시도 → 가장 많이 방문한 Top T개의 노드를 채택하는 방식

 

3.4.2 Layer sampling

Node sampling이 아닌 layer sampling을 통해서 각 layer에서 확장되는 요소를 조절할 수 있다. 

 

FastGCN - Importance sampling을 기반으로 각 layer에서 직접 receptive field를 sampling하는 방식(Monte Carlo sampling)

[FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling, Chen et al. (2018, ICLR)]

 

이후 Sampler 자체를 parameterized 하여 학습을 시킬 수 있도록하는 방법 제안. Sampling 중요도와 분산을 줄이도록 optimize하는 방법 → LADIES [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks, Zou et al. (2019, NIPS)]

 

3.4.3 Subgraph sampling

하위 그래프를 sampling

GraphSAINT - 직접 node와 edge를 sample하여 하위 그래프를 생성하는 방식

[GraphSAINT: Graph Sampling Based Inductive Learning Method, Zeng et al. (2020, ICLR)]

 

3.5 Pooling modules

어떻게 정보 추출을 할 것인가?

3.5.1 Direct pooling modules

Node 선택 전략을 가지고 선택한 node로부터 graph-level representation을  바로 학습하는 방식

3.5.2 Hierarchical pooling modules

그래프 구조의 계층적인 정보를 담은 방식

 

Graph Coarsening - Spectral clustering은 eigendecomposition 방식이 필요하기 때문에 연산이 비효율적, Graclus가 제안한 방식이 더 빠름 (ChebNet과 MoNet에서 사용)

 

ECC - Edge-conditioned convolution : 반복적으로 downsampling을 진행하는 알고리즘. Laplacian의 가장 큰 eigenvector를 가지고 나누는 방식(가장 큰 eigenvalue에 대응하는 eigenvector가 아닐까)

 

DiffPool - St(학습 가능한 assignment matrix)를 각 layer에 도입

[Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. (2017, NIPS)]

Ht - Node feature matrix, At - Coarsened adjacency matrix

St는 다음 t 번째 layer의 노드가 t+1 번째 layer에 할당이 될 확률을 의미

SAGPool - Feature와 topology를 모두 사용해 graph representation을 학습하는 방식, self-attention 기반의 방법론 사용.

[Self-Attention Graph Pooling, Lee et al. (2019, ICML)]

 

다음 포스트에 이어서↓