[KG_2019]KPRN(Explainable Reasoning over Knowledge Graphs for Recommendation)

Abstract

Abstract

• 추천 시스템에 KG를 통합하는 것은 최근 몇 년 동안 점점 더 많은 관심을 끌고 있음. 
• KG 내의 interlinks(상호 연결)을 탐색함으로써 user와 item 간의 연결성을 paths로 발견할 수 있고 이는 user-item interactions에 풍부하고 보완적인 정보를 제공해줌. 
  • 이러한 연결성은 엔티티와 relation의 semantics(의)를 드러낼 뿐만 아니라 user의 interest을 이해하는 데도 도움이 됨.
• 그러나 기존의 노력들은 경로 내의 순차적 종속성(sequential dependencies)과 전체적인 의미를 모델링하는 측면에서 user 선호도를 추론하기 위해 이 연결성을 충분히 탐구하지 못했음.
  • 본 논문에서는 추천을 위해 지식 그래프를 활용하는 새로운 모델인 Knowledge-aware Path Recurrent Network (KPRN)을 제안.
    • KPRN은 엔티티와 relations의 의미(semantics)를 구성 -> 경로 표현(path representations)을 생성할 수 있음.
    • 경로 내의 sequential dependencies을 활용함 -> 우리는 사용자-아이템 상호작용의 근본적인 이유를 추론하기 위한 효과적인 경로 추론을 가능하게 함.
    • 우리는 user가 item과 연결되는 다양한 경로의 strengths를 구별하기 위한 새로운 가중 풀링 작업(weighted pooling operation)을 설계함 -> 우리 모델에 일정 수준의 설명 가능성을 부여.
• 우리는 영화와 음악에 관한 두 개의 datasets에 대해 광범위한 실험을 수행하여 state-of-the-art 솔루션인 Collaborative Knowledge Base Embedding 및 Neural Factorization Machine에 대한 유의미한 개선을 보여줍니다.

 

Introduction

• KG를 사용하지 않는 방식
  • KG를 사용하지 않는 방식(이전의 노력들)도 사용자의 프로필이나 아이템 속성 같은 보조 데이터를 추천 시스템에 통합하는 것의 중요성을 보여줌.
• KG를 사용하는 방식
  • 최근, item에 대한 배경시직과 이들간의 관계를 포괄하는 포괄적인 보조 데이터 때문에 KGs에 대한 관심이 더 증가 함.
  • 보통 \((Ed\;S h e e r a n,\;l s S i n g e r O f,\;S h a p e \; of\; You)\)같은 triplets 형태로 user-item interaction을 표현함.
  • KG 내의 interlinks(상호연결)을 탐색함.
    • interlinks에는 user와 item간의 관계를 내포하는 connectivity(연결성)가 있는데, 이 정보가 추천에 보조적인 정보로 이용됨.

 

• KG에서 나온 extra user-item connectivity 정보로 인해 추천 시스템이 reasoning(추론) 과 explainability(설명가능)해짐.
  • 예를 들어, (Figure 1)에서 
  • 
  • user는 같은 가수 Ed Sheeran이 부른 Shape of You를 좋아하기 때문에 I see Fire에 연결됨. 이런 connectivity는 경로에서 정보를 종합해 보이지 않는 user-item interaction(즉, potential recommendation)을 reason하는데 도움이 됨.
  • Running Example : (Alice, Interact, Shape of You)∧(Shape of You, SungBy, Ed Sheeran)∧(Ed Sheeran, IsSingerOf, I See Fire)⇒(Alice, Interact, I See Fire).
    • ∧ : 논리곱, AND를 의미하는 듯. (A ∧ B)는 A와 B가 모두 참일때 참이 됨.
  • 이런 추론은 interaction 뒤에 숨겨진 user intents(사용자의 의도)드러내며 추천 뒤에 숨겨진 explanations를 제공함. 따라서 KG에서 이런 connectivity를 어떻게 모델링할 것인지는 추천시스템에 knowledge를 주입하는 데 매우 중요함.

 

• 지식 기반 추천에 대한 이전의 노력들을 크게 2가지 방법으로 분류됨. 두 방법 모두 한계가 있음
  1. Path-based methods
     • user와 item 간의 유사성을 refine(개선, 정제 정도로 해석하면 될듯)하기 위해 meta-paths를 도입함.
     • 그러나 우리는 meta-path가 다음과 같은 한계 때문에 KG를 통해 추론하는데 비효율적이라고 주장함
       1. relations는 보통 meta-pahts에서 제외되기 때문에, 특히 유사한 엔티티이지만 다른 realtions인 경우가 meta-paths에 포함될 때 경로의 전체 의미를 거의 지정하지 못함.
       2. meta-path는 사전 정의된 domain 지식을 필요로 하기 때문에 보이지 않는  연결 패턴을 자동으로 발견하고 추론하지 못함. 
          
          끄적 끄적 뇌피셜
          meta-path : 이기종 정보 네트워크(Heterogeneous Information Network, HIN)에서 중요한 개념으로, 서로 다른 타입의 노드와 엣지로 구성된 경로를 나타냄. (이기종 정보 네트워크는 노드와 엣지가 여러 종류로 구성된 그래프를 의미함.)
          
          

          추천 시스템

          • 노드 타입: 사용자(U), 아이템(I), 태그(T)
          • mata-path 예시:
            • U-I-U: 사용자가 같은 아이템을 구매하거나 좋아한 관계
            • U-I-T-I-U: 사용자가 태그가 동일한 아이템을 구매한 관계

          지식 그래프(Knowledge Graph, KG)에서 특정한 경로를 찾기 전에 메타 경로를 먼저 정의하고, 그 메타 경로에 맞춰서 구체적인 경로를 찾는 방식인듯. 아래는 gpt가 들어준 예시

          절차

          1. 메타 경로 정의 : 분석 목표에 따라 메타 경로를 정의. 메타 경로는 다양한 노드 타입과 엣지 타입의 조합으로 구성됨.
          2. 메타 경로에 맞는 실제 경로 탐색 정의된 메타 경로에 따라 실제 네트워크에서 구체적인 경로를 탐색합니다. 이는 데이터베이스 쿼리나 그래프 탐색 알고리즘을 사용하여 수행할 수 있습니다. 

          예시 : 학술 네트워크

          • 목표: 특정 연구자와 관련된 공동 연구자 찾기
          • 메타 경로 정의: A-P-A (연구자-논문-연구자)
          • 실제 경로 탐색:
            • 연구자 A가 작성한 논문 P를 찾고, 논문 P에 참여한 다른 연구자들을 탐색함.

          예시 : 영화 추천 시스템

          • 목표: 사용자가 좋아할 만한 영화를 추천
          • 메타 경로 정의: U-M-D-M-U (사용자-영화-감독-영화-사용자)
          • 실제 경로 탐색:
            • 사용자 U가 좋아하는 영화 M의 감독 D를 찾고, 감독 D가 제작한 다른 영화 M을 탐색하여 그 영화를 좋아하는 다른 사용자 U를 추천.
              
              

          메타 경로 탐색 알고리즘

          메타 경로 기반의 탐색 알고리즘은 다음과 같은 절차를 따릅니다:

          1. 메타 경로 추출: 네트워크에서 메타 경로에 해당하는 모든 가능한 경로를 추출합니다.
          2. 경로 필터링: 추출된 경로 중에서 필요한 조건을 만족하는 경로를 필터링합니다. 예를 들어, 특정 주제의 논문만을 고려할 수 있습니다.
          3. 유사도 계산: 경로를 기반으로 노드 간의 유사도를 계산합니다. PathSim이나 HeteSim과 같은 알고리즘을 사용하여 유사도를 측정할 수 있습니다.
          4. 추천 및 분석: 계산된 유사도를 바탕으로 추천을 수행하거나 네트워크를 분석합니다. 예를 들어, 유사도가 높은 논문을 추천하거나, 중심적인 연구자를 식별할 수 있습니다.meta-paths는 사전 정의되기 위해 domain 지식을 필요로 하기 때문에 보이지 않는 연결 패턴을 자동으로 발견하고 추론하지 못함.
  2. Embedding-based Methods
     • TransE 및 TransR 같은 지식 그래프 임베딩(KGE) 기술
     • KGE는 엔티티간의 직접적인 relation만 고려하며, multi-hop relation 경로는 고려하지 않음.
     • 또한,  user-item connectivity의 characterization은 representation learning을 guide하기 위함이지 user의 선호도를 추론하기 위함이 아님.

 

 

• 이 연구에서는 item에 대한 user의 선호도를 추론하기 위해 경로를 추론하는 solution을 개발하고자 함.
  • reasoning 측면에서,
    • 엔티티들의 sequential dependencies과 user-item pair을 연결하는 path상의 realtions를 잘 모델링하길 기대함.
  • explainability 측면에서, 
    • user interest를 추론할 때 각각의 경로가 어떤 기여를 하는지 구별할 수 있는, 즉 다른 경로의 다른 기여를 구별할 수 있게 함.
• 결론적으로, 우리는 이를 위해 Knowledge-aware Path Recurrent Network (KPRN)라는 새로운 solution을 제안.
  • 엔티티와 realtions를 둘다 고려해 경로에 대한 representations를 생성할 뿐만 아니라, user 선호도를 경로에 기반해서 추론함.
    • 구체적으로, 우리는 먼저 KG에서 related 엔티티와 관계로 구성된 user-item pair간의 qualified paths를 추출함.
    • 그런 다음 LSTM( Long Short-Term Memory ) 네트워크를 사용해 엔티티와 relations의 sequential dependencies를 모델링 함.
    • 그 후, pooling operation을 수행해 paths의 representations를 집계하여 user-item pair에 대한 예측 signal을 얻음.
      • pooling operation(attention mechanism과 같은 역할)이 예측에 대해 서로 다른 경로들의 기여도를 구별함. 
      • => 이 덕분에 우리 모델은 Castle on the Hill is recommended since you have listened to Shape of You sung and written by Ed Sheeran 와 같은 path-wise explanations를 제공할 수있음.
    • 그리고 2개의 데이터 세트에 대해 extensive experiments를 수행해 우리의 방법을 검증함.
• 이 연구의 기여는 3가지로 요약됨:
  1. 추천 뒤의 이유를 더 잘 드러내기 위해 KG에 대한 명시적 추론을 수행하는 것의 중요성을 강조함
  2. path 의미를 학습하고 이를 추천에 통합하기 위해 ene-to-end neural network model을 제안함.
  3. MovieLens benchmark를 IMDB와 정렬해서 KG 추천을 연구하기 위한 데이터 세트를 기여함. 우리는 데이터에서 우리의  방법을 검증하고, KG-enhanced recommendation의 신흥 분야에서 작업하는 커뮤니티를 촉진하기 위해 데이터와 코드를 공개함.

 

Knowledge-aware Path Recurrent Network

Background

KG는 노드는 entities \(\mathcal{E}\)로, 엣지는 relations \(mathcal{R}\)로 구성된 directed graph임. 

형식적으로, \(\mathcal{KG}~=~\{(h,r,t)|h,r~\in~\mathcal{E},r~\in~\mathcal{R}\}\)로 정의되고, 각 삼중항 \((h,r,t)\)는 head 엔티티 \(h\)에서 tail 엔티티 \(t\)로의 관계 \(r\)을 나타냄.

• user-item interaction 데이터는 보통 bipartite graph로 표현됨. 특히, user 집합을 \(\mathcal{U}{=}\{u_{t}\}_{t=1}^{M}\), item 집합을 \(\mathcal{I}=\{i_{t}\}_{t=1}^{N}\)로 나타내며,
  • 여기서 \(M\)과 \(N\)은 각각 user와 item의 수를 의미. 
• user와 item간의 상호작용은 triplet \(\tau=(u,\,i n t e r a c t,\,i)\)나타내며 여기서 \(interact\)는 사전 정의된 relation임.

Preference Inference via Paths

• \(\mathcal{G}\)내에서, 우리는 형식적으로 user \(u\)에서 item \(i\) 까지의 path를 정의함 : 
  • \(p=[e_{1}\stackrel{r_{1}}{\longrightarrow}e_{2}\stackrel{r_{2}}{\longrightarrow}\cdot\cdot\cdot\stackrel{r_{L-1}}{\longrightarrow}e_{L}]\)
    • 여기서 \(e_{1}=u,e_{L}=i\)
• 예시 :

  

  음악 추천

  여기서 user "Alice"가 "listen to Castle on the Hill" 행동을 하는 것은 아래와 같은 paths로 참조될 수 있음.
  
  • \(p_1=[Alice\stackrel{interact}{\longrightarrow}{Shape\,of\,you} \stackrel{IsSongOf}{\longrightarrow}{\div} \stackrel{ContainSong}{\longrightarrow}{Castle\,on\,the\,Hill}]\)
  • \(p_2=[Alice\stackrel{interact}{\longrightarrow}{Shape\,of\,you} \stackrel{SungBy}{\longrightarrow}{Ed\,Sheeran} \stackrel{IsSingerOf}{\longrightarrow}{Castle\,on\,the\,Hill}]\)
  • \(p_3=[Alice\stackrel{interact}{\longrightarrow}{Shape\,of\,you} \stackrel{InteractedBy}{\longrightarrow}{Tony} \stackrel{Interact}{\longrightarrow}{Castle\,on\,the\,Hill}]\)

동일한 user Alice에서 동일한 item Castle on the Hill 로의 위의 경로들은 그들의 다른 multiple-step relations를 분명하게 표현하고, listen 행동의 다양한 구성적 의미와 possible explanations를 암시함.

특히 \(p_1\)과 \(p_2\)는 Alice가 Ed Sheeran이 부른 노래와 앨범 \(\div\)에 속한 노래를 선호할 수 있음을 추론하며,

\(p_3\)는 collaborative filtering(CF) effect를 반영함 : 유사한 사용자는 유사한 선호도를 가지는 경향이 있음

 

따라서, reasoning의 관점에서, 우리는 경로를 따라 connectivity을 사용해 relation 표현을 구성적으로 학습하고, user와 target item간의 상호작용 관계를 예측하기 위해 이를 함께 가중 풀링함.

• Task Definition :
  • user \(u\), target item \(i\), \(u\)와 \(i\)를 연결하는 path 집합 \(\mathcal{P}(u,i)=\{p_{1},p_{2},\cdot\cdot\cdot,p_{K}\}\)이 주어졌을 때, 다음 식을 통해 interaction(둘 사이의 관계인 듯)을 추정하는 것임. :
    • $$\hat{y}_{u i}=f_{\Theta}(u,i|P(u,i)),\qquad\qquad\qquad\qquad(1)$$
      • 여기서 \(f\)는 파라미터 \(\Theta\)가 있는 기본 모델, \( \hat{y}_{u i} \)는 user-item interaction에 대한 예측 점수를 의미함.
      • Embedding-based methods과 달리, 우리는 connectivity \(\mathcal{P}(u,i)\)에 의해 추론된 triplet  \(\tau=(u,\,i n t e r a c t,\,i)\)의 타당성 점수로 \( \hat{y}_{u i} \)를 설명할 수 있음.

Modeling

KPRN은 각 user-item pair의 경로 집합을 input으로 사용해 user가 target item과 interact할 가능성을 나타내는 점수를 output으로 내놓음.

 

 

Figure 2에 설명된 바와 같이, 주요 구성 요소는 3가지가 있음 :

1. Embedding layer
   • path \(p_k\)를 임베딩 벡터로 표현하는 레이어
   • 임베딩 레이어는 엔티티, 엔티티 type, 다음 노드를 가리키는 relation 3가지 정보를 latent space로 투영함.
2. LSTM layer
   • 엔티티의 구성적 의미를 relations에 따라 캡쳐하는 것을 목표로 elements를 순차적으로 인코딩함
3. Pooling layer
   • 여러 path를 결합해 주어진 user가 target item과 interact하는 final score을 output으로 내놓음.

Embedding Layer

• 엔티티 type 과 엔티티 값
  • 경로 \(p_k\)가 주어지면, 우리는 각 엔티티의 type(e.g., person or movie) 과 특정 값(e.g., Peter Jackson or The Hobbit II)을 두개의 별도의 임베딩 벡터 \(e_{l}\in\mathbb{R}^{d}\)와 \(\mathbf{e}_{l}^{\prime}\in\mathbb{R}^{d}\)로 투영함.
    • 여기서 \(d\)는 임베딩 사이즈.
• semantics of relations
  • 경로 \(p_k\)의 각 relation \(r_l\)은 embedding vector \({\bf r}_{l}\ \ \in\ \mathbb{R}^{d}\)로 표현됨.
  • relaiton을 embedding할 때 같이 넣는 이유
    • 동일한 엔티티-엔티티 pair이 연결된 relation이 달라지면 다른 의미를 가짐. 이런 차이는 user가 item을 선택한 다양한 의도를 드러낼 수 있음.
      • 예) (Ed Sheeran, IsSingerOf, Shape of You)  과 
          (Ed Sheeran, IsSongwriterOf, Shape of You) 라는 두 경로가 user's preference를 참조하는 triplet인 경우, relation을 지정하지 않으면 이런 경로들은 동일한 embedding으로 표현됨.
        -> user 가 Ed Sheeran이 부른 노래를 선호하는지, Ed Sheeran이 작곡한 노래를 선호하는지의 가능성을 무시하게 됨. 그래서 우리는 relations의 의미를 representation learning(임베딩 말하는 듯)에 명시적으로 통합하는 것이 중요하다고 판단함.
• 결과적으로 경로 \(p_k\)의 임베딩 집합 \(\left[{\bf e}_{1},{\bf r}_{1},{\bf e}_{2},\cdot\cdot\cdot,{\bf r}_{L-1},{\bf e}_{L}\right]\) 을 얻음. 각 element는 엔티티 또는 relation을 나타냄.

LSTM Layer

• path를 설명하기 위한 embedding sequence가 주어지면, 우리는 RNN 모델을 사용해 sequential 정보를 탐색하고, 전체적인 의미(holistic semantics)를 인코딩하기 위한 single representation을 생성할 수 있음.
• 여기서는 RNN methods들 중 LSTM을 채택함.
  • LSTM이 sequence에서 long-term dependency를 기억할 수 있기 때문에 채택함.
    끄적 끄적 뇌피셜
    저기서 말하는 dependency라는게 정확히 어떤 느낌인지 애매했는데 나름의 생각정리를 해보자면,,
    - sequence 데이터 내의 관계 : 
    ㆍ시퀀스 데이터는 시간 또는 순서에 따라 배열된 데이터. 예를 들면 사용자의 클릭 기록, 시청 기록, 구매 기록 등이 시퀀스 데이터로 나타날 수 있음.
    ㆍ이런 데이터 내에서 앞선 항목과 뒤따르는 항목 사이에는 dependency(종속성)이 존재할 수 있는데, 예를 들면 사용자가 이전에 어떤 영화들을 봤는지가 이후에 볼 영화에 영향을 미칠 수 있음.
    
    - 장기 종속성 (long-term dependency) :
    ㆍ 시퀀스 데이터에서 멀리 덜어진 두 항목 사이의 관계를 의미함. 예를 들어, 몇 달 전에 본 영화가 현재 추천할 영화에 영향을 줄 수 있는 경우.
    ㆍLSTM네트워크는 이런 장기 종속성을 기억하고 학습할 수 있음. (장기 기억을 할 수 있게 모델링 되어서 그런듯)
    
  • 이런 long-term sequential pattern은 user와 item 엔티티를 연결하는 paths를 추론하여 "interact" realtion의 신뢰도를 추정하는데 중요함.

    

• path-step \(l-1\)에서, LSTM 레이어는 input vector \(x_{l-1}\)을 input으로 받고 hidden state vector \(h_{l-1}\)를 output으로 내놓음.
  • input vector \(x_{l-1}\) : 
    • $${\bf x}_{l-1}={\bf e}_{l-1}\oplus{\bf e}_{l-1}^{\prime}\oplus{\bf r}_{l-1},\qquad\qquad\qquad(2)$$
      • 여기서 \(\oplus\) : concatenation operation(연결 연산.그냥 이어붙이는 연산인 것 같다.)
      • 마지막 엔티티 \(e_L\)의 경우, path 끝에 null relation \(r_{L}\)이 패딩됨.
      •  따라서 input vector \(x_{l-1}\)은 순차적 정보 뿐만 아니라 엔티티와 다음 엔티티와의 relation의 semantic information을 포함함.
  • output \(h_{l-1}\) :
    • subsequence(부분 시퀀스) \([e_{1},r_{1},\cdot\cdot\cdot\ ,e_{l-1},r_{l-1}]\)를 소비함.
      뇌피셜 끄적 끄적
      여기서 소비라는게 무슨 의미인가 했는데 나름대로 생각해보자면 ...
      '소비한다'라는 표현은 LSTM 네트워크가 현재 단계의 계산을 수행하기 위해 이전 단계까지의 데이터를 입력으로 사용한다는 것을 의미하지 않을까..LSTM이 이전 시퀀스 정보를 사용해 현재 시퀀스 상태를 업데이트하는 과정을 의미하는듯.
      시퀀스 데이터 [A,B,C,D]가 있을 때, LSTM은 
      1. A를 입력으로 받아들여 첫 번째 hidden state \(h_1\)을 계산하고
      2. B와 첫 번째 hidden state \(h_1\)을 입력으로 받아들여 두 번째 hidden state \(h_2\)를 계산함.
      3. C와 두 번째 hidden state \(h_2\)을 입력으로 받아들여 세 번째 hidden state \(h_3\)을 계산함.
      4. D와 세 번째 hidden state \(h_3\)를 입력으로 받아들여 네 번째 hidden state \(h_4\)를 계산함.
      이제 여기서 각 단계에서 LSTM은 이전 단계의 hidden state를 소비하여 현재 단계의 hidden state를 계산.
  • 노란 형고아펜 부터 정리해야함. .ㅇㄻ니허니허니ㅓㄹ재ㅔㅓㅣㅓㅣ 오타인가 논문ㅁ 이상해서 일단 안

 

 

경로 \(p_k\)의 표현을 확립한 후, 우리는 삼중항 \(\tau=(u,i n t e r a c t,i)\)의 타당성을 예측하는 것을 목표로 함. 이를 위해 2개의 fully-connected layers을 채택해서 final state를 예측 점수(output)로 투영함 : 

• 여기서 \(\bf{W}_1\)와 \(\bf{W}_2\)는 각각 첫 번째 및 두 번째 layers의 계수 가중치. 단순성을 위해 bias vectors는 생략됨. activation function은 ReLU사용.

Weighted Pooling Layer

user-item entity pair은 보통 KG에서 그들을 연결하는 set of paths를 가지고 있음.

• \(S = \left\{s_{1},s_{2},\cdot\cdot\cdot\ ,s_{K}\right\}\) : user-item pair \((u,i)\)을 연결하는 \(K\) paths, \(\begin{array}{r l}{{\mathcal{P}}(u,i)}&{{}=\ }&{{}\{p_{1},p_{2},\cdot\cdot\cdot,p_{K}\}}\end{array}\)에 대한 predictive socres. 각각 식 (4)로 계산됨.
  • 최종 예측은 모든 경로의 점수 평균. 계산은 식(5) 와 같이 함.
    • $$\hat{y}_{u i}=\sigma(\frac{1}{K}\sum_{k=1}^{K}s_{k})\quad\quad(5)$$
  • 그러나 이전 연구들은 각 경로(경로가 각각 다르니까)는 user preference를 모델링하는데 기여하는 정도가 각각 다르다고 제안함. 그러나 방정식 (5)는 각 path의 중요도를 명시하지 않음. 
  • => 이전 연구에서 영감을 받아 우리는 모든 경로의 점수를 집계할 때 가중 풀링 연산(Weighted pooling operation)을 설계함. pooling function은 식(6)과 같이 정의함:
    • $$g(s_{1},s_{2},\cdot\cdot\cdot\cdot\cdot\cdot s_{K})=\log\left[\sum_{k=1}^{K}\exp\left(\frac{s_{k}}{\gamma}\right)\right],\qquad(6)$$
    • 최종 예측 점수는 식 (7)과 같이 주어짐 :
      • $$\hat{y}_{u i}=\sigma(g(s_{1},s_{2},\cdot\cdot\cdot\ ,s_{K}))\quad\quad\quad(7)$$
    • 여기서 \(\gamma\)는 하이퍼 파라미터로, 지수 가중치를 조절함. 이런 풀링은 path의 중요성을 구별할 수 있으며, 이는 back propagation 단계에서 각 path의 score에 비례하는 gradient 때문임.(식(8))
      • $$\frac{\partial g}{\partial s_{k}}=\frac{\exp(s_{k}/\gamma)}{\gamma\sum_{k^{\prime}}\exp(s_{k^{\prime}}/\gamma)},\qquad\qquad\qquad(8)$$
    • 게다가, pooling function(식(6))은 final prediction을 더 유연하게 해줌. 
      • 특히, \(\gamma\ \to\ 0\)로 설정하면 pooling function은 max-pooling 에 가까워짐.
      • 반면 \(\gamma\ \longrightarrow\ \infty\) 이면 pooling function 은 mean-pooling에 가까워짐.

        끄적 끄적 뇌피셜
        \(\gamma\)는 가중 풀링 연산에서 각 경로의 점수를 제어하는 하이퍼 파라미터로, 경로 score간의 차이를 강조하거나 완화하는 역할(0에 가깝게 설정할수록 차이를 강조하고 무한대에 가깝게 설정할수록 차이를 완화)
        ㆍ \(\gamma\ \to\ 0\) : \(\gamma\)가 0에 가까워지면, 지수 함수의 값들이 매우 커지게 됨. 이 경우 가장 큰 값을 가진 path가 거의 모든 영향을 미치게 됨. (결과적으로 max-pooling과 유사)
        ㆍ \(\gamma\ \longrightarrow\ \infty\) : \(\gamma\)가 매우 커지면, 지수 함수의 값들이 거의 비슷해지게 됨.(무한대로 가면 \(s_k\)가 어떤 값이던지 \(\frac{s_{k}}{\gamma}\)는 0으로 갈테니까)이 경우 모든 경로의 점수가 비슷하게 가중치를 가지를 가지게 되어서 결과적으로 mean-pooling과 유사하게 됨.
        
        √ 가중 풀링 함수 정의 유도 과정 :
             1. 지수함수 적용 및 합산 :
                  ㆍ각 경로의 점수 \(s_k\)에 지수 함수 \(exp(s_k/\gamma)\)를 적용해 변환함. 지수함수는 큰 값을 더욱 크게, 작은 값을 더욱 작게 만들어 줌.
                  ㆍ 변환된 값들을 합산함 \(:\sum_{k=1}^{K}\exp(s_{k}/\gamma).\)
             2. 로그 함수 적용 :
                  ㆍ지수 함수의 역함수인 로그 함수를 적용해 합산된 값을 다시 변환함. 이 과정은 값의 범위를 조절하고, 수치적 안정성을 보장함.
        
        
        √ gradient를 유도하는 과정 : 
        \(g(s_{1},s_{2},\cdot\cdot\cdot\ ,s_{K})=1\mathrm{og}\left[\sum_{k=1}^{K}\mathrm{exp}\left(\frac{s_{k}}{\gamma}\right)\right]\) 이 함수를 각 경로 점수 \(s_k\)에 대해 미분하는 과정
        
        1. 풀링함수 정의에서 내부 합산 부분을 \(Z\)로 치환
        \(g=\log\left(\sum_{k=1}^{K}\exp\left(\frac{s_{k}}{\gamma}\right)\right)\)
        ⇒  \(g=\log(Z)\) (\(Z\,=\,\sum_{k=1}^{K}\exp\left(\frac{s_{k}}{\gamma}\right)\))
        
        2. chain rule을 사용해 미분. 각 경로 함수 \(s_k\)에 대해 \(g\)를 미분함.
        $$\frac{\partial g}{\partial s_{k}}~=~\frac{\partial g}{\partial Z}~\cdot~\frac{\partial Z}{\partial s_{k}}$$
        
        3. \(\frac{\partial g}{\partial Z}\) 계산
        \(g=\log(Z)\) ⇒  \(\frac{\partial g}{\partial Z} = \frac{1}{Z}\)

        
        4. \(\frac{\partial Z}{\partial s_{k}}\) 계산
        \(Z=\sum_{k=1}^{K}\exp\left({\frac{s_{k}}{\gamma}}\right)\) ⇒ \(\frac{\partial Z}{\partial s_{k}}\,=\,\frac{\partial}{\partial s_{k}}\,\left(\sum_{j=1}^{K}\exp\,\left(\frac{s_{j}}{\gamma}\right)\right) = \exp\left({\frac{s_{k}}{\gamma}}\right)\cdot{\frac{1}{\gamma}}\,=\,{\frac{1}{\gamma}}\exp\left({\frac{s_{k}}{\gamma}}\right)\)
        
        5. 최종 미분 계산
        \(\frac{\partial q}{\partial s_{k}}\,=\,\frac{1}{Z}\,\cdot\,\frac{1}{\gamma}\,\exp\left(\frac{s_{k}}{\gamma}\right)\)
         ⇒  \(\frac{\partial g}{\partial s_{k}}\;=\;\frac{\exp\big(\frac{s_{k}}{\gamma}\big)}{\gamma\sum_{k=1}^{K}\exp\ \!\big(\frac{s_{k}}{\gamma}\big)}\)  (∵\(Z=\sum_{k=1}^{K}\exp\left({\frac{s_{k}}{\gamma}}\right)\))
        
        
        이제 순전파 단계에서 입력 데이터를 통해 네트워크를 통과해 예측 값을 계산하고, 이 단계에서 각 경로 score \(s_k\)가 가중 풀링 함수 \(g\)를 통해 최종 예측 값 \(\hat{y}\)를 생성.
        모델의 예측 값 \(\hat{y}\)과 실제 값 \(y\)간의 차이를 계산해서 손실 함수(\(L\))를 구하고,

        그 손실함수를 \(s_k\)에 대해 미분한 식에 저 위의 gradient 식이 포함이 되어 있을 거임.
        그래서, 각 경로 점수에 대한 손실 함수의 gradient는 경로 점수의 크기와 관계가 있음.
        즉, 점수가 높은 경로는 그래디언트의 크기가 커지고, 낮은 경로는 그래디언트의 크기가 작아짐. 이는 역전파 과정에서 각 경로 점수가 모델 학습에 기여하는 정도를 결정함.

Learning

• 최근 연구와 유사하게 우리는 추천 학습 작업을 이진 분류 문제로 처리함.
  • 여기서, 관찰된 user-item interaction은 target value가 1로 할당되며, 그렇지 않으면 0임.
• 우리는 모델의 파라미터를 학습하기 위해 pointwise learning method를 사용함. 
  • 특히, negative log-likelihood는 목표 함수로 채택되며, 이는 다음과 같이 정의됨.(참고 링크)
    • $$\mathcal{L}=-\sum_{(u,i)\in O^{+}}\log\hat{y}_{u i}+\sum_{(u,j)\in O^{-}}\log(1-\hat{y}_{u j}),\ ~\ ~(9)$$
      • 여기서 \({\cal O}^{+}\ =\ \big\{(u,i)|y_{u i}\ =\ 1\big\}\) : 긍정 user-item interaction pairs(user가 item을 좋아한 경우)
      • \({\cal O}^{-}\;=\;\{(u,j)|y_{u j}=0\}\) : 부정 user-item interaction pairs(user가 item을 좋아하지 않은 경우)
        끄적 끄적 뇌피셜
        log likelihood(클수록 좋음)에 마이너스 붙인게 negative log-likelihood(작을수록 좋음). 작을 수록 좋게 만들어서 모델의 loss로 사용하는듯.
        \({\cal O}^{+}\ =\ \big\{(u,i)|y_{u i}\ =\ 1\big\}\)가 사용자가 아이템을 좋아한 경우, \({\cal O}^{-}\;=\;\{(u,j)|y_{u j}=0\}\)가 사용자가 아이템을 좋아하지 않은 경우로, 기존  negative log-likelihood 형태인 \(l(\theta)=-\sum_{i=1}^{n}(y_{i}\mathrm{log}(\hat{y}_{\theta,i})+(1-y_{\theta,i})\mathrm{log}(1-\hat{y}_{\theta,i}))\)에서 각각  log앞에 곱해진 실제 값을 저걸로 대신한 것 같다.
        긍정 user-item interaction pairs 인 경우 모델의 예측값인  \({\hat{y}}_{u i}\)가 1에 가까울수록 좋은거 이므로, \(\log{\hat{y}}_{u i}\)는 커지는 방향으로,
        부정 user-item interaction pairs의 경우 모델의 예측값인 \({\hat{y}}_{u i}\)가 0에 가까울수록 좋은 거 이므로, \(1-{\hat{y}}_{u i}\)는 1에 가까워지는 방향으로, 마찬가지로 \(\log(1-\hat{y}_{u j})\) 는 커지는 방향으로 파라미터가 업데이트 되게 될거임. 
        
        근데 왜 $$\mathcal{L}=-\sum_{(u,i)\in O^{+}}\log\hat{y}_{u i}-\sum_{(u,j)\in O^{-}}\log(1-\hat{y}_{u j}),\ ~\ ~(9)$$이게 아니고 $$\mathcal{L}=-\sum_{(u,i)\in O^{+}}\log\hat{y}_{u i}+\sum_{(u,j)\in O^{-}}\log(1-\hat{y}_{u j}),\ ~\ ~(9)$$이거인지 모르겠다..
• 우리는 과적합을 피하기 위해 trainable parameters \(\Theta\)에 대해 L2 정규화를 해줌. 여기서는 단순화를 위해 생략함.(구현 세부사항은 Experimental Settings 섹션에서 자세히 설명됨)

Experiments

이 섹션에서는 제안한 method를 평가하기 위해 2 개의 실제 데이터 셋에서 실험을 수행함. 우리는 다음과 같은 research question 에 답하고자 한다:

• RQ1 : state-of-the-art KG-enhanced methods와 비교하여 우리의 method는 어느정도인가?
• RQ2 : multi-step modeling(e.g., 엔티티 및 relation types의 통합)은 KPRN에 어떻게 영향을 미치는가?
• RQ3 : 제안한 method가 경로를 추론하여 item에 대한 user preference를 추론할 수 있는가?

Dataset Description

우리는 2가지 시나리오를 고려함 :

1. movie recommendation
   • movie domain에서는 MovieLens-1M과 IMDb 데이터셋의 조합인 MI를 사용. 이는 영화 제목과 출시 날짜로 연결됨.
     • MovieLens-1M은 사용자-아이템 상호작용 데이터를 제공
     • IMDb는 장르, 배우, 감독 및 작가와 같은 영화에 대한 보조 정보를 포함하는 KG part로 사용
2. music recommendation
   • Music domain에서는 WSDM cup 2018 Challenge에서 채택된 벤치마크 데이터셋인 KKBox를 사용하며, 이는 음악 스트리밍 서비스 KKBox에서 제공됨.
     • 해당 데이터는 user-item interaction data외에도 가수, 작곡가 및 장르와 같은 음악 설명이 포함되어 있음.

두 데이터셋에 대한 통계는 Table 1 에 요약되어 있음.

우리는 다음과 같이 데이터 셋을 처리함. : 

• user가 movie를 평가하거나 노래와 상호작용한 기록이 있는 경우, 해당 user-movie pair 또는 user-song pair을 observed positive feedback로 설정하고, target value를 1로 설정함. 그 외에는 target value 를 0으로 설정함.
• 각 dataset에 대해, 우리는 각 user의 interaction history의 80%와 20%를 무작위로 나누어 training set와 test set를 구성함.
  • training set의 각 positive user-item interaction pair에 대해 우리는 user가 상호작용하지 않은 4개의 negative items과 짝을 이루는 negative sampling strateg을 수행함.
  • test 단계에서는 positive interaction과 negative interaction의 비율을 1:100으로 설정하며, 100개의 negative item을 무작위로 샘플링하여 하나의 positive item과 짝을이루도록 했음

 

Path Extraction

실제로 KG에 모든 connected paths를 모두 탐색하는 것은 노동 집약적이며 실행 불가능함. 특히 경로의 길이에 따라 수백만 개의 interlink들이 생성되어 경로 수가 기하급수적으로 증가함.

이전 연구에서 제안한 바와 같이, 모든 경로를 특정 길이로 잘라내고 remote connections을 무시하는것 user-item pair간의 connectivity를 모델링하는데 충분함.

또한, 길이가 6을 초과하는 paths는 noise entities를 포함함.( Sun et al. 2011 이 과거에 밝힌 듯)

따라서, 본 연구에서는 길이가 최대 6인 모든 qualified paths를 추출하여 모든 user-item pairs를 연결함.

 

Experimental Settings

Evaluation Metrics

우리는 top-K 추천 및 preference ranking을 평가하기 위해 2가지 평가 protocols를 채택함:

1. hit@K : 관련 item이 추천 목록의 상위 K 위치 내에 검색되는지 여부를 고려함
2. ndcg@K : ranking 목록의 상위 K내에서 positive item과 negative item간의 상대적 순서를 측정함.

우리는 test set 의 모든 instance에 대해 \(K=\{1,2,\cdot\cdot\cdot,15\}\)에서 평균 metrics를 보고함.

 

Baselines

다음과 같은 method들과 우리가 제안한 method를 비교함

• MF (Rendle et al. 2009) : user-item interaction만을 활용하는 Bayesian personalized ranking(BPR) loss이 있는 matrix factorization
• NFM (He and Chua 2017) : 

Parameter Settings