[논문 리딩] Inductive Representation Learning on Large Graphs

Inductive Representation Learning on Large Graphs
2017, WL Hamilton, R Ying, J Leskovec

 

Abstract

큰 그래프에서 노드를 낮은 차원으로 임베딩하는 것은 내용 추천부터 프로틴 함수 식별까지, 여러 예측 과제에서 매우 유용하다고 증명되어 왔다.

그러나 지금까지 대부분의 접근들은 임베딩을 학습하는 동안 그래프의 모든 노드가 존재해야 한다는 전제를 가졌다.

이런 접근은 내재적으로 transductive하고 학습 기간 동안 없었던 노드들에 대해 일반화가 되지 않는다.

이 논문에서 제안하는 graphSAGE는 일반적인 inductive 프레임워크로써, 노드 피쳐 정보(텍스트 등)를 활용해 학습 데이터셋에 없었던 노드들에 대해서도 효율적으로 노드 임베딩을 생성한다.

각각의 노드에 대해 임베딩을 개별적으로 학습하는 대신, 여기에서는 노드의 로컬 이웃들의 피쳐를 샘플링하고 취합하여 임베딩을 만드는 함수를 학습한다.

제시된 알고리즘은 세 개의 노드 분류 벤치마크에 있어 베이스라인모델의 성능을 뛰어 넘는다.

* Reddit 포스트 데이터와 인용 정보를 이용해 학습 데이터에 없었던 노드의 카테고리를 분류

* 단백질-단백질 상호작용에 대한 multi-graph 데이터셋에서 학습 과정에서 없었던 그래프를 일반화

 

1. Introduction

큰 그래프에서 노드를 낮은 차원으로 임베딩하는 것은 다양한 분야의 예측 과제나 그래프 분석 과제에서 유용한 feature input이 되어 왔다.

노드 임베딩의 가장 기본적인 착안은 노드의 네이버후드에 대한 고차원의 정보를 dense한 벡터 임베딩으로 변환하는 것이다.

그 후, 노드 임베딩은 다운스트림 태스크에[ 적용되어 노드 분류, 클러스터링, 링크 예측과 같은 문제를 해결하는 데 쓰일 수 있다.

 

이전의 연구들은 하나의 고정된 그래프로부터 노드를 임베딩하는 데 집중했지만, 많은 실제 세계 문제들은 새로운 노드나 혹은 아예 새로운 (서브)그래프에 대해 임베딩을 빨리 생성하는 것을 필요로 한다.

이러한 inductive함은 높은 처리율, 머신러닝 시스템의 개발에 있어 필수적이다. (e.g., 레딧의 포스트, 유투브의 사용자와 동영상)

노드 임베딩에 있어 inductive한 접근은 같은 형식의 피쳐를 가진 그래프들 간의 일반화를 용이하게 한다.

 

inductive한 노드 임베딩의 단점은 transductive한 세팅에 비해서 어렵다는 것인데, 

새로운 노드에 대한 이랍ㄴ화를 하기 위해서는 새로 관찰된 서브그래프를 이미 최적화된 알고리즘에 끼워 넣는 방법을 찾아야 하기 때문이다.

inductive한 프레임워크는 그래프 안에서의 노드의 국지적 역할과 전역적 역할을 모두 드러낼 수 있도록 노드의 이웃에 관한 구조적 정보를 인식해야 한다ㅣ

 

노드 임베딩에 대한 존재하는 접근법들은 거의 대부분 본질적으로 transductive하다.

이 접근 방식들의 대부분은 Matrix-factorization 기반의 objective를 사용해 각 노드에 대한 임베딩을 직접적으로 최적화한다.

이런 접근 방식들은 하나의 고정된 그래프에 대해 예측을 만들기 때문에, 새로운 노드들에 대해서 일반화되지는 않는다.

이런 접근법들도 inductive한 세팅에서 동작할 수 있도록 수정될 수 있는데, 이런 경우들에도 computationally expensive한 경향이 있다. (새 예측이 만들어지기 전 gradient descent를 요구하는 추가적인 라운드를 필요로 하는 등)

최근에는 컨볼루션 네트워크를 이용해 그래프의 구조를 학습하려는 접근도 있었는데, 지금까지 그래프 컨볼루션 네트워크 (GCN)은 고정된 그래프에서의 transductive 세팅에서만 활용되어 왔다.

이 논문에서 저자들은 GCN을 inductive, 비지도학습 세팅으로 확장하고, GCN을 일반화해 학습 가능한 aggregation 함수를 사용하는 프레임워크를 제안한다.

 

present work

이 논문에서는 GraphSAGE(SAmple and aggreGatE)가 제안된다.

MF에 기초했던 임베딩 방식들과 다르게, GraphSAGE는 노드 피쳐를 활용해 새로운 노드들에 대한 일반화가 가능한 임베딩 함수를 학습한다.

학습 과정에서 노드 피쳐를 활용함으로써, 각 노드의 이웃에 관한 위상적 구조를 학습함과 동시에 이웃 노드들이 가진 노드 피쳐의 분포도 학습할 수 있다.

여기에서는 보통 피쳐가 많은 그래프들에 집중하지만, 제안되는 방식은 노드 디그리와 같이 모든 그래프에 존재하는 구조적 피쳐들 역시 활용할 수 있다.

따라서, 제안되는 알고리즘은 노드 피쳐가 없는 그래프에도 적용될 수 있다.

 

각 노드에 대해 하나하나의 임베딩을 학습하는 대신, 저자들은 한 세트의 aggregator 함수들을 학습해 노드의 local neighborhood로부터 피쳐 정보를 취합한다.

각 aggregator 함수는 서로 다른 hop수, search depth를 가지고 주어진 노드의 주변 정보를 모은다.

테스트/추론 단계에서는 학습된 시스템을 이용해 완전히 새로운 노드들에 대한 임베딩을 생성한다.

노드 임베딩 생성에 관한 이전 연구들과 같이, 여기에서도 GraphSAGE가 task-specific supervision없이 학습될 수 있도록 unsuperviesd loss function을 디자인한다.

또한, GraphSAGE가 지도학습을 통해서도 마찬가지로 학습이 가능함을 보인다.

 

제시되는 알고리즘은 세 개의 노드 분류 벤치마크를 통해 평가된다.

* 인용 데이터에 기반한 문헌 그래프에서 논문의 카테고리 예측

* Reddit 포스트 데이터에서 포스트의 카테고리 예측

* 단백질-단백질 상호작용 데이터에서 multi-graph  일반화 실험

 

이 벤치마크들을 통해 저자들은 GraphSAGE가 새로운 노드들에 대해 효과적으로 임베딩을 생성하고, 상당한 차이로 베이스라인을 넘어서는 것을 보인다.

(구체적인 성능에 대한 이야기)

 

2. Related work

제시된 알고리즘은 개념적으로 이전의 노드 임베딩 방법들, 그래프에 대한 일반적인 지도학습 방법론, 그리고 그래프 데이터에 컨볼루션 신경망을 적용하는 최근의 연구 결과와 연관되어 있다.

 

Factorization-based embedding approaches

랜덤 워크 방식이나 matrix factorization 방식을 통해 저차원의 노드 임베딩을 생성하는 방법론이 여러 가지 있다.

이 방법들은 spectral clustering, multi-dimensional scaling, PageRank 알고리즘과 같은 조금 더 고전적인 방식들과도 가까운 관계를 맺고 있다.

이러한 임베딩 알고리즘들은 개별의 노드에 대해 직접적으로 노드 임베딩을 학습하기 때문에, 내재적으로 transductive하고, 새로운 노드들에 대해 예측하기 위해서 SGD를 통한 비싼 추가적 학습을 요구하게 된다.

또한, 이런 방법들 중 상당수는 임베딩의 직교 변환에 영향을 받지 않는 목적 함수를 가지고 있는데, 따라서 임베딩 공간은 그래프 사이에서 자연적으로 일반되지 않고, 재학습 기간 동안 변할 수 있다.

이에 대한 한 가지 기록할 만한 예외는 Yang등이 제안한 Planetoid-I 알고리즘인데, 이 알고리즘은 semi-supervised 학습에 대한 inductive하고 embedding-based한 방법이다.

그러나, Planetoid-I는 추론 단계에서 그래프의 구조적 정보를 활용하지 않고, 대신 학습 단계에서 regularization의 형태로 그래프의 구조를 사용한다.

이와 같은 이전의 접근법들과 다르게, 이 논문에서는 피쳐 정보를 모델을 학습하는 데 사용한다.

 

Superviesd Learning over graphs

노드 임베딩 접근법 외에도 그래프 형식을 갖춘 데이터에서의 지도학습에 대한 여러 문헌이 있다.

여기에는 다양한 커널 기반의 접근법들이 포함되는데, 이 때 그래프의 피쳐 벡터는 다양한 그래프 커널에 의해 유도된다.

또한 최근에는 뉴럴 네트워크 기반의 접근도 여럿 생겨났다.

이 논문에서의 접근법은 개념적으로 이런 알고리즘들으로부터 영햐응ㄹ 받았다.

하지만, 이전의 알고리즘들이 그래프 전체를 분류하는 데 집중한 반면, 이 논문에서는 각각의 노드들에서 유용한 임베딩을 생성하는 데 집중했다.

 

Graph Convolutional Network

최근, 그래프에서의 여러 가지 컨볼루셔널 뉴럴 네트워크 구성들이 제안되었다.

이러한 기법들의 대다수는 큰 그래프로 확장하지 않거나, 그래프 전체를 분류하기 위해 설계되었다.

이 논문에서 제안하는 방법은 Kipf 등이 제안하는 그래프 컨볼루셔널 네트워크 (GCN)과 긴밀하게 연관되어 있다.

기존의 GCN 알고리즘은 transductive한 세팅에서의 semi-supervised learning 을 위해 설계되었고, 훈련 과정동안 전체 그래프에 대한 Laplacian을 알고 있어야 했다.

본 논문에서 제안되는 알고리즘의 간단한 변형은 GCN 프레임워크의 inductive 세팅으로의 확장으로 볼 수 있다 (section 3.3)

 

3. Proposed method: GraphSAGE

이 논문에서 가장 핵심이 되는 아이디어는 노드의 local neighborhood로부터 정보를 aggregate하는 방법을 학습한다는 것이다.

이 장에서는 먼저  GraphSAGE가 이미 학습되었다는 전제 하에 임베딩을 생성하는 알고리즘을 살펴보고, (3.1장)

그 후 GraphSAGE가 표준적인 SGD와 backpropagation 기법을 사용해 학습되는 방법을 살펴본다. (3.2장)

 

3.1 Embedding generation (i.e., forward propagation) algorithm

이 장에서는 모델이 이미 학습되어 파라미터들이 고정되었다는 가정 하에, 임베딩 생성 (or forward propagation algorithm) 과정을 살펴본다.

$K$개의 aggregator 함수들의 파라미터들이 미리 학습되었다고 가정하자.

각 aggregator 함수를 $\textit{AGGREAGTE}_k$, $\forall k \in \left\{ 1, \ldots, K\right\}$라고 할 때,

모델의 서로 다른 레이어나 혹은 "search depth" 사이에서 정보를 propagate할 때 사용되는 가중치 매트리스들을

$\mathbf{W}$, $\forall k \in \left\{ 1, \ldots, K\right\}$라고 정의한다.

 

Algorithm1: GraphSAGE embedding generation (i.e, forward propagation algorithm)

Input: Graph $\mathcal{G}(\mathcal{V}, \mathcal{E})$         input features $\left\{\mathbf{x}_v, \forall v \in \mathcal{V}\right\}$         depth $K$         가중치 행렬 $\mathbf{W}^k, \forall k \in \left \{ 1, \ldots, K \right\}$         non-linearity $\sigma$         미분 가능한 aggregator functions $\textit{AGGREGATE}_k \forall k \in \left\{ 1, \ldots, K\right\}$         neighborhood function $\mathcal{N}: v \rightarrow 2^{\mathcal{V}}$ Output: Vector representations $\mathbf{z}_v$ for all $v \in \mathcal{V}$ $\mathbf{h}_v^0 \leftarrow \mathbf{x}_v, \forall v \in \mathbf{V}$ for $k = 1 \ldots K$ do      for $v \in \mathcal{V}$ do         $\mathbf{h}_{\mathcal{N}(v)}^k \leftarrow \textit{AGGREGATE}_k(\left\{\mathbf{h}_u^{k-1}, \forall u \in \mathcal{N}(v)\right\})$         $\mathbf{h}_v^k \leftarrow \sigma (\mathbf{W}^k \cdot \textit{CONCAT}(\mathbf{h}_v^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^k))$     end     $\mathbf{h}_v^k \leftarrow \mathbf{h}_v^k /  \| \mathbf{h}_v^k \|_2, \forall v \in \mathcal{V}$ end $\mathbf{z}_v \leftarrow \mathbf{h}_v^K, \forall v \in \mathcal{V}$

 

각 이터레이션 혹은 search depth마다, 노드는 그들의 local neighborhood로부터 정보를 취합한다.

이 과정이 반복되면서, 노드는 점진적으로 그래프의 더 먼 지점으로부터 점점 많은 정보를 얻게 된다.

 

알고리즘1은 전체 그래프 $\mathcal{G} = (\mathcal{V}, \mathcal{E})$와 모든 노드들의 피쳐 $\mathbf{x}_v \forall v \in \mathcal{V}$가 입력값으로 주어졌을 때 임베딩이 생성되는 과정을 설명한다.

 

아래로는 이 과정을 어떻게 미니배치에 일반화할지를 설명한다.

알고리즘 1의 바깥 루프의 각 과정은 다음과 같이 진행된다. 

이 때 $k$는 바깥 루프의 현재 스텝을 뜻하고, $\mathbf{h}^k$는 현재 스텝에서의 노드 임베딩을 뜻한다.

 

aggregate

먼저, 각 노드 $v \in \mathcal{V}$에 대해 연결된 이웃 노드들, $\left\{ \mathbf{h}_u^{k-1} \forall u \in \mathcal{N}(v)\right\}$의 representation을 모아서 하나의 벡터 $\mathbf{h}_{\mathcal{N}}^{k-1}$로 만든다.

이 aggregation과정은 이전의($k-1$번째) 바깥 루프에서 생성된 representation을 참조한다.

$k=0$일 때는 base case라고 하는데, 이 때의 representation은 노드의 인풋 피쳐를 사용한다.

 

concat

이후 GraphSAGE는 노드의 현재 임베딩 $\mathbf{h}_v^{k-1}$과 aggregate 된 노드의 이웃 피쳐 벡터들 $\mathbf{h}_{\mathcal{N}}^{k-1}$을 이어붙인다.

 

NN

이어붙여진 벡터를 fully connected layer + nonlinear activation $\sigma$의 입력값으로 사용한다.

여기에서의 출력값은 $mathbf{h}_v^k, \forall v \in \mathcal{V}$가 되어 알고리즘의 다음 스텝에서 사용된다.

 

표기상의 편의를 이유로 마지막 단계의 representation을 $\mathbf{z} \equiv \mathbf{h}_v^K \forall v \in \mathcal{V}$로 한다.

이웃 노드들의 representation을 aggregate할 때는 다양한 aggregator 설계를 사용할 수 있다. (3.3장 참조)

 

알고리즘 1을 미니배치 세팅으로 확장하기 위해, 입력된 노드의 집합에 대해서 먼저 depth K까지의 이웃 집합을 먼저 확보한다.

그 후 안쪽 루프를 실행하는데, 모든 노드에 대해서 반복하는 대신 각 depth에서 필요한 만큼 반복한다.

 

(pseudocode 추가하기)

 

Relation to the Weisfeller-Lehman Isomorphism test

GraphSAGE 알고리즘은 개념적으로 그래프 동형 사상(isomorphism)을 테스트하는 알고리즘에 영향을 받았다.

알고리즘 1에서 다음과 같은 세팅을 한다고 하자.

1. $K = | \mathcal{V} |$

2. $\mathbf{W} = \mathbf{I}$

3. aggregator로서 비선형성이 없는 적절한 해시 함수 사용

 

그러면 알고리즘 1은 naive vertex refinement 라고도 불리는 Weisfeiler-Lehman(WL) isomorphism 과 같아진다.

두 개의 서브그래프에 대해 알고리즘 1의 출력값이 되는 임베딩의 집합 $\{ \mathbf{z}_v, \forall v \in \mathcal{V}\}$이 동일하다면, WL테스트는 두 개의 서브그래프가 동형(isomorphic)이라고 결정할 것이다.

이 테스트는 어떤 경우에는 성립하지 않지만, 많은 경우에 대해 성립한다.

 

만약 해시 함수를 훈련 가능한 뉴럴 네트워크 aggregator로 대체한다면, GraphSAGE는 WL 테스트에 대한 연속적인 근사가 된다.

우리는 graphSAGE를 그래프 동형 여부를 테스트하기 위해서가 아니라 유용한 노드 표현을 생성하기 위해 사용하지만,

GraphSAGE와 고전적인 WL 테스트의 연결성은 이 알고리즘에 이론적인 맥락을 부여한다.

 

Neighborhood Definition

이 글에서는 각 배치의 계산 공간(computational footprint)을 고정된 크기로 유지하기 위해, 알고리즘 1에 묘사된 전체 neighborhood 집합을 사용하는 것이 아니라, 고정된 크기의 이웃 집합을 균일하게 샘플링해서 사용한다.

맥락에 따라 달라지는 표현을 사용하면, $\mathcal{N}(v)$를 집합 $u \in \mathcal{V}: (u, v) \in \mathcal{E}$

으로부터 균일하게 추출된 고정된 크기의 집합이라고 할 수 있다.

알고리즘 1의 각 이터레이션 $k$에서는 서로 다른 uniform sample을 추출한다.

이런 샘플링 과정이 없다면 하나의 배치에 소요되는 메모리와 실행 시간은 예측할 수 없고, 최악의 경우에는 $O(|\mathcal{V}|)$까지 될 수 있다.

GraphSAGE의 배치당 필요 공간과 시간 복잡성은 $O(\Pi_{i=1}^K)$로 고정되어 있다. *$S_i, i \in \{1, \ldots, K\}$는 user-specified constant

실질적으로 말하면, 제시된 방법은 $K=2$, $S_1 \cdot S_1 \le 500$을 가지고 높은 성능을 낼 수 있다. (4.4장)

 

3.2 Learning the parameters of GraphSAGE

지도 학습 세팅을 가지고 유용하고 예측 가능한 representation을 학습하기 위해 

• 출력 representation #\mathbf{z}_u , \forall u \in \mathcal{V}# 에 대해 그래프 기반의 손실 함수를 적용하고,
• 가중치 행렬 $\mathbf{W}^k, \forall k \in \{1, \ldots, K\}$ 과 aggregator 함수의 파라미터들을 SGD를 통해 튜닝한다.

그래프 기반의 손실 함수는 근처에 있는 노드들이 유사한 representation을 갖도록 유도하는 반면, 떨어진 노드들이 아주 다른 representation을 갖도록 한다.

 

$J_{\mathcal{G}}(\mathbf{z}_u) = -\log (\sigma(\mathbf{z}_u^T\mathbf{z}_v)) - Q \cdot {\mathbb{E}_{v_n} \sim P_n(v)} \log (\sigma(-\mathbf{z}_u^T\mathbf{z}_{v_n}))$

(1)

 

• $v$: $u$와 고정된 길이의 랜덤 워크에서 함께 등장하는 노드
• $\sigma$: 시그모이드 함수이다
• $P_n$: 네거티브 샘플링 분포
• $Q$: 네거티브 샘플의 갯수

 

기억해야 할 것은 이전의 접근법들과 달리 represenetation $\mathbf{z}_u$가 노드의 local neighborhood에 담긴 피쳐들로부터 생성되었다는 것이다.

이러한 비지도 세팅은 노드 피쳐가 다운스트림 머신 러닝 애플리케이션에 제공되는 상황을 emulate 한다.

노드 임베딩이 특정한 다운스트림 테스트에만 적용되는 상황이라면, 식 1과 같은 unsupervised 손실은 task-specific 목적 함수로 대체될 수 있다. (e.g. cross-entropy loss)

 

3.3. Aggregator Architectures

 

문장, 이미지와 같은 N차원의 lattice에서 진행되는 머신 러닝과 달리, 노드의 이웃들은 본질적으로 순서를 가지고 있지 않다.

따라서, 알고리즘 1의 aggregator 함수는 순서가 없는 벡터의 집합에서 잘 기능해야 한다.

이론적으로, aggregator 함수가 symmetric하고(i.e. 입력값이 permute 되어도 변하지 않고), 동시에 학습이 가능하면서도 높은 표현 능력을 가져야 한다.

aggregation 함수의 대칭적인 성질은 뉴럴 네트워크 모델이 임의의 순서를 가지는 노드의 이웃 피쳐 셋에 대해 학습이 가능하고, 적용될 수 있음을 뜻한다.

 

여기에서는 세 가지 후보 aggregator 함수를 검증한다.

 

Mean aggregator

Mean aggregator는 단순히 벡터들의 element-wise 평균을 구한다.

이 과정은 transductive GCN 프레임워크에서 사용된 convolution propagation rule과 거의 동일하다.

구체적으로, 알고리즘 1의 4번째와 5번째 줄을 다음과 같이 바꿈으로써 GCN 방법의 inductive한 변형을 얻을 수 있다.

 

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

(2)

 

이런 변형된 평균 기반의 aggregator를 convolution이라고 부르는데, 그 이유는 이 과정이 localized spectral convolution의 선형 근사와 같기 때문이다.

이러한 convolutional aggregator가 여기서 제시된 다른 aggregator들과 다른 것은, 알고리즘 1의 5번째 줄에 있는 concat 과정이 없다는 것이다.

즉, convolutional agregator는 노드의 이전 representation인 $\mathbf{h}_v^{k-1}$을 aggregate된 이웃 벡터 $\mathbf{h}_{\mathcal{N}}$와 이어 붙이는 과정이 없다.

이런 concatenation은 GraphSAGE 알고리즘의 레이어 사이(혹은 search depth들 사이)에 일어나는 간단한 형태의 skip connection으로도 볼 수 있는데, 상당한 성능 향상을 이룬다.

 

LSTM  aggregator

Mean aggregator에 비교하면 LSTM은 표현력에 있어서 장점을 가진다.

그러나 LSTM은 입력값을 순차적으로 처리하기 때문에 본질적으로 symmetric하지 하지 않다.

즉, 입력값의 순서가 결과에 영향을 끼친다.

여기에는 노드의 이웃들을 랜덤하게 permute한 결과에 LSTM을 적용함으로써 LSTM이 순서가 없는 집합에서 기능하도록 한다.

 

Pooling aggregator

Pooling aggregator는 symmetric하기도 하고 학습 가능하기도 하다.

pooling 접근법에서, 각 이웃의 벡터는 fully-connected 뉴럴 네트워크에 독립적으로 들어간다.

이러한 변환을 거쳐, elementwise max-pooling 연산이 이웃 집합에 대한 aggregation에 적용된다.

 

$\textit{AGGREGATE}_k^{pool} = \max(\{ \sigma (\mathbf{W}_{pool} \mathbf{h}_{u_i}^k + \mathbf{b}), \forall u_i \in \mathcal{N}(v)\})$

(3)

• $\max$: element-wise max 연산
• $\sigma$: nonlinear activation function

원론적으로, max pooling 이전에 적용되는 함수는 어떤 deep multi-layer perceptron이든 될 수 있다.

그러나 여기에서는 간단한 하나의 레이어를 가지는 구조에 집중하려고 한다.

이런 방식은 최근에 발전된 general point sets에서 인공 신경망 구조를 적용하려는 접근들에 기반한다.

직관적으로, 다중 레이어 퍼셉트론은 이웃 집합의 각 노드 representation에 대해서 feature를 계산하는, 한 뭉치의 함수들이라고 볼 수 있다.

max-pooling 연산을 각각의 계산된 피쳐에 적용함으로써 모델은 효율적으로 이웃 집합의 서로 다른 측면을 계산에 넣을 수 있다.

또한, 원칙적으로 어떤 symmetric한 벡터 함수는 max 연산 대신 사용될 수 있다. (e.g element-wise mean)

development test에서 max-  와 mean- pooling 에서는 특별한 차이가 없었고, 이후 단락부터 나오는 실험에는 max-pooling에 집중했다.