Cold Start Similar Artists Ranking with Gravity-Inspired Graph Autoencoders
https://gyazo.com/84ca1230fa34a64eccea4634fd9a9216
https://gyazo.com/e6d0afef9ee4b6991e23b076e8476cd4Deezer Research: 音楽ストリーミングサービスDeezerの研究チーム。情報検索/推薦/分析
選んだ理由
コールドスタート問題とグラフベースの推薦モデルの両方を同時に知ることができてお得そうだったため
Abstract
音楽ストリーミングサービスdeezerのアーティストページの「similar artist」に、出始めのアーティストをリコメンドする際のコールドスタート問題に対し、グラフのlink predictionを使った推薦モデルを適用した。
モデルは有向グラフに拡張したグラフオートエンコーダー "gravity-inspired graph autoencoders". ストリーミングデータを使わずにアーティストに関する事前情報のみを使って既存のアーティスト関係グラフの中から関連度の高いアーティストtop-k個とその関連度順を推定する。
実験はオンラインでdeezerでも行われ有効性確認
https://gyazo.com/468513e4a876078836feb86b81188239
背景
推薦はitem同士の関係性を表すためグラフと相性が良い。グラフを表現する指標として古典的にはAdacmi-Adar, Jaccard係数, Katz係数などのハンドメイドな指標が使われていたが、Graph Convolutional Networkなどグラフ構造を反映したノード表現を学習で獲得することで推薦性能が飛躍的に向上している。
推薦の文脈では、有向/無向グラフを使ったものがあり、また二部グラフ(user-item)に限定したものもある。
本手法は有向グラフを仕様。
今までのモデルとの差分
vs 協調フィルタリング:
item間の関係の向きを扱っている. ex. レゲエ聞く人Bob Marley聞くけど、Bob Marley聞く人レゲエ聞くわけではない
類似度スコア作るときにitemの属性(attribute)も同時に使うことができる
vs グラフ機械学習:
(*有向*グラフAutoEncoderを推薦に適用した)
有向のグラフを扱うモデル、AutoEncoder自体はある
推薦で初かは調べてないです:bow:
実サービスへの適用
グラフの畳み込みについてざっくり
GCNで 赤ノードの表現に周辺ノード(青)の情報を反映する場合
隣接する青ノードの情報に重みかけて足し、非線形関数に通す.
エッジの情報(向き, エッジタイプ)を使う場合はこの作業をエッジタイプ別に行ってから足し合わせる
https://gyazo.com/09069653c402576bc11de9abee1c610ahttps://gyazo.com/1266e0d27365e3d03edb1c22669d902dhttps://gyazo.com/0ee94c44909e08052bae40e5132a54ca
ノード表現を作り、ノード間の距離をz_iとz_jのユークリッド距離や内積で表す方針が一般的。
この場合向きを扱うことができない(やろうとするとエッジの種類で分けるなど?)
提案法
問題設定: 有向グラフにおけるLink Prediction task
cold item(まだ利用データゼロのアーティスト)をグラフに新ノードとして追加する。このとき新ノードはグラフ内にエッジが貼られたノードがなく、孤立している。この状態からlink predictionをして最もリンクが貼られそうなtop kノードを探し、またtop k個を関連度順に重み付けを行う。
孤立状態が終わり、リンクが貼られた状態をground truthとして学習データにする。
扱うグラフは有向、重み付き、属性(attribute)付きのグラフ
モデル: Gravity-inspired Graph AutoEncoder
オートエンコーダーで入力情報をエンコードし、デコーダーで再度入力データを再建することで中間出力(潜在変数Z~)に入力を圧縮した表現を獲得する.
https://gyazo.com/b385f484ae6def7038c451bdaeea12bf
入力:協調フィルタリングと同様のn×nの隣接行列A、ノード属性を表すn×fの行列X
エンコーダー: なんでもよしGNN; Graph Neural Network. この論文では2層GCN; Graph Convolutional Networkが使われている(これが一番性能良かった)
中間出力 潜在変数Z~: n×(d+1)の行列. 1~d列がノード表現z_i、d+1列目が質量m_i
デコーダー:万有引力inspiredの式 https://gyazo.com/bd014b3b458af484cf3c11f4d362c3e5
向きを扱うために万有引力の法則を参考にエッジの重みをモデリングする。そのために質量mに対応する変数を用意。
万有引力では質量1から質量2へ向かう力は次のように表される
https://gyazo.com/04c3c2f1a835df5b733df1c177feee25
↑の式を対数に直して、引力をシグモイド関数に通すことでitem_iとitem_jの推定関連度~A_jiを求める
※ハブになっているノード(中心性の高いノード)の引力が大きくなりすぎないように対数を使う
ホントは-log(r)に係数λかかってる
https://gyazo.com/1b9826e91de8258dbf07d818b3cd615b
デコーダーの出力A~ (再構成された隣接行列A)とオリジナルの入力Aの再構成誤差(reconstruction loss)を最小化するように学習していく
Gravity-Inspired Graph VAEでは潜在変数Z~が正規分布N(μ,σ)に従うと仮定し、正規分布の母数はμ、σ別個にGNNモデルを用意して学習される(詳細スキップ)
Cold Nodeにモデルを使う
1. 既存グラフに新ノードを加えたグラフの潜在表現を求める
元のGraphAEのエンコーダー:2層GCN。 W(i)が隠れ層iの重み
https://gyazo.com/7e8dc0a239bf821d9448d860046552b4
↑で学習したモデルの再構成された類似度行列A~ <n, n>, hidden layerの重みW(0, 1)<f, d_hidden>、
新Node加入前の類似度行列A<n,n>, 属性行列X<n,f>に、
新たにCold Node m個を加える
で新しくA', X'を作り式(3)を使ってZ'~が求まる。= 既存グラフに新ノードの追加Done
https://gyazo.com/d8f5a193ebad07ce4ce08489d788492d
2. gravity-inspired decoderでマスクされたリンクを予測する
過去と同様の式に通すだけ。 (n×nが(n+m)×(n+m)になる)
https://gyazo.com/cd302bfa22d3d2bf3fa2627fbb1fb129
A^の要素で大きいものtop-kが予測されたリンク
m_jはノードの影響力(アーティストのpopularity)
node_iから等距離に離れたnode_j, lがある場合、より質量の大きい方に引かれる.
音楽的に同程度似たアーティストj, lがいる場合、より広く聞かれているアーティストとの類似度が高くなる
log(r^2)は近接性proximity
node_j, lが同じ質量の場合、より距離が短いノードに引かれる
アーティストjとlの人気が同程度の場合、よりアーティストiと音楽的に近い方が類似度が高くなる
λでpopularity biasをコントロールしている
実験ではλ=5
おまけ:グラフモデルのtrainingコストをへらすためにFastGAEという最適化方法を用いた。(公開コードに入っている)
またcold nodeの追加時に一度forward passするだけで良いのでシンプル
実験 どうやって有効だと検証した?
評価は以下の2観点で行う
prediction accuracy: エッジを貼った先のノードが実際に関係があるものを選べているか
Recall@K
ranking quality: エッジweightの関連度順がどれくらい正しく並んでいるか
MAP@K; Mean Avarage Precition at K
NDCG@K; Normalized Discounted Cumulative Gain at K
データセット
Deezerの実データ。n=24,270アーティスト、各人top-20人リンクが貼られている。
隣接行列の要素(グラフのリンクの重み) A_ij 0, 1はストリーミングされるアーティスト同士の共起から得た相互情報量。 attribute表現Xの中身
レーベルからもらえるアーティスト情報、曲などから抽出して作成した56次元
ジャンル(32-dim) : 300ジャンルある。ジャンル別再生数の共起行列を作り、その歌手のジャンルの平均ベクトルを使用
国(20-dim): one-hotベクトル. 19の国+others
ムード(4-dim):曲がポジティブかネガティブか、穏やかかエネルギッシュか
ラッセルの円環モデル
https://gyazo.com/c9a0cf7183fdccee5366c6b1381f82e4
音声データをDNNで処理して4次元ベクトル化
ほんとうは他にも様々な特徴量が収集されているが非公開、本論文の実験には非使用。
train/validation/test (80:10:10)に分割して、valication, testはコールドノードになるように隣接列Aのエッジをマスク。属性情報のみ使用する。
validateionではNDCG@20が最も良くなるようにハイパラチューニング
ベースラインモデルs
グラフ系
無向グラフAE/VAE
source-target graph AE/VAE: 無向グラフでsourceとtargetにitemを分割してAEに通すことでエッジ方向awareにしたモデル
DEALモデル: 同時期に提案された有向グラフのlink predictionモデル
クラシカル系
popularity: 人気ランキングtop-K
popularity by country; cold artistの出身国の国別ランキング
In-degree: アーティストグラフでノードを指すエッジの重み合計値が高い順.
ノードiのin-degree = sum(weight_i<-j)
in-degree by country: 同上国別
アーティスト属性のみ(ストリーミング情報は使わない)
K-NN: top-k Nearest Neighbor, attribute embedding x_iとのユークリッド距離が小さい順
𝐾-NN + {Popularity, In-degree} : ユークリッド距離が近いtop200ノードを取得し、そのうちで{人気, in-degree}のtopK
Deep系
DropoutNet
STAR-GCN
結果
https://gyazo.com/a2234f2d6e4fb03d930d901b28e83247
提案法 > 有向Source-Target Graph(V)AE > Deeps >無向GraphVAE>AE >ユークリッド距離> 国別クラシカル>全世界クラシカル
グラフ構造使うほうがよい
エッジの向き情報大事 in cold start
https://gyazo.com/6980bdaf914072bc84447f4b9ff3bfd1https://gyazo.com/9a96a09626fb23b7abaf1168d98df802
重力モデルの質量mは他のpopularityを表す指標と正の相関があるが、完全ではなかった。PageRankをm_iに代入したらNDCG@200で-6pt減少したのでノードembeddingとの最適化の兼ね合いか。
Bob Marleyの周辺グラフの可視化ではアリアナ・グランデよりもブラジルのサンバアーティストThiaguinho(Deezerのtop100にはいない人)のほうが質量が大きくなった。ジャンル(サンバvs USpop)や国の違いがpopularity以上に質量に影響している。
Attributeのみモデルの評価
ジャンル>国>ムードhttps://gyazo.com/89fc4016a5500bb1ad95914a980de4db
国+mood > ジャンル+mood: speed metalのように音楽ジャンルがmoodを掴んでいるパターンの現れか
感想
コールドスタート問題が一般的な無向グラフだとときづらく、有向グラフのほうが適しているのは学びだった。
またノード
グラフの可視化もおもしろそう
関連して気になった記事, 参考文献