안녕하세요 여러분. 오늘은 graph 구조를 이용한 추천시스템 연구를 제안한 논문에 대해서 살펴보독록 하겠습니다.
잘못된 부분이나 이해가 안가는 부분이 있다면 댓글남겨주시면 감사하겠습니다.
ABSTRACT
추천시스템은 유저와 아이템의 vector representation(일명 embeddings)을 학습하는 것이 연구의 주였습니다.
초기의 matrix factorization에서 부터 최근의 딥러닝 방식들은 유저나 아이템의 임베딩 벡터를 구할 뿐 유저와 아이템의 상호작용(user-item interaction)에 잠재되어있는 collaborative signal은 학습 과정에서 인코딩되지 않는다고 저자들은 주장합니다. 그래서 저자들은 유저와 아이템의 구조를 잘 나타낼 수 있는 graph 구조를 이용한 Neural Graph Collaborative Filtering (NGCF)을 제안하였습니다.
INTRODUCTION
추천시스템은 어떤 유저의 아이템 구매나, 클릭 같은 historical interactions에 기반하여 그 유저가 어떤 아이템을 구매, 클릭할 것인지를 예측하는 것입니다. Collaborative filtering (CF)은 과거에 구매한 아이템이나 클릭한 아이템이 비슷한, 즉 행동이 유사한 유저들이 비슷한 아이템을 선호한다고 가정합니다. 이런 CF모델을 학습시키기 위해 두가지 핵심적인 요소가 있습니다.
- 유저와 아이템 정보를 벡터화 된 표현(representation)으로 변형하는 임베딩(embedding)
- 이런 임베딩에 기반하여 유저-아이템의 과거의 상호작용(historical interactions) 재구성하는 상호작용 모델링(interaction modeling)
대표적인 CF모델은 먼저 matrix factorization (MF)이 있습니다. MF는 유저와 아이템 ID를 벡터로 임베딩하고, 이 벡터를 내적하여 user-item interactions을 구합니다. neural collaborative filtering 모델들은 MF의 내적을 비선형 neural networks로 대체하였습니다.
하지만 저자들은 이 방법들이 효과적이지만, CF를 위한 임베딩을 도출하기엔 충분하지 않다고 주장합니다.
그 이유는 유저간(아이템간) 행동 유사성을 나타내기 위한 user-item interaction이 잠재된 collaborative signal을 explicit하게 인코딩하지 못하기 때문입니다. 즉 상호작용을 고려하지 않고 단순히 유저, 아이템의 ID를 임베딩하기 때문에 CF를 잘 학습하기 위한 임베딩이 부족한 경우 이 부족함을 채우기 위해서 내적과 같은 interaction function에 의존하게 됩니다.
그러면 interactions을 임베딩 함수에 입력으로 넣어주어야 하는데 현실에서는 수 많은 interactions이 있기 때문에 어렵습니다. 그래서 저자들은 interaction graph 구조에서 collaborative signal를 인코딩하는 자연스러운 방법인 user-item interactions으로 부터의 high-order connectivity를 활용해 문제를 해결합니다.
위 Figure 1은 high-order connectivity의 개념을 소개하고 있습니다. 유저1의 관점에서 설명을 드리자면 우선 왼쪽은 user-item interaction graph구조를 나타내고 있습니다. 유저1인 u1와 연결된 아이템을 보면 i1, i2, i3이고 이는 과거에 유저1이 아이템1,2,3을 클릭하거나 구매한 interaction을 나타냅니다. 오른쪽 그림은 u1의 high-order connectivity를 보여줍니다. 먼저 i(1,2,3)은 u1과 상호작용이 있는 아이템이고, i_2가 유저2와 상호작용하므로 이를 경로로 나타내면 u1 ← i2 ← u2 입니다. 이때 u1에 대한 i2의 경로 길이는 1이고 u2의 경로 길이는 2입니다. 이 경로는 u1과 u2사이에 행동 유사성이 있는 것을 나타냅니다. 더 긴 경로인 u1 ← i2 ← u2 ← i4을 보시면 u2가 i4와 상호작용한 데이터가 있기 때문에, u1도 i4을 구매하거나 클릭할 가능성이 높다고 유추할 수 있습니다. 그리고 l=3 에서 i4가 i5보다 u1이 더 흥미를 가질 아이템이라고 유추할 수 있는데, 이는 l=3에 i4가 두개있는 반면 i5는 한개가 있기 때문입니다.
저자들은 embedding propagation layer을 제안하였습니다. 이는 어떤 사용자(아이템)의 임베딩을 그 사용자(아이템)와 상호작용한 아이템(사용자)의 임베딩을 aggregate하여 refine합니다. 이 layer를 여러 층 쌓음으로써 high-order connectivities에서 collaborative signal을 뽑아내는 임베딩을 강화할 수 있습니다. 위의 u1의 예를 들어서 설명을 하면, 2개의 층을 쌓으면 u1 ← i2 ← u2의 행동 유사성을 capture할 수 있습니다. 3개의 층을 쌓으면 u1 ← i2 ← u2 ← i4에서 추천할 아이템, i4와 i5중 추천 우선순위를 capture할 수 있습니다.
논문을 3가지 main contribution으로 요약하면 다음과 같습니다.
- 모델기반 CF 에서의 임베딩함수에 내재된 collaborative signal을 이용해야 함의 중요성을 강조.
- embedding propagation을 수행함으로써 high-order connectivities의 형태로 collaborative signal을 명확하게 인코딩하는 graph neural network기반 새로운 추천시스템 프레임워크인 NGCF을 제안.
- 큰 사이즈의 데이터 셋 3개를 이용해 경험적 연구를 수행. 수행 결과 최고의 성능을 보임.
METHODOLOGY
Embedding Layer
유저나 아이템을 embedding vector을 이용하여 나타낼 수 있습니다. 데이터셋에 유저가 N명 아이템 종류가 M개 있을 때 parameter matrix를 다음과 같이 구축합니다.
E는 사용자 임베딩 및 아이템 임베딩이 최적화되기 위한 초기 상태 역할을 합니다. 기존 MF나 neural collaborative filtering은 E를 내적을 구하기위해 아니면 interaction layer에 입력하기 위해 사용합니다. 하지만 NGCF에서는 user-item interaction graph에서 E를 전파(propagate)하여 임베딩을 개선시킵니다. 이런 방법은 임베딩에 collaborative signal를 명확히 주입하여 추천을 위한 더 효과적인 임베딩으로 개선시켜줍니다.
Embedding Propagation Layers
NGCF 모델의 architecture는 다음과 같습니다.
위 구조는 u1과 i4를 예를들어서 나타내고 있습니다. 먼저 Embedding Propagation Layers을 살펴보겠습니다. one-layer propagation에 대해서 먼저 설명을 드리고 이를 일반적인 muti-layer로 확장하여 설명하겠습니다.
message construction
유저와 아이템 pair (u,i)에서 i로부터 u를 향한 메세지를 다음과 같이 정의합니다.
m_u←i 는 message embedding이고, f (·) 는 message encoding function입니다.
더 자세히 나타낸 식을 보면 W1, W2는 학습가능한 가중치 벡터이고, 임베딩된 아이템벡터 ei만을 이용하는 기존의 conventional graph convolution networks와 달리 ei와 eu의 엘리멘탈 와이즈 곱을 더해줍니다. 이는 비슷한 아이템으로부터 메세지를 더 많이 받음으로써 ei와 eu의 관련성에 따라 message를 만듭니다. p_ui는 graph Laplacian norm 1/ sqrt(|Nu ||Ni |)로 설정하였는데, 이때 Nu, Ni는 각각 유저 u와 아이템 i의 first-hop neighbors을 의미합니다. p_ui는 과거의 아이템들이 유저의 선호도에 얼마나 기여하는지를 나타냅니다.
Message Aggregation
유저 u의 representation을 위해 u의 이웃 아이템으로부터 전파된 메세지를 aggregate합니다.
e_u(1)은 첫번째 embedding propagation layer을 지난 후 얻어진 유저 u의 representation을 나타냅니다.
u의 이웃 아이템으로부터의 메세지에 더해서 저자들은 유저 u의 self-connection을 더해주었습니다. self-connection은 유저가 원래 가진 original feature의 정보를 유지하도록 해줍니다. 같은 방식으로 아이템 i의 representation인 e_i(1)도 구할 수 있습니다.
요약해보면, embedding propagation layer의 장점은 유저나 아이템의 이웃정보인 first-order connectivity information을 명확하게 이용하여 얻어집니다.
더 많은 mbedding propagation layers을 쌓음으로써 high-order connectivity information을 이용할 수 있습니다. high-order connectivities은 유저와 아이템 사이의 관련성을 나타내는 score을 추정하기 위한 collaborative signal을 인코딩하는데에 중요하게 작용합니다. 층을 쌓음으로써 유저(아이템)는, 만약 층수가 3일때 3-hop 이웃으로부터 전파된 메세지를 활용할 수 있습니다.
위 그림은 층수가 l인 경우의 유저 u의 representation을 의미합니다.
메세지도 다음과 같이 기존 층의 u와 i의 representation을 이용해 구할 수 있습니다.
위 그림은 collaborative signal u1 ← i2 ← u2 ← i4의 embedding propagation 과정을 나타냅니다.
Model Prediction
L층을 통과한 뒤 유저 u에 대한 multiple representation을 구할 수 있습니다. 각 층은 유저에 대한 각기 다른 연결성 때문에 각 층의 표현은 유저의 선호도를 반영하는데에 있어 다른 기여를 합니다. 이 표현들은 유저의 최종 임베딩을 구성하기 위해서 합쳐지게 됩니다. 아이템에 대해서도 같은 방식을 취해주었고 다음과 같이 나타낼 수 있습니다.
II은 concatenation operation입니다. 이러게 함으로써 여러 층의 표현들을 이용할 수 있고, 유저 u의 아이템 i에 대한 선호도를 추정하기 위해서 내적을 수행하게 됩니다.
Conclusion
논문은 그래프 구조를 통해서 유저와 아이템간 high-order connectivities 활용하여 3개의 데이터 셋에서 SOTA를 달성했습니다.
layer 수에 따른 결과 비교 등 추가적인 실험을 진행하였으니 논문을 통해 확인해 보시면 좋을 것 같습니다!