![[논문] Neural Graph Collaborative Filtering](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fk4HME%2FbtrGQEJpxr0%2FTB9WwzFWnOwL11ledv2Gr1%2Fimg.png)
영어도 영 시원찮고~ 그러다보니 공부도 잘 안되는 것 같아, 시간이 더 걸리더라도 새로운 방법으로 공부해보기로 했다. 아예 번역을 하듯 공부를 하는 것이다. 적당히 요약하면서 불필요한 내용은 좀 쳐내고, 암튼 그렇게 해서 논문에서 놓치는 내용 없이 공부해보도록 하자.
다 쓰고 나서 보니 할 짓 못되는 것 같다. 쓸데없이 오래걸려...
내 TODO
- time complexity 파트 다시 읽어보기
Abstract
- 유저와 아이템의 벡터 표현(임베딩)은 현대 추천 시스템에서 매우 중요하다.
- 고전적 MF부터 현대 딥러닝을 활용한 방법론까지, 대부분의 임베딩은 유저/아이템을 설명하는 pre-existing features(ID, attributes, etc...)로 매핑된다.
- 이러한 방법들의 inherent drawback은 유저와 아이템 사이의 인터랙션(collaborative signal)이 임베딩 과정에서 인코딩되지 않는다는 점이고, 그 결과 임베딩은 CF의 효과를 capture하기 힘들 것이다.In this work,
- 이분 그래프 구조의 유저-아이템 인터랙션을 임베딩 프로세스에 통합할 것을 제안
- 임베딩을 전파하여 유저-아이템 그래프 구조를 활용하는 추천시스템 프레임워크 Neural Graph Collaborative Filtering(NGCF)을 제안
- 이는 그래프 구조에서 high-order connectivity가 발생하도록 하며, 명시적으로 collaborative signal을 임베딩 과정이 적용
- 3개의 벤치마크 데이터셋으로 평가, SOTA 달성
- 임베딩 전파(Embedding Propagation)의 중요성도 검증
- 코드는 여기에
Introduction
- 개인화된 추천 시스템은 어디에나 있으며, 수많은 온라인 서비스에 존재한다.
- (이커머스의 경우) 추천 시스템의 핵심은 구매 혹은 클릭과 같은 historical interaction을 활용해 유저가 어떤 아이템을 채택할 가능성에 대해 예측하는 것이다.
- 협엽 필터링(CF)는 같은 행동의 유저가 같은 선호/기호를 가질 것이라 가정하여 예측한다.
- 이를 재구현하기 위해 일반적인 방법론은, 유저와 아이템을 parameterize하여 historical interaction을 재구성하고, 파라미터를 기반으로 유저의 선호를 예측하는 것이다.
- 일반적으로 CF모델에는 두 핵심 요소가 있는데,
- 유저/아이템을 벡터 표현으로 변환하는 Embedding
- 임베딩을 기반으로 historical interaction을 재구성하는 interaction modeling
- ex: MF의 경우 유저/아이템을 벡터로 임베딩하고 상호작용을 두 벡터의 내적으로 모델링
- ex: collaborative deep learning은 MF의 임베딩 함수를 확장
- ex: neural collaborative filtering 모델은 MF의 내적을 비선형적 신경망으로 바꿈
- ex: translation-based CF 모델은 유클리디언 거리를 상호작용 함수로 사용
- 그러나 이런 방법들이 중요한 collaborative signal을 명시적으로 인코딩하지 않으므로 CF에 쓰기에 만족스런 임베딩 결과를 내기엔 충분치 않다.
- 좀 더 구체적으로, 기존 방법들은 인터랙션 정보를 모델 학습의 목적 함수 정의에만 사용하지 임베딩 함수를 만드는 데에는 쓰지 않고, ID나 기타 attributes 등 descriptive feature만 임베딩에 사용한다는 것이다.
- 결과적으로 CF를 capture하기에 불충분한 임베딩을 사용하면 해당 추천 시스템은 그 임베딩을 보완하기 위해 interaction function에 의존해야 한다.
- interaction function을 임베딩 함수에 통합하는 것이 직관적이지만, 쉬운 일은 아니다.(non-trivial)
- 특히나 실제 서비스에서는 interaction이 너무 많고 다양해 원하는 특정 collaborative signal을 추출해내기가 어렵다.
- 저자들은 interaction graph 구조에서 collaborative singal을 인코딩하기에 자연스러운 방식인 high-order connectivity를 활용해 이러한 문제를 해결하고자 한다.
Running Example
$u_1$이 추천 아이템을 제공하고자 하는 유저의 노드라고 할 때, 왼쪽 그림의 이분 그래프 구조에서 노드 $u_1$에 대한 high-order connectivity를 오른쪽 그림과 같이 표현할 수 있다.
high-order connectivity는 user/item에 무관하게 특정 node에서 target node로까지 도달하는 데 거치는 edge의 개수 $l(l>1)$로 표기한다.
이러한 high-order connectivity에는 collaborative signal을 포함한 rich semantics가 포함된다.
예를 들어, 경로 $u_1 ← i_2 ← u_2$는 $u_1$과 $u_2$가 둘 다 $i_2$와 상호작용을 했으므로 둘의 행동적 유사성을 표현한다.
더 긴 경로 $u_1 ← i_2 ← u_2 ← i_4$는 $u_1$이 $i_4$를 후에 채택할 가능성이 높다고 제안한다.
또, $l=3$인 view에서는 $i_4$가 $i_5$보다 $u_1$으로 도달하는 경로가 더 많으므로, $u_1$이 더 선호할 만한 아이템이라고 결론내릴 수 있다.
Present Work
저자들은 임베딩 함수에서 high-order connectivity를 모델링할 것을 제안한다.
상호작용 그래프를 트리 구조(Figure1처럼)로 확장하는 것은 구현하기에 복잡하므로, 그래프 구조에서 재귀적으로 임베딩을 전파할 수 있는 신경망을 설계했다.
이는 최근에 개발된, 임베딩 공간에서 정보의 흐름을 구성하는 GNN으로부터 영감을 받았다.
구체적으로, interacted item/user의 임베딩을 통합하여 user/item의 임베딩을 refine하는 임베딩 전파 레이어를 고안했다.
여러 임베딩 전파 레이어를 쌓음으로써, 임베딩으로 하여금 high-order connectivity 사이의 collaborative signal을 capture하도록 강제할 수 있었다.
Figure 1을 예시로 들자면, 두 레이어를 쌓았을 때 $u_1 ← i_2 ← u_2$의 유사성을 capture할 수 있고, 3개의 레이어를 쌓으면 $u_1 ← i_2 ← u_2 ← i_4$의 ($u_1$이 $i_4$를 선호할 것이라는)잠재적 추천을 capture할 수 있다.
(trainable weights로 예측되는) 정보 흐름의 strength는 $i_4$와 $i_5$ 사이의 추천 우선순위를 결정한다.
NGCF의 타당성과 효과성을 입증하기 위해 3개의 벤치마크로 실험을 진행했다.
마지막으로, HOP-Rec이라는 최신의 방법론에서도 high-order connectivity를 고려했지만, 훈련 데이터를 enrich하는 데만 사용했다는 것은 언급할 만한 가치가 있다. 구체적으로, HOP-Rec의 모델은 high-order connetivity를 통해 augmented된 loss를 최적화하도록 훈련하지만 그 모델 자체는 MF로 남아있다.
HOP-Rec과 다르게, 저자들은 high-order connectivity를 모델에 통합해 HOP-Rec보다 더 나은 CF용 임베딩을 제공할 수 있도록 하는 새로운 기술에 기여하였다.
요약하자면,
- model-based CF에서 collaborative signal을 명시적으로 이용하는 것의 중요성을 강조한다.
- 임베딩 전파를 통해 high-order connectivity 형태의 collaborative signal을 명시적으로 인코딩하는 프레임워크 - NGCF를 제안한다.
- 실험 분석을 통해 NGCF가 SOTA 성능을 내며, 임베딩 전파를 통한 임베딩 성능 향상에 있어 NGCF가 효과적임을 보인다.
Methodology
전체 프레임워크에는 3개의 컴포넌트가 있는데,
1. user/item 임베딩의 초기 임베딩을 제공하는 임베딩 레이어
2. high-order connectivity를 inject하여 임베딩을 refine하는 여러 임베딩 전파 레이어
3. 서로 다른 전파 레이어에서 refine된 임베딩을 모아 user-item간의 score를 예측하는 레이어
마지막으로 NGCF와 기존의 방법론들의 time complexity를 비교했다.
Embedding Layer
주류 추천 모델과 마찬가지로, 유저 $u$에 대한 임베딩 백터를 $e_u\in\mathbb R^d$라 하자(아이템 $i$에 대해서도 똑같다).
이는 parameter matrix를 임베딩 look-up table로 나타내는 것과 같다.
$$
E=[e_{u_1},...,e_{u_N},e_{i_1},...,e_{i_M}] \cdots\cdots (1)
$$
이 임베딩 테이블은 end-to-end로 최적화될 초기 임베딩을 제공한다.
MF와 NCF같은 전통적 추천 모델에서는 이런 ID 임베딩이 상호작용해 최종 예측 스코어를 처리하는 레이어에 바로 입력되었다.
반면 본문의 NGCF에서는 user-item graph 구조에서 임베딩 전파 과정을 통해 임베딩을 먼저 refine한다.
이는 임베딩에 명시적으로 collaborative signal을 주입해 임베딩을 refine하므로 추천 시스템에서 더 효율적인 임베딩 결과를 이끌어낸다.
Embedding Propagation Layers
다음으로 graph 구조에서 CF signal을 capture하고 user/item의 임베딩을 refine하기 위해 GNN의 message-passing 구조를 만든다.
First-order Propagation
직관적으로 이미 상호작용된 item은 user에 선호 성향에 대한 직접적인 단서를 제공한다. 마찬가지로 어떤 item에 상호작용을 한 user는 그 item의 feature에 대한 단서를 제공하며, 두 item의 collaborative similarity를 계산하는 데 쓰인다.
이를 기반으로 연결된 노드 사이에 임베딩 전파를 message construction과 message aggregation이라는 두 과정으로 진행한다.
Message Construction 연결된 user-item pair $(u, i)$에 대해, $i→u$ message를 다음과 같이 정의한다.
$$
m_{u←i}=f(e_i, e_u, p_{ui}) \cdots\cdots (2)
$$
이때 $m_{u←i}$는 message embedding(전파될 정보)이고, $f(\cdot)$은 임베딩 $e_i, e_u$와 계수 $p_{ui}$를 입력으로 받아 message를 인코딩하는 함수이다.
$p_{ui}$는 edge $(u,i)$에 대한 decay factor이다.
본 논문에서는 $f$를 다음과 같의 정의한다.
$$
m_{u←i}={1\over\sqrt{|\mathcal N_i||\mathcal N_u|}}(W_1e_i+W_2(e_i\odot e_u)) \cdots\cdots (3)
$$
이때 $W_1, W_2\in\mathbb R^{d'\times d}$는 전파 과정에서 유용한 정보를 추출하는 trainable matrix이고, $d'$는 변환 크기이다.
$e_i$에 대해서만 고려하는 기존 GCN과 다르게, 여기서는 추가적으로 user-item interaction인 $e_i\odot e_u$를 메시지에 인코딩한다. $\odot$은 element-wise production이다.
이러한 과정은 메시지가 두 임베딩 사이의 affinity(아마 관련도 정도로 번역?)에 의존하게 만들고, 유사한 아이템으로부터 더 많은 메시지를 전달하게 한다. 이는 모델의 표현 능력만 증가시킬 뿐만 아니라 추천 시스템의 성능도 향상시킨다.
Message Aggregation 이 단계에서는 $u$의 이웃노드로부터 전파된 메시지들을 모아(aggregate) $u$의 표현(임베딩)을 refine하는 과정을 진행한다.
구체적으로, aggregation function을 다음과 같의 정의한다.
$$
e_i^{(1)}=\text{LeakyReLU}(m_{u←u}+\sum_{i\in\mathcal N_u}m_{u←i}) \cdots\cdots (4)
$$
이때 $e_i^{(1)}$는 $u$에 대한 첫 임베딩 레이어의 벡터 표현이다. 활성화 함수 LeakyReLU는 양의 신호와 작은 음의 신호를 인코딩하도록 한다.
이웃 노드들 $\mathcal N_u$에서 전파된 메시지 외에도 self-connection $m_{u←u}=W_1e_u$을 고려하는데, 이는 전파 과정에서 기존 feature 정보를 유지한다.(이웃 정보만 aggregate하면 기존 정보가 손실되므로)
마찬가지로 item에 대한 표현 $e_i^{(1)}$도 동일하게 구해진다.
요약해서, 임베딩 전파 레이어를 활용함으로써 얻는 장점은 user/item의 표현을 관련짓는 first-order connectivity 정보를 명시적으로 활용하는 데 있다.
High-order Propagation
first-order connectivity에서 augment된 벡터 표현을 가지고, high-order connectivity 정보를 탐색하기 위해 더 많은 임베딩 전파 레이어를 쌓는다.
그러한 high-order connectivity는 user와 item 사이의 relevance score를 예측하기 위해 collaborative signal을 인코딩하는 데 있어 중요하다.
$l$개의 임베딩 전파 레이어를 쌓으면, 유저 노드는 $l$-hop 이웃으로부터 전파된 메시지를 받을 수 있게 된다.
Figure 2에서처럼, $l$-th 단계에서 유저 $u$의 표현은 다음과 같이 재귀적으로 형성된다.
$$
e_u^{(l)}=\text{LeakyReLU}(m_{u←u}^{(l)}+\sum_{i\in\mathcal N_u}m_{u←i}^{(l)}) \cdots\cdots (5)
$$
전파되는 메시지는 다음과 같이 정의된다.
$$
\begin{matrix}
m_{u←i}^{(l)}=p_{ui}(W_1^{(l)}e_i^{(l-1)}+W_2^{(l)}(e_i^{(l-1)}\odot e_u^{(l-1)}))\\m_{u←u}^{(l)}=W_1e_u^{(l-1)}
\end{matrix}\cdots(6)
$$
이때 $W_1^{(l)}, W_2^{(l)}\in\mathbb R^{d_l\times d_{l-1}}$는 trainable transformation matrix이고, $d_l$은 변환 크기이다.
$e_i^{(l-1)}$은 이전 message-passing 단계에서 생성된, $(l-1)$-hop 이웃들의 메시지들을 기억하고 있는 item의 벡터 표현이다. 이는 레이어 $l$의 유저 $u$의 벡터 표현에 영향을 준다.
item에 대해서도 마찬가지로 벡터 표현을 얻을 수 있다.
Figure 3에서처럼 $u_1 ← i_2 ← u_2 ← i_4$와 같은 collaborative signal이 임베딩 전파 과정에서 capture될 수 있다.
그런 식으로 여러 임베딩 전파 레이어를 쌓는 것은 collaborative signal을 vector representation learning process에 주입할 수 있다.
Propagation Rule in Matrix Form. 임베딩 전파에 대한 전체적인 그림을 보여주고 batch 전략에 대한 구현을 하기 위해서 layer-wise한 전파 규칙의 matrix form을 제시한다. (식 (5), (6)과 동일하다.)
$$
E^{(l)}=\text{LeakyReLU}((\mathcal L+I)E^{(l-1)}W_1^{(l)}+\mathcal LE^{(l-1)}\odot E^{(l-1)}W_2^{(l)}) \cdots\cdots (7)
$$
이때 $E^{(l)}\in\mathbb R^{(N+M)\times d_l}$은 $l$ step의 임베딩 전파 이후 얻어진 user/item representation이고, $E^{(0)}$은 초기 message-passing iteration 과정에서 $E$로 설정된다. 즉, $e_u^{(0)}=e_u$ 그리고 $e_i^{(0)}=e_i$이다. $I$는 항등 행렬이다.
$\mathcal L$은 user-item 그래프의 라플라시안 행렬이고, 다음과 같다.
$$
\mathcal L=D^{-{1\over2}}AD^{-{1\over2}}\ \text{and}\ A=\begin{bmatrix} \bf 0 & R \ R^\text T & \bf 0 \end{bmatrix} \cdots\cdots (8)
$$
이때 $R\in R^{N\times M}$은 user-item interaction matrix이고, $A$는 인접행렬이다. $D$는 $t$ 번째 주대각 성분이 $D_{tt}=|\mathcal N_t|$인 diagonal degree matrix이다. 따라서 0이 아닌 비대각(off-diagonal) 성분들은 $\mathcal L_{ui}={1/\sqrt{|\mathcal N_u||\mathcal N_i|}}$인데, 이는 식 (3), (6)에서의 $p_{ui}$와 같다.
matrix-form propagation rule함으로써, 모든 노드에 대해 representation update를 일괄적으로 적용하여 더 효율적인 방식으로 진행했다. 이 는 큰 사이즈의 graph을 대상으로 실행되는 GCN에서 흔히 사용되는 Node Sampling 과정을 없애준다. 이에 대한 복잡도 분석도 진행했다.
Model Prediction
$L$개의 레이어를 통한 전파 과정 이후, 유저 $u$에 대한 여러 임베딩 ${e_u^{(1)}, \cdot\cdot\cdot, e_i^{(L)}}$을 얻는다. 이 임베딩들은 각기 다른 연결에서 전달받은 메시지를 강조하므로, 유저 선호에 대해 각기 다른 부분을 반영한다. 따라서 이 임베딩들을 concat하여 최종 유저에 대한 임베딩을 구성한다. item에 대해서도 동일한 연산을 진행하여 아래와 같은 최종 임베딩을 얻는다.
$$
e_u^=e_u^{(0)}||\cdot\cdot\cdot||e_u^{(L)},\ \ e_i^=e_i^{(0)}||\cdot\cdot\cdot||e_i^{(L)} \cdots\cdots (9)
$$
이때 $||$는 concat 연산이다.($A||B=\text{concat}(A, B)$)
이렇게 함으로써 임베딩 전파 레이어로 초기 임베딩을 향상시킬 뿐만 아니라 $L$을 조정하여 전파 범위를 제어할 수 있다.
concat 연산 외에도 weighted avg, max pooling, LSTM 등을 진행할 수 있으며, 이는 각기 다른 차수(order)의 연결을 다르게 처리한다는 것을 의미한다.
concat 연산 사용의 장점은 학습할 부가적인 파라미터가 없어 단순하다는 점에 있으며, 게다가 concat 연산이 최신 GNN 연구에서 layer-aggregation 방식으로서 꽤 효과적이라고 밝혀졌다.
최종적으로 타겟 아이템에 대한 유저 선호를 내적으로 개산하였다.
$$
\hat y\text{NGCF}(u, i)={e_u^}^\text Te_i^\ \ \ \ \ \ \ \ \ \ (10)
$$
본문에서는 임베딩 함수와 그 학습을 강조하므로 단순히 내적만을 사용하였다. 신경망 기반 상호 작용 함수와 같은 다른 더 복잡한 선택은 연구할 만한 가치가 있으며, future work로 남겨둔다.
Optimization
모델을 학습하기 위해서 추천 시스템에서 많이 쓰여온 pairwise BPR loss를 최적화한다. 이는 observed/unobserved user-item interaction 사이의 상대적 우선순위를 고려한다.
구체적으로, BPR은 유저의 선호를 더 잘 반영하는 observed interaction에 unobserved interaction보다 더 높은 점수를 부여한다.
목적 함수는 다음과 같다.
$$
\text{Loss}=\sum_{(u, i, j)\in O}-\ln{\sigma}(\hat y_{ui}-\hat y_{uj})+\lambda||\Theta||_2^2\ \ \ \ \ \ \ \ \ (11)
$$
이때 $O={(u,i,j)|(u,i)\in\mathcal R^+,(u,j)\in\mathcal R^-}$는 pairwise한 훈련 데이터이다. $\mathcal R^+$는 observed interaction을, $\mathcal R^-$는 unobserved interaction을 가리키며, $\sigma(\cdot)$은 sigmoid이다.
$\Theta={E,{W_1^{(l)}, W_2^{(l)}}_{l=1}^L}$는 모든 학습 가능한 파라미터들을 가리키며, $\lambda$는 오버피팅을 방지하기 위한 L2 정규화의 세기를 조절한다.
optimizer는 Adam을 채택했고, 임의로 샘플링된 배치 $(u,i,j)\in O$에 대해 모두 최종 임베딩 $[e^{(0)},...,e^{(L)}]$을 구한 후 모델 업데이트를 진행했다.
Model Size
NGCF는 $l$개의 각 전파 레이어마다 임베딩 행렬 $E^{(l)}$가 존재하지만서도 매우 적은 파라미터의 개수를 가지고 있다는 데 주목할 가치가 있다.(각 임베딩마다 $d_l\times d_{l-1}$ 크기의 행렬이 두개씩 존재한다.)
구체적으로, 이 임베딩 행렬들은 embedding look-up table $E^{(0)}$로부터 user-item graph 구조와 weight matrix들을 기반으로 한 변환으로 생성된다.
가장 간결한 임베딩 모델인 MF에 비교해 NGCF는 $2Ld_ld_{l-1}$개의 추가적인 파라미터만 존재한다.
이런 추가 비용은 무시할 만한데, $L$은 일반적으로 5보다 작은 숫자이며 $d_l$은 유저 및 아이템 개수 $N, M$보다 훨씬 더 작은 크기로 설정되기 때문이다.
예를 들어, 후술할 Gowalla 데이터셋(20K 유저와 40K 아이템)에 대한 실험에서, 임베딩 사이즈는 $64$ 였고 $64\times64$ 크기의 전파 레이어를 3개 사용했다. 이때 MF는 4.5M개의 파라미터가 있고, NGCF는 0.024M개의 추가 파라미터만 존재했다.
요약하자면, NGCF는 매우 적은 수의 추가적인 모델 파라미터만 가지고 high-order connectivity 모델링을 이뤄냈다.
Message and Node Dropout
딥러닝이 충분한 표현력을 갖췄음에도 불구하고 오버피팅 현상이 자주 발생한다. Dropout은 신경망이 오버피팅하지 않도록 방지하는 효과적인 방법 중 하나이다. GCN에 관한 선행연구들을 따라 NGCF에 2가지 dropout 기술을 적용한다. message dropout과 node dropout이다.
Message Dropout은 임의로 outgoing message(outbound edge)를 drop한다. 구체적으로, 식 (6)에서 전파되는 메시지를 drop한다. 이 때 dropout rate는 $p_1$이다. 따라서 $l$번재 전파 레이어에서는 부분적인 메시지들만이 표현 refine 과정에 영향을 준다.
또한 Node Dropout을 수행해 특정 노드를 임의로 차단하고 해당 노드에서의 outgoing message를 모두 차단한다. $l$번째 전파 레이어에서, 라플라시안 행렬의 노드들 중 임의로 $(N+M)p_2$개의 노드를 drop한다. 이 때 $p_2$는 dropout rate이다.
dropout은 학습 단계에서만 사용되었고, 테스트 단계에서는 비활성화 돼야 한다.
message dropout은 user-item 사이의 단일 연결의 존재 여부에 대해 더 많은 robustsness를 임베딩에 제공하고, node dropout은 특정 user/item에 대한 영향을 줄이는 데 초점이 맞춰져 있다.
본문에서는 NGCF에서 dropout에 대한 효과를 실험했고, 이에 대해 후술한다.
Discussion
이 섹션에서는 NGCF가 SVD++를 어떻게 일반화했는지를 보이고, NGCF의 시간 복잡도를 분석한다.
NGCF Generalizes SVD++
SVD++는 high-order connectivity가 없는 NGCF의 special case로 보일 수 있다. 구체적으로, $L=1$로 설정했을 때의 경우이다.
전파 레이어 내에서 변환 행렬과 비선형 활성화함수를 사용하지 않으면 $e_u^{(1)}, e_i^{(1)}$는 $u, i$에 대한 최종 임베딩이 된다. 저자들은 이렇게 단순화된 모델을 NGCF-SVD라 이름짓고, 이에 대해 다음과 같이 공식화한다.
$$
\hat y\text{NGCF-SVD}=(e_u+\sum_{i'\in\mathcal N_u}p_{ui'}e_{i'})\ \ \ \ \ \ \ \ \ \ \ (12)
$$
간단하게 $p_{ui'}$와 $p_{u'i}$를 $1/\sqrt{|\mathcal N_u|}$과 $0$으로 설정함으로써 SVD++ 모델을 정확하게 구현할 수 있다.
게다가 널리 쓰이는 item-based CF 모델인 FISM도 식 (12)에서 $p_{iu'}$가 0으로 설정된 NGCF의 special case로 볼 수 있다.
Time Complexity Analysis
봤다시피 layer-wise propagation rule이 가장 주된 연산이다. $l$번째 전파 레이어에 대해 행렬곱은 $O(|\mathcal R^+|d_ld_{l-1})$의 계산 복잡도를 가지며, $|\mathcal R^+|$는 라플라시안 행렬에서 0이 아닌 요소들의 수이다.
예측 레이어에서는 내적만 사용되었는데, 이때 time complexity는 $O(\sum_{l=1}^L|\mathcal R^+|d_ld_{l-1}+\sum_{l=1}^L|\mathcal R^+|d_l)$이다.
실험적으로 같은 조건일 때, Gowalla 데이터셋에 대해 학습하면 MF와 NGCF는 epoch당 20s와 80s의 비용이 든다. inference 과정에서 모든 testing 샘플에 대해 MF와 NGCF는 80s와 260s의 시간이 걸렸다.
RELATED WORKS는 skip
Experiments
3개의 벤치마크 데이터셋에 대해 실험을 진행했고, 다음의 3개의 reasearch questions에 답하는 데 집중했다.
- RQ1: SOTA CF 방법론들에 비해 NGCF는 어떤 성능을 내는가?
- RQ2: 하이퍼 파라미터들은 NGCF의 성능에 어떤 영향을 주는가?
- RQ3: 벡터 표현이 어떻게 high-order connectivity에서 향상이 이루어지는가?
Dataset Description은 skip
Experimental Settings
Evaluation Metrics
test set의 유저들에 대해 해당 유저들이 한 번도 상호작용하지 않은 모든 아이템들을 negative item으로 취급한다.
그리고 train set에서 사용된 positive item들을 제외하고 모든 아이템의 대한 유저들의 preference score를 각각의 method들이 산출해낸다.
top-k 추천과 선호도에 대한 랭킹을 평가하기 위해, recall@K와 ndcg@K를 사용한다.
기본적으로 $K=20$으로 설정되며, test set의 모든 유저들에 대한 평균 지표들을 정리했다.
Baselines 모델의 효과성을 증명하기 위해 NGCF를 다음의 방법들과 비교하였다.
- MF : interaction function의 target으로만 user-item 사이의 direct interaction을 이용하는 Bayesian Personalized Ranking(BPR)을 통해 최적화된 Matrix Factorization(MF).
- NeuMF : 상호작용의 비선형적 feature를 capture하기 위해 user/item 임베딩을 element-wise/concatenation하여 그 위에 여러 은닉층을 쌓은 SOTA neural CF model.
- CMN : SOTA memory-based model로, user represetation이 memory 레이어를 통해 이웃 유저들의 memory slot을 결합하는 방식. 1차 연결(first-order connection)이 같은 아이템에 상호작용한 유사한 유저를 찾기 위해 사용되었다.
- HOP-Rec : SOTA graph-based model로, random walks로 구한 high-order neighbor가 interaction data를 enrich하는 데 쓰임.
- PinSage : item-item graph에서 GraphSAGE 모델을 차용. 본문에서는 user-item interaction graph에 적용하여 실험. 특히 PinSage 논문에서 제시된 두 개의 graph convolution layer를 사용하고, hidden dim은 임베딩 크기와 동일하게 설정했다.
- GC-MC : 이 모댈을 user/item representation을 생성하기 위해 GCN encoder를 사용. 이때 first-order 이웃만 고려된다. 따라서 hidden dim이 임베딩 크기와 동일하게 설정된 하나의 GCN 레이어만 사용했다.
저자들은 추가적으로 SpectralCF에 대해서도 실험을 시도했지만 eigen-decomposition과정의 time cost와 resource cost가 user/item count가 커질수록 너무 높아졌다. 따라서 작은 데이터셋에 대해서 어느정도 성능이 나왔지만 비교를 위한 baseline으로 선택하지 않았다.
공정한 비교를 위해 모든 방법들은 식 (11)의 BPR loss로 학습되었다.
Parameter Settings
- embedding size: 64
- HOP-Rec random walks: {1, 2, 3}
- HOP-Rec lr : {0.025, 0.020, 0.015, 0.010}
- optimizer: Adam(HOP-Rec제외)
- batch size: 1024
- 하이퍼파라미터: grid search로 탐색
- lr: {0.0001, 0.0005, 0.001, 0.005}
- L2 norm coeffs: {10e-5. 10e-4, ..., 10e1, 10e2}
- dropout rate: {0.0, 0.1, ..., 0.8}
- node dropout rate: {0.0, 0.1, ..., 0.8}
- weight init: Xavier initializer
- val set의 recall@20에 대해 early stopping strategy 사용
- NGCF high-order connectivity depth: 3
- 특별한 말이 없으면 후술되는 결과는 node dropout rate/message dropout rate이 0.0/0.1인 3개의 임베딩 전파 레이어의 결과임
Performance Comparison (RQ1)
상기한 모든 방법들에 대해 성능을 비교했고, sparse setting에서 high-order connectivity를 어떻게 모델링하는지 연구한다.
Overall Comparison
- MF는 3개 데이터셋에서 좋지 않은 성능을 내었다. 이는 내적이 user와 item 사이의 복잡한 관계를 capture하기에 충분치 못하고, 따라서 성능이 제한됨을 의미한다. NeuMF는 모든 경우에서 MF보다 향상된 성능을 보였고, 이는 user-item embedding 사이에서 비선형적 관계가 중요하다는 것을 의미한다. 하지만 MF와 NeuMF 모두 학습 과정에서 명시적으로 임베딩의 연결성을 모델링하지 않아서 suboptimal한 결과로 이어지기 쉽다.
- MF와 NeuMF에 비해 GC-MC의 성능은 first-order 이웃을 통합하는 게 표현 학습 향상에 도움된다는 걸 보여준다. 하지만 Yelp2018에서 GC-MC는 ngcg@20 지표에 대해 NeuMF보다 낮은 성능을 보였다. 이는 GC-MC가 user-item의 비선형적 feature를 충분히 탐색하지 못했기 때문일 수도 있다.
- CMN은 대부분의 경우에서 GC-MC보다 더 나은 성능을 보였다. 이는 각 이웃 user에 대해 GC-MC처럼 동일하거나 heuristic한 가중치를 사용하는 대신 attentive weight를 사용하는 neural attention mechanism을 사용하기 때문일 수도 있다.
- PinSage는 Gowalla와 Amazon-Book 데이터셋에서 CMN보다 조금 낮은 성능을 보였고, Yelp2018에서는 훨씬 좋은 성능을 보였다. 반면 HOP-Rec은 일반적으로 모든 경우에서 눈에 띄는 성능 향상을 보였다. 이에 대해 CMN은 유사한 유저만 고려한 반면, PinSage는 high-order connectivity를 embedding function에 도입하였고, HOP-Rec은 high-order 이웃을 이용하 training data를 augment했기 때문이라고 설명하는 게 타당하다. 따라서 이는 high-order connectivity/neighbors를 모델링하는 것의 긍정적 효과를 보여준다고 볼 수 있다.
- NGCF는 모든 데이터셋에 대해 가장 높은 성능을 보였다. 특히 NGCF는 recall@20에 대해 가장 고성능의 baseline과 비교하여 11.68%, 11.97%, 9.61%의 성능 향상이 있었다(순서대로 Gowalla, Yelp2018, Amazon-Book). 여러 임베딩 전파 레이어를 쌓음으로써 NGCF는 명시적인 방법으로 high-order connectivity를 탐색할 수 있었고, 반면 CMN이나 GC-MC는 표현 학습을 위해 오직 1차 이웃만 이용하였다. 이는 embedding function에서 collaborative signal을 capture하는 게 중요하다는 걸 보여준다. 더욱이 PinSage와 비교해서 NGCF는 유저 선호도를 예측하기 위해 multi-grained 표현을 고려하지만(여러 임베딩 레이어의 결과물을 모두 concat해서 사용하지만), PinSage 마지막 레이어의 결과만 사용한다. 이는 다른 전파 레이어가 표현에서 각기 다른 부분을 인코딩함을 보여준다. 그리고 HOP-Rec에 대한 성능 향상은 임베딩 함수에서 명시적으로 CF를 인코딩하는 것이 더 좋은 표현을 생성할 수 있음을 의미한다. one-sample t-test를 진행하였고 $p<0.05$였다. 이는 가장 강력한 baseline에 대한 NGCF의 성능 향상이 통계적으로도 유의미했음을 의미한다.
Performance Comparison w.r.t Interaction Sparsity Levels
inactive 유저의 적은 interaction은 좋은 표현을 생성하기에 부족하므로 sparsity는 자주 추천 시스템의 표현력을 제한하는 issue이다. 연결 정보를 이용하는 것이 이 문제를 완화하는 데 도움이 되는지 연구했다.
이를 위해 다른 sparsity level 집단의 유저에 대해 실험을 진행했다. 구체적으로, 유저당 interaction 개수에 따라 test set을 4개의 그룹으로 나누었고, 각 그룹의 총합 상호작용 수는 동일하다.
Gowalla 데이터셋을 예시로 들자면, 유저 당 상호작용 수는 각각 24, 50, 117, 1014보다 작다.
Figure 4는 세 벤치마크 데이터셋에서 각기 다른 유저 그룹에 대한 ndcg@20의 결과를 보여준다. recall@20에 대해서도 비슷한 경향을 볼 수 있으며, 공간 제한으로 인해 그 부분은 생략한다.
저자들은 다음과 같은 사실을 발견했다.
- NGCF와 HOP-Rec은 일관되게 모든 그룹에 대해 다른 baseline들을 뛰어 넘었다. 이는 high-order connectivity가 collaborative signal을 capture하여 inactive 유저에 대한 표현 학습을 상당히 향상시킨다는 걸 보여준다. 따라서 추천 시스템에서의 sparsity issue를 해결하는 데 효과가 있어 보이며, 이는 future work로 남겨둔다.
- Fiture 4(a)와 4(b), 4(c)를 같이 분석해봤을 때, 첫 두 그룹에서의 향상이 다른 그룹보다 더 중요하다는 걸 발견했다(예: Gowalla에서 <24, <50 그룹애 대해 각기 best baseline과 비교하여 8.49%, 7.79%의 향상이 있었고, <1014에서는 1.29%의 향상이 있었음). 이는 임베딩 전파가 상대적으로 inactive 유저에 대해 더 효과적이었음을 보여준다.
Study of NGCF (RQ2)
임베딩 전파 레이어가 NGCF에서 중요한 역할을 하므로 이것이 성능에 미치는 영향을 조사한다. 먼저 레이어 개수에 대한 영향을 조사하고, 라플라시안 행렬(decay factor $p_{ui}$)의 성능에 대한 영향을 연구한다. 이후 node dropout/message dropout ratio의 영향을 분석하고, NGCF의 학습 절차에 대해서 연구한다.
Effect of Layer Numbers
NGCF가 여러 임베딩 전파 레이어로부터 성능 향상이 있는지 따져보기 위해, model depth에 변화를 주었다. 구체적으로, 레이어의 개수를 1개에서부터 4개까지 변화시켰다. Table 3가 실험 결과를 요약해서 보여주는데, NGCF-3는 3개의 임베딩 전파 레이어로 구성된 모델을 말하며, 다른 이름들도 마찬가지이다.
Table 2와 3을 같이 분석했을 때 다음과 같은 것들을 발견할 수 있었다.
- NGCF의 depth를 늘리는 것은 전반적으로 성능이 향상된다. NGCF-2와 NGCF-3은 1차 이웃만 고려하는 NGCF-1보다 꾸준한 성능 향상이 있었다. 저자들은 이를 CF 모델링의 효과라고 말하는데, collaborative user similarity와 collaborative signal은 2차, 3차 연결에서 전달될 수 있기 때문이다.
- NGCF-3에서 전파 레이어를 더 쌓았을 때, NGCF-4가 Yelp2018에서 오버피팅했음을 알 수 있다. 이는 너무 깊은 구조를 적용하여 표현 학습에 노이즈가 발생했기 때문이라고 볼 수 있다. 나머지 2개 데이터셋에서의 사소한 향상은 3개의 전파 레이어로도 CF signal을 capture하기에 충분하다는 걸 보여준다.
- 전파 레이어의 개수를 변화시키면서, NGCF는 일관적으로 모든 데이터셋에서 다른 모델들에 비해 더 좋은 성능을 보였다. 이는 NGCF의 효과성을 증명하며, 명시적으로 high-order connectivity를 명시적으로 모델링하는 것이 추천 task에서 성능 향상에 크게 기여한다는 것을 실험적으로 보여주는 것이다.
Effect of Embedding Propagation Layer and Layer-Aggregation Mechanism
임베딩 전파(graph convolution) 레이어가 성능에 어떻게 영향을 주는지 조사하기 위해서, 각기 다른 레이어를 사용하는 NGCF-1의 변형들을 따져본다. 구체적으로, message passing function에서 node와 그 이웃들 사이의 representation interaction(식 (3)에서 $e_u\odot e_i$)을 제거하고 이를 각각 PinSage와 GC-MC의 것으로 대체했다. 그리고 각각 $\text{NGCF-1}_\text{PinSage}$와 $\text{NGCF-1}_\text{GC-MC}$라고 한다.
추가적으로 SVD++를 따라 식(12)에 기반한 또 하나의 변형을 구했고, 이를 $\text{NGCF-1}_\text{SVD++}$라 한다.
결과는 Table 4에 있으며, 다음과 같은 것들을 발견했다.
- NGCF-1은 일관되게 모든 변형보다 좋은 성능을 보였다. 저자들은 이를 representation interaction의 개선으로 설명하는데, 메시지가 $e_i$와 $e_u$ 사이의 affinity와 attention mechanism과 같은 함수에 의존하여 메시지가 전달되도록 한다. 반면 모든 변형들은 선형 변환만 고려한다. 따라서 이는 본문의 임베딩 전파 함수의 효과와 타당성을 입증한다.
- 대부분의 경우에서 $\text{NGCF-1}_\text{SVD++}$는 $\text{NGCF-1}_\text{PinSage}$와 $\text{NGCF-1}_\text{GC-MC}$보다 낮은 성능을 보였다. 이는 node 그 자체에서 전달되는 메시디와 비선형적 변환의 중요성을 말한다.
- Table 2와 4를 같이 봤을 때, 모든 레이어의 결과를 concatenation할 때가 $\text{NGCF-1}_\text{PinSage}$와 $\text{NGCF-1}_\text{GC-MC}$의 성능을 PinSage와 GC-MC보다 더 향상시키는 걸 발견했다. 이는 layer-aggregation mechanism의 중요성을 강조한다.
Effect of Dropout
기존 선행연구와 마찬가지로 NGCF가 오버피팅하는 것을 방지하기 위해 node dropout과 message dropout을 적용했다.
Figure 5이 각각 다른 데이터셋, 다른 평가 프로토콜에 대해 message dropout ratio $p_1$과 node dropout ratio $p_2$의 효과를 보여준다.
두 dropout 전략을 보면 node dropout이 더 좋은 성능을 보인다. Gowalla를 예시로 보면, $p_2$를 0.2로 설정하는 건 가장 높은 0.1514의 recall@20 점수로 나타나는데, 이는 message dropout의 점수인 0.1506보다 더 좋다. 그 이유 중 하나는 특정 노드의 모든 outgoing message를 drop하는 것이 특정 edge의 영향뿐만 아니라 특정 node의 영향도 줄여주어 표현을 더 robust하게 만들어준다.
따라서 node dropout이 message dropout보다 더 효과적이고, 이는 선행 연구에서 도출된 결과와 일치한다.
저자들은 이것이 흥미로운 발견이라 생각하는데, node dropout이 GNN에서 오버피팅을 설명하는 효과적인 전략이 될 수 있기 때문이다.
Test Performance w.r.t Epoch
Figure 6이 MF와 NGCF의 각 epoch마다의 recall에 대한 성능 평가를 보여준다.
여백이 부족하므로 recall과 비슷항 경향을 보이는 ndcg에 대한 성능 평가는 생략한다.
NGCF가 3개 데이터셋에서 MF보다 더 빨리 수렴하는 걸 볼 수 있다. 이는 간접적으로 연결된 유저와 아이템이 mini-batch에서 interaction pair로 최적화되므로 reasonable하다.
이런 현상은 NGCF의 더 좋은 model capacity와 임베딩 공간에서 임베딩 전파의 효과성을 보여준다.
Effect of High-order Connectivity (RQ3)
임베딩 전파가 어떻게 임베딩 공간에서 표현 학습을 증진시키는지 이해한다. 이를 위해 임의로 6개의 유저와 관련된 아이템들을 Gowalla 데이터셋에서 뽑았다.
NGCF의 depth 측면에서 임베딩 표현들이 어떻게 영향을 받는지 관찰했는데, Figure 7에 나타나 있다.
Figure 7(a)와 7(b)는 각각 MF(NGCF-0)와 NGCF-3의 표현을 시각화한 것이다. item들은 학습 단계의 user들과 관계 없는 test set의 아이템으로 구성되었다.
2가지 주목할 만한 사항이 있다.
- 유저와 아이템의 연결이 임베딩 공간에서 잘 반영되었고, 이는 공간에서 (거리상) 가까운 부분으로 임베딩되었음을 말한다. 특히, NGCF-3의 표현은 눈으로 봐도 알 수 있을 정도로 클러스터링이 되었는데, 같은 색을 가진 점(어떤 유저에 의해 상호작용된 아이템은 같은 색으로 칠해졌다)들이 클러스터를 형성하는 모습을 볼 수 있다.
- Figure 7(a)와 7(b)에서 같은 유저들(12201과 6880)을 분석해봤을 때, 3개의 임베딩 전파 레이어를 쌓았을 때 유저들의 historical items들의 임베딩이 가까워지려는 경향을 발견했다(즉, 연속적으로 상호작용한 아이템들이 임베딩 공간 상에서 같은 클러스터 내 다른 아이템보다 더 가까이 위치함). 이는 임베딩 전파 레이어가 명시적인 collaborative signal을 표현이 주입할 수 있다는 걸 양적으로 보여준다.
Conclusion and Future Work
본문에서, 저자들은 명시적으로 collaborative signal을 model-based CF의 embedding function에 통합했다.
user-item interaction graph에서 high-order connectivity를 이용하는 framework, NGCF를 개발했다.
NGCF의 핵심은 새로이 제안된 임베딩 전파 레이어로, 이를 기반으로 user와 item의 embedding이 서로 상호작용해 collaborative signal을 수집할 수 있다.
세가지 데이터셋에 대해 진행된 넓은 연구는 user-item graph 구조를 임베딩 학습 과정에 주입하는 게 효과적이고 타당함을 보여준다.
저자들은 후속연구로서, 다른 차수(different order)의 연결과 임베딩 전파 과정에서의 이웃들에 대해 다른 가중치를 적용하고 이를 학습하는 attention mechanism을 적용해 NGCF를 향상시킬 계획이다. 이는 모델의 일반화와 해석가능성(interpretability)에 도움이 될 것이다.
더욱이 저자들은 user/item 임베딩과 graph 구조에 대해 NGCF의 robustness를 강화시킬 adversarial learning에 대해서 연구하는 부분에도 관심 있다.
본 논문은 model-based CF에서 message-passing 메커니즘으로 structural knowledge를 활용한 최초 시도를 보였고, 새로운 연구 가능성을 열었다. 구체적으로 cross features in context-aware, semantics-rich recommendation, item knowledge graph, social network와 같이, 유저의 행동을 이해하는 데 유용한 structural information의 많은 형태가 존재한다.
예를 들어, item knowledge graph를 user-item graph에 통합함으로써 유저와 아이템 사이의 knowledge-aware connectivity를 구축할 수 있고, 이는 아이템을 선택하는 과정에서 유저의 의사 결정 프로세스를 이해하는 데 도움이 될 것이다.
저자들은 NGCF의 개발이 더 효과적이고 이해 가능한 추천 시스템을 위해 유저의 online behavior를 규명하는 데 도움되기를 바란다.