[논문 리뷰] Neural Graph Collaborative Filtering

 

최근 graph를 활용한 추천시스템에  대한 연구가 활발히 진행되고 있는데, 이번에는 "Neural Graph Collaborative Filtering" 논문을 리뷰해보고자 합니다. 본 논문은 2019년 international ACM SIGIR conference에 게시된 논문으로 여기를 통해 확인 가능합니다. 

 

논문의 리뷰는 저의 주관적인 해석과 오역이 있을 수 있습니다. 이에 대해서 댓글 남겨주시면 감사하겠습니다 :) 

---

1. Introduction 

  추천시스템에서 사용되는 Collaborative filtering(CF) 방법은 행동의 유사성(behaviorally similar)을 가진 유저들이 비슷한 아이템을 선호할 것이라고 가정한다. 일반적으로 CF 모델을 학습하기 위해서는 다음과 같은 2가지 핵심이 있는데, 먼저 유저와 아이템을 벡터 형태로 표현하는 임베딩(embedding)이 필요하다. 또한 임베딩을 기반으로 과거의 유저와 아이템 간의 상호작용을 재구성하는 상호작용 모델링(interaction modeling)이 필요하다.

  CF 모델의 예시로  Matrix factorization (MF) 방법은 유저와 아이템을 임베딩 된 벡터로 표현하고, 유저와 아이템의 interaction을 내적을 통해 계산한다.  또한 collaborative deep learning은 아이템의 부가 정보를 deep representations learned을 통해 통합 함으로써 MF의 임베딩 된 함수들을 확장하고, neural collaborative filtering 모델은 내적을 사용했던 MF 방식을 비선형 방식인 neural networks를 사용하여 대체하였다. 마지막으로 translation-based CF 모델은 유클리디언 거리를 interaction 함수로 사용하였다.  

  하지만 위와 같은 방법 들은 CF를 위한 만족스러운 임베딩을 얻기에 부족한데, 그 이유는 유저와 아이템 간의 interaction이 잠재된 collaborative signal을 명시적으로 인코딩하지 않기 때문이다. 그 결과 임베딩이 충분하지 않다면, 최적이 아닌 임베딩의 부족함을 채우기 위해서 interaction function에 의존해야만 한다. 

  현실에 있는 데이터는 100만개 혹은 그 이상의 interaction 규모를 갖기 때문에 유저와 아이템 간의 interactions을 임베딩 함수에 넣는 것은 단순한 일이 아니다. 이에 따라 본 논문에서는 interaction graph의 형태로 collaborative signal을 인코딩하고, 유저와 아이템 간의 interactions을 high-order connectivity를 활용하고자 한다. 

 

  위의 그림은 high-order connectivity의 개념을 묘사한다. 좌측의 그림은 유저와 아이템 사이의 interaction이 이루어진 그래프를 의미하며, 우측은 $u_1$을 기준으로 high-order connectivity가 형성됨을 보여주는 그림이다. 우측 그림에서 보듯이 high-order connectivity는 기준이 되는 노드로부터 path length가 $l$ 크기만큼 노드들이 뻗어 나가는 것을 의미한다. 이를 통해 collaborative signal을 전달할 수 있는 rich semantics를 포함한다. 예를 들어 위의 그림에서 $u_1$ 과 $u_2$는 $i_2$로 연결되어 있어 둘 사이의 행동의 유사성이 있다고 할 수 있다. 이에 따라 $u_1$에게 $u_2$가 구매했던 $i_4$를 추천할 수 있게 된다. 또한 $l$ = 3 관점에서 $u_1$이 $i_5$보다 $i_4$에 더 큰 관심을 가질 가능성이 높은데, 이는 <$i_4$, $u_1$>의 경로가 <$i_5$, $u_1$> 보다 많기 때문이다. 

 

  본 논문에서 기여하는 3가지를 요약하면 다음과 같다.

• model-based CF모델의 임베딩 함수에서 collaborative signal을 명시적으로 이용해야 함을 강조한다.
• graph neural network를 기반으로한 새로운 추천 프레임워크 NGCF를 제안한다. 해당 모델은 임베딩 전파를 수행하면서 high-order connectivities의 형태로 collaborative signal을 명시적으로 인코딩할 수 있다. 
• 100만 개 크기를 가진 3가지 데이터셋에서 경험적인 연구를 실행하여, NGCF가 SOTA모델보다 우수함을 증명하였다. 뿐만 아니라 임베딩 전파를 통한 임베딩의 성능이 개선되었음을 나타내었다. 

 

2.  Methodology

  위 그림은 NGCF의 전체적인 구조를 보여준다. 모델은 크게 유저와 아이템 임베딩 값의 초기값을 전달해주는 (1) embedding layer, high-order connectivity 관계를 임베딩에 주입하여 개선해 나가는 (2) multiple embedding propagation layers가 있다. 마지막으로 서로 다른 propagation layers로부터 나온 유저와 아이템 간의 선호도 점수를 예측하는 (3) prediction layer가 있다. 이후에 기존 모델과 NGCF의 시간 복잡도를 비교한다.

 

  먼저 (1) embedding layer의 경우 user $u$ ( item $i$)가 임베딩 벡터 $e_u \in \mathbb{R}^d$ ($e_d \in \mathbb{R}^d$)로 묘사될 수 있으며, 이때의 $d$는 임베딩 사이즈를 의미한다. 이를 parameter matrix로 표현하면 아래와 같다.

 

  유저와 아이템의 임베딩은 end-to-end 방식으로 최적한다. 또한 유저와 아이템의 interaction을 interaction layer에 직접 연결하는 MF와 NCF랑 달리 NGCF는 유저와 아이템 간의 interaction graph를 활용하여 임베딩 전파의 수행을 통해 값들을 개선한다. 이를 통해 collaborative signal을 명시적으로 주입하여 보다 효과적인 임베딩이 가능하도록 한다. 

 

  다음으로 (2) embedding propagation layers는 collaborative signal을 포착하기 위해 GNN의 message-passing 구조를 만들게 된다. 먼저 embedding propagation layers의 첫번째 전파 과정을 보면 message construction과 message aggregation이 핵심적인 요소가 된다. 

 

  message construction의 경우 유저와 아이템의 쌍에서 아이템으로 부터 유저에게 전달되는 메시지를 의미하며, 아래와 같이 표현될 수 있다. 

 

  $W_1$, $W_2$ $\in$ $\mathbb{R}^{d' \times d}$ 은 학습 가능한 가중치 매트릭스를 의미하며 $d'$ 는 변환 크기이다. 임베딩 된 아이템 $e_i$만 고려하는 전통적인 graph convolution networks와 달리, 여기서는 아이템 임베딩과 유저 임베딩의 element-wise 곱을 더해준다. 이를 통해 비슷한 아이템으로부터 많은 메시지를 전달할 수 있게 된다. message construction에서 $p_ui$는 grpah Laplacian norm 1 / $\sqrt{\left\vert N_u \right\vert \left\vert N_i \right\vert}$ 을 의미하며 $N_u$와 $N_i$는 유저와 아이템의 first-hop 이웃들을 나타낸다. $p_ui$를 통해 과거의 항목들이 사용자의 선호도에 얼마나 반영했는지 나타낸다. 

 

  message aggregation은 유저의 이웃들로 부터 생성되는 message construction을 aggregation 한다. aggregation function은 아래와 같이 표현 가능하다. 

  $e_u^\left( 1 \right)$ 는 첫번째 embedding propagation layer가 통과된 후 얻어진 user $u$의 값을 의미한다. 활성 함수 LeakyReLU를 통해 positive와 약간의 negative 신호의 메시지를 받는다. self-connection인 $m_u \leftarrow u$를 통해 유저가 가지고 있었던 원래 features 정보를 유지한다. 아이템에 대한 임베딩 값 역시 위와 같은 방법으로 진행하면 된다. 

  

이후 여러 embedding propagation layer 쌓아서 high-order connectivity의 정보를 탐색할 수있다.  

 

  마지막으로 (3) model prediction은 embedding propagation layers를 통해 유저와 아이템의 임베딩 값을 얻게 되면 다음과 같이 concat을 사용하여 최종 유저 임베딩과 아이템 임베딩을 얻는다. 

 

  최종 유저와 아이템의 임베딩 값을 내적을 통해 목표 아이템에 대한 유저의 선호도를 추정할 수 있다. 

 

  모델의 optimization 과정은 파라미터를 학습하기 위해 추천시스템에서 강력하게 사용 중인 pairwise BPR loss를 사용한다. 해당 손실 함수는 유저와 아이템의 interactions에서 관측된 interactions에 대해선 유저의 더 높은 선호도를 반영한다. 

 

  여기서 $ O = \{(u, i, j)|(u, i) \in \mathbf{R}^+, (u,i) \in \mathbf{R}^-\}$ 는 positive와 negative를 포함하는 pairwise training data를 의미하며, $\mathbf{R}^+$는 관측된 interactions을 의미하고 $\mathbf{R}^-$는 관측되지 않은 interactions을 의미한다. 또한 $\sigma(\cdot)$는 sigmoid function, $\Theta = \{E, \{W_1^{\left( l \right)}, W_2^{\left( l \right)}\}_{l=1}^L\}$ 는 모든 학습 가능한 파라미터를 의미한다. $\lambda$는 $L_2$ regulariztion을 통해 오버피팅을 예방한다. 

  NGCF모델에서는 message dropout과 node dropout이 학습과정에서 사용된다. 먼저 전자의 message dropout은 유저와 아이템의 연결이 single connections일 경우 출력되는 메세지를 랜덤 하게 dropout 하여 모델이 robustness 할 수 있도록 만든다. 반면에 후자의 node dropout은 특정 유저와 아이템의 영향력이 많은 노드들에 대해서, 해당 노드들을 삭제함으로써 영향력을 감소시킨다. 

 

3. Conclusion

  본 논문의 저자는 해당 연구를 통해 유저와 아이템간의아이템 간의 interaction graph를 통해 high-order connectivities를 형성하는 NGCF모델을 제안하였다. embedding propagation layer를 새롭게 제안함으로써, 유저와 아이템 간의 collaborative signal을 보다 명확하게 임베딩 할 수 있음을 증명하였다. 이에 대하여 3가지의 목표로 실험을 진행했는데, (1) NGCF모델이 SOTA CF 모델과 비교하였을 때 얼마나 더 좋은 성능을 보이는지 (2) hyper-parameter의 값들이 NGCF에 어떠한 영향을 주는지 (3) high-order connectivity의 장점이 어떻게 나타나는지 실험을 통해 확인하였다. 실험 결과는 생략하도록 하겠다.