[CS224W] GNN for RecSys (3) - NGCF (Neural Graph Collaborative Filtering)

Neural Graph Collaborative Filtering (NGCF)

Overview

기존의 collaborative filtering (CF)은 shallow embedding을 이용하기 때문에

- 그래프 구조를 반영하지 못함

- 모델 학습이 high-order graph structure를 포착하지 않음

Figure from NGCF paper

위 그림을 보자.

왼쪽 그림은 3명의 user와 5개의 item의 상호작용이 있는 이분그래프이다.

$u_1$이 target user라 하자. 

기존 CF은 $u_1$와 직접 연결된 $i_1, i_2, i_3$의 item만 포착한다.

그런데 $i_2$는 $u_2$와도 연결되어 있고, $i_3$은 $u_3$와도 연결되어있다.

그러나 shallow embedding은 이러한 관계는 포착하지 못한다.

실제 user-item 상호작용은 million 이상의 단위이기 때문에 모든 상호작용을 임베딩하는것은 쉽지 않다.

따라서 high-order connectivity를 찾는 것이 보다 더 자연스럽다.

 

NGCF의 큰 그림은 다음과 같다.

• (shallow) Embedding
• Embedding Propagation
• Model Prediction
• Optimization

Key idea of NGCF (CS224W)

 

Figure from NGCF paper

 

Embedding Layer

user와 item을 각각 $u, i$라고 하고 임베딩 차원은 $d$라 하자. 

그러면 임베딩 벡터를 $\mathbf{e}_u \in \mathbb{R}^{d}$, $\mathbf{e}_i \in \mathbb{R}^{d}$라고 하자.

임베딩을 학습할 parameter matrix를 $E$라 하면

Embedding Matrix (NGCF paper)

 

여기까지는 이전에 설명한 shallow embedding model과 동일하다.

 

Embedding Propagation

message-passing인 GNN을 이용하여 CF가 user-item의 embedidng을 업데이트(refine)할 것이다.

이때 그래프 구조를 반영하여 임베딩을 재구성할것이다.

 

먼저, $i \to u$ message는 GCN과 유사하게 구성한다.

Message Construction (NGCF paper)

 

$\mathbf{W}_1$, $\mathbf{W}_2$는 trainable weight matrix이고 $\odot$는 element-wise product이다.

이는 $\mathbf{e}_i$와 $\mathbf{e}_u$의 affinity에 의존하기 때문에 비슷한 item끼리 더 많은 메시지를 패싱한다.

 

message aggregation은 다음과 같이 정의한다.

Message Aggregation (NGCF paper)

 

$\mathbf{m}_{u \leftarrow u}$는 self-connection이다. 즉 $\mathbf{m}_{u \leftarrow u} = \mathbf{W}_1 \mathbf{e}_u$ 이다.

self-connection은 original feature를 보존하는 효과를 가진다.

 

High-order Propagation은 다음과 같이 정의된다.

High-order propagation (NGCF paper)

이때 $u \leftarrow u$와 $u \leftarrow i$의 message passing은 다음과 같다

Message Passing at $l$-th step

Three-order embedding propagation (NGCF paper)

 

이제 이 propagation rule을 matrix로 나타내자.

Matrix form of propagation (NGCF paper)

이때 $\mathcal{L}$은 user-item graph의 Laplacian matrix이고 다음과 같다.

Laplacian matrix (NGCF paper)

$\mathbf{R}$은 user-item interaction matrix이다. (rating matrix)

$u$와 $i$가 interaction이 있으면 $\mathbf{R}_{ui}=1$이고, interaction이 없으면 $\mathbf{R}_{ui}=0$이다.

 

Model Prediction

최종적으로 $L$개의 layer를 통과하여 얻은 임베딩을 구했다.

그러면 각 user는 $L$개의 임베딩을 얻는다. ($\{ \mathbf{e}_{u}^{(1)}, \dots, \mathbf{e}_{u}^{(L)} \}$)

item의 경우도 마찬가지이다.

final user(또는 item)의 임베딩을 $\mathbf{e}_u^*, \mathbf{e}_i^*$라 하자.

final embedding은 각 layer에서 얻은 임베딩을 concatenate한 벡터이다.

Final embedidng vector of user/item (NGCF paper)

 

이렇게 concatenation을 하면 초기(initial) 임베딩을 풍부하게(enrich) 할뿐만 아니라 $L$을 이용하여 propagation의 범위를 조절할 수 있다.

이 방법 말고도 다른 aggregation을 사용할 수 있다. (weighted average, max pooling, LSTM)

이렇게 구한 final embedidng의 내적을 이용하여 user의 item에 대한 선호(preference)를 추정할 수 있다.

Prediction

Optimization

NGCF는 pairwise BPR loss를 이용한다.

$\sigma(\cdot)$는 sigmoid, $\mathbf{\Theta}$는 전체 모델의 파라미터, $\mathcal{R}^+$와 $\mathcal{R}^-$는 observed/unobserved interaction, 그리고 $\mathcal{O}$는 pairwise training data라 하자.

그러면 

$\mathbf{\Theta} = \{ \mathbf{E},\ \{ \mathbf{W}_1^{(l)},\ \mathbf{W}_2^{(l)} \}_{l=1}^{L} \}$

$\mathcal{O} = \{ (u,i,j) \mid (u,i) \in \mathcal{R}^+,\ (u,j) \in \mathcal{R}^- \}$

Loss에 L2-regularization을 적용하면 다음과 같다.

pairwise BPR loss (NGCF paper)