Graph Convolutional Neural Networks for Web-Scale Recommender Systemsを読んだのでメモ

はじめに

Graph Convolutional Neural Networks for Web-Scale Recommender Systemsを読んだのでメモ．30億ノード，180億エッジを持つグラフデータに対しても処理可能なrandom walkに基づくgraph convolutional neural network (GCN)，PinSageを提案するというもの．

問題設定

今回扱うデータはPinterestのデータで，Pinterestはユーザーが興味のあるコンテンツ（画像）を自分のboard上にpin留めしたり他人のboardにpin留めされているデータを自分のボードにpin留めすることで交流するSNSとのこと（自分は使ったことないのでよくわからないが）．データとしては20億のpinと1億のboardと180億のエッジがあるらしい．

問題としてはpinの推薦のためにpin とboard からなるPinterestの環境をモデル化することでpinの表現学習を行いたいというもの（ただし提案手法は一般化され他手法で適用範囲はPinterestに限らない）．ここでの推薦というのはあるユーザーがpinしたコンテンツを，興味が近いユーザーに提示してpinしてもらうこと．つまりpinと表現しているのはpinされた画像を表し，そこには実数値が割り当てられる．

以下，表記の一般化のためグラフのノード集合をとしてpinとboardの区別をしない．

model architecture

Forward propagation algorithm

ノードの埋め込みベクトルをとその近傍のノードから生成することを考える． 基本的なアプローチとしてはノードの近傍のノードの埋め込みベクトルをノードごとにニューラルネットワークに入力した後，ReLU等の非線形関数を噛ませてプーリングにより一つのベクトルを作り出す．得られたベクトルとノードの埋め込みベクトルをconcatしてニューラルネットに入力して非線形関数を噛ませたのち，L2正規化して新たな埋め込みベクトルを得るというもの．つまり一つのノードの埋め込みベクトルを得るのに二つのNNを使うということ．

Importance-based neighborhoods

このアプローチの重要となる点の一つとして，どの様に近接のーどを定義して，前述のforward propagationにおける近接ノードの集合をどの様に選択するかということにある．一般的には-hopなどの方法が取られていたが，PinSageはノードに最も影響するであろう個のノードで定義する．最も影響する個のノードはrandom walkで訪れた回数の多い上位個のノードとして定義する．

この選び方はノード数が固定となることと，forward propagationで変換された近傍ノードのプーリング処理を行う際にL1正規化された訪れた回数を重みとして重み付き平均をとることができるという二つの利点がある．特にこの後半のプーリング処理をimportance poolingとして提案する．

Model training

モデルの学習はmax-margin ranking lossを使った教師あり学習で行ったとのこと．ラベルはitem とquery item のペアの集合で定義されていて，このペアの埋め込みベクトルが近くなることが学習の目標．

目的関数は次の様に表され，この最小化問題はquery itemの埋め込みベクトルがポジティブペア（ラベルペア）のアイテムの埋め込みベクトルとの内積が大きくなる様に，逆にネガティブペアの埋め込みベクトルとの内積が小さくなる様にする．

はアイテムのネガティブサンプルの分布で，はハイパーパラメータ．いわゆるtriplet lossのユークリッド距離をコサイン距離的なものにした感じ．

その他論文には巨大なデータで学習する際のいろいろな問題と解決方法を述べていたが割愛．

まとめ

データが巨大すぎて企業ならではな研究だなと．発表された会議の性質もあってアルゴリズムよりも実装面をかなり頑張った感じがあった．