STAM: A Spatiotemporal Aggregation Method for Graph Neural Network-based Recommendation (WWW'22)

Contents

• Introduction 
• Preliminaries and Problem
• Method
  • STAM
  • STAM for GNN-based Recommendation
  • Optimization with STAM

 

 

해당 논문은 기존 추천 관련 연구에서는 주로 Spatial 정보만을 고려하고 Temporal 정보는 고려하지 않는 문제점을 해결하고자, Spatial-Temporal Aggregation Method (STAM) 기법을 제안하였다. 

 

Introduction 

Graph Neural Network (GNN)의 성능이 우수한 것으로 검증된 후 Recommendation 분야에서는 주로 GNN 기법을 기반으로 추천 시스템을 구축하고 있다. Recommendation에 적용된 GNN의 Aggregation Function을 종합하면 1) Mean Pooling, 2) Degree Normalization, 3) Attentive Pooling, 4) Central Node Augmentation 으로 총 4개로 구성되어 있다. 그러나, 기존 GNN의 Aggreagtion Function은 중요한 정보인 Temporal 정보를 고려하지 않는다는 문제점이 존재한다. 다시 말해, 기존 GNN 기법은 Temporal 정보를 고려하지 않고, 오로지 Spatial 정보만을 고려하여 추천 시스템을 구축하고 있기 때문에 시간에 따라 변화하는 Dynamic Interest를 학습하는 것이 어렵다. 이와 같은 문제를 해결하고자 본 연구에서는 SpatioTemporal 정보를 고려한 Spatial-Temporal Aggregation Method (STAM) 기법을 제안한다. 

위 그림을 예로 들면, Sherry와 Amy는 동일한 제품을 클릭하였으나, Temporal 정보는 다른 것을 확인할 수 있다. Temporal 정보를 배제한 Spatio-based Aggregation에서는 일반적인 Graph를 통해 User Embedding을 도출하고, Spatiotemporal-based Aggregation에서는 Temporal 정보를 고려하여 STAM을 통해 User Embedding을 생성한다. 그런 다음, Candidate Item Embedding과 유사도를 계산하여 사용자에게 다음 제품을 추천하는 방식이다.

 

Preliminaries and Problem

GNN-based Recommendation은 1) Embedding Layer, 2) Embedding Aggregation Layer, 3) Embedding Propagation Layer, 4) Prediction Layer, 5) Joint Training으로 구성되어 있다.

 

먼저 Embedding Layer는 데이터를 입력으로 받고 사용자와 제품에 대한 Embedding을 생성하는 단계다. $E_{\mathcal{V}}\in {\mathbb{R}}^{N\times d}$와 $E_{\mathcal{U}}\in {\mathbb{R}}^{M\times d}$는 각각 제품과 사용자에 대한 Embedding Matrix를 의미한다. $M$과 $N$는 각각 사용자의 수와 제품의 수를 의미한다. 각 제품(사용자)에 대한 Embedding Vector는 $e_v\in {\mathbb{R}}^d$, $e_u\in {\mathbb{R}}^d$로 표현할 수 있다. 

 

Embedding Aggregation Layer는 이웃들로부터 Signal을 수집해 Embedding을 업데이트하는 단계다. 이를 수식으로 표현하면 아래와 같이 표현할 수 있다.

$$n_u=f_{u\leftarrow v}(e_v|v\in {\mathcal{N}}_u)$$

$$n_v=f_{v\leftarrow u}(e_u|u\in {\mathcal{N}}_v)$$

$n_u/n_v\in {\mathbb{R}}^d$는 각각 사용자 $u$와 제품 $v$의 Neighbor Embedding을 Aggregation한 값을 의미한다. $f(\cdot )$는 Aggregation Function으로 연구자의 목적에 따라 다양한 함수를 사용할 수 있다.

 

Embedding Propagation Layer는 Higher-order Interaction을 캡쳐하기 위해, Multiple Layer로 층을 쌓아 사용한다. 이때 $l$ 번째 Layer의 User Representation과 Item Representation은 $h_u^{(l)}$, $h_v^{(l)}$로 표현한다. 이를 수식으로 표현하면 아래와 같이 표현할 수 있다.

$$n_u^{(l+1)}=f_{u\leftarrow v}(h_v^{(l)}|v\in {\mathcal{N}}_u$$

$$h_u^{(l+1)}g(n_u^{(l+1)},h_u^{(l)})$$

 

Prediction Layer는 위 과정을 통해 도출된 각 Layer의 Representation을 Fusion Function $o(\cdot )$을 사용해 계산하여 Final Representation을 도출한 후 이를 내적하여 최종 스코어 ${\hat{r}}_{uv}$를 도출하는 단계다.

$$e_u^{\ast }=o(h_u^{(1)},\cdots ,h_u^{(L)})$$

$$e_v^{\ast }=o(h_v^{(1)},\cdots ,h_v^{(L)})$$

$${\hat{r}}_{uv}{e}_u^{\ast \mathrm{\top }}{e}_v^{\ast }$$

 

마지막 Joint Training에서는 Negative Sampling을 활용하여 Loss Function을 정의하고 이를 최소화하는 방향으로 학습을 진행한다.

$$\mathcal{L}=\sum _{(u,v)\in \mathcal{D}}-\log \frac{\exp (e_u^{\ast \mathrm{\top }}{e}_v^{\ast })}{\exp (e_u^{\ast \mathrm{\top }}{e}_v^{\ast })+\sum _{v_n\sim p_n(\cdot )}\exp (e_u^{\ast \mathrm{\top }}{e}_v^{\ast })}$$

$v_n\sim p_n(\cdot )$는 Negative Sampling을 위한 Distribution을 의미하고, $\mathcal{D}$는 All User-Item Interaction을 의미한다. 

 

Method

STAM

STAM 기법은 Figure 2와 같이 구성되어 있으며, Temporal-Order Embedding과 Temporal-Position Embedding을 더한 값을 Scaled Dot-Product를 수행해 각 Layer 마다 $h_l^{T_u}$를 출력한다. User Item Pair $(u,v)$가 주어졌을 때, Temporal Information은 $T_u=\{v_1,\cdots ,v_S\}$, $T_v=\{u_1,\cdots ,u_S\}$가 된다. 이때 $S$는 Temporal Order의 길이를 의미한다. 각 Imformation을 Encoding하면 $X_u=\{e_v^1,e_v^2,\cdots ,e_v^S\}$와 $X_v=\{e_u^1,e_u^2,\cdots ,e_u^S\}$가 될 것이다. 그런 다음, 각 Temporal Over Embedding에 Position Embedding을 더하면 아래와 같은 Embedding을 도출할 수 있다.

$$Z_u=\{e_v^1+p_v^1,e_v^2+p_v^2,\cdots ,e_v^S+p_v^S\}$$

$$Z_v=\{e_u^1+p_u^1,e_u^2+p_u^2,\cdots ,e_u^S+p_u^S\}$$

$Z_u\in {\mathbb{R}}^{S\times d}$와 $Z_v\in {\mathbb{R}}^{S\times d}$를 Attention Function의 입력으로 사용하면 아래와 같은 값을 도출할 수 있다.

$$h^{T_u}=\text{Softmax}\left(\frac{(Z_u{W}_Q)(Z_u{W}_K{)}^T}{\sqrt{D^{\prime }}}\right)(Z_u{W}_V)$$

$$h^{T_v}=\text{Softmax}\left(\frac{(Z_v{W}_Q)(Z_v{W}_K{)}^T}{\sqrt{D^{\prime }}}\right)(Z_v{W}_V)$$

마지막은 Feed-Forward Network를 수행하는 것이다. 이는 각 Layer에서 출력된 $h_l^{T_u}$, $h_l^{T_v}$에 대해 각각 수행하며 아래와 같은 수식으로 표현할 수 있다.

$$h_u=\text{FFN}(h_1^{T_u}||\cdots ||h_k^{T_u})$$

$$h_v=\text{FFN}(h_1^{T_v}||\cdots ||h_k^{T_v})$$

$\text{FFN}$ Function은  $\text{FFN}(x)=x{W}_0+b_0$을 사용한다. 마지막으로는 각 Temporal Order 만큼의 Embedding을 평균하여 최종 $n_u$, $n_v$를 도출한다.

$$n_u=\frac{1}{S}\sum _{i=1}^S{h}_{v_i},n_v=\frac{1}{S}\sum _{i=1}^S{h}_{u_i}$$

 

STAM for GNN-based Recommendation

STAM는 Graph-Based Recommendation으로도 적용할 수 있다. LightGCN 기법과 비슷하게 STAM 기법에서도 Non-linear Transformation을 제거하고 사용한다. 

$$h^{(l+1)}=(D^{-\frac{1}{2}}(A\odot \mathrm{\Phi })D^{-\frac{1}{2}})h^{(l)}$$

$\mathrm{\Phi }\in {\mathcal{R}}^{(M\times N)\times (M\times N)}$는 Spatiotemporal Attention Weight Matrix를 의미한다. 그런다음 Final Representation을 구하는 수식은 Weighted-Pooling Operation을 사용하여 계산할 수 있다.

$$e_u^{\ast }=\sum _{l=0}^L{\alpha }_l{h}_u^{(l)},e_v^{\ast }=\sum _{l=0}^L{\alpha }_l{h}_v^{(l)}$$

 

Optimization with STAM

BPR Loss를 사용한다.

$$\mathcal{L}=-\underset{v_n\sim p_n(\cdot |u)}{\sum _{(u,v)\in \mathcal{D}}}\text{ln}\sigma (e_u^{\ast \mathrm{\top }}{e}_v^{\ast }-e_u^{\ast \mathrm{\top }}{e}_{v_n}^{\ast })+\lambda ||\mathrm{\Theta }|{|}_2^2$$

 

 

 

Experiments

본 연구에서는 STAM 기법의 성능을 측정하기 위해 MovieLens, Amazon, Taobao 등의 데이터를 사용하였으며, 베이스라인 모델로는 MostPopular BPR-MF, NeuMF, GC-MC, NGCF, PinSage, LightGCN, GRU4Rec, Caser, SASRec, BERT4Rec 등의 기법을 사용하였다. 

 

실험은 1) Performance Comparison, 2) Ablation Study, 3) Parameter Sensitivity 로 구성되어 있다. 먼저 Performance Comparison 에서는 Representative Model과 Sequential Model 간의 성능을 비교한 실험이다 (Table 2, 3). Ablation Study는 기존의 Spatial-Based Aggregation Function과 비교한 실험과 Layer, Input Length에 따른 영향을 비교 분석한 실험이다 (Figure 3, Table 4, Figure 4). 마지막 Parameter Sensitivity에서는 Multi-head Attention의 수, Hidden Dimensionality에 대한 값에 변화를 주어 성능이 변화하는 지 확인하는 실험이다 (Figure 5).