読者です 読者をやめる 読者になる 読者になる

読んだ:Reduce and Aggregate: Similarity Ranking in Multi-Categorical Bipartite Graphs(WWW2014)

数式追えてないのでざっくり。数式よまないとこの論文はいかんけど。

Reduce and Aggregate: Similarity Ranking in Multi-Categorical Bipartite Graphs

大規模な複数カテゴリからなる二部グラフから、ユーザの類似性をランキングする問題を扱う。
ここで言う二部グラフは、ユーザとアイテム(どちらも複数のカテゴリに分割される)
から構成される。
二つの挑戦
1.2部グラフは巨大でいびつ(数百万の広告にたいして数億のクエリが結びつくような)である
2.可能な限りのカテゴリの組み合わせを、結果ごとに再計算するのを防ぐ
グラフで類似度を測る際に一般的に利用されるCommonNeighborやPersonalizedPageRank(PPR)を使う。

●計算方法
今回のフレームワークはreduceオペレーターとaggregationオペレーターからなる。
reduceオペレータ(\odot)・・・actorとitemからなるグラフをactorの集合から成るグラフに落とす。
aggregateオペレータ(\oplus)・・・actor集合を類似度に応じてランキングする。

G=(A \cup B,E):重み(非負)付き無向グラフ
N(a,G):ノードaの隣接ノード集合
sim_{a}(b,G):aに対するbの類似度
ノードaのランキングはG(・,G)を降順ソートする事で得られる。
今回はitem集合Bが非常に巨大である事を想定しているので、そのままランキングしようとすると膨大な計算量がかかる。なので、reduceオペレータによってactorベースのグラフに落とし込むのが非常に重要になる。

reduceオペレータを構成する上での問題
問題1.二部グラフG=(A \cup B,E)が与えられたとき、類似度関数を新たな重み付きグラフG(A',E)に対して計算し、sim_{a}(b,G)=sim_{a}^{*}(b,\hat{G})とする。

  • >各itemのカテゴリC_{i}に対して、actor集合Aのみから構成されるグラフ\hat{G}_{i}[A \cup C_{i}]を計算。そして、任意の2ノードに対して類似度を計算する。

問題2.リアルタイムに複数カテゴリのaggregationを行わなければならない。任意のカテゴリ集合D={C'{1},\dots,C'_{c}}と削減済みグラフ\hat{G}_{i}[A \cup C_{i}]が与えられる。G'=G[A \cup C'_{1} \dots \cup C'_{c}]をGの誘導部分グラフとして定義し、すべてのaに対して類似度ランキングsim_{a}(・ ,G')を求める。

この二つの問題を解決するためのノードの類似度をはかる手法について考える。

[1]CommonNeighbors
[2]Jaccard係数
[3]Adamic-Adar
[4]Katz
[5]Personalized PageRank

それぞれの指標に関して、reduceとaggregationの方法について記載されている。
KatsとPersonalized PageRank、特にPersonalized PageRankは複雑。

●実験
データセット
・query-ads
アド(A)とクエリ(B)から成る二部グラフ
正解データ:google AdWordsチームより提供
・DLBP
著者(A)と論文(B)から成る二部グラフ
正解データ:論文のtitileのbi-gramをとってその類似度
・parent
特許?
正解データ:共通引用数?

presicion-recallCurveで評価。topKのランキング結果に対して評価。
結果を見ると、KatzとPPRが他の指標に比べてよい結果。DLBPデータに関しては正解データにそもそもノイズが多いので、Recallが低くなりがち。
Katzのパス長の深さを増やしても結果にそこまで影響はなかった。(l=5と7の比較)
PPRに関しては、aggregation部分のiteration数を増加してやる事で、より精度を上げられる。