論文
[1806.01973] Graph Convolutional Neural Networks for Web-Scale Recommender Systems
著者
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, Jure Leskovec
背景
Pinterestでは、ユーザーは画像をpinと呼ばれるオンラインブックマークとして自分のボードに集めることが可能になっている。 ユーザーが付けたpinに応じて、関連する人気のあるコンテンツの発見・共有を行うサービスを提供している。 Pinterestでは、世界最大級の画像共有サービスとなっており、10億のボードが存在し、20億のノード(pin)と180億のエッジが存在する巨大グラフネットワークとなっている。
近年のグラフ構造に対するニューラルネットワークの応用は、最新のレコメンデーションシステムの性能高度化に寄与している。 しかしながら、この手法は何十億というアイテムと何千万というユーザを要するようなwebスケールのアプリケーションには適用が難しいという問題がある。
目的とアプローチ
目的
- 巨大なwebスケールのシステムにおけるGraph Convolutional Network (GCN)の適用
アプローチ
- PinSage
提案手法
Graph Convolutional Networkの概要
提案手法における推論モデルの概念図を下記に示す。
まず次のようなグラフ構造について考える。
ノードAについて着目して推論を行うことを考えると、ノードAに結合しているのはノードB, C, Dである。 結合しているノードに着目したときの推論の出力を関数hで表現するとき、ノードAに関する推論は下記のような概念図のような構造を考慮すれば良いことになる。
ここで関数hについて補足すると、
はノードAに関するホップ数2まで考慮したときの出力を意味している。
上図のように、結合しているノードに着目し、ホップ数の大きいところから畳み込みを行うことでグラフ構造における畳込みを実現する。
ホップ数が遠い部分については係数を使用することで出力に対して重み付けを行う。
これをグラフ全体に適用することを考えると、着目するノードごとに別の形の計算グラフが考えられる。
このように、同じ計算パイプラインを使用するものの、結合するノードが異なることで出力結果が異なるようになっている。
問題設定
レコメンデーション機能に使用できるようなpinのembeddingsあるいはその他の表現形式を考える。 Pinterestのデータ構造はpinとボードの2つの集合からなる2部グラフとみなす事ができる。
ここで、ノードを構成するembeddingsはアイテム画像の様々な特徴の集合体とする。
加えて、pin/画像側には何らかの属性があると考えることができる。 Pinterestにおいては、リッチテキストと画像の間に関係性があると考えられる。
このようなグラフ構造の中から、着目するノードと関連のあるノードを探索することをターゲットとする。
Model Archtecture
Localized graph convolutions
局所的畳み込みのアルゴリズムを下記に示す。
1行目で、ノードuの近傍にあるノードvにおいて、各ノードの出力hに関し、行列の積和演算を行い、ReLU関数を適用する。 これに、加重和／加重平均を適用する(γ)。
次に、1行目で出力されたベクトルを連結する。 注目しているノードuのembeddingsと近傍から得られたnを結合し、行列の積和演算を行い、ReLU関数を適用する。(2行目)
最後に学習の安定化のために、出力を正規化する。(3行目)
このようにして近傍のembeddingを使用して畳み込みを実現する。
ランダムウォークによる近傍探索
一般的なグラフネットワークでは、単純にkホップ以内でたどり着けるノードを近傍とする場合が多い。 PinSageでは、重要度によって近傍を定義する。
具体的には、注目するノードuからランダムウォークを行い、ランダムウォークによってたどり着いたノードのカウントを正規化していくことで、着目するノードに影響度の強いノードを確率的に判断し、その値が大きいものを近傍と定義する。
この手法によるメリットは、
- ノードの形状に関係なく、一定の数の近傍を収集できる
- 先の畳込みアルゴリズムにおいて重要度を考慮する事が可能になる(γ)
このように、重要度に基づいた近傍探索を行う。
畳み込みの多層化
着目するノードに関する出力ｈを計算するためには、グラフ構造上で接続するノードの集合を求める必要がある。 畳み込み演算の積み上げに必要なノードの集合の算出とそれを含めた畳込み処理のアルゴリズムを下記に示す。
1−7行目では、着目するノードに関して畳込みの深さごとに畳み込み処理に必要となるノードを算出している。 8−14行目では、上で求めたノードの集合を使用して、深さの順に畳み込みを行う制御を行っている。 15行目以降で最終的なembeddingを全結合のニューラルネットで算出している。
学習
PinSageの学習は、max-margin ranking lossを使用した教師あり学習として取り扱う。
Loss function
Pinsageで使用するLoss関数を下記に示す。
ここで、は着目点qと本来関連のないないノードの分布を表し、
はマージンを表すハイパーパラメータである。
最終的な目的関数として、
- 関連性の強いもの=>値が大きく
- 無関係のもの=>値は小さく
なるものとすると、Lossはその逆の関数になれば良い。
関連の無いが多いとLossは大きく、関連する
が多いとLossは小さくなるようにLossを設定している。
ミニバッチの設計
一つのマシンに搭載される複数のGPUを完全に使用するために、forward-backwardの二本柱の形式で実行することを考える。 マルチGPUに分散するため、同じサイズのミニバッチに分割して、計算に使用する共通のパラメータと一緒に各GPUに割り当てる。 backwardまで計算が終わったすべてのGPUで計算された勾配をCPUに集め、同期処理的にSGDによるパラメータの更新が行われる。 このときのバッチサイズは512から4096とすることで、学習の安定化を図る。 学習率については、開始から徐々に学習率を大きくし上限まで線形に増加させる。その後、学習率を指数関数的に減少させていく。
Producer-consumer ミニバッチ
着目するノードがどのノードと隣接するか求めるには、非常に巨大なメモリを必要とし、CPUでこれを算出することは現実的とは言えない。 一方、畳込みを実行するGPUには隣接するノードの情報を転送する必要がある。
これらの問題を解決するために、re-indexingを行い、隣接するノードを含むサブグラフを改めて作成する。 これにより、結合関係は小さな行列で表現することが可能になり、必要なノードだけをGPUに転送すれば良く、GPU間での通信の必要もない。
無関係のノードのサンプリング
Lossでも紹介したように、Lossを計算する際に関係ないノードに関して考慮する。
今回は予め無関係ノード用として500個ノードを用意した。 しかし、Pinterestでは画像側のノードは20億存在し、関連するノードを見つけるタスクに対して無関係のノードを見つけるタスクは簡単すぎる。 そのため、"Hard Negative"のノードを評価に加える。 これは、着目しているノードからパーソナライズされたページランクのスコアをもとに、2000-5000番の範囲のノードをランダムにサンプリングすることで抽出する。これにより、着目しているノードにはなんとなく関連がありそうで、Positive Exampleに対してはほとんど無関係の、ほぼ無関係のノードを選定・使用する。
各ノードの分類としては下記のようになる。
対象となるノード（左端）から見て、Positive Exampleは正のデータとして、Random Negative は明らかに無関係のノード、Hard Negativeはその間程度の関連性としている。 このように、関連性を分けることで無関係ノードの他のノードを使用してLoss計算の精度を向上させる。
MapReduce並列モデルの適用
学習が終わったあと、各ノードに関する推論結果であるembeddingsをノードごとに出力する必要がある。 この学習と推論を効率的に実行するモデルとしてMapReduce並列モデルを使用する。 全体像としては下記の様になる。
最初の層（layer-0）はpin/itemを想定しており、画像やアノテーション、評価のデータを収集して畳み込みを行う。 それぞれのノードに関する計算の後、リダクションが行われる。
評価
PinSageに関して、2種類の評価を行う。 一つは関連するpinの推薦、もう一つはユーザーのホーム画面・ニュースフィードに関するpinの推薦である。
Experimental setup
- 学習データ: 12億の学習用ペア（pin, 関連item）
- 合計データセット: 18TB
- 出力embedding : 4TB
- visual embedding : 4096次元
- textual annotation embedding : 256次元
Baseline
- Visual : visual embedding を使用した場合の推論
- Annotation : annotation embedding を使用した場合の推論
- Combined embeddings : 上記2つを組み合わせて2層パーセプトロンで算出した推論
- Pixie : pinのembeddingを生成しない、ランダムウォークに基づくランキング法による推論（現在のpinterestの推論）
Pooling
- max-pooling
- mean-pooling
- mean-pooling-xent
- mean-pooling-hard
- Pinsage
Computation resource
学習
- マシン1台
- 32core CPU
- 16 Tesla K80 GPU
推論
Offline Evaluation
オフライン評価のメトリクスとして、hit-rateとMean Reciprocal Rank(MRR)を使用する。
hit-rateはテストセットと推論による出力のずれを元に、どれだけ推論が当たっているかを表す。 これにより直接的な推論と現実のズレを測定する。 数値が大きいほど優れていることになる。
MRRは下記の式によって表現される。
MRRでは、着目するノードから推論されたノードの順位も含めて考慮する。 推論された順位をRとし、ランキング上位のノードを推論できるほど値が大きくなる指標となっている。
比較対象を含めた各手法によるhit-rate, MRRの結果を下記に示す。
結果より、比較対象の中では最も優れた推論モデルであることがわかる。
embeddingのコサイン類似度に対する推論結果の確率密度を下記に示す。
Visualのみ、あるいはAnnotationのみを使用した場合にくらべ、幅広い範囲で推論ができていることがわかる。 これにより、他の手法より多様な推論ができていることがわかる。
User Studies
実際にユーザに使ってもらう評価も実施する。 2つのレコメンデーションアルゴリズムを使用した推論結果をユーザに見せ、どちらが適切であったかを問いかける。 回答は、提案手法が優れている、提案手法が悪い、どちらも同じくらいの3通りで受け付ける。
評価の結果を下記に示す。
全体的に比較対象の手法より提案手法のほうが優れていることがわかる。
推論結果の実際のサンプルを下記に示す。
着目するpinを左、その右に推論の結果を表示している。 Visualだけ、あるいはAnnotationだけの場合は、感じの異なる推論になってしまっている。 既存のPixieでは、意味も画像もおおよそ推論できているように見受けられるが、その中での順位付けがうまく行っていないように見受けられる。
加えて2次元のｔ−SNEによる関連画像を下記に示す。
だいたい同じような画像が同じような位置に分布していることがわかる。
A/Bテスト
A/Bテストによる評価を行う。 レコメンドした結果、ユーザーがそれをpinするかどうかを用いて評価を行う。
実際やってみると、pinされる割合が１０−３０％の改善され、実アプリケーションとして有用であることがわかった。
Runtime分析
PinSageのバッチサイズごとの演算所要時間を下記に示す。
バッチサイズが小さいと演算は小さくなるものの、その分擾乱が大きくなるためiterationの回数が増やす必要がある。 このトレードオフの関係の中、バッチサイズ2048が最も効率的であった。
importance poolingに関し、推定する隣接ノードの数によって演算時間は変化する。 測定結果を下記に示す。
10-50まで隣接ノードの数を変化させたところ、推論としては50の時最も優れ、推論のスケールに対する演算効率も50の時が最も優れていた。
結論
Web scaleの問題に対してGCNを適用するため、PinSageを開発した。 PinSageにより、Pinterestの膨大なグラフネットワークが持つノードのembeddingsに対してGCNアルゴリズムを適用可能であることを示した。 また、ランダムウォークやカリキュラムの使用によって、演算効率の向上にも成功した。 結果として、PinSageによってABテストの結果、レコメンデーションの効果は向上し、その有用性が示された。
感想
グラフネットワーク(GCN)はなかなか読む機会がなかったんですが、今回初めて読んで非常に勉強になりました。 構造が予めわからないのと、データ量が巨大になりがちなので、こういった局所化がポイントになるんでしょう。 こうやって読むと簡単そうに見えるんですが、めっちゃ難しいことはなんとなくわかりました。
非常に勉強になりました。