[논문리뷰] Graph Neural Networks for Social Recommendation

https://arxiv.org/abs/1902.07243

Graph Neural Networks for Social Recommendation

Abstract & Intro

구조적으로 데이터의 node information과 위상학적 구조를 표현할 수 있는 GNN은 Graph data에 대해 탁월한 성능을 보이며, user-user & user-item간의 관계인 graph data로 표현할 수 있는 social data에 대한 recommender system의 발전에 크게 기여할 수 있을것으로 보인다.

 

하지만, Social Recommender System을 GNN으로 구현하기 위한 데이터를 만드는데 몇가지 해결해야할 부분이 존재한다.

• 'the user-item graph encodes both interactions and their associated opinions'
  • 단순한 user-item interaction외에, Interaction에 대한 user의 평가도 고려해야함
    • A라는 user가 아이템 B를 좋아하고, 아이템 C를 싫어함 
  • user-item interaction 정보와 관련된 side information(user & item information)등을 고려해야함
• 'social relations have heterogeneous strengths'
  • 각 relation마다 서로 다른 영향력을 가지고 있음
    • 매우 가까운 관계와 형식적인 관계의 구분이 명확하지 않은 경우가 많음
    • 이 관계를 잘 구분해서 모델링 하였을 때, 더 좋은 결과를 이끌어 낼 수 있음
• 'users involve in two graphs'
  • user-user & user-item

필자는 이러한 문제점을 동시에 결합적으로 다루기 위해 GraphRec을 제안한다.

2. The Proposed Framework

Definitions and Notations

• $U = \{u_{1},u_{2},...,u_{n}\}$
  • Set of users
• $V = \{v_{1},v_{2},...,v_{n}\}$
  • Set of items
• $R \in \mathbb{R}^{n \times m}$
  • Rating Matrix
  • N users
  • M items
  • $r_{ij} =\begin{cases} 
    0 & \text{if } \text{unknown} \\ 
    1 & \text{if } \text{known} 
    \end{cases}$
    • user's opinion
  • $ O = \{\langle u_{i},v_{j} \rangle\ \vert r_{ij} \neq 0 \} $
    • set of known ratings
  • $ \tau = \{\langle u_{i},v_{j} \rangle\ \vert r_{ij} = 0 \} $
    • set of unknown ratings
  • $N(i)$
    • $u_i$가 직접적으로 연결된 유저들의 집합
  • $C(i)$
    • $u_i$가 직접적으로 연결된 아이템들의 집합
  • $B(j)$
    • $v_j$와 직접적으로 연결된 유저들의 집합
  • $T \in \mathbb{R}^{n \times n}$
    • user-user Matrix
    • $T = \begin{cases} 1 & \text{if } \text{connected} \\ 0 & \text{if } \text{not connected} \end{cases}$
  • $p_i \in \mathbb{R}^{d}$
    • 유저 $u_i$에 대한 embedding vector
  • $q_i \in \mathbb{R}^{d}$
    • 아이템 $v_j$에 대한 embedding vector

An Overview of the Proposed Framework

https://arxiv.org/abs/1902.07243 : GraphRec Architecture

모델은 다음의 3가지 구조로 이루어져있다.

• User modeling
  • User에 대한 latent factor를 학습
  • Item aggregation(user-item)과 social aggregation(user-user)에 대한 정보를 결합함으로써 User latent factor를 얻어낸다.
• Item modeling
  • Item에 대한 latent factor를 학습
  • user aggregation(user-item opinion)활용
• Rating Prediction

User Modeling

User ${u_i}$에 대한 latent factor의 notation은 다음과 같다.

• $h_{i} \in \mathbb{R}^{d}$

이 부분에서 중요한 점은 어떻게 user-item과 user-user의 Graph를 결합하냐는 것인데,

위에서 잠시 언급한대로 'item aggregation'과 'social aggregation'을 활용해 user latent factor를 얻게된다.

Item Aggregation

• user-item graph로 부터 Item을 기준으로한 user latent factor $h_{i}^{I} \in \mathbb{R}^{d}$를 구한다.
• user-item interaction과 Opinion을 복합적으로 고려하기 위해, 다음과 같은 수식을 사용해 latent factor를 계산
  • $h_{i}^{I} = \sigma(W \cdot \text{Aggre}_{\text{items}}(\{\mathbf{x}_{ia}, \forall a \in C(i)\})+b)$
    • $\sigma$ : Non-linear activation function
    • $W, b$ : Weights and biases
    • $C_i$ : $u_i$와 연결된 item set
    • $\mathbf{x}_{ia}$ : user $u_i$의 item $v_a$에 대한 opinion을 나타내는 vector
      • Rating에 대한 embedding $e_r$과 item embedding $q_a$를 MLP $g_{v}$를 통해 결합한
        'opinion-aware interaction representation'
      • $\mathbf{x}_{ia} = g_{v}([q_{a} \oplus e_{r}])$
      • Item Embedding vector와 Rating Embedding vector의 concat vector에 MLP를 거친 것
    • $\text{Aggre}_{\text{items}}$ : item aggregation function
      • $\{\mathbf{x}_{ia}, \forall a \in C(i) \}$, 'opinion-aware interaction representation' vector들의 Mean vector
      • $\text{Aggre}_{\text{items}}(\mathbf{x}_{ia}) = \sum_{a \in C(i)} \alpha_{i} \mathbf{x}_{ia} \text{, where } \alpha_{i} = \frac{1}{\vert C(i) \vert}$
      • 최초에는 위와 같은 단순 평균을 사용하도록 고안하였지만, user와 다양한 item간의 서로 다른 영향력을 고려할 수 없다는 단점이 존재해 , 전체 item set의 크기인 $\alpha_{i}$ 대신 attention network를 통해 구해진 item attention $\alpha_{ia}$를 사용
  • Item Attention & Attention Network
    • $\alpha_{ia}^{*} = \mathbf{w}^{T}_{2} \cdot \sigma(\mathbf{W}_{1} \cdot [\mathbf{x}_{ia} \oplus \mathbf{p}_{i}] + \mathbf{b}_{1}) + b_{2}$
    • 위의 연산을 통해 얻어진 $\alpha^{*}_{ia}$의 softmax 함수 output값이 $\alpha_{ia}$가 계산된다
    • $\alpha_{ia} = \frac{exp(\alpha^{*}_{ia})}{\sum_{a \in C(i)} exp(\alpha^{*}_{ia})}$

Social Aggregation

Social(user-user) graph로 부터 Social Relationship을 기준으로한 user latent factor $h_{i}^{S} \in \mathbb{R}^{d}$를 구한다.

 

Social-space에 대한 user latent factor는 다양한 user간의 관계와 그 영향력을 모델링 할 수 있어야 하기 때문에, Attention Mechanism을 적용해 이를 나타낸다.

 

따라서, Social-space user latent factor는 다음과 같이 나타낼 수 있다.

$h^{S}_{i} = \sigma(\mathbf{W} \cdot \text{Aggre}_{\text{neigbhors}} (\{h^{I}_{o}, \forall o \in N(i) \}) + \mathbf{b})$

 

위 식에 따르면, social-space latent factor를 구하기 위해서

1. item-space user latent factor에 대한 계산이 선행되어야 하며, 
2. $\text{Aggre}$ 함수는 item-space factor 계산에 사용된 것과 마찬가지로 attention mechanism을 활용해 계산한다.

$h^{S}_{i} = \sigma( \mathbf{W} \cdot \{ \sum_{o \in N(i)} \beta_{io} h^{I}_{i} \} +\mathbf{b})$

 

$\beta^{*}_{io} = \mathbf{w}^{T}_{2} \cdot \sigma(\mathbf{W}_1 \cdot [h^{I}_{o} \oplus \mathbf{p}_{i}] + \mathbf{b}_{1} ) + b_2$

 

$\beta_{io} = \frac{exp(\beta^{*}_{io})}{\sum_{o \in N(i)} exp(\beta^{*}_{io})}$

 

User Latent Factor

이렇게 구해진 두 latent factor를 결합해 하나의 user latent factor $h_{i} \in \mathbb{R}^{d}$를 구한다.

 

User Latent Factor는 위의 과정으로 구해진 item-space & social-space latent factor를 concatenate한 vector를 MLP의 input으로 사용하게 된다.

 

$c1 = [h^{I}_{i} \oplus h^{S}_{i}]$

$c2 = \sigma(\mathbf{W}_2 \cdot + \mathbf{b}_2)$

$\text{ ... }$

$h_i = \sigma(\mathbf{W}_{l} \cdot \mathbf{c}_{l-1} + \mathbf{b}_{l})$

---

Item Modeling

User Modeling과 마찬가지로, Item $v_{j}$에 대한 latent factor $\mathbf{z}_{j}$를 구하는 것이 목적이다.

 

위에서 다뤘던 item-space latent factor를 구할때와 마찬가지로, item에 대한 latent factor는 user-item interaction과 이에 대한 opinion의 관계를 복합적으로 설명하는 것이 중요하다.

 

따라서, 본 논문에서는 'User Aggregation'을 소개하고 있는데, 이는 위의 'Item Aggregation'과 주체만 바뀐것일 뿐 그 과정과 논리는 동일하다.

User Aggregation

Item $v_{j}$와 연관된 user set $B(j)$의 각 user별로 item에 대해 상이한 opinion을 가지고 있을수 있으며, 이를 적절히 활용하는 것이 특정 item에 대한 latent factor를 구하는데 중요할 것이다.

 

user $u_{t}$가 item $v_{j}$에 대해 $r$이라는 opinion으로 평가를 했다고 할때, 이를 opinion-aware interaction user representation $\mathbf{f}_{jt}$로 나타내고자 하며, 이는 위에서의 $\mathbf{x}_{ia}$와 유사한 개념으로 볼 수 있다.

 

마찬가지로, $\mathbf{f}_{jt}$는 user embedding $\mathbf{p}_{t}$와 opinion embedding $\mathbf{e}_{r}$을 concatenate한 vector에 대해 MLP를 거쳐 계산된 Output으로 구할 수 있다.

 

$\mathbf{f}_{jt} = g_{u} ([ \mathbf{p}_{t} \oplus \mathbf{e}_{r} ])$

 

(복습해보자면, $\mathbf{x}_{ia} = g_{v}([q_{a} \oplus e_{r}])$)

 

Item Latent Factor

최종적으로, Item Latent Factor $\mathbf{z}_{j}$를 구하기 위해, item $v_{j}$와 연관된 모든 유저 $\forall t \in B(j)$에 대한 모든 opinion-aware interaction representation을 구하고,$\text{Aggre}_{\text{users}}$ 함수를 통해 모든 representation을 Aggregate하게 된다.

 

$\mathbf{z}_{j} = \sigma( \mathbf{W} \cdot \text{Aggre}_{users} (\{ \mathbf{f}_{jt}\text{, } \forall t \in B(j) \}) +\mathbf{b} )$

 

마찬가지로, $\text{Aggre}_{\text{users}}$ 함수 내에서는 Attention Mechanism을 사용해 각 representation마다 동일한 가중치를 적용하지 않고 서로 다른 가중치를 적용해 Weighted Sum을 취하게 된다.

 

$\mathbf{z}_{j} = \sigma(\mathbf{W} \cdot \{ \sum_{t \in B(j)} \mu_{jt} \mathbf{f}_{jt}\} + \mathbf{b})$

$\mu^{*}_{jt} = \mathbf{w}^{T}_{2} \cdot \sigma( \mathbf{W}_{1} \cdot [\mathbf{f}_{jt} \oplus \mathbf{q}_{j}] +\mathbf{b}_{1} ) + b_{2}$

$\mu_{jt} = \frac{exp(\mu^{*}_{jt})}{\sum_{t \in B(j)} exp(\mu^{*}_{jt})}$

---

Rating Prediction

위에서 계산된 user latent factor $\mathbf{h}_{i}$와 item latent factor $\mathbf{z}_{j}$를 활용해 Rating Prediction을 진행하게 된다.

 

1. Concatenate(Input)
   • $\mathbf{g}_{1} = [\mathbf{h}_{i} \oplus \mathbf{z}_{j}]$
2. MLP(Hidden State)
   • $l$개의 layer가 존재(output layer 포함)하는 MLP라고 했을 때, 다음과 같다.
   • $\mathbf{g}_{2} = \sigma(\mathbf{W}_{2} \cdot \mathbf{g}_{1} + \mathbf{b}_{2})$
   • $\text{ ... }$
   • $\mathbf{g}_{l} = \sigma(\mathbf{W}_{l} \cdot \mathbf{g}_{l-1} + \mathbf{b}_{l})$
3. Rating Prediction(Output)
   
   • $r^{'}_{ij} = \mathbf{w}^{T} \cdot \mathbf{g}_{l-1}$

Model Training

GraphRec의 Task는 Rating Prediction이므로, 주로 Loss Function은 MSE를 사용하게 된다.

이를 조금 변형해 본 논문에서는 다음과 같은 Loss Function을 사용한다.

$\text{Loss} = \frac{1}{2\vert \mathcal{O} \vert} \sum_{i,j \in \mathcal{O}} {(r^{'}_{ij} - r_{ij})}^{2}$

$\text{, where } \mathcal{O} \text{ is # of observed Ratings}$

 

이와 같은 Objective(Loss) Function을 기반으로, 해당 논문에서는 vanilla SGD 대신, Random하게 데이터를 사용해 Gradient Update를 진행하는 RMSprop Optimizer를 사용하고 있다.

 

또한, [user, item, opinion]의 Embedding Vector의 경우에는 학습이 시작됨에 따라 Random하게 Initialize 되며,

Opinion Embedding은 사용되는 데이터의 Rating Scale에 따라 다르게 결정된다. 예를 들어, N개의 Rating(1~N까지의 점수)인 경우에는 N개의 Vector를 Initialize하게 된다.

 

마지막으로, 학습중 Overfitting을 방지하기 위해서 Dropout을 사용하고 있다.

Hyper-params in Training(Baseline)

• Train/Valid/Test set Ratio
  • 각각 $x$%, $(1-x)/2 $%, $(1-x)/2$%
  • $x \in [80, 60]$
• Embedding Size($d$)
  • $d \in [8, 16, 32, 64, 128, 256]$
• Batch size
  • $\text{bs} \in [32, 64, 128, 512]$
• Learning rate
  • $\text{lr} \in [0.0005, 0.001, 0.005, 0.01, 0.05, 1]$
• Hidden layer dimension
  • Same as Embedding Size($d$)
• Activation Function
  • ReLU
• Number of Hidden Layers
  • 3
• Early Stopping
  • $\text{Tolerance} = 5$
• Parameter Initialization(For all NN methods)
  • Gaussian Distribution($\mu = 0 \text{ and } \text{std} = 0.1$)