"Graph Convolutional Neural Networks for Web-Scale Recommender Systems"で
- importance-based neighborhoodの定義のためにrandom walkを使う方法
が引用されていたのでこれらのアルゴリズムをメインに読む。
3 Proposed method
- notations
- $P$: ピンの集合
- $B$: ボードの集合
- $P \cup B$: ノードの集合
- $E$: エッジの集合。$(p, b) \in E$ ならばピン $p$はボード $b$にあるユーザーによって保存されている。
- $E(p)$: ピン $p$と接続されているボードの集合。
- $E(b)$: ボード $b$と接続されているピンの集合。
- $Q=\{(q, w_q)\}$: クエリピン$q$とその重要度$w_q$。$Q$はユーザー固有となる。
Basic Random Walk
- この論文では新しいアルゴリズムを提案する。
Biasing the pixie random walk
- ユーザーごとにrandom walkにバイアスを掛けることが重要である。
- Pinterestでは、異なる言語やトピックが存在し、ユーザーはユーザーの言語や興味のあるトピックに関するリコメンドを好む。
- この論文では、ユーザーの特徴量に応じてrandom walkのバイアスを変化させることを提案している。
- PersonalizedNeighbor(E, U)によりユーザーの特徴量に応じてバイアスを掛けている。
Multiple query pins with weights
- ユーザーごとにリコメンドするためにクエリ$q$ごとに$w_q$を使ってrandom walkのステップ数を決める。
- $N_q = w_q N \frac{s_q}{\sum_{r \in Q} s_r}$ (Eq. 2)
- $s_q = |E(q)| \cdot (C - \log |E(q)|)$
Multi-hit Booster
- $Q$に含まれる複数のピンに基づいてレコメンドをしたい。
- 基本的なアイデアは、Qに含まれる複数のクエリに最も関連するピンがレコメンドの候補となる。
- アルゴリズム3の5行目のように、各クエリに対するvisit countを集約することで実現する。
- $V[p] = (\sum_{q \in Q} \sqrt{V_q[p]})^2$
Early stopping
- Pixieの実行時間はrandom walkのステップ回数に依存する。実行時間を短縮するためにEarly stoppingを行う。
- $n_p$と$n_v$を導入し、訪問回数が$n_v$以上のピンが$n_p$個存在した時点でrandom walkを終了する。
- アルゴリズム2の10から13行目
3.2 Graph Pruning
- Graphのサイズを小さくすることにより、精度の向上や計算リソースの削減を行う。
- LDAを使って潜在ベクトルを計算し、エントロピーの大きいボードをグラフから取り除く。
- また、ピンとボードのCos類似度を計算し、類似度の低いピンを取り除く。
最後に
- 今回の目的は"Graph Convolutional Neural Networks for Web-Scale Recommender Systems"を理解するためにPixieのアルゴリズムを理解することだったので、アルゴリズム以外のところはそのうちまとめる。