[Paper Review] Session-based Recommendation with Graph Neural Networks

S. Wu, Y. Tang, Y. Zhu, L. Wang, X. Xie, and T. Tan, “Session-based
recommendation with graph neural networks,” in Proceedings of the
AAAI Conference on Artificial Intelligence, vol. 33, 2019, pp. 346–353.

I. Introduction

인터넷 상의 정보량이 매우 빠른 속도로 증가하는 오늘날, 추천시스템은 유저가 흥미를 느낄만한 정보를 획득하는 데에 도움을 준다. 전통적인 추천시스템은 유저의 정보와 과거 활동들이 꾸준히 기록된다는 가정 하에 작동한다. 하지만 대부분의 서비스에서 유저의 신원은 불분명한 경우가 많고, 진행 중인 session 내의 유저 행동만을 관찰할 수 있다.

이런 한계를 극복하기 위해 유저가 과거에 구매한 아이템을 고려하여 새로운 아이템을 추천해주는 Markov chain이나 Recurrent Neural Networks(RNN)에 기반한 session-based recommendation 방식이 개발되었지만 여전히 해결되지 않은 한계점이 존재한다. 바로 유저 representation을 추정하는 데에 어려움이 있다는 점과, 연속적인 아이템 간의 단방향 transition만을 고려하고 세션 내 다른 아이템 간의 transition은 무시한다는 점이다.

본 논문에서는 Session-based Recommendation with Graph Neural Networks(이하 SR-GNN)를 제안한다. SR-GNN은 아이템 간의 transition을 충분히 탐색하고 정확한 아이템 latent vector를 생성하는 모델이다.

위 그림은 SR-GNN의 흐름을 나타낸 것이다. 먼저 모든 session sequence를 directed session graph로 나타낸다. 각 session graph는 연속적으로 진행되고 모든 노드의 latent vector는 gated GNN을 통해 얻어진다. 이후 각 session을 global한 선호도와 유저 개인의 선호도를 조합해 표현한다. 이때 global, local session embedding vector는 node의 latent vector로 구성된다. 마지막으로 session별로 특정 아이템이 다음에 클릭될 확률을 예측해낸다.

SR-GNN은 분리되어 있는 session sequence들을 graph 구조의 data로 나타낸 후 GNN을 통해 복잡한 item transition들을 잡아낼 수 있다. 또 유저 representation 대신 각 session에 포함된 아이템들의 latent vector로 만들어진 session embedding을 활용한다.

II. Related Work

1. Conventional recommendation methods

추천시스템의 가장 일반적인 접근은 Matrix Factorization이다. MF의 목표는 유저-아이템 matrix를 유저와 아이템의 latent factor를 나타내는 두 개의 low-rank matrix로 factorize하는 것이다. 그러나 MF는 클릭 데이터만으로 유저의 선호도를 유추하기 때문에, session-based recommendation에는 적절하지 않다.

그래서 등장한 것이 item-based neighborhood 방법이다. 이 method에서는 같은 session 내에 아이템이 함께 등장하는 정도를 고려해 item similarity를 계산한다. 다만 아이템의 구매 순서를 고려하진 못한다는 한계점이 있다.

이후 유저의 다음 행동은 직전 행동에 영향을 받는다는 전제 하에 Markov chain을 이용한 sequential method가 제안되었다. 하지만 이런 Markov chain 기반 모델들은 과거 component들을 독립적으로 결합하여 예측 정확도가 그리 높지 않다.

2. Deep-learning-based methods

최근에는 언어 모델 분야에서 좋은 성능을 내고 있는 Recurrent Neural Networks(이하 RNN)를 session-based recommendation에 적용하려는 시도가 이어졌다. 그 예로 유저 행동의 시간적 변화를 고려한 모델, RNN과 neighborhood-based method를 합쳐 순차적 패턴과 co-occurrence signal을 포착한 모델, 3차원 CNN으로 아이템 카테고리와 세부 정보까지 학습하는 모델 등이 있다.

3. Neural network on graphs

Neural network는 그래프 형태로 구조화된 데이터를 표현하는 데에 사용되기도 한다. 대표적으로 word2vec을 확장한 비지도학습 알고리즘 DeepWalk는 random walk를 기반으로 그래프 노드 표현을 학습한다. 전통적인 CNN을 임의의 크기와 모양을 가진 그래프에 적용한 선행 연구도 존재한다.

하지만 undirected graph에서만 이루어진 위 모델들과 달리, directed graph에서 작동하는 GNN을 변형해 만들어진 gated GNN은 gated recurrent unit과 back-propagation through time(BPTT)을 사용하여 gradient를 계산한다. 최근 몇 년간 GNN은 script event prediction이나 situation recognition, image classification 등 다양한 task에 활용되고 있다.

III. The Proposed Method

1. Notations

Session-based recommendation은 유저의 장기적인 선호도를 고려하지 않고도 현재의 sequential session 데이터만으로 유저가 다음에 클릭할 아이템을 예측하는 데에 초점을 둔다.

논문에서 사용될 기호를 정리해보면, 우선 $V= \{ v_1, v_2, ..., v_m \}$은 모든 session을 이루는 아이템 집합을 의미한다. 임의의 session sequence $s$는 시간 순서대로 $[v_{s,1}, v_{s,2}, ..., v_{s,n}]$로 표현되는데, 이때 $v_{s, i} \in V$는 유저가 session $s$에서 $i$번째 클릭한 아이템이다. 따라서 session-based recommendation의 목표는 session $s$에 대해 $v_{s, n+1}$을 예측하는 것이 된다.

각 session $s$에서 가능한 모든 아이템에 대해 output probability를 계산해서 vector $\hat{\mathbf{y}}$를 도출한다. 이 중 상위 $K$개의 아이템을 뽑아 candidate item으로 추천을 해준다.

2. Constructing Session Graphs

각각의 session sequence $s$는 directed graph $\mathcal{G}_s =(\mathcal{V}_s, \mathcal{E}_s)$로 나타낼 수 있다. 그래프에서 각각의 노드는 아이템 $v_{s, i} \in V$를 나타내고, edge $(v_{s,i-1},v_{s,i})\in \mathcal{E}_s$는 세션 $s$에서 유저가 아이템 $v_{s,i-1}$를 클릭한 후 아이템 $v_{s,i}$를 클릭했다는 것을 의미한다.

sequence 내에 아이템 조합이 여러 번 등장할 수도 있기 때문에, 그래프에서 각 edge에 normalized weight를 할당했다. 이때 weight은 edge의 등장 횟수를 해당 edge의 start node의 outdegree로 나누어 계산된다.

저자는 모든 아이템 $v \in V$를 통합된 embedding space에 대응시켰다. 노드 벡터 $\mathbf{v}\in\mathbb{R}^d$는 GNN을 통해 학습된 아이템 $v$에 대한 latent vector를 의미한다. 이 노드 벡터를 기반으로 각 session $s$는 embedding vector $\mathbf{s}$로 표현될 수 있다.

3. Learning Item Embeddings on Session Graphs

GNN은 session-based recommendation에 적합한 모델이다. 다양한 노드 connection을 고려하여 session graph로부터 feature를 뽑아낼 수 있기 때문이다. 노드 벡터를 학습시키기 위해 그래프 $\mathcal{G}_s$의 노드 $v_{s,i}$에 다음과 같은 update 함수들을 적용한다.

식에서 $\mathbf{H} \in \mathbb{R}^{d \times 2d}$는 가중치 matrix, $\mathbf{z}_{s,i}$와 $\mathbf{r}_{s,i}$는 각각 update, reset gate이다. $[\mathbf{v}^{t-1}_1 , ..., \mathbf{v}^{t-1}_n]$는 session $s$의 노드 벡터이고 $\sigma(\cdot)$는 sigmoid 함수, $\odot$은 element-wise multiplication 연산자, $\mathbf{v}_i \in \mathbb{R}^d$는 노드 $v_{s,i}$의 latent vector를 의미한다. connection matrix $\mathbf{A}_s \in \mathbb{R}^{n \times 2n}$은 그래프에서 각 노드가 서로 어떻게 상호작용하는지를 결정하는데 이때 $\mathbf{A}_{s,i:} \in \mathbb{R}^{1 \times 2n}$은 $\mathbf{A}_s$에서 노드 $v_{s,i}$에 대응되는 부분이다.

$\mathbf{A}_s$는 두 개의 인접행렬 $\mathbf{A}^{\text{(out)}}_s$과 $\mathbf{A}^{\text{(in)}}_s$이 결합해서 만들어진다. 아래 session $s=[v_1, v_2, v_3, v_4, v_5]$에 대한 그래프 $\mathcal{G}_s$의 예시를 보면 이해가 쉬울 것이다.

session graph를 생성하는 방식은 저마다 다를 수 있지만 SR-GNN은 서로 다른 connection matrix $\mathbf{A}$를 지원할 수 있다. 나아가 만약 각 노드에 추가적인 content feature가 존재하는 경우 해당 feature들을 node vector와 결합하여 추가 정보를 학습시킬 수 있다.

각각의 session graph $\mathcal{G}_s$에 대해, gated graph neural network는 다음과 같은 작업들을 동시에 처리한다. 식 (1)은 matrix $\mathbf{A}_s$ 조건 하에서 서로 다른 노드 간에 정보를 전파한다. 구체적으로 이웃 노드 간에 latent vector를 추출해 GNN의 input으로 넣어주는 역할을 한다. 다음으로 update와 reset gate가 어떤 정보를 보존하고 삭제할지 결정해준다. 그렇게 되면 식 (4)에서 이전의 state와 현재 state, reset gate를 종합하여 candidate state가 도출된다. 마지막으로 update gate는 이전의 hidden state와 candidate를 얼마나 보존할지 결정해 final state를 도출한다. 모든 노드가 수렴할 때까지 업데이트가 완료되면 final node vector를 얻을 수 있다.

4. Generating Session Embeddings

기존 session-based recommendation들이 각 session에 대해 유저의 distinct한 latent representation이 있을 것이라고 가정한 것과 달리, SR-GNN은 session을 구성하는 노드만으로 session을 표현한다. 이때 유저의 장기적인 선호도와 현재 session에서의 관심도를 결합한 session embedding 방식을 제안했다.

모든 노드에 대해 node vector를 얻은 후, session $s$에 대한 local embedding $\mathbf{s}_1$을 구했다. session $s=[v_{s,1},v_{s,2},...,v_{s,n}]$에 대해 local embedding은 마지막에 클릭한 아이템 $v_{s,n}$의 벡터 $\mathbf{v}_n$이 된다.

다음으로 session graph $\mathcal{G}_s$의 모든 노드 벡터를 종합해 global embedding $\mathbf{s}_g$를 계산했다. 이때 soft-attention 메커니즘을 적용해 embedding의 우선순위가 다를 수 있다는 점을 고려했다.

$\mathbf{q} \in \mathbb{R}^d$와 $\mathbf{W}_1, \mathbf{W}_2 \in \mathbb{R}^{d \times d}$는 item embedding vector의 가중치를 조절한다.

최종적으로, local embedding vector와 global embedding vector를 결합하고 선형 변환을 통해 hybrid embedding $\mathbf{s}_h$를 얻었다. 행렬 $\mathbf{W}_3 \in \mathbb{R}^{d \times 2d}$는 결합된 embedding vector를 $\mathbb{R}^d$ 차원의 latent space로 압축시키는 역할을 한다.

5. Making Recommendation and Model Training

각 세션의 embedding을 모두 얻은 후 candidate item $v_i \in V$의 embedding $\mathbf{v}_i$와 session representation $\mathbf{s}_h$를 곱하여 score $\hat{\mathbf{z}_i}$를 계산했다.

그리고 모델의 output vector를 얻고자 softmax 함수를 적용했다.

$\hat{\mathbf{z}}\in \mathbb{R}^m$은 모든 candidate item에 대한 recommendation score, $\hat{\mathbf{y}}\in \mathbb{R}^m$은 특정 노드가 session $s$의 다음 클릭이 될 확률을 의미한다.

loss function은 예측값과 실제값 간의 cross-entropy로 정의되었다.

마지막으로 Back-Propagation Through Time(BPTT) 알고리즘을 이용해 SR-GNN 모델을 학습시킨다. 이때 대부분의 추천 상황에서 session의 길이는 그리 길지 않으므로 training step 수를 작게 해 overfitting을 방지했다.

IV. Conclusions

본 논문에서 제안한 SR-GNN은 session sequence를 graph 모델로 표현하는 방식의 session-based recommendation이다. SR-GNN은 session sequence 내에서 아이템의 복잡한 구조와 transition을 고려할 뿐만 아니라, 장기적인 선호도와 현재 선호도를 결합해 유저의 다음 action을 예측해낸다.

---

Graph Neural Network를 추천시스템에 적용하여 global, local 선호도를 추출한 점이 인상깊었다. GNN이 현업에서도 많이 사용된다고 들었는데, 관련해서 더 공부를 해봐야겠다!