PEGASUS

PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations の実装をここからダウンロードしてきて眺めてみる。

うーん、なんか論文に書かれていることと違うような。。論文の主張はGIM−Vという汎化行列ベクトル積演算とユーザ定義関数を組み合わせることで、さまざまなグラフアプリが実現できる、というニュアンスなのだが、実装を見る限りどこにも汎化計算はない。個々のアプリは独立したHadoopアプリで、枠組みを共有しているような形跡はない。 速度のことを考えて、ということなのだろうか？それにしても個々のアプリの構造が結構バラバラな気がするが。。

プログラムとしても結構微妙。 Hadoopのmapreduce APIではなく、古い mapred APIを使っている。 プログラムのディレクトリ構造とパッケージ構造が一致していないのでビルドが面倒。というか そのままだとできない。 うーん。。

Hadoop で行列ベクトル積

PageRankは本質的に疎行列ベクトル積になる。Jimmy Lin のData-Intensive Text Processingに乗っているアルゴリズムは、Mapの入力として、Nodeを用いている。Nodeは他のノードへのリンクを保持している。 行列的に捉えれば、行列のカラムに相当する。つまり、このアルゴリズムは、カラムの非ゼロ要素数が十分小さく、メモリに乗るという前提で考えられている。Page Rankというアプリケーションの特性を考えれば妥当である。

class Mapper
   method Map(nid n, node N)
       p ← N.PageRank/|N.AdjacencyList|
       Emit(nid n, N ) 
       for all nodeid m ∈ N.AdjacencyList do
         Emit(nid m, p)

class Reducer
   method Reduce(nid m, [p1, p2, . . .])
   M←∅
   for all p ∈ counts [p1,p2,...] do
       if IsNode(p) then 
          M ← p
       else
          s ← s + p 
   M.PageRank ← s
   Emit(nid m, node M )

node のなかに AdjacencyList が含まれているが、これが疎行列のコラム方向の情報に相当する。

CPSYで提案したReduceのみでMatMulを行うアルゴリズムは、ベクトルがメモリに乗ることを前提としている。 ベクトルとカラムは同じ長さだが、ベクトルは密なのでこちらのほうが強い制約となる。

PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations で示されている、naiveな方法では行列ベクトル積はMR2回が必要となるが、サイズの制約はない。かと思ったけど、やっぱり1段めのMRのReduceのところで、一度コラム方向を全部オンメモリに持っているから条件は変わらない。データの持ち方の違いだけか？

map-reduce-mergeのmergeがあれば、merge + reduce で非常に素直に書けそう。