論文位址
code
overview
本文可以認為是GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph的改進版本，建議先看GRAMI。ScaleMiner源碼閱讀部分還未完成（棄坑）。
本文的主要貢獻是将GRAMI進行并行化，實作了超大規模的頻繁子圖挖掘系統，最大可支援千萬節點，十億邊的圖。
問題
頻繁子圖挖掘要并行化，主要的難點在負載均衡。基于模式增長的挖掘模式，其搜尋空間是包括了所有頻繁子圖和一層不頻繁子圖，且是未知的，示意圖如下；對于子圖同構計算上，不同的子圖其計算難度是不同的，會導緻即使劃分均衡，最終執行時的負載也是不均衡的。
并行的基本思路是，将為了解決這兩個問題，論文提出了兩個方法。針對域搜尋空間的不規則，通過快速估算給出一個近似的搜尋空間。為了解決每個子圖支援度計算難度不同的問題，對較難算的子圖任務進行劃分，将任務縮小。
近似搜尋的作用：“快速剪枝”，沒有真正剪枝，隻是記錄不頻繁的模式中MNI小于域值的點，便于後續快速處理。
1.系統概要
1.1 并行的思路
将每個子圖（模式）的支援度計算時為一個task，master節點保持一個task pool，每個worker取一個task并傳回master結果。以此作為baseline。
1.2 系統架構
系統是采用一主多從的結構，每個程序都儲存一分完整的圖結構。程序之間通過MPI進行通信，master将待驗證的模式發送給worker，可能會附帶一些統計資訊，worker傳回的是驗證的結果。通信代價較小，并且沒有需要進行主從同步的。
每個程序可以去fork新的線程來進行輔助，程序不會儲存完整的圖，對資源的需求較小。
1.3 算法
為了解決兩個負載不均衡的問題（1.任務數量不穩定，2. 任務執行的所需的時間差别較大），提出了一個兩階段的算法。首先進行近似挖掘，近似挖掘的目的是為了給精确挖掘提供資訊，保證其
近似挖掘階段
快速建構一個近似的搜尋空間。近似搜尋和精确挖掘是進行的相同的流程，最大的差別在與支援度的計算上。在近似階段，支援度計算是通過采樣來估計。在該階段産生的不頻繁的模式也會被記錄下來，對于其中一些關鍵資訊，包括那些MNI col值較低等将被記錄，用來指導精确挖掘。
采樣估計MNI。将一個點是否屬于某個MNI col視為一種0-1分布，則多個節點與某個MNI col的關系可以視為一種二項分布。那麼MNI值即為節點數N和機率p的乘積，也是二項分布的均值。根據中心極限定理，通過多次采樣，獲得多組平均值，多組平均值的分布是滿足正态分布D，正态分布D的均值即為二項分布的均值。
精确挖掘階段
這階段沒有大動作，主要是借助于近似中的結果，加速判斷。