[aMMAI] Paper Summary: PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

Title: PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

Author: U Kang, Charalampos E. Tsourakakis, Christos Faloutsos

Publication: ICDM 2009

這篇paper主要是在描述一個graph mining library, PEGASUS, 其中最重要的部分GIM-V (Generalized Iterated Matrix-Vector multiplication)

GIM-V最主要的概念:

假設有n*n的matrix M和大小為n的vector v，m_i,j 表示在M中(i,j)位置的值。

將兩者相乘，可用下面的數學式子表示

接著將它轉換成需要的graph mining algorithms

1. combine2: multiply mi,j and vj .

2. combineAll: sum n multiplication results for node i.

3. assign: overwrite previous value of vi with new result to make v′i.

接著paper就描述了許多mining的方法，都將它轉成GIM-V上述三個主要的operation，有PageRank、Diameter Estimation、Connected Components。

• GIM-V BASE: Naive Multiplication是每個將matrix裡面每個項目拆開下去做。
• GIM-V BL: Block Multiplication是將matrix中的資料切成一個個block去做，能加快速度的原因有二，一個是減少需要在shuffling步驟中排序的數量，二是資料的大小減少。
• GIM-V CL: Clustered Edges先對matrix內的值作分群，在切block去做，可以有效加快速度，但是要注意的是，必須是block base才有加速的效果，如果是每個項目分開去跑，事先分群並沒有意義。
• GIM-V DI: Diagonal Block Iteration:由於GIM-V的主要瓶頸在於shuffling與I/O。在HCC中利用與diagonal block相乘來減少迭代的次數。

時間複雜度分析，每次迭代所需要的時間為O( ((V+E)/M) log ((V +E)/M) )，空間消耗上，需要O(V+E)。

paper後面有利用GIM-V對實際的例子測試Connected Components、PageRanks、Diameter這三個mining演算法。

這篇paper主要的貢獻有

1.      提出了一個可以是用在很多mining算法的方法。

2.      GIM-V有很多最佳化的方式。

3.      有針對實際的例子作測試。

整體來說，內容寫得很詳細，每個它所提到的演算法都有一步步拆成GIM-V的形式，能達到最佳化的原因有用圖示說明比較清楚，最後也有實際做在真實世界上的實驗，很有說服力。