[Paper Review] (2019, ACM) Neural Graph Collaborative Filtering

작성자 : 이혜린

Neural Graph Collaborative Filtering (2019, ACM)

---

1. Introduction

Recommender system은 크게 Content-based Filtering과 Collaborative Filtering으로 나눌 수 있습니다. 본 강의는 Collaborative Filtering Model을 중심으로 학습할 예정입니다.

Collaborative Filtering Model의 일종인 Latent Factor Mdoel의 여러 방법들 중 하나로 Matrix Factorization이 존재합니다. Matrix Factorization은 latent factor간의 내적, 즉 선형결합을 통해 Collaborative Signal(유저 - 아이템 상호작용)을 나타내기 때문에 복잡한 구조의 Signal을 알아내기 어렵습니다. 또한 새로운 유저가 등장하면 저차원 공간에 이를 표현하기 어렵다는 단점이 존재합니다. 그래서 등장한 모델이 바로 Neural Collaborative Filtering 모델입니다.

Neural Collaborative Filtering Model은 Deep Neural Network를 사용하여 유저-아이템간 상호작용을 학습합니다. Neural Network를 사용하기 때문에 비선형적인 Collaborative Signal을 표현할 수 있다는 것이 Matrix Factorization과의 차이점입니다. 그러나 몇몇 연구자들은 Neural Collaborative Filtering(이하 NCF)조차도 유저-아이템간 상호작용을 나타내기에 아직 부족하다며 새로운 모델을 제안합니다. 이 모델은 바로 Neural Graph Collaborative Filtering(이하 NGCF) 모델입니다.

일반적으로 CF 모델은 유저와 아이템을 벡터로 변환하는 Embedding과정과, 이를 기반으로 사용자의 historical interaction(구매 혹은 클릭)을 예측하는 Interaction Modeling로 구성되어 있습니다.
기존의 CF 모델들은 유저-아이템간 상호작용을 명시적으로 사용하지 않았습니다. 즉, 모두 Embedding에 유저-아이템간 상호작용을 반영하지 않았습니다. 단지 유저와 아이템 각각의 descriptive feature만을 embedding에 사용했습니다.

이러한 기존 CF 모델의 한계점을 극복하기 위해 NGCF 모델에서는 High-order Connectivity라는 새로운 특성을 모델에 반영하고자 합니다.

• Notation
  • $u_{i}$ : $i$번째 유저
  • $i_{j}$ : $j$번째 아이템
• 기존 NCF Model
  • $u_{1}$이 $i_{1}$을 선택 → 관계 종료
  • 1차적인 관계
• NGCF Model
  • 유저와 아이템 간의 여러 관계를 그래프적으로 표현
  • 여러 관계 = High-order → Sequential한 관계라고도 표현

• NGCF Model의 High-order connectivity
  • $u_{1} ← i_{2} ← u_{2}$
    : $u_{1}$과 $u_{2}$ 간 유사성 존재 (두 사용자 모두 i_{2}와 상호작용을 했기 때문)
  • $u_{1} ← i_{2} ← u_{2} ← i_{4}$
    : $u_{1}$은 $i_{4}$를 사용할 가능성이 있음 ($u_{1}$은 $u_{2}$와 유사)
  • $u_{1}$은 $i_{5}$보다 $i_{4}$를 선호할 것
    : $u_{2}$ 뿐만 아니라, $u_{1}$와 유사한 또 다른 유저 $u_{3}$도 $i_{4}$를 사용하기 때문

이처럼 High-order Connectivity에서 Collaborative Signal를 표현하기 위해 GNN의 아이디어를 embedding propagation layer에서 실현합니다.

2. Methodology

• 모델 구조
  기존 CF 모델들과 다르게 NGCF는 Embedding Propagation Layer를 가집니다.

• GNN
  GNN은 Node(ex. 사용자)와 Edge(ex.관계) 등으로 표현되는 graph형태의 데이터를 모델링하기 위한 네트워크입니다. 그래프 데이터는 기존 정형, 비정형 데이터와 다르게 유클리드 공간에 벡터화할 수 없다는 성질이 있습니다. 따라서 이를 기존 ML 알고리즘에 넣기 위해 추가적인 Network를 활용하여 벡터 형태의 값을 도출하는 데, 이 때 사용하는 네트워크를 Aggregation Function이라고 합니다. 본 논문에서는 Embedding Propagation Layer가 그와 같은 역할을 한다고 볼 수 있습니다.

1) Embedding Layer

처음 Input data로는 유저와 아이템간 상호작용이 반영되지 않은 유저, 아이템 각각의 Embedding이 사용됩니다.

• $E = [e_{u_{1}}, ..., e_{u_{N}}, e_{i_{1}}, e_{i_{M}}]$ : 임베딩 matrix
• $e_{u_{N}}$ : N번째 사용자의 임베딩 벡터
  

2) Embedding Propagation Layers

Input 값으로 앞서 Embedding layer의 output인 유저, 아이템의 임베딩 벡터가 사용됩니다.
논문에서는 First-order propagation → High-order propagation 순으로 설명이 진행되고 있으므로, 동일한 순서로 리뷰를 진행하도록 하겠습니다.

• First-order propagation : 첫번째 Embedding Propagation Layer에서 발생하는 전파
• High-order propagation : 두번째 ~ $l$번째 Embedding Propagation Layer에서 발생하는 전파

[First-order propagation]

First-order propagation을 구성하는 두 가지 주요 작용은 Message Construction과 Message Aggregation입니다.

a. Message Construction
Message Construction은 propagation layer에서 전파될 메시지를 생성해내는 과정을 의미합니다. 그래프 데이터에서 Connected user-item pair $(u,i)$를 도출해내고, 두 노드의 정보를 이용하여 전파될 정보를 의미하는 Message Embedding을 도출합니다.

• function $f$의 input
  • $e_{i}$ : item의 embedding
  • $e_{u}$ : user의 embedding
  • $p_{ui}$ : decay factor (매 전파마다 전파되는 메시지가 감가상각 되는 것을 반영해주는 coefficient)

또한 Message Construction의 function $f$는 다음과 같은 구조를 가집니다.
기존 GCN(GNN의 일종, Graph Convolutional Network)과 다르게 $e_{i}$ (자기자신) 에 대해서만 고려하지 않고, 추가적으로 user-item interatcion을 메시지에 인코딩 합니다.
이 interaction 때문에 메시지는 두 임베딩 사이의 관련성 (affinity)에 의존하고, 유사한 아이템으로부터 더 많은 메시지를 전달할 수 있게 됩니다. (결과적으로 성능 향상이 이루어집니다.)

• $|N_{u}|$ : user $u$의 이웃들의 수
• $|N_{i}|$ : item $i$의 이웃들의 수
• $W$ : trainable matrix
  

b. Message Aggregation
Message Aggregation은 $u$의 이웃노드로부터 전파된 메시지들을 모아(aggregate) $u$의 임베딩을 refine하는 과정을 의미합니다. 이 때 Aggregation function으로 $LeakyReLU$를 활용하며, 이웃노드로부터의 메시지 뿐만 아니라 본래 자신에 대한 정보인 $m_{u ← u}$까지 input으로 넣습니다. 이를 통해 $e_{u}^{(1)}$ ($u$에 대한 첫 임베딩 레이어의 벡터 표현)을 도출합니다.

[High-order propagation]
first-order connectivity에서 변환된 벡터 표현을 가지고, high-order connectivity 정보를 탐색하기 위해 더 많은 embedding propagation layers를 쌓습니다(stacking).
이 과정을 통해 사용자와 아이템 사이의 relevance score를 예측할 수 있으며, $l$ 개의 embedding propagation layer를 쌓으면, 유저 노드는 $l$-hop 이웃으로부터 전파된 메시지를 받을 수 있습니다. 이 때 사용되는 함수 식은 다음과 같습니다.

• $e_{u}^{l}$ : $u$에 대한 $l$번째 임베딩 레이어의 벡터 표현
• $e_{u}^{l} = LeakyReLU(m_{u←u}^{(l)} + \sum_{i \in N_{u}}m_{u←u}^{(l)})$
• $m_{u←i}^{(l)} = \rho_{ui}\big(W_{1}^{(l)}e_{u}^{(l-1)} + W_{2}^{(l)}(e_{i}^{(l-1)}\odot e_{u}^{(l-1)})\big)$
• $m_{u←u}^{(l)} = W_{1}^{(l)}e_{u}^{(l-1)}$

다음 그림의 빨간선이 $u_{1}$의 임베딩 벡터를 찾아나가는 과정이므로 참고하시면 될 것 같습니다.

3) Model Prediction

$l$개의 embedding propagation layer를 거친 후 나온 output은 $\{e_{u}^{(1)}, ..., e_{i}^{(l)} \}$ 입니다.
각각의 임베딩들을 concatenate함으로써 최종 유저에 대한 임베딩을 구성합니다.

• $e_{u}^{*} = e_{u}^{(0)}\vert\vert ... \vert\vert e_{u}^{(L)}$
• $e_{i}^{*} = e_{i}^{(0)}\vert\vert ... \vert\vert e_{i}^{(L)}$

concatenate를 사용했기 때문에 파라미터가 없어 연산이 단순하다는 장점이 있으며, 최신 GNN 연구를 통해 layer-aggregation 방식으로 꽤 효과적임을 검증받았습니다.
결론적으로, Prediction Layer의 최종 output은 다음과 같습니다.

• $\hat{y}_{NGCF}(u, i) = (e_{u}^{*})^{T} e_{i}^{*}$
  

4) Etc...

[Loss Function]

• Pairwise BPR Loss
  : 유저의 선호를 더 잘 반영하는 observed interaction에 높은 점수 부여 (vs unobserseved interaction)
• Optimizer : Adam

[Message and Node Dropout]

a. Message Dropout

• High-order connectivity에서 전파되는 메시지를 drop
• 최종 $l$번째 전파 레이어에서는 부분적인 메시지들만이 표현 refine과정에 영향을 줌

b. Node Dropout

• 특정 노드를 임의로 차단해서, 해당 노드에서 나가는 메시지를 모두 차단하는 방법

3. Evaluation / Conclusion

Evaluation

3개의 벤치마크 데이터셋에 대해 실험을 한 후, 3개의 Research Question에 답하는 것을 중점으로 논문은 진행되고 있습니다.

Recall과 ndcg를 metric으로 사용했습니다.

RQ1. SOTA CF 방법론들에 비해 NGCF는 어떤 성능을 내는가?
NGCF는 모든 데이터셋, 평가지표에서 가장 우수한 성능을 보였습니다. 또한 high-connectivity를 모델 자체가 아닌, training data를 증가시키는 것에만 사용한 HOP-Rec 모델에 비해 NGCF-3의 성능이 좋았다는 사실을 통해, 임베딩 함수에서 명시적으로 Collaborative Signal을 인코딩하는 것이 성능을 개선했음을 알 수 있습니다.

RQ2. 하이퍼파라미터들은 NGCF의 성능에 어떤 영향을 주는가?

a. 임베딩 전파레이어의 개수
전반적으로 전파 레이어에서 레이어 개수를 높일수록 성능이 개선되었으나, NGCF-4의 경우 일부 데이터에서 과적합되었습니다.
이를 통해, 3개의 전파레이어를 사용하는 것이 가장 적합하다는 것을 알 수 있었습니다.
또한 레이어의 개수와 상관없이 NGCF는 다른 모델에 비해 더 성능이 좋았는데, 이를 통해 high-order connectivity를 명시적으로 모델링하는 것이 추천 task에서 성능 향상에 크게 기여한다는 것을 알 수 있습니다.

b. 하이퍼 파라미터
(생략)

RQ3. 벡터 표현이 어떻게 high-order connectivity에서 향상이 이루어지는가?

임베딩 전파가 임베딩 공간에서 표현학습을 어떻게 증진시키는지 TSNE를 이용해 확인했습니다. 유저와 관련된 임의의 아이템을 의미하는 ★을 6개 추출하였습니다. 왼쪽그림은 MF를, 오른쪽 그림은 NGCF-3의 경우를 의미하는데, NGCF-3을 이용했을 때 같은 색의 ★과 ●이 거리상으로도 가까이 위치하고, 클러스터를 잘 형성하고 있었습니다. 이를 통해 high-order connectivity를 통해 벡터 표현이 항상되었음을 확인했습니다.

Conclusion

결론에서는 NGCF에 대해 요약 설명하고, 후속 연구를 제시하며 논문이 마무리 됩니다.

참고 문헌

• https://towardsdatascience.com/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc
• https://velog.io/@ysn003/%EB%85%BC%EB%AC%B8-Neural-Graph-Collaborative-Filtering#running-example
• https://joyae.github.io/2020-09-02-nDCG/
• https://towardsdatascience.com/collaborative-filtering-and-embeddings-part-1-63b00b9739ce
• https://pongdangstory.tistory.com/511