[논문리뷰] GDSRec : Graph-Based Decentralized Collaborative Filtering for Social Recommendation

https://arxiv.org/abs/2205.09948

GDSRec: Graph-Based Decentralized Collaborative Filtering for Social Recommendation

Abstract & Intro

해당 논문은 GNN을 활용한 일반적인 추천 기법에서 간과하고 있는 부분에 집중하여 새로운 방식을 제시하고 있다.

일반적인 GNN의 경우, Rating에 대해 고려할 때, 절대적인 수치(3점, 4점 등)에 대해서만 고려하기 때문에 user, item간의 평가에 대한 bias offset, 평점이 매겨진 주체(user, item)의 경향성에 대해 고려하지 않는다고 지적하고 있다.

 

예를 들어, 유저의 경우, 평소 평점을 짜게 매기는 유저가 평균적으로 2점의 평점을 매긴다고 할때 해당 유저가 어떠한 Item에 대해 3점의 평점을 매긴다면 긍정적인 신호로 여겨야하는 반면, 일반적으로는 그렇지 못한다는 점이다.

마찬가지로, 아이템의 경우, 어떤 아이템에 대한 평균 평점이 4.5점이라고 했을 때, 4점을 받은 경우는 좋은 평점이 아니라고 간주할 수 있다.

 

이런 경우에 user, item에 대한 representation이 제대로 반영되지 않을 수 있고 더 나아가 좋지 않은 추천 결과로 이어질 수 있다.

 

이를 해결하고자 FunkSVD, SVD++와 같은 모델이 제시되었지만, 해당 모델은 위에서 설명한 bias를 scalar값으로 처리하기 때문에 이와 같은 개념을 명확하게 모델링하기 어려우며, 각 Social-Connection은 서로 다른 영향력이 존재하기 때문에 이를 잘 구분해서 모델링하는 것이 최적의 결과를 이끌어 낼 수 있다.

 

그렇기 때문에 본 논문에서는 크게 세가지 특징을 토대로 GNN기반의 모델을 제안한다.

1. 본 논문에서는 bias를 scalar가 아닌, vector값으로 처리해 user/item representation을 구한다.
2. user/item bias에 대한 통계적인 의미를 잘 표현하기 위해, 'Decentralized interaction graph'를 사용한다.
3. user-user connection에 대한 정보(가중치)를 'preference similarity'를 사용해 재정의해 사용함으로써 social connection의 효과를 명확히 모델링한다.

Framework

Problem Formulation

해당 논문에서는 Rating Prediction task를 다루고 있으며,
$N$명의 유저($\mathcal{U} = \{ u_1, u_2, \text{ ... } u_N \}$)와 $M$개의 아이템($\mathcal{V} = \{ v_1, v_2, \text{ ... } v_M \}$)이 있을때의
user-item rating matrix $\mathbf{R} \in \mathbb{R}^{N \times M}$의 missing value를 전부 채우는 것이 목적이다.

https://arxiv.org/abs/2205.09948

위의 그림과 같이 그래프의 형태(Node / Edge)로 구성된 user-item rating matrix가 있다고 할 때, 그림 (b)는 $u_1$이라는 노드를 기준으로 보았을 때, 좌측은 'user-item graph'로 본 논문에서 표현하고 있으며, $u_1$과 interaction이 존재하는 item $v_2\text{, } v_4$가 존재하고, 각 edge에 표기된 값은 각 아이템에 대한 $u_1$의 rating으로 이해할 수 있다.

 

우측의 그래프는 'social graph'로 표현되며, $u_1$과 interaction이 존재하는 유저들인 경우에 연결되는 그래프이다. 각 유저에 연결된 edge의 값에 대해서는 본 논문에서 자의적으로 그 값을 계산해 부여하고 있으며 이를 'relationship coefficient'로 표현하고 있다.

 

Relationship Coefficient 값을 계산하는 수식은 다음과 같다.

$T_{ij} = 1+ \sum_{v_k \in \{R(u_i) \cap R(u_j)\}} \, I(\vert r_{ik} - r_{jk} \vert \leq \delta)$

$I(x) = \begin{cases} 1 & \text{if } x \leq \delta \\ 0 & \text{otherwise} \end{cases}$

 

여기서 $\delta$는 수식에서도 유추할 수 있듯, 동일한 아이템 $v_k$에 대해 서로 다른 두 유저$u_i, u_j$가 얼마나 비슷한 취향을 가지고 있는지 판별하는 threshold로 이해할 수 있다.

 

Coefficient에 대한 수식을 해석해보면, 서로 다른 유저 i,j간에 공통된 아이템의 집합 $v_k$에서 각 아이템 별로 두 유저 i,j가 부여한 평점의 차이가 일정 수준 이하인 경우(서로 다른 유저가 한 아이템에 대해 비슷하게 평가한 경우)의 합을 coefficient로 사용한다고 볼 수 있다.

 

다시 그림 (b) social graph와 (a)를 살펴보면, $\delta =1$이라고 했을 때, $T_{12} = 2, T_{14} = 0$인 것을 확인해볼 수 있다.

본 논문에서는 Rating Prediction task를 위해 위의 그림(b)와 같은 구조의 데이터를 사용하게 된다.

General Framework

https://arxiv.org/abs/2205.09948

위의 그림에서 볼 수 있듯, 일반적으로는 좌측의 이분 그래프로 유저-아이템의 Interaction을 나타내지만, 이러한 방식은 실제 유저의 선호도에 대한 정보를 왜곡시킬 수 있다. (e.g. 까다로운 유저)

 

따라서 이러한 문제를 해결하기 위해 본 논문에서는 원래의 이분 그래프(bipartite graph)를 'decentralized graph'(우측 그래프)로 변환해 사용하도록 한다.

 

유저-아이템 interaction의 경우, 각 interaction마다 연결되는 유저/아이템에 대한 mean average를 rating에서 뺀 값을 사용하고, 유저-유저의 social interaction의 경우에는, 위에서 정리한 'relationship coefficient'를 그대로 사용한다.

https://arxiv.org/abs/2205.09948

위의 그림은 전체 모델의 구조를 도식화한 것으로, 이를 통해 볼 수 있듯이 모델은 크게 4가지 구조로 이루어져 있다.

• User Modeling
• Item Modeling
• Social Modeling
• Preference Rating Prediction

Rating Prediction을 제외한 세가지 구성요소들은 각각에 대한 representation latent factor를 모델링하는 것을 목표로 하고 있으며, 이를 위한 방식은 큰 틀 안에서 서로 비슷하다.

 

Rating Prediction은 위에서 설명한 'decentralized graph'에 대한 정보를 활용해 이루어지며, 그 계산은 다음과 같이 이루어진다.

 

$\hat{r}_{ij} = \frac{1}{2} [E(u_i) + E(v_j)] + f(u_i, u_j)$

 

여기서, $E(u_i), E(v_j)$는 각각 유저와 아이템에 대한 rating의 평균값을 의미하며, $f(u_i, v_j)$는 유저-아이템에 대한 최종 선호도(final preference rating)를 의미한다.

 

final preference rating을 구하기 위한 수식은 다음과 같은데,

$f(u_i, v_j) = \frac{1}{2}(r^{p}_{ij} + \sum_{u_k \in N(u_i)} \lambda_{ik} r^{p}_{kj})$

 

이 수식을 통해 이해할 수 있는 것은, final preference rating이란 단순히 유저-아이템에 대한 rating을 사용하는 것이 아니라 어떠한 유저가 아이템에 대해 rating을 매겼을 때,

해당 유저와 socially connected된 유저들의 해당 아이템에 대한 평가 정보를 참조해 사용하게 되므로 유저-아이템에 대한 정보 뿐만 아니라 social 정보 역시 고려한 개념이라고 이해할 수 있다.

 

여기서 $E(u_i), E(v_j)$에 대한 정보는 쉽게 얻을 수 있으므로, 관건은 $r^{p}_{ij}$를 구하는 것이다.

 

본 논문의 모델에서는 이를 구하기 위해 user/item/social representation(latent factor)를 사용하므로 이를 적절히 구하기 위한 방식을 이해하는 것이 중요하며, 

 

특히, 새로운 유저나 아이템이 등장해 이에 대한 정보가 없어 기존의 방식으로 preference rating을 구할 수 없는 경우(Cold-Start)에

본 논문에서는 해당 유저/아이템에 대한 평균 rating값을 활용하도록 제시하고 있다.

User Modeling

위에서 언급했듯, rating prediction을 위해서는 유저, 아이템, social relationship에 대한 각각의 representation(latent factor)를 구해야 하므로, 우선 User에 대해 먼저 알아보도록 하겠다.

 

위에서 설명했듯, rating의 절대적인 값을 그대로 사용하게 되면 정확한 해석이 되지 못할 여지가 있으므로(e.g. 까다로운 유저) User modeling에서는 $\bar{r}_{ij} = \lceil {\vert r_{ij} - E(v_j) \vert} \rceil$의 값을 사용한다.

 

이렇게 계산된 값에 대해 embedding lookup table을 생성하고, user latent factor($h_{u_i}$)를 계산하기 위해 table에서 추출된 embedding vector를 사용한다.

 

$\mathbf{h}_{u_i} = \text{Tanh}(\mathbf{W} \cdot G_I(\{ \mathbf{x}_{il}, \forall v_l \in R(u_i) \} + \mathbf{b})$

 

여기서, $\mathbf{x}_{il}$은 유저와 아이템 간의 'rating difference aware representation vector'로서 간단히 유저와 아이템 간의 rating에 대한 representation으로 이해할 수 있으며, 이는 다음과 같은 방식으로 구해진다.

 

$\mathbf{x}_{il} = L_U([ \mathbf{q}_{v_l} \oplus \mathbf{s}_{\bar{r}_{il}}])$

 

즉, rating difference에 대한 embedding vector와 item에 대한 embedding vector를 concatenate한 것을 input으로 삼아 MLP($L_U(\cdot)$)를 거친 Output vector가 representation $\mathbf{x}_{il}$이 되는 것이다

 

그리고 이 부분에서, 맨 앞부분에서 언급했던 'bias를 scalar가 아닌 vector로 사용해 representation을 구한다'라는 개념이 적용되고 있으며, $\bar{r}_{ij}$가 bias의 개념으로 사용된 것으로 이해할 수 있다.

 

또한, user representation을 위해서는 user와의 interaction이 존재하는 서로 다른 모든 item과의 관계에 대해 모델링 해야하는데, 이러한 Item aggregation을 위해서 aggregate functinon $G_I$를 사용하게 된다.

 

$G_I(\{ \mathbf{x}_{il}, \forall v_l \in R(u_i) \}) = \sum_{v_l \in R(u_i)} \eta_{il} \mathbf{x}_{il}$

 

위와 같이 정의되는 aggregate function 내에 존재하는 $\eta_{il}$에 대해 주목할 필요가 있는데, 이는 한 유저가 상호작용한 서로 다른 아이템에 대한 weight를 나타내는 것으로, attention mechanism을 통해 구하게 된다. 

 

$\dot{\eta}_{il} = \mathbf{w}^{T}_{2} \cdot \text{ReLU}(\mathbf{W}_1 \cdot [\mathbf{x}_{il} \oplus \mathbf{p}_{u_i}] + \mathbf{b}_1) + b_2$

$\eta_{il} = \frac{\text{exp}(\dot{\eta}_{il})}{\sum_{v_l \in R(u_i)} \text{exp}(\dot{\eta}_{il})}$

 

위의 모든 식을 종합해 계산된 user latent factor $\mathbf{h}_{u_i}$는 다음과 같다.

 

$\mathbf{h}_{u_i} = \text{Tanh}(\mathbf{W} \cdot \{ \sum_{v_l \in R(u_i)} \eta_{il} \mathbf{x}_{il} \} + \mathbf{b})$

Item Modeling

Item aggregation을 통해 user latent factor를 구한 user modeling과 마찬가지로, item modeling은 user aggregation을 통해 item latent factor를 구해내는 과정이다.

 

user modeling에서 사용된 rating difference $\bar{r}_{ij}$과 마찬가지로 item modeling에서는 $\tilde{r}_{ij}$를 rating difference로 사용하며, 정의는 다음과 같다.

$\tilde{r}_{ij} = \lceil \vert r_{ij} - E(u_i) \vert \rceil$

 

그 뒤로 이어지는 과정은 user modeling의 그것과 유사하며, 정리해보자면 다음과 같다.

1. representation vector를 구한다.
   • user embedding($\mathbf{p}_{u_k}$)과 rating difference embedding($\mathbf{s}_{\tilde{r}_{kj}}$) vector사용
   • MLP($L_I(\cdot)$)를 거쳐 output vector 도출
   • $y_{jk} = L_I([\mathbf{p}_{u_k} \oplus \mathbf{s}_{\tilde{r}_{kj}}])$
2. 구해진 representation vector를 aggregation function($G_U(\cdot)$)의 input으로 사용해 계산된 값에 대한 Linear Combination과 Non-linear activation function($\text{Tanh}$)를 거쳐 item latent factor($\mathbf{h}_{v_j}$) 도출
   • $\mathbf{h}_{v_j} = \text{Tanh}(\mathbf{W} \cdot G_U(\{ \mathbf{y}_{jk}, \forall u_k \in R(v_j) \} + \mathbf{b}))$
   • $G_U(\{ \mathbf{y}_{jk}, \forall u_k \in R(v_j) \}) = \sum_{u_k \in R(v_j)} \xi_{jk} \mathbf{y}_{jk}$
   • $\xi_{jk} = \frac{\text{exp}(\dot{\xi}_{jk})}{\sum_{u_k} \in R(v_j) \text{exp}(\dot{\xi}_{jk})}$
   • $\dot{\xi}_{jk} = \mathbf{w}^{T}_{2} \cdot \text{ReLU}(\mathbf{W}_1 \cdot [\mathbf{y}_{jk} \oplus \mathbf{q}_{v_j}] + \mathbf{b}_1 + b_2)$
3. Item latent factor
   • $\mathbf{h}_{v_j} = \text{Tanh}(\mathbf{W} \cdot \{ \sum_{u_k \in R(v_j)} \xi_{jk}\mathbf{y}_{jk} \}+\mathbf{b})$

Social Modeling

Social Modeling은 User Modeling의 방식으로 계산된 user latent factor에 대해, 구하고자 하는 user와 social relationship이 존재하는 유저들의 latent factor의 집합을 나타낸다.

$\{ \mathbf{h}_{k}, \forall u_k \in N(u_i) \}$

Rating Prediction

위의 세가지 구성요소(user / item  / social latent factor)를 구하고 나면 다음과 같은 과정을 거쳐 Preference Rating 값을 예측해낼 수 있게 된다.

 

$\mathbf{z}_1 = \text{Tanh}(\mathbf{W}_1 \cdot [\mathbf{h}_{u_i} \oplus \mathbf{h}_{v_j}] + \mathbf{b}_2)$

$\mathbf{z}_2 = \text{Tanh}(\mathbf{W}_2 \cdot \mathbf{z}_1 + \mathbf{b}_2)$

$r^{p}_{ij} = \mathbf{w}^{T} \cdot \mathbf{z}_2$

 

이렇게 구해진 preference rating값을 활용해 위에서 언급한 수식을 한번 더 거쳐 최종적인 예측값을 구하게 된다.

 

$f(u_i, v_j) = \frac{1}{2}(r^{p}_{ij} + \sum_{u_k \in N(u_i)} \lambda_{ik} r^{p}_{kj})$

$\hat{r}_{ij} = \frac{1}{2} [E(u_i) + E(v_j)] + f(u_i, u_j)$

Model Training

본 논문에서는 고안된 모델을 Rating prediction, Ranking의 두가지 task를 기반으로 평가한다.

 

Objective Function

• Rating Prediction
  • MSE
• Ranking
  • BCE(binary cross entropy)

Optimizer

• RMSProp

추가적으로, overfitting을 방지하기 위해 'node dropout strategy'를 사용한다.

 

유저당 interaction의 imbalance가 존재할 수 밖에 없기 때문에, 이로 인해 특정 유저에 overfitting되는 것을 방지하기 위해 Dropout을 적용하게 되며,

최초에는 전체 비율에 따라 node를 제거하는 dropout을 고려하였지만 이미 수가 너무 적은 경우에는 overfitting 방지에 크게 효과가 없을 것이므로, 노드당 K개의 interaction을 보존하고 dropout을 진행하는 방식을 채택하고 있다.

Time Complexity

$O(((N+M)K + \langle \mathcal{O} \rangle)D)$

Evaluation Metric

Rating Prediction

• RMSE, MAE

Ranking

• Recall@5, NDCG

Parameter Settings

Train/valid/test Ratio

• $[x / \frac{(1-x)}{2} / \frac{(1-x)}{2}] \text{ where, } x \in [60,80]$

Threshold

• $\delta \in [0,1,2,3]$

Embedding Size

• $D \in [16, 32, 64, 128, 256, 512]$

Interaction node reservation

• $K \in [5, 10, 15, 20]$ : Ciao
• $K \in [15, 20, 25, 30]$ : Epinions

Learning Rate

• $\text{lr} \in [10^{-6}, 10^{-5}, 10^{-4}, 5 \times 10^{-4}]$

Batch size

• $\text{batch size} \in [64, 128, 256]$

Early Stopping

• Stop if sum of MAE and RMSE increases 10 successive epochs on validation set

Initialization

• Uniform Distribution