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

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

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

大規模な複数カテゴリからなる二部グラフから、ユーザの類似性をランキングする問題を扱う。
ここで言う二部グラフは、ユーザとアイテム（どちらも複数のカテゴリに分割される）
から構成される。
二つの挑戦
1.２部グラフは巨大でいびつ（数百万の広告にたいして数億のクエリが結びつくような）である
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.リアルタイムに複数カテゴリの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数を増加してやる事で、より精度を上げられる。