數據管理和系統實現課程上要分享的論文：《LEOPARD: Lightweight Edge-Oriented Partitioning and Replication for Dynamic Graphs》

背景

目前分析處理圖數據已經成為一項重要的任務，例如，研究互聯網結構，分析社會關系，或捕獲蛋白質之間的關系等。在網上也有許多公開的數據集，可以看到圖數據已經廣泛應用在多個領域。

處理這類圖是具有挑戰性的，因為這些圖往往十分巨大，甚至會有數萬億的邊，如此龐大的數據在單機器上是很難處理的，典型的方法就是對數據進行劃分，分布到多個機器上。因為我們最終是要在圖上進行各種計算，所以圖劃分的速度、劃分效果的好壞都將直接影響計算系統的運行效率。

從劃分方式上來看，圖劃分問題可以被分為兩類:邊劃分和點劃分。
點劃分指將圖中的點集合劃分為若干部分，圖中每個點及其相關信息(鄰接列表等)存放于一個劃分出的子圖中，而圖中的邊則可能因為兩個頂點被劃分在 不同的子圖中而成為割邊，如圖中的邊 (d,z) 和 (b,z)。邊割集的大小將直接影響分布式算法的通訊代價。
邊劃分則是將圖中的邊集合劃分為若干部分，圖中每條邊及其相關信息存放 于一個劃分出的子圖中，而當一個點的鄰邊被劃分在不同的子圖中時，這個點將在多個子圖中均存在，這樣的點被稱為割點, 如圖中的點 d 和 z。與邊割集相同，點割集的數量也將直接影響分布式算法的通訊代價。

圖劃分的目標有兩個：負載均衡和最小割。負載均衡是為了使分布式系統中的多臺機器有相近的任務負荷，負載不均會導致負載較小的處理器出現空等的情況而浪費資源。此外，要盡量減少分割，以便最小化由不同分區之間交換消息引起的通信成本。

目前圖劃分算法主要可以分為三類：

靜態圖劃分算法：它在獲得整個圖數據后進行全局劃分，能取得很好的劃分效果，但需要多次迭代運行時間長。

流式圖劃分算法：它將圖數據看作是持續不斷地數據流，當數據到達時基于當前的數據信息判斷該數據的劃分位置，可以獲得較快的運行速度，但效果差于靜態圖劃分。

動態圖劃分算法：上述的靜態圖劃分算法不適合處于大規模圖數據。除此之外，目前很多圖是動態的，新的友誼出現，新的聯系建立，或者蛋白質相互作用改變。那么原先通過靜態圖劃分或流式圖劃分得到的初始良好劃分會隨著圖結構的不斷變化而惡化。動態圖劃分算法的作用就是在圖結構變化的同時及時的調整劃分，使得系統保持可以一個良好的劃分。

研究現狀

在動態圖算法的研究方面，之前大部分的動態圖劃分研究集中在一批更改導致原始分區惡化之后再對圖進行重新分區，然而這樣的算法是重量級的。

最近也有一些關于輕量級的動態圖劃分算法，一些研究者不認為復制是一種改進邊切的機制，當然他們這么認為是有道理的，因為保持副本之間的同步是需要巨大開銷的。但是這篇論文引入了復制機制，所以它其實只適用于只讀圖計算，例如：子圖模式匹配、三角計數、圖遍歷等。另外也有一些工作引入了復制機制，但是沒有考慮動態重劃分。

所以這篇論文的工作重點就是將動態重劃分和復制緊密結合起來，每次增加或刪除頂點、邊后，檢查分區情況，決定是否需要重新分配。同時，復制可以提供一定的容錯性，并增加訪問局部性，可以有效的減少邊切割。

那么該方法需要考慮的問題有：

在劃分方面：如何進行頂點的分配；頂點重分配計算的時機；哪些頂點需要重分配。

在復制方面：副本復制到哪些分區；副本復制的數量。

Leopard：劃分

論文的劃分算法借鑒了2014所提出的FENNEL算法，它是一種流式圖劃分算法。

FENNEL算法的主要思想：為了減少邊切割，一個頂點應該被分配到有較多鄰居的分區，同時還要加入一個懲罰因子，以防止一個分區變得過大。前面這部分就表示 v 節點在 i 分區的鄰居數，后面項是對分區節點數的懲罰因子。

在許多情況下，使大多數動態圖變化的是新添加的頂點和邊。因此，在任何時間點，動態圖都可以被認為是該算法的中間狀態。該算法對于頂點只分配一次，后續不再變更。但是Leopard會不斷地重新訪問由單次劃分所分配的頂點和邊，以此來實現重新分配。

如何進行重分配一個最簡單的辦法就是在添加或刪除邊后，去重新計算每個頂點的值，但這樣肯定太傻了。事實上，當一個節點發生變化時，基本上只有它的鄰居節點才會受到較大的影響。所以這里我們可以設立一個候選集，逐步將更改節點的鄰居加入候選集。這個過程其實有點像BFS。

接下來再考慮一個問題，就是重新進行分配計算其實也是很耗時間的，事實上，對于候選集中的節點，如果它在分區內已經擁有大量鄰居節點時，其重新分配的概率就相對較小，所以我們也沒有必要每次都計算檢測，給定頂點 v 和閾值 t ，如果跳過的計算與v的總鄰居的比率小于t，則函數跳過重新分配分數的計算。但同時隨著計數的增大，每個節點都可以保證被定時的檢測。

Algorithm for deciding when to examine a vertexfor reassignment

Leopard：復制

論文提出了一種稱為MAP的方法，也就是包含兩個參數，即最小復制數和平均復制數。最小數量的拷貝確保了容錯性，任何超出最小數量的額外拷貝都提供了額外的訪問局部性，可以減小邊切割率。Leopard首先運行頂點分配算法。第二，將第一步計算得到的分數與最近其他頂點計算得到的分數進行排序。排名越是靠前，復制的概率就越大。

An algorithm to choose partitions for the primaryand secondary copies for a vertex

首先計算主節點的劃分，直接將其分配至分數最高的分區上。然后對副本節點計算分數，因為有最小復制數的規定，所以top（min-1) 的分區會復制該節點的副本。同時該方案也還有平均復制數，將剩下的計算分數與最近計算得到分數進行排序，如果分區的分數在top內，就在該分區復制節點副本。這里用滑動窗口維護最近最近計算得到的分數。

(【注】這里主節點的分配計算和副本節點的分配計算都是用的FENNEL算法，但是由于引入了復制，所以論文中重新定義了鄰居，這里就省略了，詳細的看論文?？傊?#xff0c;它們的區別就是FENNEL算法中鄰居的數量會不一樣，所以結果也就會不一樣。)

實驗

最后論文在多個不同的圖形上進行了實驗評估，包括社交圖、協作圖、網絡圖、電子郵件圖等等。總共比較了5種不同的方法：

Statistics of the graphs used in the experiments. Diameter is reported at 90th-percentile to eliminate outliers

1 Leopard：論文所提出的方法

2 FENNEL：沒有涉及頂點重分配，用來比較頂點重分配的好處

3 METIS： state-of-the-art靜態圖劃分算法，METIS需要所有的更新請求完成后，也就是得到最終的圖后對其進行靜態分區，在分區時擁有最終圖形的全局視圖是一個很大的優勢。因此，METIS被用作分區質量的近似上限，Leopard的目標是獲得與METIS相似的最終分區。

4 ParMETIS： ParMETIS先允許分區惡化，然后再批量重新分區操作。而Leopard持續保持對圖形的良好分區，所以也對它們進行比較。

5 哈希劃分算法：哈希劃分算法簡單，容易實現負載均衡，缺點是會產生大量割邊，但是現在仍然是在廣泛使用著，所以也和它進行比較。

我們采用兩個評估指標：

1 邊切割率 λ ：λ = 切割邊的數量除以邊的總數(對于復制數據，切割邊的定義按照論文所述的，這里沒說，詳情看論文)

2 負載不平衡 ρ ：ρ = 分區中的最大頂點數除以分區中的平均頂點數

Edge cut experiment. Cut ratio for hash partitioning is independent of the data set, and so it is displayedjust once on the left-hand side

首先評估沒有復制時的分區質量，使用上面描述的五種劃分生方法將我們上面所提到的11個真實世界的圖形集劃分成40個分區，該圖僅顯示了邊切割率，因為負載不平衡率對于所有方法都大致相同（哈希劃分：1.00，其它：1.02~1.03）。

由這張圖可以看出黑色的哈希算法效果是最差的，除此之外最差的就是紅色的FENNEL算法了，論文的Leopard邊切割率比起FENNEL來低了不少，這顯示出了動態重新分配的重要性。這里面靜態圖劃分算法METIS的效果是最好的，雖然Leopard的效果沒它好，但已經十分接近了。只有在最后面四個網絡圖的劃分中，Leopard與METIS的劃分效果相差較大，因為網絡圖往往具有較大的直徑，更容易劃分。而Leopard沒有全局的圖，容易陷入局部最優，導致更多的邊被切割。

需要注意的是，這里沒有考慮運行的時間，事實上，FENNEL算法的速度是Leopard的44.6倍，但是如果使用論文所提到的優化技術的話，就可以降至2。

Effects of skipping examination on edge cut ratio AND Computation savings vs. skipping threshold

Run time improvement vs. skipping threshold

我們這里定義

為節點跳過檢查計算的比例，可以看到，當把跳過閾值設為0.1~0.2左右的時候，邊的切割不會增加多少，但是卻可以跳過十分多的節點檢查計算。這可以直接反映在運算時間上，最左邊的1就是永遠不會跳過，對于一些稠密圖來說，它甚至都縮短至了原來的0.1及以下。

Effect of number of partitions on edge-cut on theTwitter graph

然后考慮分區數量對劃分效果的影響，在實驗中分區數量從2逐漸增至256，但METIS和Leopard的差異并沒有太大的改變，這說明Leopard對于不同的分區數量都能有較好的劃分效果。

Effect of replication on edge-cut

最后，我們再加入復制，由于Leopard是第一個(據他們所知)將復制與動態分區集成在一起的系統，所以這里是將帶有復制的Leopard與不帶復制的Leopard進行了比較。負載不平衡 $rho$ 的值還是和之前差不多的，但是切割率卻可以達到一個顯著的下降。

總結

Leopard是為大規模、不斷變化的圖所設計的算法，通過將動態圖的劃分和復制緊密結合，能夠很好的實現訪問局部性和容錯性。但是它也有一個很大的局限性，因為復制機制的引入，所以其只適用于只讀圖計算。

個人想法

副本是否要重分配？副本的個數是否會改變？這些問題論文里好像并沒有提到。

參考

【1】J. Huang and D. J. Abadi. Leopard: Lightweight edge-oriented partitioning and replication for dynamic graphs. Proceedings of the VLDB Endowment, 9(7):540–551, 2016

【2】C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In WSDM ’14

【3】許金鳳，董一鴻，王詩懿等. 大規模圖數據劃分算法綜述. 電信科學，2014，30(7)；100-106

【4】M. Besta, M. Fischer, V. Kalavri, M. Kapralov, and T. Hoefler, “Practice of streaming and dynamic graphs: Concepts, models, systems, and parallelism,” arXiv preprint arXiv:1912.12740, 2019.

【5】圖流劃分算法綜述

總結

以上是生活随笔為你收集整理的动态分区分配的“首次适应算法_动态图划分复制算法：Leopard的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。