Inductive Representation Learning on Large Graphs
대규모 그래프에서의 귀납적 표현 학습
William L. Hamilton, Rex Ying, Jure Leskovec (2017)
이웃 노드를 샘플링하고 집계하는(sample and aggregate) 귀납적 학습 프레임워크로, 학습 시 보지 못한 새로운 노드에도 임베딩을 생성할 수 있는 확장 가능한 그래프 표현 학습 방법이다.
배경
GCN 등 기존 그래프 임베딩 방법들은 학습 시 전체 그래프가 필요한 변환적(transductive) 방식이어서, 학습 후 새로 추가되는 노드에 대해서는 전체를 다시 학습해야 했다. 이는 수십억 개의 노드가 지속적으로 추가되는 소셜 네트워크나 생물학적 네트워크 같은 대규모 동적 그래프에서는 실용적이지 않았다. 또한 전체 그래프를 메모리에 올려야 하는 풀배치 학습의 확장성 문제도 있었다.
핵심 아이디어
GraphSAGE(SAmple and aggreGatE)는 노드의 임베딩을 생성하는 '함수'를 학습한다는 핵심 아이디어에 기반한다. 각 노드에 대해: (1) 고정된 수의 이웃을 무작위로 샘플링하고, (2) 집계 함수(mean, LSTM, pooling)로 이웃 정보를 요약한 후, (3) 자신의 특징과 결합하여 새로운 표현을 생성한다. 이 과정을 K 홉까지 반복하며, 각 홉의 집계 함수가 학습 가능한 파라미터를 가진다. 고정 크기 이웃 샘플링 덕분에 미니배치 학습이 가능하고, 학습된 집계 함수를 새로운 노드에 직접 적용할 수 있어 귀납적(inductive) 학습이 가능하다.
방법론
각 레이어에서 이웃 중 S개를 균일 무작위 샘플링하여 고정 크기의 연산 그래프를 구성한다. 집계 함수로 mean(평균), LSTM(순서 무작위화 후), max-pooling 중 선택하여 사용한다. 비지도 학습(인접 노드는 가까이, 비인접 노드는 멀리)과 지도 학습(크로스엔트로피) 모두 지원하며, 미니배치 SGD로 학습한다.
주요 결과
Reddit 포스트 분류, PPI 단백질 기능 예측 등에서 기존 방법을 크게 상회했다. 특히 학습 시 보지 못한 노드에 대한 귀납적 성능이 뛰어났다. 전체 Reddit 그래프(23만 노드)에서 DeepWalk 대비 성능이 우수하면서 학습 시간은 크게 단축되었다. Pooling 집계 함수가 전반적으로 가장 우수한 성능을 보였다.
임팩트
GraphSAGE는 대규모 그래프에서의 귀납적 학습과 확장 가능한 학습이라는 두 가지 핵심 문제를 해결하여, GNN의 실용적 적용 범위를 크게 넓혔다. Pinterest의 추천 시스템(PinSage)에 적용되는 등 산업 규모의 그래프 학습에 직접적인 영향을 미쳤다. 이웃 샘플링과 미니배치 학습이라는 아이디어는 이후 거의 모든 확장 가능한 GNN 방법에 채택되었다.