search

nogawanogawa / paper_memo

4 stars 0 forks source link

GraphJet: Real-Time Content Recommendations at Twitter #82

Closed nogawanogawa closed 1 year ago

nogawanogawa commented 1 year ago

論文URL

https://www.vldb.org/pvldb/vol9/p1281-sharma.pdf

著者

Aneesh Sharma, Jerry Jiang, Praveen Bommannavar, Brian Larson, and Jimmy Lin

会議

VLDB' 16

背景

Twitterの"Who to Follow"推薦は、2010年から開始され、Twitterの中の重要な推薦となった。 この仕組みは、初期はバッチ推薦によって行われていたが、時間的に近いログに基づく推薦が有効であることが過去の開発の経験からわかっていた。

しかし、これまで行っていた推薦の仕組みでリアルタイム性を確保することは難しかった。

目的

リアルタイムにグラフを扱った推薦を行う

アプローチ

ひとことメモ

Twitterのコードが公開されたので

nogawanogawa commented 1 year ago

背景

Twitterにおいてuser-user, user-contentの新しいつながりを推薦することは、ユーザーの活性化につながる。

nogawanogawa commented 1 year ago

Twitterのシステムの変遷

WTF and Cassovary

Graphレコメンデーションは2010年にWtf（"Who to Follow"）の開発が始まった際にスタートした。 このときの設計は、グラフ全体が1台のサーバーのメモリに収まることを想定した設計になっていた。

ムーアの法則に従って増加するメモリ容量に比べ、グラフデータの拡大の速度が早いかどうかが焦点となっていた。 このとき、経験的に1台のサーバーに乗り切ることがわかったためこの設計にした。

この当時の仕組みCassovaryでは、レコメンデーションエンジンが推薦内容を計算した結果をシャード化されたMySQLDBに保存していた。 定常状態では、Cassovaryサーバーは常にユーザーへの推薦文を生成し、「最終更新」タイムスタンプでソートされたユーザーを含む分散キューから消費する。

image

スナップショットやHDFSへのインポート処理によってフロントエンドのグラフストアに負荷がかかるため、インメモリのCassovaryグラフを1日1回以上頻繁に更新するのは現実的ではない。 これは新規ユーザーにとって問題であり、Twitterに参加してもすぐにレコメンドを利用することはできない。 新規ユーザーに対して高品質なレコメンドを行うことは、新規ユーザーにとって非常に難しい設計になっていた。 そのため、新規ユーザー向けにはオンライン推論にて提供していた。

このときの推薦には下記のようなアルゴリズムが使用されている

image

Hadoop and RealGraph

その後、より幅広いデータ、行動ログを使用したいというモチベーションでCassovaryの後継を作り始めた。 この段階になると、1台のサーバーですべてのデータを扱うのはもはや現実的でなくなった。

image

このときは、RealGraphを使用し、Follower prediction modelの学習を行って推薦を行っていた。

MagicRecs

ここまでは1日に一回バッチによる推薦を行っていたが、リアルタイム性をより取り込みたい意図で更に改善が行われた。 このときのロジックは、フォロー関係をもとに推薦するものになっている。

image

A2に関して、AがフォローしているB1, B2が直近フォローしているC2はA2にとってもフォローすると考えて推薦する。 これはfollowだけでなく、いいねやリツイートに関しても適用可能である。

nogawanogawa commented 1 year ago

GraphJet

MagicRecsは、「今何が起こっているか」を議論するメディアとしてのTwitterの強みを生かしたリアルタイム・レコメンデーションの力を実証した。

GraphJetは、直近のn時間にわたるユーザーとツイートの相互作用を追跡する2分木グラフを維持するようにした、インメモリグラフ処理エンジンとなっている。

image

（以下、処理エンジンの仕組みの話なので省略）

nogawanogawa commented 1 year ago

リアルタイムレコメンデーション

GraphJetでは主に2種類のクエリに対応していて

を行う機能が備わっている。

コンテンツ推薦

あるユーザーが直近Tweetに対して行ったアクションをもとに、そのTweetに対してアクションした別のユーザーを探索する。 そして、そのユーザーが行動したまた別のTweetを探索する。こうしたuser-tweetの2部グラフ上でのランダムウォークを奇数回行うことで、ユーザーに対して関連するtweetの訪問分布が得られる。 これによって、関連性として扱うことで推薦を行う。

認証済みユーザーのTweetだけを使用するなどして、二部グラフのサイズを更に小さくすることができる。このようにして、インメモリに収まるデータサイズで処理を行っている。

類似性

Tweetの類似Tweetを検索する際にも使用できる。

ここでは、Tweet tが与えられたとき、それに関連するuserをランダムサンプリングによって得る。（NS(t)） 次に、このNS(t)が関連しているTweetをランダムサンプリングして、そのときの訪問回数を類似度として扱うことで類似性を判定する。