논문 링크: arxiv.org/abs/2009.09588
div2vec: Diversity-Emphasized Node Embedding
Recently, the interest of graph representation learning has been rapidly increasing in recommender systems. However, most existing studies have focused on improving accuracy, but in real-world systems, the recommendation diversity should be considered as w
arxiv.org
학부연구생 시절 network embedding, diverse recommendation 관련 연구를 진행했었고, 덕분에 수많은 도메인 중 관심있는 분야를 정할 수 있었습니다. 당시 network embedding 관련해서 DeepWalk, LINE, node2vec 등의 논문을 읽고 구현하고 나아가 이를 diverse recommendation에 접목시키는 연구를 했었는데, 이번에 리뷰할 논문은 DeepWalk로부터 출발합니다. 메인 아이디어는, DeepWalk, node2vec와 비교해서 random walk에서, neighbor 중 다음 노드를 선택하는 확률을 조절함으로써 diversity를 증가시켰다는 것입니다.
Preliminary - Network embedding(Representation learning)
먼저 논문의 근간이 되는 DeepWalk, node2vec에 대해 간략하게 알아봅시다. 그 전에 앞서 언급한 network embedding(representation learning)에 대해 보면, 기존 graph, network 연구에서는 input으로 adjacency matrix를 이용했다면 network embedding은 각 노드, 또는 network를 낮은 차원으로 embedding시켜 얻는 embedding vector(latent representation)를 이용합니다. 기존 방식에 비해 메모리 공간 측면에서 이득을 볼 수 있고, 추천 시스템에서 collaborate filtering에도 적용할 수 있습니다.
예를 들어 10만명의 user, 100만개의 item이 있고 user-item 간 edge가 평점으로 나타난 graph를 생각합니다. Adjacency matrix를 그대로 사용하면 (10만*100만)-matrix를 사용해야 합니다. 이 때 한 user vector는 100만-dim vector가 되겠죠. 대신 각 노드들의 embedding vector를 사용하면 각 user,item을 나타내는 낮은 차원의 vector(ex. 64, 128...)를 사용하게 됩니다.
Matrix의 차원을 낮추는 차원축소 방식은 이미 존재했습니다. PCA, SVD, 그 외에도 다양한 factorization 방식이 있습니다. Network embedding은 낮은 차원 공간 내 기존 데이터를 잘 담기 위해 "다른 노드와의 관계"를 이용합니다. 두 노드가 연관성이 높다면, embedding space 내에서 두 노드가 실제로 가깝게 위치하도록 embedding을 하는 것입니다. 노드 간 연관성이 무엇인지는 문제마다 다르겠지만, facebook 친구 network에서는 친구 관계 여부, 같이 알고 있는 사람의 수, 사는 지역 및 출신 학교, 관심사 등을 이용해서 노드 간 연관성을 정의할 수 있을 것입니다. MovieLens dataset같은 경우는 높은 점수를 매길수록 그 user와 item 간 연관성이 높다고 잡을 수도 있구요.
연관성을 정의했으니 이제 학습을 통해 연관성이 높은 노드가 가깝게 위치하도록 embedding vector를 update하면 됩니다! 이거 어디서 봤던 것 같은데... 하시는 분들은 word2vec을 떠올리시면 됩니다. 실제로 DeepWalk는 word2vec에서 영감을 받아 "단어" 대신 graph 내 노드로, "문장"을 graph 상에서 수행한 random walk sequence로 치환하여 skip-gram을 이용해 embedding을 수행합니다. 이제 문제는 DeepWalk, node2vec에서 어떻게 random walk sequence를 sampling하는가입니다. 두 모델의 차이는 다음과 같습니다.
위 그림은 node2vec 논문에 있는 random walk procedure입니다. 이전 노드 t에서 현재 노드 v로 random walk이 진행되었고, 그 때의 각 v's neighbor로의 transition probability $\alpha$를 나타냅니다. 이전 노드, 현재 노드를 고려해서 주위 노드의 transition probability가 달라지는데, 자세한 내용은 해당 논문 3절을 참고하시면 됩니다. 반대로 DeepWalk는 가장 간단하게 uniform transition probability를 사용합니다. node2vec은 weighted graph에도 적용 가능한 반면 DeepWalk는 노드 간 edge의 weight와 상관 없이 transition probability가 정해지기 때문에 unweighted graph에서만 사용 가능합니다.
이 2가지 모델 외에도 LINE이라는 network embdding 분야의 기념비적인 논문이 있습니다. Random walk 대신 2nd-order proximity를 고려한 모델인데, 관심 있으시면 해당 논문을 읽어보길 추천드립니다. 여유가 된다면 위 논문 3개를 정리해서 글로 남기고 싶네요. 요약 ppt는 아마 어딘가에 있을텐데...
Preliminary - Diverse recommendation
대부분의 추천 시스템 모델은 accuracy를 높이는 것을 목표로 하고 있습니다. User 입장에서는 본인이 좋아할법한 item이 추천 리스트에 많은 것을 당연히 좋아하겠죠. 하지만 이런 모델들은 long-tail problem, filter bubble problem 등의 문제를 안고 있습니다.
간단한 예시로, 슈퍼마켓 방문자에게 물건 추천 리스트를 제공하는데, 90%의 사람들이 방문 시 커피를 꼭 사간다고 합시다. 이를 보고 추천 시스템이 모든 사람들에게 커피를 추천하면 정확도는 90%가 되겠지만 쓸모 없는 추천 시스템이 되겠죠. 막 입고된 새로운 물건, 또는 몇몇 사람만 사가는 가치있는 물건들은 추천되지 않을 가능성이 높습니다. 추천 시스템은 "user가 아직 경험해보지 못했지만 좋아할법 한 item"을 추천해야 의미가 있다고 생각하기 때문에 정확한 item과 더불어 다양한 주제, 다양한 item을 추천해주는 것 또한 real-world 추천 시스템에서 중요하다고 합니다.
Diversity를 높이기 위해 다양한 종류의 item이 학습되도록, 또는 unpopular item이 학습되도록, 나아가 GAN, 강화학습, RNN 등을 이용한 다양한 연구들이 있습니다. div2vec에서는 이 중 unpopular item의 학습 기회를 transition probability를 조정함으로써 늘리는 방법을 사용합니다. 여담으로 대부분의 경우 baseline과 비교해서 accuracy를 소폭 희생하고 diversity를 많이 높였다던가, accuracy와 diversity 두 가지를 모두 향상시켰다는 결과로 논문이 나오는 것 같습니다.
Proposed method
이 논문에서는 현재 노드가 $v$일 때, 그 neighbor $N(v)$ 중 노드 $u$에 대한 transition probability를 다음과 같이 정의합니다. $deg(v)$는 노드 v의 degree입니다.
$\alpha(u) = \frac{f(deg(u))}{\sum_{w \in N(v)}f(deg(w))}$
논문에서는 $f(x)$로 $\frac{1}{x}, \frac{1}{\sqrt{x}}$ 두 가지를 사용합니다. 전자의 경우 div2vec, 후자의 경우 rooted div2vec이라고 이름을 붙였습니다. 간단하게 $N(v) = {a, b}, deg(a)=10, deg(b)=90$인 경우를 봅시다.
$div2vec : \alpha(a) = \frac{1/10}{1/10 + 1/90} = 0.9, \qquad \alpha(b) = \frac{1/90}{1/10 + 1/90} = 0.1$
$rooted\, div2vec : \alpha(a) = \frac{\sqrt{1/10}}{\sqrt{1/10} + \sqrt{1/90}} = 0.75,\quad \alpha(b) = \frac{\sqrt{9/10}}{\sqrt{1/10} + \sqrt{1/90}} = 0.25$
rooted div2vec보다 div2vec이 unpopular items을 더 많이 sampling하도록 transition probability를 조절합니다.
제가 학부연구생 때 했던 연구와 비교해보면, 저는 accuracy를 유지하면서 diversity를 높이기 위해 기존 random walk에 teleport를 끼워넣는 방식을 사용했는데, 이 연구는 그런 것 없이 degree가 낮은 node의 transition probability를 역수로 높여버립니다. 그러면 low degree node, 즉 덜 유명한 node만 엄청 학습되니까 popular한 node는 학습이 아예 안 되지 않냐구요? 제 생각입니다만, popular node는 기본적으로 N(v)에 등장할 확률이 높기 때문에 상쇄되는 것 같습니다. 논문의 Fig.2를 보면 그 효과를 알 수 있습니다.
DeepWalk의 경우 degree가 높은 node들이 대부분의 sampling 기회를 가져가버리는 것에 비해 rooted div2vec, div2vec으로 갈 수록 random walks 내 node frequency가 균등해지는 것을 확인할 수 있습니다. DeepWalk처럼 일부 노드만 매우 많이 샘플링 되는 경우, long-tail problem 문제를 야기할 수 있습니다. 실제로 MovieLens dataset을 이용한 결과에서, top-1 coverage를 보면 DeepWalk에 비해 div2vec이 2배 이상 높은 결과를 보여준다는 것을 볼 수 있습니다. DeepWalk에 비해 div2vec이 더 다양한 item을 학습시켜 실제 추천까지 해준다는 이야기겠죠.
Experiment
DeepWalk는 unweighted graph에서 이루어지기 때문에 이 논문 또한 MovieLens dataset을 binary data로 바꿔서 실험을 진행했습니다(평점 1~3 -> Negative, 4~5 -> Positive) 또한 unipartite graph 상에서 작동하기 때문에, user/item이라는 2 종류의 node가 있는 bipartite graph 상에서 RW를 진행하면 RW sequence가 U-I-U-I-... 이런 식으로 만들어질 것 같습니다.
추천 시스템을 만들 때 predicted rating matrix를 만들수도 있지만 link prediction 문제로 접근할 수도 있습니다. User, item embedding vector를 잘 만들고 그것들을 바탕으로 link가 있는지 없는지를 예측할 수 있습니다. node2vec에서 4가지 operator를 사용해서 이 문제를 풀었고, 본 논문도 비슷하게 실험을 진행한 것 같습니다. 개인적으로 experimental settings 부분이 잘 이해가 안 가는데, positive, negative embedding vector를 concatenate한다는 부분에서 혼동이 조금 옵니다.
*이 부분에 대해 저자분께서 댓글을 달아주셨습니다. Concatenate에 대한 설명이 있으니 이해가 안 가시는 분들은 참고하시면 좋을 것 같습니다.
Metric
Accuracy metric으로 AUC score, diversity metric으로 coverage(CO), entropy-diversity(ED), intra-list similarity(ILS)를 사용했습니다. Metric 중 몇 가지는 제 이전 포스팅(링크)에서 확인할 수 있고, 여기서는 entropy-diversity에 대해서만 보겠습니다. 수식은 다음과 같습니다.
$Entropy-Diversity = -\sum_{i}{(\frac{rec(i)}{k*U})ln(\frac{rec(i)}{k*U}})$
User U명에게 top-k recommendation을 한다고 할 때, i는 set(추천된 모든 아이템)의 개수, k*U는 총 추천 횟수, rec(i)는 item i를 추천받은 사람의 수를 의미합니다. 다양한 아이템이 추천될수록 entropy-diversity의 값이 올라간다고 이해할 수 있습니다.
User 1, 2가 있고, Item a, b, c, d가 있습니다. 첫 번째 모델은 user 2명에게 모두 a, b를 추천했고, 두 번째 모델은 user 1에게 a, b를, user 2에게 c, d를 추천했습니다. 이 때 두 모델의 entropy-diversity는 다음과 같이 구할 수 있습니다.
$model\, 1\, :\, -(\frac{2}{4}ln\frac{2}{4})*2 + 0*2 = ln2$
$model\, 2\, :\, -(\frac{1}{4}ln\frac{1}{4})*4 = ln4$
이렇게 model 2가 더 diverse하다고 이야기할 수 있습니다.
Result
다음 표는 DeepWalk, node2vec, div2vec, rooted div2vec의 offline evaluation 결과입니다. Metric(k)에서 k는 top-k recommendation을 의미합니다.
div2vec이 rooted div2vec보다 popular item에 대한 억제가 더 많이 들어간다는 것을 확인했었습니다. 우선 정확도 metric인 AUC 측면에서는, 일관되게 div2vec < DeepWalk, node2vec < rooted div2vec인 것을 확인할 수 있습니다. Accuracy만을 목적으로 하는 모델보다 적당한 diversity를 추구할 때 accuracy가 실제로 더 올라가지만, 너무 제약을 많이 걸면 accuracy가 떨어진다고 해석할 수 있습니다. 아무래도 accuracy와 diversity는 trade-off 관계니까요. 반면 3종류의 diversity metric에서는 k=1, 10인 경우에는 div2vec이, k=50인 경우에는 rooted div2vec이 비교적 앞서는 것을 확인할 수 있습니다.
주목할 점은, AUC score 측면에서는 비록 일관되긴 하지만 모델 간 큰 차이가 없는 반면, diversity 측면에서는 div2vec, rooted div2vec이 DeepWalk, node2vec을 대부분 크게 앞선다는 것입니다. ILS에서 일부 node2vec이 더 좋은 점수를 보여주긴 합니다만, "다양한 사람에게 다양한 아이템을 추천하는 것"을 평가하는 지표인 ED에서 기존 모델에 비해 높은 점수를 보여줍니다.
짧은 후기?
Diverse recommendation을 하기 위한 다양한 시도들이 있는데, 아무래도 unpopular items, newbie는 활동 기록 자체가 적기 때문에 학습 시 sampling될 확률이 적은 것이 사실입니다. 그래서 unpopular items,users를 더 많이 sampling해서 학습하도록 연구를 했었는데, 제가 생각했던 것보다 더 강력하게 제약을 걸어도 적은 accuracy 손실로 꽤 큰 diversity 효과를 볼 수 있다는 결과를 보여준다고 합니다.
Deepwalk의 transition probability를 바꾸는 방식이라서 그런지, 1~5점 scale의 movielens 평점을 4점을 기준으로 그 이상은 positive, 미만은 negative로 두었습니다. User 입장에서는 4점보다 5점을 준 item을 더 좋아할테니 평점 그 자체를 edge의 weight로 두고 반영하도록 random walk를 조정할 수 있을 것 같습니다.
Online evaluation(Click UU, CTR) 부분도 있는데 언젠가 여유가 될 때 읽고 추가하겠습니다. 논문 읽어야지 하고 저장해둔 게 많은데, 이제서야 처음으로 읽고 정리를 하네요...
Reference
div2vec : arxiv.org/abs/2009.09588
DeepWalk : arxiv.org/abs/1403.6652