読んだ: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オペレータ()・・・actorとitemからなるグラフをactorの集合から成るグラフに落とす。
aggregateオペレータ()・・・actor集合を類似度に応じてランキングする。
:重み(非負)付き無向グラフ
:ノードaの隣接ノード集合
:aに対するbの類似度
ノードaのランキングはを降順ソートする事で得られる。
今回はitem集合Bが非常に巨大である事を想定しているので、そのままランキングしようとすると膨大な計算量がかかる。なので、reduceオペレータによってactorベースのグラフに落とし込むのが非常に重要になる。
reduceオペレータを構成する上での問題
問題1.二部グラフが与えられたとき、類似度関数を新たな重み付きグラフG(A',E)に対して計算し、とする。
- >各itemのカテゴリに対して、actor集合Aのみから構成されるグラフ]を計算。そして、任意の2ノードに対して類似度を計算する。
問題2.リアルタイムに複数カテゴリのaggregationを行わなければならない。任意のカテゴリ集合と削減済みグラフ]が与えられる。]をGの誘導部分グラフとして定義し、すべてのaに対して類似度ランキングを求める。
この二つの問題を解決するためのノードの類似度をはかる手法について考える。
[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数を増加してやる事で、より精度を上げられる。