0. Abstract

• Large graphs에서 node embedding은 다양한 prediction 문제에 매우 유용하다.
• 기존의 방법들의 문제는 embedding을 학습하는 과정에서 모든 node가 필요하다는 것이다.
• 기존의 방법들은 transductive하고, 보지 못한 node에 대해 일반화를 하지 못한다.
• GraphSAGE는 Inductive한 방법이기 때문에 이러한 문제를 해결할 수 있다.
  • Transductive vs Inductive
• Embedding을 만드는 function을 학습하는 방식이다.
• 여러 데이터셋에 SOTA 성능을 달성했다.

1. Introduction

• Node embedding의 기본적인 아이디어 → Dimensionality Reduction: 고차원의 정보를 dense vector embedding으로!
• 이전의 연구들은 고정된 그래프에 대한 embedding을 다루는데, 이는 현실에 적용하기 적합하지 않다.
• 계속해서 변하고 새로운 노드들을 다루는 상황에서는 inductive한 방식이 필요하다.
• 하지만 inductive한 방식에는 어려운 측면이 존재한다.
  • unseen nodes에 대한 일반화는 새로 관측된 subgraph를 기존에 알고리즘이 최적화된 embedding에 맞게 “aligning” 하는 과정이 필요하기 때문이다.
• 기존의 방식들은 대부분 transductive 하고, inductive하게 수정할 경우 많은 계산비용이 든다.
• GCN 방법 또한 고정된 그래프에서의 transductive한 경우에서만 적용가능한 문제가 있다.

Present work

• GraphSAGE(SAmple and aggreGatE)는 node feature를 활용해서 unseen nodes에 대한 일반화를 해결하려고 한다.
• 학습 알고리즘에서 node features들을 통합하면서 node의 이웃들에 대한 topological structure와 이웃에 속한 node feature들의 distribution에 대해서도 학습한다.
• 각 node에 대해 embedding vector를 학습하기 보다는, 주변 이웃(local neighborhood)를 이용한 aggregator functions의 집합을 학습한다.
• 따라서 예측 단계에서도 학습한 aggregator functions를 이용해 embedding을 만들어낸다.
• 실제 다양한 citation, Reddit, protein-protein interactions 데이터에 대해 좋은 결과를 보인다.