SR-GNN(-ing)

논문 제목: SR-GNN (Session-based Recommendation with Graph Neural Networks)

들어가기 전에, GNN을 이해하기 위한 참고 글:
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
http://www.secmem.org/blog/2019/08/17/gnn/

Abstract

• anonymous user에 대한 추천 예측이 어려움
• 이전의 추천 방식:
  - session을 sequence로 모델링함
  - item representation 외에도 user representation을 진행함
  • 이는 정확한 유저 벡터를 표현하기에는 insufficient
  • 충분한 유저-아이템 interaction에 의존함
• 정확한 item embedding과 complex transitions of items(복잡한 아이템 전환?) 을 고려하기 위해서 새로운 방식을 고안함
• 새로운 추천 방식
  • session sequences를 graphstructured data로 표현
  • session graph를 통해 GNN은 complex transitions of items을 고려가능
  • 각각의 세션은 attention network를 통해 composition of global preference와 해당 세션의 current interest로 표현됨

Introduction

• 이전의 추천 시스템은 유저의 프로필과 past activities가 계속 저장된다고 예상함
• 그러나 실제 서비스에서는 anonymous user이거나 진행중인 세션 내의 유저 행동 기록만 사용가능
• 한 세션에서 제한된 행동 기록을 모델링하고 이에 맞는 추천을 생성해야함
• 결국 GNN의 가장 큰 장점은 다음과 같다
  • capture transition of item
  • generate accurate item embedding vectors
  • 위의 두 개는 전통적인 sequential method(Marcov Chain, RNN-based model)에서는 발견하기 어려움

SR-GNN 방식의 workflow

1. 모든 세션 시퀀스를 directed session graph (방향 세션 그래프?)로 모델링함
- 여기서 각각의 세션 시퀀스는 subgraph로 취급됨
2. 각각의 세션 그래프는 하나씩 진행되며(successively), 각 그래프에 포함된 모든 노드의 latent vector는 gated GNN을 통해 얻게 됨
3. attention network를 통해, 각각의 세션은 global prefernece와 이번 세션의 current interest의 혼합으로 표현됨
- 이떄의 global, local session embedding vector는 노드들의 latent vector들로 구성됨
4. 마지막으로, 각 세션에서 각의 아이템이 다음 번 클릭할 때 등장할 확률을 예측함

main contribution
1. 구별된 세션 시퀀스를 graph structured data로 모델링하고, GNN을 통해 복잡한 item transition을 잡아냄
2. session based 추천시스템을 만들기 위해, session embedding을 사용함
- session embedding: 각각의 단일 세션에 포함된 아이템들의 latent vector를 기반으로 얻을 수 있음

The proposed Method

Notations

• session based 추천 시스템은 한 유저가 어떤 아이템을 그 다음에 클릭할 것인가에 초점을 둔다
• 장기적인 선호 프로필 없이, 오로지 유저의 current sequence session data에 기반함
• formulation
  - let V = {v1, v2, . . . , vm} : 모든 세션에 포함된 모든 unique item으로 구성된 집합
  • list s = [v(s,1),v(s,2), ... v(s,n)] : 타임스탬프 순으로 정렬된 리스트, An anonymous session sequence s
  • v(s,i) ∈ V :a clicked item of the user within the session s
• session based 추천 시스템의 목표: 다음 클릭(sequence label for the session: v(s,n+1))을 예측
• session s에서, 모든 가능한 아이템에 대한 확률값 yˆ 을 도출
  - vector yˆ의 각 원소값: 각 원소에 대응하는 아이템에 대한 recommendation score
• yˆ벡터 안의 top-K 아이템들은 추천될 아이템 후보군이 된다

Constructing Session Graphs

• 각 세션 시퀀스 s는 directed graph Gs = (Vs, Es) 로 표현됨
• 이 세션 그래프에서는, 각 노드들이 item v(s,i) ∈ V 를 의미함
• 각 edge (vs,i−1, vs,i) ∈ Es는 한 유저가 (vs,i−1) 다음에 (vs,i)를 클릭했다는 의미임
  - 아이템들이 한 시퀀스에서 반복적으로 등장할 수 있기 때문에, 각 edge(간선)를 normalized weighted(정규화된 가중치)로 할당함
  • 가중치: edge의 발생정도/ edge의 시작 노드의 outdegree(출력차수)
• 각 아이템v ∈ V 을 unified embedding space로 임베딩함
• 노드 벡터 v ∈ R(d)는 GNN을 통해 학습된 아이템의 latent vector v 를 의미, d는 dimention
• 노드 벡터에 기반하여, 각 세션 s는 임베딩 벡터s로 표현될 수 있음
  - 임베딩 벡터s는 해당 그래프에서 사용된 노드 벡터로 구성됨
  

Learning Item Embeddings on Session Graphs

• 그렇다면, 어떻게 GNN을 통해 노드의 latent vector를 얻을 수 있는가?
• Graph NN은 session-based 추천시스템에 적합함
  - 정보가 풍부한(?) 노드 벡터 덕분에 세션 그래프의 feature를 자동적으로 추출할 수 있기 때문이다
• parameters
  - H ∈ R(d×2d) 은 가중치 조정
  - z(s,i), r(s,i)는 각각 reset and update gates를 의미
  - [v(t-1)1,...,v(t-1)n]: 세션 s에서의 노드 벡터들의 리스트
  - vi ∈ R(d): 노드 v(s,i)의 latent vector
  - connection matrix As ∈ R(n×2n): 그래프 안의 노드들이 서로 어떻게 상호작용하는지를 결정함
  - A(s,i:) ∈ R(1×2n) : node v(s,i)에 대응하는 2개의 column blocks in matrix As
  - As: 두개의 인접행렬 As(out), As(in)의 concatenation
• update function for the node v(s,i) of graph Gs
  
• 각각의 session graph Gs는 동시에 진행됨
• (1) 은 다른 노드 간의 information propagation을 위해 사용됨(matrix As의 제약조건을 기반으로)
  - 이웃간의 latent vector를 추출하고, GNN의 input으로 feeding 함
  • 두 개의 게이트(update, reset gate)는 어떤 정보를 유지/버릴 것인지를 결정함 -> GRU와 비슷한 개념이라고 생각함!
• (4) 이전 state,현재 state, reset gate를 기반으로 후보 state를 구성
• 마지막 state는 이전의 hidden state와 후보 state의 혼합으로 구성(update gate의 제약 하에서)
• 한 세션 그래프에서의 모든 노드가 수렴될 때까지 업데이트가 끝나면(?) 최종 노드 벡터를 얻을 수 있음

• A example of a session graph and the connection matrix As
  
• 예를 들어, session s =[v1, v2, v3, v2, v4] 로 이루어져 있다고 하자.
• outgoing edges: x(가로)->y(세로)로 나가는 방향의 간선
• incoming edges: x(가로)->y(세로)로 들어가는 방향의 간선
• outgoing edges matrix(2,3),(2,4)를 보면 앞에서 제시된 normalized weighted(정규화된 가중치)가 적용된 것을 알 수 있음

Generating Session Embeddings

• 이전의 session based recommendation은 각 세션에서의 유저의 distinct latent representation이 있다고 가정함
• 그러나 SR-GNN은 해당 벡터에 대해 어떠한 가정도 하지 않음
• 대신, 한 세션은 그 세션이 포함하고 있는 노드들로 바로 표현된다
• 유저의 다음 클릭을 더 잘 예측하기 위해, 장기적인 선호와 이번 세션에서의 현재의 관심을 혼합하고, 이렇게 혼합된 임베딩을 세션 임베딩으로 삼는다
• 모든 세션 그래프를 gated GNN으로 feeding한 후, 모든 노드에 대한 벡터를 얻을 수 있다
• 각 세션s 를 embedding vector s ∈ R(d)로 표현하기 위해, 다음을 고려한다.
  - session s=[v(s,1), v(s,2), ... , v(s,n)]
  - local embedding sl (of session s) 은 가장 마지막에 클릭된 아이템 v(s,n) 벡터인 vn으로 표현될 수 있다 -> sl = vn
  - global embedding sg (of the session graph gs)는 모든 노드 벡터의 집합으로 생각한다
  - 이 임베딩의 정보들이 다른 우선순위를 가지고 있다면, 이를 soft-attention mechanism을 통해 global session representation 선호를 더 잘 나타낼 수 있을 것이다
  
• parameter meters q ∈ R(d), W1,W2 ∈ R(d×d)는 아이템 임베딩 벡터의 가중치를 조정한다
• 최종적으로, 하이브리드 임베딩인 sh를 the concatenation of the local and global embedding vector에 대해 선형변환을 취한다.
  
• 이때, matrix W3 ∈ R(d×2d) 는 두 혼합 임베딩 벡터를 latent space R(d)로 압축한다
  

Making Recommendation and Model Training

• 각 세션의 임베딩을 획득한 후, (각 후보 아이템 vi ∈ V에 대한) score zˆi은 session represetation sh * embedding vi로 계산한다
  
• 그후 softmax를 취한다
• zˆ ∈ R(m) : 모든 후보 아이템에 대한 recommendation scores을 의미
• yˆ ∈ R(m) : 해당 노드가 세션 s에서의 다음 클릭이 될 확률을 의미
• loss function: cross-entropy
  - y는 ground truth 아이템의 one hot encoding vector
  
• 마지막으로, BPTT를 사용해서 SR-GNN을 학습시킴
  - 보통 session based 추천 시스템에서는, 대부분의 세션이 짧은 길이이기 때문에, 상대적으로 적은 수의 training step을 통해 오버피팅을 예방함
  

논문의 소스코드: https://github.com/CRIPAC-DIG/SR-GNN

참고: https://soobarkbar.tistory.com/184