논문: https://arxiv.org/pdf/1706.02216.pdf
코드 등: http://snap.stanford.edu/graphsage/

현재 대부분의 graph embedding framework는 본질적으로 transductive하여 a single fixed graph에 대한 embedding만 생성할 수 있다. 이러한 transductive 접근 방식은 보이지 않는 노드(예: 진화하는 그래프)를 효율적으로 generalize하지 못하고, 서로 다른 graph에서도 generalization을 배울 수 없다.

이와 대조적으로 GraphSAGE는 node attribute 정보(text attributes, node profile information, node degrees 등)를 활용하여 이전에 볼 수 없었던 데이터에 대한 representation을 효율적으로 생성하는 inductive framework다. 각 node에 대한 개별적인 embedding을 학습하는 대신에, node의 local neighborhood로부터 feature를 sampling, aggregating함으로써 embedding을 생성 (GCN 응용도 할 것이다)한다. (SAmple and aggreGatE)

세 종류의 inductive node classification task에서 baseline을 능가했다.

• Key idea:
  How to aggregate feature information from a node’s local neighborhood (e.g., the degrees or text attributes of nearby nodes)

Model param이 이미 학습되었다고 가정하고 embedding 생성 방법(3.1)을 알아보고, model param 학습 방법(3.2)을 알아보자.

일단 K aggregator functions (AGGREGATE_k, ∀k ∈ {1, ..., K})의 param, W_k를 포함한 모든 model param은 학습되어 고정된 값들이다.

위 iteration 반복할수록 점점 더 먼 범위의 이웃 노드의 information을 aggregate할 수 있다. AGGREGATE_k 함수로는 다양한 변형들(3.3)이 있다.

우리는 각 batch의 computational footprint(memory, expected runtime)를 고정하기 위하여, 각 iteration마다 노드 이웃들에서 고정 크기 set을 uniformly sampling했다.

Graph-based loss function을 z_u에 적용하고, W_k와 aggregation function의 param을 stochastic gradient descent로 tuning한다. Loss function은 가까운 노드는 비슷한, 이질적인 노드는 더욱 차이나는 representation을 가지도록 만든다.

• v: u의 fixed-length random walk 위에 공동? 등장하는 노드
• σ: sigmoid function
• P_n: negative sampling distribution
• Q: negative sample 수

각 노드에 대하여 embedding lookup을 통해 각각의 embedding을 학습하던 이전의 접근법들과 다르게, 이 loss function의 input인 representations z_u는 그 이웃 노드까지 포함한 특징으로부터 생성된다.

이 representation이 오직 하나의 task에만 이용된다면 이 식은 그 특정 task에 맞게 다른 식으로 대체되거나 무언가가 추가될 수 있다.

그래프의 노드는 다른 데이터들(문장, 이미지, ...)과 다르게 순서가 없다. 위 알고리즘 1의 aggregation function의 input은 정렬되지 않은 노드 set이다. 따라서 우리의 이상적인 aggregator는 symmetric해야하며, 동시에 여전히 학습 가능해야하며 높은 representational capacity를 유지해야한다. (Symmetry property는 우리의 NN model이 학습되어 임의의 순서 이웃 노드 feature set에 적용될 수 있음을 보장)

우리는 3가지 candidate aggregator functions를 실험해보았다.

• Mean aggregator
• LSTM aggregator
  • larger expressive capability, but not symmetric (sequential)
• Pooling aggregator
  
  • symmetric and trainable
  • max-pooling, mean-pooling 성능 비슷, 그래서 뒤 실험에서 max-pooling으로 사용

LSTM과 Pooling이 실험 결과가 좋았고, LSTM은 Pooling에 비해 매우 느렸다고 한다.