個人的な論文メモ④：Knowledge Graph Attention Network for Recommendation

個人の興味関心の備忘録として記録したものであり、情報の正確性や完全性を保証するものではありません。

# 目次
+ [三行まとめ](#三行まとめ)
+ [背景・目的](#背景・目的)
+ [タスクの定式化](#タスクの定式化)
+ [方法](#方法)
+ [検証](#検証)
+ [結論と今後の課題](#結論と今後の課題)

[論文：Knowledge Graph Attention Network for Recommendation](https://arxiv.org/pdf/1905.07854)

# 三行まとめ
:::note info
+ KGATは知識グラフを用いてユーザーとアイテム間の高次の関係性をモデル化した手法
+ アテンション機構により重要な関係性だけに注目し、高い推薦精度と説明可能性を実現
+ データが疎なユーザーには有効だが、クリックが多すぎるユーザーには高次関係性が逆効果になる場合も存在
:::


# 背景・目的
推薦システムの成功により、検索エンジンやEコマースやニュースポータルなどのWEBアプリケーションで広く用いられている。
ユーザーの行動データからユーザーの趣味嗜好を推測するため、多くの研究が協調フィルタリングに取り組んできた。
協調フィルタリングはアイテム属性やユーザープロファイル、テキストなどの補助情報のモデル化が困難という欠点が存在。
ファクタライゼーションマシンは、ユーザーIDやアイテムIDと一緒に補助情報もベクトルに変換し、教師あり学習モデルに入力することで協調フィルタリングの問題を改善。
しかし、これらの手法は、相互作用のあるデータを独立したデータとしてモデル化するため、関係性を考慮していないという欠点が存在する。

### 欠点を具体的に考える
ユーザー$u_1$と映画$i_1$には関係性があり、この映画は人物$e_1$によって監督されている
黄色と灰色の背景が、高い関係性によって発見されるユーザーと映画

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426482/20e567b0-028d-4770-855a-95bd8147aae7.png)

**協調フィルタリングだと**
+ 映画$i_1$を視聴した類似ユーザーのユーザー$u_4$や$u_5$に注目することになる

**教師あり学習だと**
+ 属性情報である監督$e_1$を共有する類似アイテムの映画$i_2$を注目することになる

協調フィルタリングがユーザー間の類似性を見ていて、教師あり学習は属性の情報を見ているため、お互いは推薦において補完関係にある。この２つを組み合わせれば、より高次の関係性を捉えることが可能である。

そこで、知識グラフとユーザー・アイテム間グラフを統合したハイブリットな構造を、
**協調的知識グラフ : Collaborative Knowledge Graph CKG**と呼ぶ

推薦を成功させるカギは、CKG内の高次の関係性を十分に捉えること。
例えば、
- $\( u_1 \xrightarrow{r_1} i_1 \xrightarrow{r_2} e_1 \xrightarrow{r_2} i_2 \xrightarrow{r_1} \{u_2, u_3\} \)$
- $\( u_1 \xrightarrow{r_1} i_1 \xrightarrow{r_2} e_1 \xrightarrow{r_3} \{i_3, i_4\} \)$

### CKGの問題点
1. 対象ユーザーと高次の関係を持つノードの数は、その次数（関係の長さ）が大きくなるにつれて爆発的に増加するため、モデルに計算負荷をもたらす

2. 高次関係は予測への貢献度が一様ではないため、それぞれの関係の重要度を注意深く重み付け（あるいは選択）する必要がある

最近のいくつかの研究では、推薦システムのためにCKG構造を活用しようと試みている。
**パスベース**と**正則化ベース**の二つに分類できる
+ **パスベース**
全てのパスを入れたら計算量が多くなるので、高次の情報を含むパス(経路)を抽出し、それらを予測モデルへ入力する。重要なパスを選択するためにパス選択アルゴリズムを適用したり、パスを限定するためにメタパスのパターンを定義したりする。

　**パス選択アルゴリズム**：頻繁に現れるパターン、過去の行動と関連するパターンを選択
　**メタパス**：あらかじめ有用など思うパスを定義しておいて一致するパスのみ選択

パス選択を先に行う方法だと、推薦の性能がその選び方に左右されるのに、選択自体は推薦の目的で最適化されていない問題がある。また、事前に『どのパスを使うか（メタパス）』を決める方法は、複雑な知識グラフに対して専門的な知識が必要で、非常に手間がかかる

+ **正則化ベース**
知識グラフの構造を捉える追加の損失項目を設置して、推薦モデルの学習を正則化する
（予測誤差を小さくするだけではなく、知識グラフの構造にあった表現を学習するように促す）
高次関係性を推薦モデルに明示的に取り組むのではまく、あくまでも「暗黙的」な形で取り組んでいる
AとBの関係が深いので、それが似るように学習しましょうというルールを損失に入れること。
このルールを守ろうとするが、具体的なパスや関係性を使ったまでかは明確に残らない（解釈性が消える）

KGATでは、高次関係のモデリングにおける２つの課題に対応する工夫を備えている。
+ **再帰的なエンベディング伝播**
ノードのエンベディング(表現)を、その近隣ノードのエンベディングに基づいて更新し、この更新を再帰的に繰り返すことで、高次の接続性を線形時間で効率よく捉える。
+ **アテンションに基づく集約**
アテンション機構を活用して、伝播時に各隣接ノードの重要性(重み)を学習する。
これにより高次関係でどれほど重要かが分かる

従来のパスベース手法のような面倒なパス抽出は不要であり、正則化ベース手法よりも高次関係性を明確にモデル化できる。

# タスクの定式化
まずCKG(協調的知識グラフ)の概念を導入して、ノード間に存在する高次の接続性や複合的な関係性について説明

### ユーザー・アイテム二部グラフ(User-Item Bipartite Graph)
ユーザーとアイテムの過去のインタラクション(購入やクリック)をユーザー・アイテム２部グラフ$G_1$として表現
```math
G_1 = \{ (u,y_{ui},i ) | u\in U , i \in I \}
```
$U$：ユーザーの集合
$I$：アイテムの集合
リンク$y_{ui} =1$は、ユーザー$u$とアイテム$i$の間にインタラクションが存在することを表し、
そうでなければ、$y_{ui} =0$とする。

### 知識グラフ(Knowledge Graph)
アイテムの補助情報を知識グラフ(KG)と呼ばれる構造で整理する。
KGは、主語ー述語ー目的語のトリプルから構成される有向グラフである。

```math
G_2 = \{ (h,r,t ) | h,t\in E , r \in R \}
```
ある関係性($r$)が、主語($h$)から目的語($t$)に向かって存在していることを表す
(Hugh Jackman,ActorOf,Logan)は、「ヒュージャックマンは映画ローガンに出演している」

関係集合$R$は、標準的な方向(ActorOf)と逆方向(ActedBy)の両方を含む

アイテムとエンティティの対応関係を示す集合を以下のように定義
```math
A = \{ (i,e ) | i\in I , e \in E \}
```
ペア$(i,e)$は、「アイテム$i$が、知識グラフ内のエンティティ$e$と対応している」ことを示す

### 協調的知識グラフ(Collaborative Knowledge Graph : CKG)
ユーザーの行動とアイテムに関する知識を統合した「協調的知識グラフ(CKG)」という概念を定義
ユーザーの各行動を以下のトリプルで表現
```math
(u,interact,i)
```
ユーザー$u$とアイテム$i$の間に関係性がある場合($y_{ui} = 1 $)と表現する

アイテムとエンティティの対応関係を用いて、ユーザー・アイテムグラフとKGを融合させ、以下のように表現
```math
G = \{ (h,r,t) | h,t \in E' , r \in R' \}
```

$E' = E \cup U $ : エンティティとユーザーの集合を統合
$R' = R \cup Ineract $ : ユーザーとアイテムの関係性(購買やクリック)


### タスクの説明
+ 入力：ユーザー・アイテム2部グラフ$G1$と知識グラフ$G2$を含んだ協調的知識グラフ$G$
+ 出力：ユーザー$u$がアイテム$i$を選ぶ確率$\hat{y}_{ui}$を予測する

# 方法
提案手法のKGAT(Knowledge Graph Attention Network)を説明

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426482/a6cbba8f-f7ea-4418-af76-15ea3f9777fe.png)

主に3つのコンポーネントから構成させる
1. **エンベディング層(Embedding layer)**
各ノードをベクトルとしてパラメータ化し、協調的知識グラフの構造を表現する
1. **アテンション型エンベディング伝播層(Attentive embedding propagation layers)**
ノードのエンベディングを隣接ノードから再帰的に伝播させて表現を更新する。
アテンション機構を利用して伝播中の各隣接ノードの重みを学習する。
1. **予測層(Prediction layer)**
ユーザーとアイテムの最終的な表現をすべての伝播層から集約し、ユーザーとアイテムのマッチングスコアを予測して出力

### エンベディング層
グラフのノードをベクトルで表現し、異なる関係ごとに異なる空間に射影することで多面的な情報を表現し、正しい関係が常に最もらしくなるように学習する。
例えば、「ヒュー・ジャックマン」を「俳優」という関係性で見るときと、「監督」という関係性で見るときでは意味が異なる的なこと。

### アテンション型エンベディング伝播層
グラフ畳み込みネットワークの仕組みをベースとして、エンベディングを再帰的に伝播する方法を構築。
さらに、グラフアテンションネットワークの考えた方を用いて、各伝播の重要度を示す「アテンション重み」を生成し、その接続性の重要性を明らかにする。

この層は以下の3つの層から構成される。
1. 情報伝播(Information Propagation)
各ノードのエンベディングを近隣ノードへと伝播させる。
1. 知識を考慮したアテンション(Knowledge-aware Attention)
伝播する際に、各ノード間の関係性に応じて重要度（アテンションの重み）を学習する。
1. 情報集約(Information Aggregation)
伝播された情報を集約して各ノードのエンベディングを更新する。

### 予測層
伝播層で得られたユーザーとアイテムのエンベディング（ベクトル）を使って、ユーザーがアイテムを気に入るかどうかを予測する。
具体的には、ユーザーとアイテムのエンベディングの内積（ベクトルの類似性）を計算し、そのスコアが高ければ高いほど、そのユーザーがそのアイテムを選ぶ可能性が高いと予測する。

### 最適化
推薦モデルの最適化にはBPR損失を採用
この損失は、ユーザーが実際に関心を持ったアイテムに対して高い予測スコアを与えるように学習する。

# 実験
提案手法の有効性を示すために、3つの実世界データセットを用いて実験を行う。
実験では以下の問に答えることを目的としている。
+ KGATは、知識グラフを利用した最先端の推薦手法と比較して、どれほどの性能を示すのか？
+ KGATの各構成要素（知識グラフ埋め込み、アテンション機構、アグリゲータの選択）が性能にどのように影響するのか？
+ KGATは、ユーザーがアイテムに対して持つ嗜好について、妥当で理解可能な説明（解釈）を提供できるのか？

**使用データセット**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426482/8132b9bb-36cb-4b7a-9499-fb8583763758.png)


+ Amazon-book
Amazonのレビューデータで商品推薦において広く使われているデータセット
データの質を確保するために、ユーザーとアイテムの両方について、最低でも10回以上のインタラクションがあるもの
+ Last-FM
オンライン音楽プラットフォーム「Last.fm」から収集された、ユーザーが音楽を視聴した履歴のデータセット
2015年1月から2015年6月までの期間のデータを抽出。
データの質を担保するためにユーザーとアイテムが10回以上のインタラクションを持つものに限定
+ Yelp2018
Yelpの「Yelp Challenge 2018」で提供されたデータ
レストランやバーなどの地域の店舗（ローカルビジネス）を「アイテム」として扱う

トリプルが少ないデータは信頼性やモデルがうまく学習できない可能性があるので削除
（監督した、出演したなど、主語と目的語を結びついける関係のこと）

**データセットの分割**
+ 各データセットについて、各ユーザーのインタラクション履歴の80%をランダムに訓練データ、残りの20%をテストデータとして利用
+ 訓練データから10%をランダムに検証用データとしてハイパラ用に使用
+ ユーザーとアイテムに関係性があるものを正解として、関係性がないものを不正解とする

# 検証
ユーザーに対して推薦した上位20個のうち、いくつ正解していたかを各種モデルと比較する。

**評価指標**
+ Recall@K：何個含まれていたか
+ NDCG@K：好きなアイテムを上位に推薦できているか

KGATモデルはTensorflowで実装。埋め込みのサイズは64次元で固定。

### 全体的な比較
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426482/a8d47b88-9268-4be7-9524-46c5364a0a06.png)

KGATは全てのデータセットで最も良い性能を示す。
Amazon-Book:8.95%の改善
Last-FM:4.93%の改善
Yelp2018:7.18%の改善

### インタラクション数が少ない場合は？
知識グラフ(KG)を利用している目的の一つが、ユーザーとアイテム間のインタラクションが非常に少なく、ほとんど未観測な状態になっている問題への対処。
高次の関係性をモデル化することがこの問題の解決に役立つか調査
インタラクションの数に応じてグループ分けを行い実験
Amazon-bookでは、１ユーザーあたりのインタラクション数に応じて４グループに分割
+ インタラクション数が7未満
+ インタラクション数が15未満
+ インタラクション数が48未満
+ インタラクション数が4475未満

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426482/e9e5a273-ce8c-4024-a74e-4e1118a6684d.png)

+ KGATはほとんどのケースで他モデルよりもいい性能を示す
高次の関係性をモデル化することで、インタラクションが極めて少ないユーザーで優れた性能を発揮

+ インタラクションが非常に多いグループでは、KGATはベースラインをわずかに上回る程度
インタラクション数が多すぎるユーザーは嗜好が非常に一般的になり、捉えにくいことがあげられる
高次の関係性をを取り込むことがユーザーの嗜好にノイズを持ち込んで逆効果を生む可能性がある。

### 推薦の説明
アテンション機構のメリットが「高次の関係性」を用いてユーザーがあるアイテムを好む理由を説明できる。
Amazon-Bookからランダムに選んだ1人のユーザー(u208)とテストセットに含まれる未知のアイテム(i4293)を用いて、ユーザーとアイテムの間をつなく行動ベース・属性ベースの関係を抽出。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426482/8f71f504-3e52-4b1d-ae22-b271366d5a96.png)

+ KGATは行動ベースおよび属性ベースの高次の関係性を捉えることが出来る
+ 最も高いアテンションスコアを持っているのは左図の実線
u208→Old Mans war → john Scalzi → i4923
あなたは同じ著者ジョンスコルジーの作品「老人と宇宙」を読んだので「The Last Colony」を推薦します
Englishというエンティティはあまりにも一般的過ぎて質の高い説明には繋がらない。
将来的には「有益でない情報」を取り除くhardattentionの導入が重要になると考えられる

# 結論と今後の課題
KGATの中心は「アテンション付きエンベディング層(attentive embedding propagation layer)」
この層は、各ノード(ユーザー、アイテム)の近隣ノードからの情報をアテンション機構を用いて適応的に伝播し、各ノードの表現を更新する。
ソーシャルネットワークをCKGと統合することで、「社会的影響」が推薦にどのような影響を与える研究が可能
また、「情報伝播の仕組み」と「推薦の意思決定プロセス」を統合することも可能
説明可能な推薦という研究領域が発展していくことが考えらえる。


:::note info
+ 階層構造とかにしてより複数の関係性を考慮できないのかな？
+ トリプルでなくてもいいのでは？
+ 知識グラフが有向グラフであるならば、因果関係の把握とかにも使えそう
+ ノードを起点にしてクラスタリングとか出来そう
+ インタラクションが多いユーザーはノイズが多くなり推薦が難しくなるという事象は面白い
:::