작성자: 김현지

1. Introduction

1.1 Session-based Recommendation

• 기존 추천 시스템은 대부분의 유저 프로필과 과거 행동 데이터들이 끊임없이 저장된다고 가정한다.
• 하지만 실제 서비스에서는 유저의 신원을 모를 수도 있고, 진행 중인 세션 내의 유저 행동 기록만을 사용해야 할 수도
  ⇒ "따라서 한 세션에서 제한된 행동 기록들을 모델링하고 그에 맞춰 추천을 생성해야한다."

기존 모델

• 이전의 RNN 계열의 모델에서는 유저의 선호도를 반영하는 user representation이 따로 존재하지 않고, RNN의 hidden vector를 user representation으로 삼고 다음 아이템을 예측해 왔다.
  그러나 각 세션은 user-specific하지 않고, 세션 클릭과 관련된 유저의 행동은 대부분 한정되어 있다.
  ⇒ 각 세션에서 user representation을 정확하게 추정하는 것은 어렵다.

• 기존 모델들은 연속적으로 선택되는 아이템들의 single-way Transition을 모델링하고, 세션 내의 다른 여러 아이템들 간의 복잡한 Trainstion은 무시한다.
  ⇒ 멀리 떨어진 아이템들 사이의 복잡한 Transition은 간과되어 왔다.

1.2 SR-GNN (Session-based Recommendation with Graph Neural Networks)

Graph Neural Networks를 사용한 Session-based 추천시스템
기존 모델들의 단점들을 보완하기 위해 본 논문에서 제안된 모델

• Graph Neural Networks를 통해 아이템 간의 관계를 파악하고, 아이템 임베딩에 대해 정확한 값을 만들어낸다
  이는 Markov Chain & RNN 기반 모델 같은 전통적인 시퀀셜 모델에서는 구현되기 어렵다.
• 아이템 임베딩에 대한 정확한 값들을 기반으로 global preference와 current interest를 구하여 예측에 사용한다.
• User-specific 하지는 않지만, 해당 세션의 시퀀스가 반영된 임베딩이 들어가기 때문에 session-specific하게
  예측할 수 있다.

---

2. Related Works

2.1 Conventional recommendation methods

1) Matrix Factorization

Target 값(implicit, explicit)을 저차원 아이템 임베딩 행렬과
임베딩 행렬로 분해하는 방법론

• 세션 기반 추천에서는 적절하지 못하다.
  → 왜냐하면 유저 선호도 일부가 positive 클릭에 의해서만 제공되며, 아이템 시퀀셜 순서를 고려하는데 어려움이 있고, 단지 마지막 클릭을 바탕으로 예측을 수행하기 때문

2) Markov chain-based method

Transition probability를 바탕으로 아이템 간의 관계를 정의하고 그 관계로부터 행렬 분해를 하는 방법론

• 이 모델의 가장 큰 결점은 이 모델들이 과거 구성요소들을 독립적으로 결합한다는 것이다.
  → 이러한 독립가정은 너무 강력하기 때문에 예측 정확도를 국한
  시킨다.

2.2 Deep learning-based recommendation methods

1) Improved recurrent neural networks for session-based recommendations

: 유저 행동의 시간적 변화를 고려하고 적절한 data augmentation기법을사용하여 순환 모델의 성능을 높임.

2) When recurrent neural networks meet the neighborhood for session-based recommendation

: 시퀀셜 패턴과 동시에 발생 신호를 혼합하기 위해 이웃 기반 기법과 순환기법을 결합함.

3) 3D convolutional networks for session-based recommendation with content features

: 추천을 수행하기 위해 3c CNN을 사용하여 아이템 카테고리 & 설명 같은컨텐츠 features와 세션 클릭을 통합함.

4) List-wise DNN

: 각 세션 내 제한된 유저 행동을 모델링하고, 각 세션에 대한 추천을 수행하기 위해 List-wise 랭킹 모델을 사용함.

5) NARM(A Neural Attentive Recommendation Machine with an encoder-decoder architecture)

: 유저의 시퀀셜 행동의 features와 주요 목적을 포착하기 위해 RNN 어텐션 메커니즘을 사용함.

6) STAMP(Short-Term Attention Priority model)

: 유저의 일반적인 흥미와 현재 흥미를 효율적으로 포착하기 위해 제시됨.

2.3 Graph Neural Networks

1) Graph Neural Nerworks

• 그래프 구조에서 사용하는 인공 경망이다.
• 인공 신경망들을 보통 벡터나 행렬 형태로 input이 주어지는 데 반해서 GNN의 경우 input이 그래프 구조라는 특징이 있다.
• 관계, 상호작용과 같은 추상적인 개념을 다루기에 적합하다.
• 일반적인 그래프는 𝐺 = (𝑉, 𝐸)로 정의하며 𝑉는 점 집합이고 𝐸는 두 점을 잇는 선 집합이다. 아래 그래프는 다음과 같이 정의할 수 있다.
  𝐺 = ( 1,2,3 ,{ 1,2 , 2,3 ,{1,3}})
  

2) Gated Graph Neural Networks

• GNN의 수정 버전으로 노드 벡터를 업데이트할 때 GRU cell을 이용한다.
• 시간 경과에 따른 역전파(BPTT, Back-Propagation Through Time)를 사용하여 Gradients를 계산한다.

---

3. The proposed Methods

3.1 The workflow of the proposed SR-GNN

세션 기반 추천은 장기 선호도 프로필 접근 없이 유저의 현재 시퀀셜 세션 데이터(current sequence session data)만을 기반으로 유저가 다음에 클릭할 아이템이 무엇인지 예측하는 것에 초점을 둔다.

3.2 Notations

3.3 Constructing Session Graphs

각 세션 시퀀스 𝑠 는 directed graph 𝒢𝑠 = (𝒱𝑠, ℰ𝑠) 로 표현된다. 각 노드들은 아이템 $v_{s,i}$ ∈ 𝑉를 의미하고, 각 Edge $(v_{s,i-1},v_{s,i}) \in$ ℰ𝑠는 유저가 $(v_{s,i-1})$ 다음에 $(v_{s,i})$를 클릭했다는 의미이다.

• 아이템들이 한 시퀀스에서 반복적으로 등장할 수 있기 때문에 각 edge를 정규화된 가중치로 할당한다.
  가중치: edge의 발생정도 / edge의 시작 노드의 outgree(출력차수)
• 모든 아이템 𝑣 ∈ 𝑉을 통합된 임베딩 공간에 임베딩하며, 노드 벡터 𝑣 ∈ 𝑅
  𝑑는 GNN을 통해 학습된 아이템 𝑣의 latent vector를 의미한다. (𝑑는 차원)
• 노드 벡터에 기반하여 각 세션 𝑠는 임베딩 벡터 𝑠로 표현될 수 있다. 임베딩 벡터 𝑠는 해당 그래프에서 사용된 노드 벡터로 구성된다.

3.4 Learning Item Embedding on Session Graphs

Parameter

Update function for the node $v_{s,i}$ of graph 𝒢s

A example of a session graph and the connection matrix $A_s$

3.5 Generating Session Embeddings

• 모든 세션 그래프를 gated GNN에 공급한 후에 모든 노드 벡터를 얻는다.
• 각 세션을 embedding vector $s \in R^d$로 표현하기 위해 다음을 고려한다.
• session $s=[v_{s,1},v_{s,2},...,v_{s,n}]$
  

3.6 Making Recommendation and Model Training

• loss function: cross-entropy
  $y$는 ground truth 아이템의 one-hot encoding vector
  
• 마지막으로 BPTT(Back-Propagation Through Time)를 사용해서 SR-GNN을 학습시킴
• 보통 세션 추천 시스템에서, 대부분의 세션은 상대적으로 짧은 길이를 가진다는 것을 유의해야함. 따라서 오버피팅을 예방하기 위해 비교적 적은 수의 훈련 스템을 선택하는 것을 제안

---

4. Experiments and Analysis

4.1 Datasets

• Yoochoose, Diginetica dataset: e-commerce 웹사이트에 유저들의 클릭 기록
• 세션 길이 1짜리는 제거
• Cold-start problem 방지를 위해 최소 등장 횟수 5회로 설정
• Input 세션 $s=[v_{s,1}, v_{s,2},..., v_{s,n}]$의 경우 시퀀스와 레이블 시리즈를 다음과 같이 생성한다.
  

4.2 Baseline Algorithms

제시된 모델의 성능을 평가하기 위해 아래와 같은 대표적인 베이스라인들과 비교한다.

• POP & S-POP: 훈련집합과 현재 세션에서 각각 빈번하게 등장한 top-N개의 아이템들을 추천
• Item-KNN: 세션에서 이전에 클릭된 것과 유사한 아이템을 추천 (유사도는 세션 벡터 사이의 코사인 유사도로 정의)
• BPR-MF: SGD(Stochastic Gradient Descent)를 통해 Pairwise 랭킹 목적 함수 최적화
• FPMC: 마르코프 연쇄 기반 시퀀셜 예측 기법
• GRU4REC: 세션 기반 추천에 대해 유저 시퀀스를 모델링하는 RNN을 사용
• NARM: 유저의 핵심 목적과 시퀀셜 행동을 포착하는 어텐션 메커니즘 RNN을 사용
• STAMP: 유저의 일반적인 선호도와 현재 세션에서의 마지막 클릭을 통해 현재 관심사를 포착

4.3 Evaluation Metrics

• P@20 (Precision): 예측 정확도 측정치로 널리 사용됨.
  top-20 아이템들 중에서 정확하게 추천된 아이템의 비율을 나타냄.

• MARR@20 (Mean Reciprocal Rank): 정확하게 추천된 아이템의 역순위 평균임.
  역순위가 20을 초과할 때는 0으로 설정됨.
  MRR 측청치는 추천 랭킹 순서를 고려함.
  → MRR 값이 크면 TOP 랭킨 리스트에 정확한 추천이 나타남.
  

4.4 Parameter Setup

• 이전 모델들 (NARM, STAMP)에 따라 두 데이테 셋에 대해 latent vector의 차원을 $d=100$으로 설정함
• validation set을 통해 하이퍼파라미터 튜닝
• 모든 파라미터들은 평균=0, 표준편차=0.1을 가지는 가우시안 분포를 사용하여 초기화됨.
• mini-batch Adam optimizer
• 초기 학습률 0.001, 3 Epochs 후에 0.1씩 감소
• Batch 크기 = 100
• L2 규제화 = $10^{-5}$

4.5 Comparison with Baseline Methods

• POP&S-POP은 반복적으로 동시에 발생한 아이템 혹은 연속적인 아
  이템만을 기반으로 추천을 수행하는 단순한 알고리즘으로 성능이 상대
  적으로 좋지 않음.
• 그러나 S-POP은 최근 세션들에서 인기 아이템을 고르기에 BPR, FPMC보다 성능이 좋음 ⇒ 세션의 contextual한 정보가 중요함을 알 수 있음.
• GRU4REC나 NARM은 RNN 모델을 사용하여 유저의 general interest를파악하려 했기에 성능이 좋아짐.
• 그러나 STAMP는 마지막 아이템에 대해 강조함으로써 short-term interest를 파악했기에 성능이 더 좋아짐.
• SR-GNN은 세션만 보는 것이 아니라 아이템들이 가지는 관계를 전체적으로 파악하면서 preference를 이해하려 했음.
• 또한 어텐션 메커니즘을 통해 아이템 간의 관계를 좀 더 잘 파악하도록 설계됨.

  실험에 따르면 본 논문에서 제안된 SR-GNN 기법이 P@20&MRR@20의 관점에서 봤을 때 모든 데이터 셋에서 가장 좋은 성능을 보였다.

4.6 Comparison with Variants of Connection Schemes

세션에서의 유저 행동은 제한적이기 때문에 각 세션 그래프 간의 또 다른 형태의 연결을 제시한다.

SR-GNN

시퀀스 별로 그래프 구성

SR-GNN-NGC

전체 시퀀스를 두고 한 번에 global graph를 구성

SR-GNN-FC

시퀀스 별로 시작 노드와 끝 노드만을 잇는 방식으로 구성

• 세 연결 방식 모두 STAMP&NARM 모델보다 더 좋거나 거의 동일한 성능을 달성했다.
• SR-GNN과 비교하여
  NGC: 최근에 발생한 세션에 집중하지 못하므로 short-term이 중요한 해당 데이터 셋에서는 성능이 저하됨.
  FC: 큰 차이는 없지만 SR-GNN보다 성능이 조금 더 안 좋음.
  이는 아이템의 등장 순서가 매우 중요하고 아이템 간의 관계 사이에 다른 아이템의 존재가 중요할 수 있음을 시사함.
  → 예를 들어 유저가 웹 사이트를 검색할 때 다음 페이지를 본 경우A→B→C, A와 C 사이의 직접 연결이 부족하기 때문에 중간 페이지 B가 없이 A 다음에 C 페이지를 추천하는 것은 적절하지 않을 수 있다.

4.7 Comparison with Different Session Embeddings

SR-GNN

$s_l+s_g$ local embedding과 global embedding 모두 사용

SR-GNN-L

오직 local embedding($s_l$)만 사용

SR-GNN-AVG

평균 pooling을 사용한 global embedding($s_g$) 사용

SR-GNN-ATT

어텐션 메커니즘을 사용한 global embedding($s_g$) 사용

• local embedding과 global embedding을 모두 사용한 SR-GNN이 가장 좋은 결과
  → 이는 장기 선호도를 이용한 현재 세션에서의 관심사를 명시적으로 통합하는 것에 대한 중요성을 보여줌.
• ATT가 두 번째로 좋은 성능을 보임.
  → 행동 시퀀스들의 노이즈를 잡아내는 것이 중요하며 중요한 행동을 파악하는 것이 중요함을 알 수 있음.
  또한 어텐션 메커니즘이 장기 선호도를 구축하기 위해 세션 데이터에서 중요 행동을 추출하는 데 도움을 준다는 것을 보여줌.
• L버전도 성능이 좋음.
  → current interest도 전체 시퀀스에서 알 수 있는 장기 선호도만큼 중요함을 알 수 있음.

4.8 Analysis on Session Sequence Lengths

• 서로 다른 길이의 세션에 대처하기 위해 세션 길이 별 분석을 진행한다.
• 평균 길이5를 기준으로 short session과 long session으로 구분한다.
  
• SR-GNN은 서로 다른 세션 길이를 가진 두 가지 데이터 셋에서 안정적인 성능을 보인다.
• NARM과 STAMP 모두 RNN 계열의 모델을 기반으로 하기에 길이가 긴 시퀀스에 대해서는 성능이 저하되었다

---

5. Conclusions

• 세션 기반 추천은 유저 선호도와 기록 내역을 얻기 어려울 때 필수적이다.
• 본 논문은 그래프 모델로 세션 시퀀스를 표현하기 위한 새로운 아키텍처를 제시하였다.

  SR-GNN
  • 세션 시퀀스 아이템 간의 복잡한 구조와 Transition을 고려할 뿐만 아니라 유저의 다음 행동을 더 잘 예측하기 위해 장기 선호도와 현재 세션에서의 관심사를 결합하여 사용하였다.
  • 종합적인 실험들은 제시된 알고리즘이 다른 최신 기법들보다 일관적으로 좋은 성능을 내는 것을 입증하였다.

| 참고자료
http://dsba.korea.ac.kr/seminar/?mod=document&uid=75
https://soobarkbar.tistory.com/184
https://velog.io/@jkl133/SR-GNN-ing
https://medium.com/watcha/gnn-%EC%86%8C%EA%B0%9C-%EA%B8%B0%EC%B4%88%EB%B6%80%ED%84%B0-%EB%85%BC%EB%AC%B8%EA%B9%8C%EC%A7%80-96567b783479