GraphSAGE : Inductive Representation Learning on Large Graphs

LEE HANBIN·2023년 2월 9일

논문

목록 보기

7/8

1. Introduction

Large Graph에서 node에 대한 low-dimensional vector embedding(저차원 벡터 임베딩)은 다양한 예측 및 그래프 분석 과제에서 feature inputs으로 유용하다. 그러나 이전의 연구들은 고정된 단일 그래프에 대하여 embedding 하는 것에 집중해왔다. 현실에서는 Youtube에 새로운 동영상이 올라오는 것처럼 새로운 node와 sub graph가 우후죽순으로 생기기 때문에, 관찰하지 못했던 새로운 node에 대하여 embedding을 빠르게 생성할 필요가 있었다. GraphSAGE는 node feature 정보를 활용하여 각 node에 대한 embedding을 수행하는 inductive framework이다.

2. GraphSAGE

2.1. Embedding generation (i.e. forward propagation) algorithm

GraphSAGE model의 파라미터가 이미 학습되었다는 것을 가정.

NOTE:

$AGGREGATE_k, \forall k \in \{1, ..., K\}$ : 이웃 node 들의 정보를 결합하는 K개의 parameters aggregator functions
$W^k, \forall k \in \{1, ..., K\}$ : 서로 다른 layer, 혹은 "search depth(탐색하고자 하는 이웃 노드의 깊이)"에서 정보를 전달할 때, 정보량을 결정하는 weight matrices

Algorithm 1은 전체 그래프 $G=(V,E)$ 와 모든 node에 대한 features $x_v, \forall v \in V$ 이 input으로 주어졌을 때, embedding generation 과정을 설명한다. Algorithm 1에서 outer loop의 각 step은 다음과 같이 진행된다. 이 때, $k$ 는 outer loop에서 현재 step, 혹은 search depth을 의미하고, $h^k$ 는 현재 step에서 node representation을 의미한다.

각 node $v \in V$ 에 인접한 이웃 node의 representations $\{h^{k-1}_{u}, \forall u \in N(v)\}$ 을 single vector $h^{k-1}_{N(v)}$ 로 aggregate(결합)한다. 이 때, aggregate되는 이웃 node의 representations은 이전 outer loop step( $i.e., k-1$ )의 node representation이며, $k=0$ (base case)일 때 representation은 input node features와 동일하다.
현재 node의 representation $h^{k-1}_v$ 과 aggregated neighborhood vector $h^{k-1}_{N(v)}$ 를 concatenate(연결)한다. 그리고, 이렇게 연결된 값을 fully connected layer와 nonlinear activation function $\sigma$ 를 통과한다. 이 값은 $h^k_v, \forall \in V$ 로 표현한다.
Depth $K$ 에서 최종 representations output은 $z_v \equiv h^K_v, \forall v \in V$ 이다.

이웃 node들의 정보를 다양한 방법으로 aggregate 할 수 있다. 이는 Section 2.3.에서 다루고자 한다.

Algorithm 1을 minibatch 환경으로 확장하면, inner loop(line 3 in Algorithm 1)에서 모든 node를 탐색하는 것이 아닌, 각 depth에서 recursion을 위해 필요하여 sampling 된 representation만 탐색한다.

Neighborhood definition
Batch 단위 당 연산량을 동일하게 하기 위하여 고정된 크기의 이웃들만 학습에 사용한다. 이를 $N(v)$ 로 정의하고, 각 iteration $k$ 에 대하여 다르게 샘플링한 node $u$ 를 사용한다. 위와 같은 sampling을 사용하지 않으면 single batch에 대해 필요한 메모리와 실행 시간을 예측할 수 없고, 최악의 경우 $O(|V|)$ 이다. 반대로, sampling 기법을 사용하면 batch 단위 당 시간 및 공간 복잡도는 $O(\Pi^K_{i=1}S_i),$ where $S_i, i \in \{1, ..., K\}$ ( $K$ 는 hyper-parameter)로 고정된다. 논문에서는 $K=2$ 이고 $S_1 \cdot S_2 ≤ 500$ 일 때 높은 성능을 보이는 것을 확인했다.

2.2. Learning the parameters of GraphSAGE

본 논문에서는 unsupervised 환경에서 representation을 학습하기 위하여 output representations, $z_u, \forall u \in V$ 에 대한 graph-based loss function을 제안한다. Graph-based loss function은 인접한 node는 비슷한 representation을 갖고, 인접하지 않은 node는 구별되도록 weighted matrices $W_k, \forall k \in \{1, ..., K\}$ 와 aggregator functions의 parameter를 SGD(stochastic gradient descent)를 통해 학습 시킨다.

J_{G(z_u)}=-log(\sigma(z^T_uz_v))-Q \cdot E_{v_n \sim P_n(v)}log(\sigma(-z^T_uz_{v_n}))

이 때, $v$ 는 고정된 크기의 random work를 통해 node $u$ 와 인접하게 된 node이며, $\sigma$ 는 sigmoid 함수이다. $P_n$ 은 negative sampling distribution이고, $Q$ 는 negative sample의 개수를 정의한다. 여기서 주의해야할 것은 loss 함수에 사용되는 $z_u$ 는 각 node에 대한 unique embedding이 아닌, local neighbor node의 정보를 활용하여 feature로부터 생성한 node embedding 값이다.

특정한 downstream task에서 GraphSAGE를 사용하고자 한다면, task의 목적에 맞게 loss 함수를 변경하여 사용할 수 있다. (e.g., cross-entropy loss)

2.3. Aggregator Architectures

Sentence, images, or 3-D volumes와 같은 N-D 구조와 다르게 graph에서 node's neighbors 구조는 순서가 존재하지 않는다. 그러므로, Algorithm 1에서 aggregator functions은 순서가 없는 vectors set에 대하여 동작할 수 있어야 한다.

Mean aggregator:
$\{h^{k-1}_u, \forall u \in N(v)\}$ 에 대하여 elementwise mean을 적용한다.
Algorithm 1의 Lines 4와 5를

h^k_v \leftarrow \sigma(W \cdot MEAN(\{h^{k-1}_v\}\cup\{h^{k-1}_u, \forall u \in N(v)\})

로 변경하면 transductive GCN framework와 유사하게 된다. 여기서 line 5에서 수행하던 concatenation이 존재하지 않는데, 이미 MEAN 연산을 수행할 때 정보를 주고 받았기 때문이다. 이러한 concatenation은 다른 "search depths"나 "layers" 간의 skip connection으로 간주할 수 있고, 이를 통해 모델의 성능 향상을 기대할 수 있다.

LSTM aggregator:
LSTM은 본질적으로 input을 순차적으로 처리하기 때문에 symmetric 하지 않는다. 따라서 본 논문에서는 LSTM을 순서가 없는 node를 랜덤하게 조합하기 위하여 사용한다.

Pooling aggregator:
Pooling aggregator은 symmetric하고 학습 가능한 파라미터를 갖고 있다. Pooling 방법론에서는, neighbor's vector를 각각 fully-coonected neural network를 통과 시킨다. 다음으로, elementwise max-pooling 연산을 적용한다.