[論文紹介]グラフニューラルネットワークによる推薦アルゴリズム

# はじめに
　昨今、サービスに推薦システムを導入することでUXを向上させることが多くなり、様々な推薦アルゴリズムが取り入れられております。学術界でも推薦は大きなテーマであり、様々なアルゴリズムが提案されております。

　本記事では、推薦をする際に、「メディア上で、どんな人とと繋がっているか、どのアイテムにライクをしたか、どんなページを閲覧しがちか」など、人やアイテムとのつながりを重視して推薦するSocial Recommendationの最新論文であるGraphRec[1]を紹介します。GraphRecは2019年にWeb系のTop Coferenceの一つであるWWWで採択された論文です。

　GraphRecは、近年グラフ界隈を盛り上げているグラフニューラルネットワーク(以下GNNs)を用いております。GNNsでは、あるノードiの特徴量に近傍ノードの特徴量を足し合わせること(aggregation)で、ノードiの特徴量を得ていきます。
 GNNsについては、以下の記事やサーベイ論文がおすすめです。
https://qiita.com/shionhonda/items/d27b8f13f7e9232a4ae5

https://arxiv.org/abs/1812.04202 [2]


なお、social recommendationをより知りたい方は、以下のsurveyをお勧めします。
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.4243&rep=rep1&type=pdf [3]

## 対象読者
・グラフを使った推薦システムに興味がある方
・GNNsを勉強したい方

GNNsがわからない方にもわかるように書いております(つもり)。
何か質問や、間違いなどがありましたら、お気軽にコメントしてください。

# 背景
　社会理論として、人は周りの人の好みや意見から影響を受けることが分かっており、推薦をする際に、あるユーザーの他のユーザーとのつながりを考慮に入れることで精度向上することが示されています。
　また、グラフ上でノードのベクトル表現(分散表現、潜在表現)を得る際に、GNNsを用いることが有効であることが示されております。GNNsでは、近傍ノードのベクトルを足し合わせることで自らのベクトルを生成していきます。したがって、GNNsでは自らの特徴に加えて、周りとの関係性が考慮されることになります。　
　つまり、他のユーザーとの関わりが重要なファクターであるSocial recommendationと、周辺関係を考慮してベクトルを生成するGNNsでは、非常に相性が良いことがわかります。

　一方、推薦を行う際には、図1のように、人と人との繋がりのグラフ(ユーザー・グラフ, Social Relations)、人とアイテムとのつながりのグラフ(ユーザー・アイテムグラフ、User-to-item Interaction)の二つが存在します。それら2つをうまく統合することが重要になります。
また、アイテムには1-5などの意見(評価)をつけることができるため、その情報を用いることも大切です。さらに、ユーザー同士の関係性で強い繋がりもあれば、弱い繋がりもあり、それらを考慮したほうが精度は高まるでしょう。
これらに取り組む必要があり、GraphRecの貢献はまとめると以下になります。
・ アイテムに対する意見(評価)を組み込むこと
・ ユーザー同士の関係で強い繋がり、弱い繋がりを考慮すること
・ ユーザーグラフと、ユーザー・アイテムグラフをうまく融合させること

　![スクリーンショット 2019-07-20 8.09.27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/4f44d016-17ae-5907-d5f3-1d664cc68f7e.png)
図1. 推薦におけるグラフデータ [1]より引用

# 手法
　推薦の方法としては、あるユーザーがまだ関わっていないアイテムへの意見(評価)を当てる、rating predictionというものです。実際にシステムで用いる際は、あるユーザーがまだ関わっていないが、関わった場合高い評価をするであろうアイテムを推薦することになります。
フレームワークの全体像としては図2のようになります。
![スクリーンショット 2019-07-20 8.45.57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/0ce42107-8e3a-cadc-c355-d7207417a622.png)

モデルは、ユーザー・モデリング、アイテム・モデリング、レート予測の3つの構成要素に分割することができます。
簡単にそれぞれの役割を
・ユーザー・モデリングで、ユーザーのベクトル表現を生成する
・アイテム・モデリングで、アイテムのベクトル表現を生成する
それら二つをうまく組み合わせることで、あるユーザーのあるアイテムに対する意見(評価)を予測するというものです。
これらを押さえた上で詳細に入っていきましょう。

## ユーザー・モデリング
ユーザー・モデリングは、アイテム・アグリーションと、ソーシャル・アグリゲーションの二つの構成要素に分けられます。
アイテム・アグリーションは、ユーザーのアイテムに対する嗜好を表すベクトルを生成し、ソーシャル・アグリゲーションは、ユーザーの他のユーザーからの影響を考慮した、ユーザーのベクトルを生成します。どちらの構成要素もユーザーのベクトルをアウトプットとしております。それぞれで得られたユーザーベクトルをうまく組み合わせることで、最終的なユーザーのベクトルを得ることが、ユーザー・モデリングのゴールです。
それでは、アイテム・アグリゲーションとユーザー・アグリゲーションを紹介します。

### アイテム・アグリゲーション
図3は図２のアイテムアグリゲーションの部分を拡大したものです。
ユーザーの過去に意見をもった（評価を与えた)アイテムを情報として、ユーザーのベクトル表現を生成することが目標になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/fec196ad-3e41-3f60-0542-8d6e5578fc67.png" width=800>

　まず、アイテムのベクトル表現をランダムに初期化し、それをアイテムエンベッティングq<sub>a</sub>とします。また、評価を5段階評価とし、評価のベクトルをランダムに初期化し、それをオピニオンエンベッティングe<sub>r</sub>とします。ここで、同じアイテムには同じベクトル、同じ評価には同じベクトルが割り当てられていることに注意してください。小文字のaはアイテムの種類、rは評価の種類を表します。

　では、ユーザーv<sub>i</sub>にとってのアイテムaのベクトルx<sub>ia</sub>を得ましょう。以下のように得ることができます。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/3d1a92f5-4493-9c97-6197-a84315774bb7.png" width=400>

　ここで、g<sub>v</sub>はニューラルネットワークで論文では二層のMLPを想定しております。⊕はconcatを表します。ユーザーがこれまでに意見をしたアイテムの分だけxが得られることになります。
　次に、得られたユーザーv<sub>i</sub>にとっての全てのアイテムベクトルをxから、ユーザーv<sub>i</sub>のベクトル表現を得ましょう。アイテムベクトル全てから、ユーザーベクトルが生成されると考えると、以下のように定式化できます。

　![スクリーンショット 2019-07-20 9.13.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/2dd616bc-ef93-7f52-1a0f-40f13e39d9c9.png)

W, bは重みとバイアスの行列で、C(i)というのはユーザー<sub>i</sub>がこれまで接したアイテムの集合です。σはReLUなどの非線型変換関数です。
つまり、ユーザーベクトルh<sub>i</sub><sup>I</sup>は、これまで評価したアイテムのベクトルをまとめあげた(アグリゲートした)ベクトルから生成されるということです。
アグリゲーション関数としては、全てのアイテムを同等に扱うMeanがありますが、ある特定のアイテムに対して好感を持っていて、そのアイテムがよりユーザーを表すと考えることが通常のため、論文では、Attentionを用いております。もちろんMeanでもできますが、MeanよりもAttentionの方が最終的な結果がよかったと実験的に示しております。

　この節で、アイテムから生成されるユーザーのベクトル表現を得ることができました。このベクトルはユーザーの嗜好を表すベクトルと解釈できます。

### ユーザー・アグリゲーション
　ユーザー・アグリゲーションはもっとシンプルです。
ユーザー・アグリゲーションでは、近接したユーザーからの情報をまとめあげて(アグリゲートして)自らのベクトル表現を生成するフェーズです。
アイテム・アグリゲーションで得たユーザーベクトルh<sub>i</sub><sup>I</sup>を入力として用います(図のitem-spaceという箱に対応)。
![スクリーンショット 2019-07-20 9.38.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/0ec42e9b-8afd-49bd-9d83-b17faa2a8324.png)
ユーザーiと隣接したユーザーから情報を受け取り、自らのベクトルを生成します。式で表すと以下の通りです。

![スクリーンショット 2019-07-20 9.40.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/d39ef99a-7e2e-8ed6-b87c-49871f20350a.png)

N(i)はユーザーiに隣接したユーザーの集合です。その他の変数はアイテム・アグリゲーションと同じです。
アグリゲーション関数としては、同様にAttentionを用いております。
この節でユーザーの隣接関係を考慮したユーザーのベクトルを生成することができました。
このベクトルは、周りのユーザーからの影響を考慮したユーザーの嗜好を表すベクトルと解釈できます。

### ユーザーベクトルの完成
先の2節でユーザーのベクトルを二つ生成しました。この説では、それらを一つのベクトルにまとめ上げることをします。
手法としてはかなり単純で、二つのベクトルをconcatした上で、l層のMLPを通すというものです。

![スクリーンショット 2019-07-20 9.46.34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/2b4605f2-e98d-64fc-0030-98f48ee899c9.png)

特に説明は不要でしょう。

## アイテム・モデリング
これまで、ユーザーのベクトルをどう得るかを紹介しました。この節では、アイテムのベクトルをどのように得るかを紹介します。
![スクリーンショット 2019-07-20 9.49.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/5a72da0f-a0c6-a15e-2423-a6e91f29ce80.png)

考え方はユーザーモデリングと全く同じです。アイテムは、ユーザーとそのユーザーからの意見(評価)からベクトルが得られると考え、それらをアグリゲートし、どの意見を重視するかattentionによって重みをつけたものが、アイテムのベクトルになります。

## レート予測
以下までで、ユーザーのベクトル、アイテムのベクトルを得ました。ここでは、あるユーザーiのアイテムjに対する意見(評価、レート)を予測します。
考え方は、単純で、ユーザーベクトルh<sub>i</sub>と、アイテムベクトルz<sub>j</sub>をconcatし、それらをMLPに通すというものです。式で書くと以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/04a0a5c1-c4ac-46a4-67ec-bfae309230b8.png)

最終層の出力はレートであり、1次元のスカラー値になります。

## 学習
ここまででモデルの説明が終えました。
ここではどのように学習するのかを述べます。
ロスを以下のように定義します。シンプルなMSEと同じです。
![スクリーンショット 2019-07-20 9.56.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/262308/07da2731-030b-976f-3dd8-404f8939ee24.png)
Oは現時点で出ている評価で、r'<sub>ij</sub>はユーザーiのアイテムjに対する評価の予測値、r<sub>ij</sub>はユーザーiのアイテムjに対する評価の実現値です。
　最適化関数としては、RMSPropを用いておりますが、Adamなどでも同様に機能するでしょう。

# 実験
実験では、強調フィルタリングベースの手法、他の深層学習を使う手法と比較しており、baselineを超えることが示されております。
また、ユーザーアグリゲーションを抜いたバージョン、attentionをmeanにしたバージョンなども実験しており、その結果から、
・ユーザーは他のユーザーの嗜好から影響を受けている
・他のユーザーとの関係性には、強い関係と弱い関係が存在する
といった仮説を検証しております。

# まとめ
GraphRecは推薦システムにGNNsを用いることでより精度の高い推薦ができることを示しました。周りのユーザーとの関係に強弱をつけたり、アイテムとの関わり方に強弱をつけて、二つのグラフを考慮した推薦をすることはこれまでやられていなかったことでした。
今後は、アイテム自体・ユーザー自体の属性などを考慮できるようなモデルを作ることを目指します。

# おわりに
GNNsは非常に盛り上がっており、この先どんどん応用論文が出てくるでしょう。推薦分野への応用は既存の手法の精度を大きく上回るため、どんどん導入が進んでいくでしょう。
GNNs系で読んだ都度紹介していければと思っております。

わかりづらい点や感想などフィードバックをいただけると幸いです。

# Reference
[1] GraphRec
Fan, Wenqi, et al. "Graph Neural Networks for Social Recommendation." The World Wide Web Conference. ACM, 2019.

[2]Deep Learning on Graphs
Zhang, Ziwei, Peng Cui, and Wenwu Zhu. "Deep learning on graphs: A survey." arXiv preprint arXiv:1812.04202 (2018)

[3]recommend survey 
Tang, Jiliang, Xia Hu, and Huan Liu. "Social recommendation: a review." Social Network Analysis and Mining 3.4 (2013): 1113-1133.