DGCN: Diversified Recommendation with Graph Convolutional Networks, (WWW'21)

Paper Link

Official Github

Abstract

Accuracy를 올리려는 연구는 많이 진행이 되었지만, user의 만족도와 관련된 diversity는 그렇지 않다.

Challenges

1. 대부분의 diversification은 candidate items을 생성한 뒤에 고려된다. 이처럼 decoupled design은 전체 system을 suboptimal한 방향으로 이끈다.
2. GCN은 복잡한 collaborative filtering을 효과적으로 modeling하여 accuracy를 올리지만, diversity를 무시한다.

Address

1. 본 논문에서는 decouple하지 않고, diversity를 고려하는 부분을 GCN을 활용해 candidate generation의 upstream으로 둘 것이다.
2. 저자들은 rebalaced neighbor discovering, category-boosted negative sampling, adversarial learning 활용해 diversity를 고려할 것이다.

1. Introduction.

Accuracy를 위한 추천 연구는 많이 진행되었지만, 정확한 추천이 반드시 만족스러운 것은 아니다. Accuracy를 높이는 추천에서는 information overload (정보 과부화) 문제는 완화되지만, 유사한 item이 추천된다는 information redundancy (정보 중복) 문제가 발생하게 된다. User의 만족도를 위해 relevance뿐만 아니라 freshness, diversity, explainability 등 다양한 요소가 고려되어야 한다. 이 중 diversity는 user의 참여(interaction)를 직접적으로 결정하는 요소이다.

이전 연구에서 Diversity를 고려하기 위해서 3가지 방법 제안되었다.

1. Post-processing
   • Re-rank 전략에서 candidate generation 후, heuristic하게 item 선택한다.
2. DPP (Determinantal Point Process)
   • Post-processing에서 heurstic 대신 DPP 사용한다.
   • 여전히 candidate generation 후, diversity process가 진행된다.
   • 이러한 구조에서 추천 성능은 candidate generation에서 학습된 user, item embedding에 많이 의존한다.
   • 또한 diversity signal이 candidate generation model에 반영되지 않기 때문에, 최종 추천 결과가 suboptimal되기 쉽다.
   • 즉, diversity를 올리면서 추천 성능을 유지할 수 있는 candidate가 생성될 가능성이 있는데, decouple되어 있다면 이것이 불가능하다.
   • 따라서 수용할 수 있는 정도의 accuracy 감소로 추천 결과를 diversifiy하는 지에 대한 불확실성이 있다.
3. LTR (Learning To Rank)
   • Decouple 문제점을 해결하기 위해 LTR을 제안하였다.
   • LTR은 candidate set 대신 ordered list of items를 생성한다.
   • 이 방법을 사용하기 위해 적절한 listwise dataset을 만들어야 하는데, 이 부분이 어렵다.
   • 즉, feasible datasets을 모으기 어렵다.

User와 items 사이의 interactions는 heterogeneous graph (a bipartite of users and items)로 표현할 수 있다. 그리고 higher order neighbors는 좀 더 다양한 items을 가지는 경향이 있다. 따라서 diversification을 graph에서 하는 것이 유리하고, 이를 통해 decouple되는 문제를 해결할 수 있다.

Accuracy를 위해 user가 많이 소비한 items category(graph 관점에선, user와 연결된 edge 중 대부분이 해당 item category로 이어진다.)에 속한 item을 추천하는 것은 당연하다. 따라서 diversity를 고려하지 않으면, high order connections는 dissimilar items을 자동으로 찾지 못한다. 하지만 대부분의 GCN based method는 diversity는 고려하지 않고, accuracy에만 집중하고 있다.

저자들은 GCN을 활용한 category diversification 방법인 DGCN (Diversified recommendation with Graph Convolutional Networks)을 제안한다.

Rebalanced neighbor discovering

• Disadvantaged categories, user가 많이 소비하지 않은 item categories,에 더 쉽게 접근한다.

Category-boosted negative sampling

• User가 소비한 items와 similar하지만 negative인 item이 더 많이 sampling 한다.
• 같은 category를 가지는 items 간의 선호도를 구별한다.

Adversarial learning

• 학습된 user embeddinge에 implicit category preference를 제외(distill)시킨다.

2. Preminaries

2.1. Diversity

추천에서 diversity는 intra-user level 또는 inter-user level로 구분된다.

• Inter-user level은 사용자 간 추천되는 items의 diversity이다. 예를 들어, decentration 또는 long-tail 추천이 이에 해당한다.
• Intra-user level은 한 명의 user에게 추천되는 items에 대한 diversity이고, 본 논문에서는 대부분의 diversity 논문과 같이 intra-user level diversity를 향상 시키는 것을 목표로 한다.

Diversity와 novelty(or serendipity: 우연한 발견)과 혼동되기 쉬우나, 차이점이 존재 한다. User가 구매한 items 중 70%가 전가 기기, 20%가 의류, 나머지 10%가 음료라고 하자. Diversity는 전자 기기를 10개 추천하는 것보다 전자기기 5개 이상, 의류 1~2개, 음료 1~2개를 포함한 추천을 말한다. 반면, novelty는 user에게 매력적이지만 스스로 깨닫지 못한 item(e.g., 책)을 추천해주는 것이다.

본 논문에서는 category diversification에 집중한다.

저자들은 diversity를 측정하기 위해 3가지 metric을 채택한다.

Coverage

• 추천된 item categories의 수.
• Coverage가 높을수록 diversity하다.

Entropy

• 추천된 item categories의 entropy.
• Entropy가 높을수록 diversity하다.

Gini index

• 경제학에서 사용되는 measure로 gini index가 1이면 소수의 사람이 다 해먹는 것이고, 0에 가까울수록 평등하다는 것이다.
• 특정 category에 속하는 item의 수는 해당 category의 wealth로 설명할 수 있다.
• Gini index가 0일수록 diversity하다.

2.2. Recommendation Pipeline

대부분 추천 시스템은 3가지 stage로 이뤄져 있다.

1. Matching (candidate generation)
   • Large item pool에서 수백 개의 items를 선택한다.
2. Scoring
   • Interaction 확률을 추정하고, 상위 수십 개의 items이 선택된다.
   • 복잡한 DNN을 사용해 accuracy를 높일 수 있는 items을 선택한다.
3. Re-ranking
   • 추가적인 constraints를 만족시키도록 선택된 items를 재배열한다.
   • Diversity를 고려하는 부분이다.

기존에 relevance와 diversity의 균형을 맞추기 위해 다양한 re-ranking 방법이 제안되었다. 하지만 re-ranking에서 diversification을 고려하는 것은 matching, scoring model과 independent하기 때문에 전체 시스템을 suboptimal하게 만든다. 또한, matching 단계에서 diversification signals를 인식하지 못하면 생성된 candidate items가 이미 redundant할 수 있어 diversity를 제한할 수 있다.

본 논문에서는 matching에서 diversity를 고려하는 end-to-end method를 제안한다.

2.3. Accuracy-Diversity dilemma

3. Method

3.1. Overview

1. Rebalanced Neighbor Discovering
   • Diverse한 items를 발견하기 위해 neighbors의 분포에 기반한 neighbor sampler를 설계한다.
   • 저자들은 disadvantaged categories의 item을 선택할 확률을 높인다.
   • Neighbor sampler의 guidance로 다양한 categories의 items에 더 쉽게 접근할 수 있다.
2. Category-Boosted Negative Sampling
   • Random negative sampling 대신 user가 선호하는 items와 유사하지만 negative인 items을 sampling한다.
   • 이를 통해 similar items 사이에서의 user 선호도를 결정할 수 있다.
3. Adversarial Learning
   • Category classification에 대한 min-max game을 수행한다.
   • GCN에서 만들어진 item embedding으로 해당 item category를 예측하지 못하도록 만든다. 즉, item embedding이 clustering되는 것을 방해한다.
   • 추천 성능을 유지하면서, clustering이 되지 못하도록 만든다.
   • 그렇기 때문에 user가 많이 소비하지 않은 item category에 속하지만, user가 좋아할만한 item이 user 근처에 위치하게 되고, 많이 소비했지만 좋아하지 않는 itme은 user와 멀어지게 된다.

3.2. GCN

(중략)

3.3. Rebalanced Neighbor Discovering

Large-scale users/items에 GCN을 적용시키는 것은 cost가 많이 든다. 그리고 전체 graph에서 mini-batch training을 구현하는 것은 어렵다. 그래서 효육적인 training을 위해 neighbor sampler로 sub-graph를 sampling한다.

Fig. 4는 random neighbor discovering의 toy example이다. Training 동안, users/items을 특정 수 (즉, batch size)만큼 seed nodes로 설정한다. 그리고 seed nodes의 neighbors를 random하게 sample해서 sub-graph를 만든다. GCN의 layer를 더 쌓을려고 한다면, recursive하게, sampling된 neighbors가 seed nodes가 되고 neighbors를 sampling한다. 이처럼 node sampling에서는 node 간의 edge는 연속된(consecutive) layers에만 존재하고, 이런 block이 여러 개 있는 sub-graph를 Node Flow라고 한다. GCN 연산은 block by block으로 수행된다.

User는 category에 따라 items를 인식한다. 예를 들어, 영화를 직접 보기 전엔 action, romance 등 영화 장르로 item을 판단하게 된다. 그렇기 때문에, user의 preference를 반영한 과거 interaction에는 user가 많이 소비한 categories (dominant categories)와 적게 소비한 categories (disadvantaged categories)가 존재하게 된다. Diversified 추천 시스템은 dominant categories의 items 뿐만 아니라 disadvantaged categories를 추천할 수 있어야 한다.

Random neighbor sampling으로 embedding을 학습하면, dominant items와 연결된 edge가 많으므로, user embedding은 dominant categories의 item embeddings와 너무 가깝게 될 가능성이 있다. 이는 disadvantaged categories를 가지는 item이지만, user가 선호할 수 있는 item이 retrieve될 가능성을 낮춘다.

본 논문에서는 category diversification을 고려하는 neighbor sampling process인 rebalanced neighbor sampling을 제안한다. 간단히 말하면, dominant categories인 items가 sampling될 확률을 낮추고 disadvantaged categories인 items이 sampling될 확률을 높인다. 방법 또한 간단하다.

User node가 seed node일 때, rebalanced sampling을 한다.

1. Dominant, disadvantaged categories를 찾기 위해, user의 neighbor items를 바탕으로 category histogram을 만는다.
2. Histogram 값의 역수를 각 item이 sampling될 확률로 설정한다.
3. Rebalance weight $\alpha$로 bias를 control한다. $\alpha$ 값이 크면 disadvantaged categories를 많이 뽑는다.

Disadvantaged items가 더 많이 뽑히게 되면서, user embeddings는 다양한 categories의 item embedding 정보를 얻는다. 따라서 학습된 user embedding은 disadvantaged category items의 embedding과 비교적 가까워지게 된다.

3.4. Category-Boosted Negative Sampling

Accuracy를 높이기 위한 negative sampler를 설계하는 다양한 연구들이 있지만, diversity를 고려한 것은 거의 없다. 본 논문에서는 같은 category (positive category)에 속하는 items이지만 negative인 items(similar but negative)을 sampling한다. Positive categories에서 negative item을 sampling 함으로써, model은 같은 categories의 items내에서 user의 선호도를 구분하게 된다. 즉, 같은 categories에 있는 negative item은 retrieve될 가능성이 낮아져 더 다양한 categories의 item이 추천될 가능성이 높아진다. Hyper-parameter $\beta$가 클수록, positive category에서 negative item을 sampling될 확률을 높인다.

이를 통해 user/item embedding이 더 세밀하게 (finer) 학습되어, 추천 시스템이 더 다양한 categories에서 user의 관심사를 capture할 수 있다.

Fig. 5에서 볼 수 있듯이, negative item 중 positive category인 item이 더 많이 sampling되어 negative category에서 positive items이 추천될 가능성이 높아져 더 다양한 후보가 생성된다.

3.5. Adversarial Learning

대부분의 추천 models은 accuracy만 고려하는 objective function을 사용하면서 diversity는 무시한다. Accuracy만 고려한다면, user의 interaction datas로부터 category 선호도가 implicit하게 학습된다.

Category 선호도가 implicit하게 학습된다는 것에 대한 citation이 없다. 일단 받아드리고 넘어가자.

이로 인해, 같은 category 내의 다른 items에 대한 user의 선호도를 학습할 수 없다. Implicit하게 capture된 category 선호도를 제거하지 않으면, dominant categories의 items이 더 많이 추천되어 user에게 다양한 item이 노출될 기회가 제한된다.

GANs에 영감을 받아, 저자들은 item category classification에 관한 adversarial task를 추가해서 category 선호도를 없애고 diversity를 강화한다.

• 학습된 item embedding으로 item category를 예측하는 classifier를 학습한다.
• Recommendation model은 classifier를 속이는 방향으로 item embeddings을 만들어야 한다.

Training sample로는 $(u, i, y, c)$를 사용한다. $y$는 user $u$와 item $i$가 interaction이 있으면 1, 없으면 0이다. $c$는 item $i$의 category id를 나타낸다.

저자들은 classifier로 fully connected layers를 사용하고 cross entropy loss로 optimization을 진행한다.

\[\begin{split} \hat{c} &= Wh_i^K \in \mathbb{R}^{|C|}\\ L_c(i, c) &= -\hat{c}[c] + log\big(\sum_j\text{exp}(\hat{c}[j])\big) \end{split}\]

• Category의 ground truth vector는 one-hot vector이다.
• 그리고 log softmax를 사용하면, $L_c$는 위와 같이 정의된다.

추천 model에는 많이 사용되는 log loss를 사용한다.

\[\begin{split} \hat{y} &= <h_u^K, h_i^K> \\ L_r(u,i,y) &= -[y\cdot\text{log }\sigma(\hat{y}) + (1-y)\cdot\text{log }\sigma(1-\hat{y})] \end{split}\]

• $h_u^K, h_i^K$는 GCN으로 학습된 embedding이다.

Adversarial learning에서 classifier는 $L_c$를 최소화하고, 추천 model은 $L_r - \gamma L_c$를 최소화한다. Classifier는 같은 category를 가지면, item embeddings로 clusters를 할 수 있는 방향으로 학습된다. 그리고 추천 model은 user의 선호도를 학습하지만, item embeddings로 cluster를 형성 못하는 방향으로 학습된다.

구현 관점에서 adversarial learning은 DAN(Domain Adaptation Networks)에서 사용된 GRL(Gradient Reversal Layer)을 활용한다. GCN에서 GCN으로 학습한 item embedding과 classifier 사이에 GRL을 삽입한다. GRL은 gradient에 negative constant를 곱해주는 간단한 것이다.

\[\begin{split} \theta_G &\leftarrow \theta_G - \alpha\bigg(\frac{\partial L_r}{\partial \theta_G} - \gamma\frac{\partial L_c}{\partial \theta_G}\bigg) \\ \theta_c &\leftarrow \theta_C - \alpha\bigg( \frac{\partial L_c}{\partial \theta_c} \bigg) \end{split}\]

• $\theta_G$는 user, item embeddings를 의미한다.
• $\theta_c$는 classifier의 weight인 $W$를 의미한다.

이러한 adversarial learning을 통해 category-level 선호도는 없앤 user, item embeddins를 학습하게 된다. 그렇기 때문에 embedding space 상에서 disadvantage category에 속하지만 user가 선호할만한 item이 user와 가깝게 위치하게 된고, dominant category에 속하지만 user가 비선호할만한 item은 user와 멀어지게 된다.

4. Experiments

자세한 것은 논문을 참고하자.

Diversity를 고려하지 않은 GCN에 비해 추천 성능은 떨어지지만, diversity 성능은 높다. 이전 방법인 DPP보단 성능과 diversity가 모두 높다.

GRL의 유무로 adversarial에 대한 ablation study이다. GRL 없이 classifier가 있는 GCN을 학습하면 accuracy는 GCN보다 높지만, diversity가 낮다.

• GRL이 없으면, 학습된 item embedding은 embedding space에서 같은 category의 item이 cluster를 형성된다.
  • 이는 classifier의 accuracy로 확인된다.
  • 그리고 cluster를 더 잘 형성하게 되면서, 단순 GCN을 사용하는 것보다 accuracy가 높아졌다.

    이는 user가 category에 따라 items를 인식한다는 의견을 뒷받침 해주는 것 같다.

Diversity를 조절할 수 있는 hyper-parameter로 아래와 같은 것들이 있다.

• $\alpha$
  • Neighbor sampling에서 사용되는 것.
  • 높을수록 disadvantage categories에 속하는 item이 많이 sampling되어 diversity가 높아진다.
• $\beta$
  • Negative sampling에서 사용되는 것.
  • 높을수록 positive categories에서 negative item이 많이 sampling되어 diversity가 높아진다.