PinSage: A new graph convolutional neural network for web-scale recommender systems

[takapy0210]

Meta

• Link: https://medium.com/pinterest-engineering/pinsage-a-new-graph-convolutional-neural-network-for-web-scale-recommender-systems-88795a107f48
• Author:
• Date:

どんなもの？（3行ぐらいで）

詳細

所感

参考リンク

• https://medium.com/criteo-engineering/top-applications-of-graph-neural-networks-2021-c06ec82bfc18

[takapy0210]

ディープラーニング手法は、視覚認識、音声認識、機械翻訳などの幅広い機械学習や人工知能のタスクにおいて、前例のない性能を達成してきました。しかし、驚くべき進歩にもかかわらず、ディープラーニングの研究は、主にグリッド（画像など）やシーケンス（音声、テキストなど）のようなユークリッド領域で定義されたデータに焦点を当ててきました。しかし、最も興味深いデータや課題は、グラフ、マニフォールド、レコメンダーシステムなどの非ユークリッド領域で定義されたデータである。主な問題は、このような複雑なデータ型のための基本的な深層学習操作をどのように定義するかということです。サービスが成長し、グローバル化している中で、日常的な利用にはスケールしないシステムという選択肢はありません。私たちの答えは、何十億ものオブジェクトを含むウェブスケールのグラフのノードの埋め込みを学習することができるランダムウォークグラフ畳み込みネットワークであるPinSageの形で出てきました。
ここでは、大規模なグラフに接続されたノード（例：Pins/images）の高品質なエンベッディング（密なベクトル表現）を作成する方法を紹介します。このアプローチの利点は，近くのノード/ピンから情報を借りることで，結果として得られるノードの埋め込みがより正確でよりロバストなものになることです．例えば，ベッドレールのピンは庭のフェンスのように見えるかもしれませんが，ゲートとベッドがグラフ上で隣接していることはほとんどありません．我々のモデルは、このグラフ情報に依存してコンテキストを提供し、（視覚的には）似ているが意味的には異なるPinを区別することを可能にします。
私たちの知る限りでは、これはディープグラフエンベッディングのこれまでの最大のアプリケーションであり、グラフ畳み込みアーキテクチャに基づく新世代のウェブスケールのレコメンダーシステムへの道を開くものである。

Background

Pinterestの最大の価値の一つは、何億人ものユーザーが付加した文脈を考慮して、好みに応じたビジュアルなレコメンドを行うことで、人々が自分の興味に合ったアイデアや商品を発見できるようにすることです。Pinterestの利用者数が2億人以上のMAUを超え、保存されたオブジェクトの数が100Bを超えた今、私たちは追いつくだけでなく、レコメンデーションをよりスマートにするための技術を継続的に構築していかなければなりません。
コンテンツディスカバリーアプリケーションとして、人々はPinterestを利用して、オンラインコンテンツ（レシピ、服、商品など）への視覚的なしおりであるPinsをボード上に保存し、整理します。我々は、Pinterest環境を、Pinsとボードという2つの不連続な集合のノードからなる二部グラフとしてモデル化しています。各Pinは、画像やテキストの注釈（タイトル、説明）などの情報に関連付けられています。ここでは、視覚的なエンベッディングと注釈のエンベッディングを入力特徴として、二部グラフから高品質なピンのエンベッディングを生成することを目的としています。
Pinのエンベッディングは、広告やショッピングなどの動的なPinsを含むPinsの推薦、分類、クラスタリング、さらにはリランキングなどの様々なタスクに不可欠です。このようなタスクは、関連ピン、検索、ショッピング、広告などの主要なサービスの基盤となっています。高品質のエンベッディングを生成するという目標を達成するために、我々は、ウェブスケールのグラフからノードのエンベッディングを抽出するために、PinSageと呼ばれるスケーラブルで汎用的な深層学習モデルを開発しました。数十億のノードと数百億のエッジを持つPinterestのデータにPinSageを適用することに成功しました。

Challenges

近年、グラフをモデル化するためのグラフ畳み込みネットワーク（GCN）が提案され、さまざまなレコメンダーシステムのベンチマークで成功を収めている。しかし、ベンチマークタスクでの成果は、実際の運用環境での成果には至っていない。主な課題は、数十億のノードと数百億のエッジを持つグラフに対して、GCNベースのノードエンベッディングの学習と推論の両方をスケーリングすることである。GCNのスケーリングが困難なのは、ビッグデータ環境で作業する場合、その設計の基礎となる多くのコアな仮定が違反しているからです。例えば、既存のGCNベースのレコメンダーシステムはすべて、トレーニング中に完全グラフのラプラシアン上で動作する必要があります。

Key Innovations

ここでは、私たちが開発し、Pinterestの本番で展開した、拡張性の高いGCNフレームワークを紹介します。このフレームワークは、PinSageと名付けられたランダムウォークベースのGCNで、30億ノードと180億エッジを持つ巨大なグラフ上で動作します。PinSageは、いくつかの重要な洞察を活用して、GCNのスケーラビリティを劇的に向上させています。

1. On-the-fly convolutions

従来のGCNアルゴリズムは、特徴行列に完全グラフのラプラシアンの累乗を乗じてグラフの畳み込みを実行します。これとは対照的に，我々のPinSageアルゴリズムは，ノード周辺をサンプリングして動的に計算グラフを構築することで，効率的で局所的な畳み込みを実行する．これらの動的に構築された計算グラフ（図1）は，特定のノードの周りで局所的な畳み込みを実行する方法を指定し，学習中にグラフ全体を操作する必要性を軽減します．

Constructing convolutions via random walks

ノードの完全な隣接領域で畳み込みを実行すると膨大な計算グラフになるので、サンプリングに頼ります。我々のアプローチの重要な革新点は、ノード近傍をどのように定義するか、つまり、畳み込みを行う近傍のセットをどのように選択するかということです。これまでのGCNのアプローチでは、単にK-hopグラフの近傍を調べるだけでしたが、PinSageでは、ランダムウォークをシミュレートし、訪問回数が最も多い近傍を選択することで、重要度に基づいた近傍を定義しています。この方法の利点は2つあります。
第一に、アグリゲータが隣人のベクトル表現を集約する際に、隣人の重要度を考慮に入れることができます。この新しいアプローチを重要度プーリングと呼んでいます。
第二に、集約するノードの数を固定して選択することで、訓練中のアルゴリズムのメモリフットプリントを制御することができる。
我々の提案するランダムウォークベースのアプローチは、我々のオフライン評価指標において、従来のK-hopグラフ近傍法と比較して46%の性能向上をもたらす。

Efficient MapReduce inference

完全に訓練されたGCNモデルを用いても、訓練中に見られなかったノードを含むすべてのノードの埋め込み値を生成するために、訓練されたモデルを直接適用することは困難です。局所的な共解像度を持つノードのエンベッディングを黙って計算すると、ノードのK-hop近傍の重なりが原因で、計算を繰り返すことになります。
ノードの埋め込みのボトムアップ集約（図1参照）は、すべてのノードにわたる各集約ステップをMapReduceの3つの操作、すなわちマップ、ジョイン、リダクションに分解すると、MapReduceの計算モデルに非常にうまく適合することがわかります。簡単に言えば、各集約ステップについて、mapを用いて全ノードを重複計算なしで潜在空間に投影し、joinを用いて階層上の対応する上位ノードに送信し、最後にreduceを用いて上位ノードの埋め込みを得るための集約を行う、というものである。我々の効率的なMapReduceベースの推論は、数百インスタンスのクラスタ上で数十億ノードのエンベッディングを数時間以内に生成することを可能にしている。

Offline Evaluation

我々は、PinSageをPinterestのデータ上に実装し、評価しています。PinSageは、ビジュアルエンベッディングとアノテーションエンベッディングを入力特徴として持つ二部構成のPin-boardグラフで、PinSageを実装しています。視覚的エンベッディングは、Pinterestに配備されている最新の畳み込みニューラルネットワークからのものを使用しています。アノテーションのエンベッディングは、PinterestのWord2Vecベースの生産モデルを用いて学習します。PinSageの性能を、Pinのエンベッディングを生成する以下のコンテンツベースのディープラーニングベースラインと比較して評価します。
ビジュアルエンベッディング（Visual embeddings）。視覚的埋め込み (Visual): (上述の) ディープな視覚的埋め込みの最近傍を利用してレコメンデーションを行います．
Annotation embeddings (Annot.). 注釈埋め込み (Annot.): 注釈埋め込み (上記) の最近傍に基づいて推薦します。
複合埋め込み (Combined): 上記の埋め込みを連結して推薦します。視覚的特徴と注釈の埋め込みを連結し、2層多層パーセプトロンを用いて視覚的特徴と注釈の両方の特徴を含む埋め込みを計算して推薦します。PinSageと全く同じデータと損失関数を使って学習します。
我々が使用している視覚的特徴と注釈の埋め込みは、Pinsの表現を生成するために現在Pinterestで展開されている最先端のコンテンツベースのシステムであることに注意してください。我々の問題の規模が大きいという理由から、文献にある他のディープラーニングのベースラインとの比較はしていません。
我々は、RecallとMean Reciprocal Rank (MRR)を指標として、Pin-to-Pin推薦の観点から様々なアプローチの性能を比較しています。PinSageは、Recallでは40%の絶対値（相対150%）でトップベースラインを上回り、MRRでは22%の絶対値（相対60%）でトップベースラインを上回りました。

User Studies

また、異なる学習済み表現の間でヘッド・トゥ・ヘッド比較を行うことで、PinSageの有効性を調査しています。この研究では，ユーザはクエリピンの画像と，2つの異なるレコメンデーションアルゴリズムによって取得された2つのピンを提示されます．ユーザーは、2つの候補Pinのうち、どちらのPinがよりクエリPinに関連しているかを選択するように求められます。ユーザは、視覚的外観、オブジェクトのカテゴリ、個人のアイデンティティなどの観点から、推薦されたアイテムとクエリアイテムとの間の様々な相関関係を見つけるように指示されます。両方の推奨項目が同じように関連していると思われる場合、ユーザは「等しい」を選択することができます。同じ質問を評価するユーザーの2/3の間でコンセンサスが得られなかった場合、結果は結論が出ていないものとみなします。

表1は、PinSageと4つのベースラインの間のヘッド・トゥ・ヘッド比較の結果を示しています。ここでは、クエリPinから始まるランダムウォークをシミュレートしてランキングスコアを生成するために、偏ったランダムウォークを使用する純粋なグラフベースの手法であるPixieを含めています。トップスコアを持つアイテムをレコメンデーションとして取得する。
ユーザーが「どちらが関連性が高いか」という意見を持っているアイテムのうち、好ましいアイテムの約60%がPinSageによってレコメンデーションされる。図3はレコメンデーションの例を示し、異なる手法の長所と短所を示している。最終的には、視覚情報、テキスト情報、グラフ情報の両方を組み合わせることで、PinSageは、視覚的にも局所的にもクエリ項目に類似した関連項目を見つけることができます。

A/B Test

ホームフィードと関連ピン広告の両方でA/B実験を開始し、アノテーション埋め込みベースのベースラインと比較したところ、ユーザーのエンゲージメント率の面で約30%の相対的な改善が見られました。

Conclusion

私たちは、数十億個のオブジェクトを含むウェブスケールのグラフのノードのエンベッディングを学習することができ、高いスケーラビリティを持つランダムウォークグラフコンボリューションネットワーク「PinSage」を開発しました。
この作品は、商品発見のバックエンドをスーパーチャージャー化し、Pinterestを使ったショッピングの未来を大規模にパワーアップさせるものです。
学習したエンベッディングの品質を、オフラインのメトリクス、ユーザースタディ、A/B テストなど、多くのレコメンデーションタスクで総合的に評価した結果、レコメンデーションのパフォーマンスが大幅に向上し、Shop the Look 商品のインプレッションが 25% 増加するなどの結果が得られました。PinSageの詳細については、SIGKDD '18の論文をお読みください。私たちの仕事に興味のある方は、ぜひ私たちのチームに参加してください。