Graph Neural Networks에 대한 이해
GNN 기반 추천 논문들을 읽기 전에 정리를 해보았다. 기본은 A Gentle Introduction to Graph Neural Networks (Basics, DeepWalk, and GraphSage)에 대한 내용 번역이고 추가로 정리한 내용들을 포함했다.
GNN은 그래프에서 노드 간의 종속성을 모델링하는 능력을 가지고 있다! 관계, 상호 작용과 같은 추상적인 개념을 다루기 적합해서 관계를 분석할 필요가 있을 때 기초적으로 사용할 수 있다.
Basics of Graph Neural Network
그래프 G는 노드라고 부르는 버텍스의 집합 V 그리고 엣지의 집합 E로 간단하게 설명할 수 있다.
$G = ( V, E)$
그리고 GNN의 핵심은 특정 노드를 그 이웃 노드 와의 연결로 정의하는 것이다. 노드 간 연결 관계와 이웃 노드들의 상태를 활용해서 각 노드의 상태를 반복해서 업데이트하고 최종 업데이트 된 상태를 사용해서 원하는 태스크를 수행한다.
GNN을 사용한 대부분의 어플리케이션은 노드 분류 태스크를 한다. 기본적으로 그래프의 모든 노드는 라벨과 연결되어져 있고 우리는 노드의 레이블을 예측하려고 한다. 일부 노드가 라벨링 되어져있는 그래프 $G$가 주어지면, 레이블 된 노드를 활용해서 라벨링 되지 않은 노드 라벨을 예측하는 것을 목표로 한다.
환경
- 각각의 노드 $v$는 고유한 피처 $x_v$를 가지고 그라운드 트루스 라벨 $t_v$와 연결된다.
- 그래프 $G$ 중 일부 노드에만 라벨링이 되어있다.
목표
- 라벨링 된 노드들을 활용해서 아직 라벨링 되지 않은 라벨을 예측해야한다.
학습
- 각각의 노드를 자신의 이웃 노드의 정보를 가지는 $d$ 차원의 벡터 $h_v$로 표현하도록 학습한다.
최종적으로 노드를 표현하는 상태를 노드 임베딩($h_v$)이라고 한다.
$h_v = f(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})$
- $x_v$는 v의 피처를 의미한다.
- $x_{co[v]}$는 $v$와 연결되어 있는 엣지의 피처를 의미한다.
- $h_{ne[v]}$는 $v$와 연결된 이웃 노드의 임베딩을 의미한다.
- $x_{ne[v]}$는 $v$와 완결된 이웃 노드의 피처들을 의미한다.
- 함수 $f$는 트랜지션 함수로 입력을 d 차원 공간으로 투영시킨다
$h_v$에 Banach fixed theorem( 변수 x와 연속 함수 $f(x)$의 정의영역[$f(x)$의 정의역과 공역]이 닫힌 공간 $[0,1]$로 한정되면 $f(x_0) = x_0$ 인 고정점 $x_0$이 반드시 존재한다 )을 적용해서 반복적으로 업데이트 하도록 위 식을 재작성 할 수 있다. 이런 연산( 멀리 있는 노드로 부터 현재 노드 까지 정보가 전달 되는 과정 )을 ‘message passing’ 이나 ’neighborhood aggregation’ 라고 한다.
$H^{t+1} = F(H^t, X)$
- $H$와 $X$가 모든 $h$와 $x$를 결합한 것을 의미한다.
GNN의 결과는 출력 함수 $g$로 상태 $h_v$와 피처 $x_v$를 전달해서 결과값을 출력한다.
$o_v = g(h_v, x_v)$
$f$와 $g$는 feed-forward fully-connected 네트워크다. L1 로스는 다음과 같이 공식화할 수 있다.
$loss = \sum_{i=1}^{p}(t_i - o_i)$
마찬가지로 그래디언트 디센트 같은 방법으로 옵티마이즈 할 수 있다.
초기의 GNN은 세가지의 중요한 이슈가 있었고 이러한 이슈들을 해결하기 위해서 계속해서 발전하고 있다.
- ‘Fixed Point’ 가정이 완화되면, MLP로 더 안정적인 표현을 학습하고 반복적인 업데이트 과정을 제거할 수 있다. 원래 제안 방법에서는 반복 시, 전이 함수 $f$에 동일한 파라미터를 사용했지만, 서로 다른 MLP 레이어의 서로 다른 파라미터들은 계층적 피처 추출을 허용하기 때문이다.
- 엣지 정보를 처리할 수 없음.
- ‘Fixed Point’는 노드 분포의 다양성을 해칠 수 있어서 노드 들의 표현의 학습에 적절하지 않을 수 있다.
DeepWalk
비지도 방식으로 노드 임베딩 학습을 제안한 첫번째 알고리즘. 워드 임베딩과 유사하다. 두가지 과정을 가진다.
- 노드 시퀀스 생성을 위해서 노드에 랜덤 워크를 수행한다.
- 생성된 노드 시퀀스를 기반으로 Skip-Gram 방식으로 각 노드 임베딩을 학습한다.
램덤 워크의 각 타임 스탬프에서 다음 노드는 이전 노드의 이웃 중 유니폼하게 샘플링된다. 논문에서는 노드의 수가 많기 때문에 소프트맥스의 연산량을 해결하기 위해서 계층적 소프트맥스를 적용했다.
딥워크 GNN이 학습되면 모델은 각 노드에 대한 표현을 학습하게 된다. 그러나 ‘일반성이 부족하다’는 이슈가 있다. 새로운 노드가 추가되면, 새로운 노드를 표현하기 위해서 모델을 재학습 해야한다. 그래프의 노드가 계속해서 변화하는 다이나믹 그래프에는 적합하지 않다.
Graph Convolutional Networks
노드와 노드의 이웃 노드 정보를 이미지의 각 픽셀에 대한 주변 정보를 캡처하는 컨볼루션 신경망을 사용해서 캡처한다. GCN 모델이 거대해 질수록 그래프에서 더 추상적인 피처를 뽑아낼 수 있다. 일반적으로 그래프의 노드 간 연결이 표현된 인접 행렬과 노드의 피처 행렬을 입력으로 받는다.
-
노드 피처를 업데이트 하기 위해서 노드의 피처와 이웃 노드들의 정보를 이용한다.
$f(H^i, A) = \sigma(AH^iW^i)$
- $A$는 인접 행렬을 의미한다.
- $W^i$는 i번째 레이어의 가중치 매트릭스로 그래프에 있는 노드 전체에 적용된다.(Weight Sharing)
-
이웃 노드와의 연결 만을 고려한다면 해당 노드 자체에 대한 정보가 노드 임베딩에 포함 되지 않아 self-loop를 추가한다
$\tilde{A} = A + I$
-
인접 행렬인 A가 정규화 되어있지 않으면 피처 벡터를 곱하는 경우 불안정할 수 있다. 따라서 $A$를 정규화 한다.
$\tilde{A} = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$
- $D$는 $A$의 차수 행렬(Degree)을 의미한다.
GCN은 크게 두 알고리즘으로 분류 될 수 있다.
Spatial Convolutional Network
그래프 위에 컨볼루션 연산을 공간 기반으로 직접 적용하는 방식이다. 컨볼루션의 고정된 크기의 필터를 사용한다. 따라서 고정된 이웃 노드에서만 정보를 받아서 노드의 정보를 업데이트한다.
Spectral Convolutional Network
신호 처리 분야에서 영감을 받은 알고리즘이다. 노드 간 정보 전파를 신호 전달로 고려한다. 그래프를 노멀라이즈한 라플라시안 매트릭스로 표현 한 후에 ‘Spectral-based’ 라는 스펙트럼에 기반한 한 컨볼루션을 그래프에 적용해서 그래프를 표현한다.
GraphSage
그래프 세이지는 각 노드 임베딩을 귀납적인 방식으로 학습해서 딥워크가 가진 문제에 대한 솔루션을 제공한다. 각각의 노드가 자신의 이웃에 대한 집계 결과로 표현된다. 따라서 학습 중에 그래프에 포함되어 있지 않았던 노드도 그 노드의 이웃 노드 들로 표현될 수 있다. GCN과의 차이점은 GraphSage는 셀프와 이웃이 CONCAT 된다는 점이고 GCN은 SUM이 된다는 점이 다르다.
- 2번 줄 : 총 $k$ 횟수 만큼 업데이트를 진행한다.
- 5번 줄 : $h^k_v$ 는 집계 함수를 사용해서 업데이트 된다. 업데이트에는 이전 스텝의 $v$의 벡터, 이전 스텝의 $v$의 이웃에 대한 벡터 집계 그리고 가중치 매트릭스 $W^k$를 사용한다.
논문에서는 세가지 집계 함수를 제시한다.
1. Mean aggregator
노드 벡터와 그 노드의 이웃 노드의 벡터에 평균을 취한다.
원래 연산과 비교하면 5번 줄의 CONCAT 연산이 제거 되었는데 이 연산은 “skip-connection"으로 볼 수 도 있다.
2. LSTM aggregator
그래프 노드들 간에 정해진순서가 없어서 순서를 랜덤하게 할당한 후에 LSTM을 적용한다.
3. Pooling aggregator
노드의 이웃 노드 셋에 엘리먼트 별 풀링 함수를 수행한다.
풀링은 평균 등의 다른 풀링 함수로 교체될 수 있다. 논문에서는 맥스 풀링을 디폴트로 사용한다. 로스 함수는 다음과 같이 정의되고 가까운 노드가 유사한 임베딩을 가지고 멀리 떨어진 노드는 투영된 공간에서 분리되도록 한다.
- $u$와 $v$는 고정된 길이의 랜덤 워크에서 동시에 등장한다.
- $v_n$은 $u$와 동시에 등장 하지 않는 네거티브 샘플 들이다.
Graph Attention Network
셀프 어텐션 개념을 그래프 구조의 데이터에 적용한 방법. 같은 이웃 노드 셋에 가중치를 다르게 준다. 전체 그래프에 대한 접근이 없이 학습이 가능하다.
Graph Isomorphism Networks
GCN과 GraphSage 에서의 aggregation의 과정이 injective(일대일)이 아닌 경우가 있다.(서로 다른 엘리먼트로 구분을 못한다. ) 이러한 한계를 해결하기 위한 솔루션으로 sum aggregation을 사용해서 그래프의 구조적인 차이를 파악하는 새로운 그래프 뉴럴 네트워크 구조를 제안했다.