Engineering a direct k-way Hypergraph Partitioning Algorithm【2017 ALENEX】

文章目錄

一、作者
二、摘要
三、相關工作
四、算法概述
五、實驗結果
六、主要貢獻

一、作者

??Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders, Sebastian Schlag

二、摘要

??我們開發了一種快速且高質量的多層算法，能夠直接將超圖劃分為 k 個平衡的塊 —— 無需借助遞歸二分法這一迂回方式。特別是，我們的算法能有效實現強大的 FM 局部搜索啟發式算法，使其適用于復雜的 k 路情況。這對于依賴超邊所連接塊數的那些目標函數來說意義重大。此外，我們還消除了處理大型超邊的多個瓶頸，開發了一種更快的收縮算法以及一種新的局部搜索自適應停止規則。為進一步縮小超邊規模，我們基于 min - hashing 技術開發了一種將具有相似鄰域的頂點聚類的引腳稀疏化方法。大量實驗表明，我們的 KaHyPar 劃分器與其他最佳的先前系統相比具有優勢。KaHyPar 比 hMetis 更快且計算出的解更好。相比于（速度更快的）PaToH 劃分器，KaHyPar 的結果要好得多。

三、相關工作

研究現狀：
- 常用工具
  - PaToH^[7]（科學計算）
  - hMetis^[8] ^[9]（VLSI 設計）
  - Mondriaan^[10]（稀疏矩陣劃分）
  - MLPart^[11]（電路劃分）
  - Zoltan^[12]、Parkway^[13]、UMPa^[14]（定向超圖模型，多目標）
  - kPaToH^[15]（多約束，固定頂點）
- 其他文獻
  - n 級范式一直運用于基于隨機增量結構的幾何數據結構^{[2] [3]} 和布線計劃的預處理階段^[4]，而且，也成功運用于圖和超圖的劃分中，例如：KaSPar^[5]（圖直接 k 劃分）和 KaHyPar^[1]（超圖遞歸 k 劃分）。
  - 有一個未正式發表的直接 k 路 n 級劃分算法^[6]，盡管在部分實驗取得不錯的效果，但是運行時間比較長。
準備工作：
- 術語表

term	explanation
$H=(V,E,\omega(v),\omega(e))$	H 表示超圖，V 表示超圖的頂點集，E 表示超圖的超邊集， $\omega$ 是權重
$\epsilon$	不平衡系數
$V_x$	劃分塊
$E_x$	包含頂點 x 的超邊集合
$d(v)=\|E_v\|$	頂點 v 的度
$N(v)=\{v'\|v'\in E_v \wedge v' \ne v\}$	頂點 v 的鄰居頂點
$P=\{V_1,\dots,V_k \| \cup_{i=1}^k V_i=V \wedge (V_i\cap V_j=\varnothing \Leftrightarrow i \ne j ) \}$	劃分 P
$b(v)=\{V_i \| v \in V_i\}$	頂點 v 所屬的劃分塊
$b(e)=\{b(v)\|v \in e \}$	超邊 e 所屬的劃分塊
$\Zeta(v)=\{b(e)\|e\in E_v\}-\{b(v)\}$	頂點 v 的鄰居劃分塊
$\Phi(e,V_i)=\big\|\{v\| v \in e \wedge v \in V_i\}\big\|$	超邊 e 在劃分塊 $V_i$ 的頂點數量
$Cut(e)=\begin{cases} \omega(e) &, \|b(e)\|>1 \\ 0 &, \|b(e)\|=1 \end{cases}$	e 的割邊權重

$\;$
- 約束
  - 平衡約束
    $\begin{equation} \forall V_i \subseteq P,\;\; \omega(V_i)\le(1+\epsilon) \bigg\lceil \frac{\omega(V)}{k} \bigg\rceil \end{equation}$
- 目標：
  - 最小割邊
    $\begin{equation} \min \sum\limits_{e\in E} Cut(e) \end{equation}$
  - 最小連接權重
    $\begin{equation} \min \sum\limits_{e\in E} \big(b(e)-1\big) \cdot \omega(e) \end{equation}$

四、算法概述

基于 Min-Hash 的頂點劃分器【限定頂點的更新范圍】
- 指紋【每個頂點一個指紋，第 i 輪建立 hash 表 $T_i$ ，使用指紋分量 $g_i\big(v,z(v)\big)$ 作為 key】
  $\begin{equation} \{g_i(x,z)=\big(h_{i,1}(x),h_{i,2}(x),\cdots,h_{i,z}(x)\big)\}_{i=1,2,\cdots,l} \end{equation}$
- Min-Hash 簇
  $\begin{equation} H=\{h_{\sigma}(v)=\min \{ \sigma(e) | e\in E_v\}|\sigma \in \Sigma\} \end{equation}$
- hash 函數
  $\begin{equation} \sigma(x)=(ax+b)\;mod\;P \end{equation}$
- 構建 hash 表
  - 初始化：
    - 將所有頂點設置為活躍狀態，
    - $z = 1,\;h_{min}=10,\;h_{max}=100$
    - 建立空表 T。
  - 迭代：
    - 迭代條件：存在活躍頂點且 $z\le h_{max}$
    - 迭代過程：
      - 建立 hash 表 $T^{'}$
      - 遍歷所有活躍頂點 v，將活躍頂點按照 ${g(v,z),v\}$ 插入到 $T^{'}$ 。
      - 遍歷所有活躍頂點 v：
        如果 $∣ T [v] ∣ = ∣ T^{'} [v] ∣$ 且 $\ge h_{min}$ ，將 $T^{'} [v]$ 的頂點全部標記為不活躍。
        如果 v 為活躍頂點且 $\le c_{max}$ 且 $\ge h_{min}$ ，將 $T [v]$ 的頂點全部標記為不活躍。
      - $z = z + 1$
      - $T = T^{'}$
- 自適應聚類算法
  - 初始化
    - $i=1,\;c_{min}=2,\;c_{max}=10,\;l=5$
  - 迭代：
    - 迭代條件：如果簇的數量大于頂點數的一半且 $i\le l$
    - 迭代過程：
      - 構建 hash 表 $T_i$
      - 遍歷所有活躍頂點 v ，如果 $|T_i[v]| \le c_{max}$ ，將 $T_i[v]$ 中的頂點加入到簇 $c_v$ 中，并且移除 $T_i[v]$ 。
      - 如果 $c_v \ge c_{min}$ ， $c_v$ 中的所有頂點都標記為不活躍。
      - $i = i + 1$
聚類：
- 瓶頸【使用 n 級范式來消除】
  - 使用 PQ 來確定下一個聚類的頂點對
  - 聚類后更新鄰居頂點的評分函數
- 預處理
  - 移除單頂點網絡【 $∣ e ∣ = 1$ 】
  - 合并平行網絡
    - 建立指紋【在聚類前】
      $\begin{equation} f(e)=\sum\limits_{v\in e}v^2 \end{equation}$
    - 更新指紋【合并頂點 u 和頂點 v 時，保留頂點 u】
      - 超邊 e 不包含 u 和 v ，不需要更新
      - 超邊 e 同時包含 u 和 v ， $f(e)=f(e)-v^2$
      - 超邊 e 只包含 u ，不需要更新
      - 超邊 e 只包含 v ， $f(e)=f(e)-v^2+u^2$ 【但是論文中沒有 $v^2$ 】
- 頂點合并 $C (u, v)$
  - 評分函數
    $\begin{equation} r(u,v)=\sum\limits_{e\in E_u \cap E_v}\frac{\omega(e)}{|e|-1} \end{equation}$
  - 合并步驟【將 v 替換為 u】
    （1） $\omega(u)=\omega(u)+\omega(v)$
    （2） $\Leftrightarrow v\in \{E_v-E_u\}$
    （3）刪除 $\Leftrightarrow v\in \{E_v \cap E_u\}$
  - 約束【滿足約束的頂點才可以進行合并， $t = 160 k$ 】
    $\begin{equation} \omega(v)\le \bigg\lceil \frac{\omega(V)}{t} \bigg\rceil \end{equation}$
  - 停止條件：不存在滿足約束的頂點或者頂點數小于 $t$
初始劃分
同上篇論文的初始劃分一致，不過進行了優化，將被分割的網絡生成兩個小的網絡的加入到對應的劃分塊中【上一篇論文是不考慮被分割的網絡】
$\begin{equation} \begin{aligned} n_0=\{ v\; |\; v\in e \wedge b[v] \in V_0\} \\ n_1=\{ v\; |\; v\in e \wedge b[v] \in V_1\} \end{aligned} \end{equation}$
局部搜索
- 優化
  - 每個塊一個優先隊列【共計 k 個優先隊列】【 Sanchis 的算法^[16]，優先隊列數量為 $k (k ? 1)$ 】
  - 頂點 v 的移動目標只考慮鄰居塊 $\Zeta(v)$
- 初始化
  - 所有優先隊列設置為空且禁用的。【禁用的優先隊列不會考慮移動增益】
  - 所有頂點都設置為不活躍的且未標記的。【未標記的頂點代表沒有移動過】
- 局部搜索
  - 激活所有邊界頂點【如果不存在邊界頂點，跳過這一輪局部搜索】【不考慮 $∣ e ∣ > 1000$ 的超邊的頂點】
  - 計算邊界頂點 v 的移動增益 $G_i(v)$ 并插入到對應優先隊列 $Q_i$ 【只考慮頂點 v 的鄰居劃分塊 $\Zeta(v)$ 】
    $\begin{equation} G_i(v)=\sum\limits_{e \in E_v}\{\omega(e):\Phi(e,b(v))=1\}-\sum\limits_{e \in E_v}\{\omega(e):\Phi(e,V_i)=0\} \end{equation}$
  - 激活所有輕負載的優先隊列。
  - 迭代移動【一個頂點一輪至多移動一次】
    - 查詢所有激活的優先隊列，獲得最高移動增益 $G_i(v)$
    - 如果滿足平衡約束，移動該頂點 v 到劃分塊 $V_i$ ，并將該頂點標記不活躍且已標記。否則，則跳過。
    - 激活頂點 v 的所有不活躍的鄰居頂點
      - 如果鄰居頂點不是邊界頂點，則標記為不活躍的且從優先隊列中刪除其移動增益。
      - 如果鄰居頂點是邊界頂點，則通過 $DeltaGainUpdate(v, V_{from}, V_{to})$ 來更新鄰居頂點的移動增益。
  - 回滾移動，直到處于最優的目標狀態。
  - 自適應停止規則： $log\;n$ 步非正增益移動，則停止。
- $DeltaGainUpdate(v, V_{from}, V_{to})$
  【當一個頂點 v 移動后，在目標劃分塊 $V_{to}$ 中可以連接到所有超邊，則該劃分塊對于超邊 $e\in E_v$ 來說是不可移動的。如果一個由于平衡約束而無法移動，則源劃分塊 $V_{from}$ 對于超邊 $e\in E_v$ 是不可移動的。如果源和目標劃分塊都是不可移動的，則這部分超邊 e 不進行更新】
  - 遍歷頂點 v 的所有超邊 $E_v$
    - 對于 $e\in E_v$ ，遍歷超邊 e 的所有頂點 $u\in e$
      - 如果頂點 u 是已標記的，則跳過；【已經移動過的就不用更新了】
      - 如果 $\Phi(e,V_{from})=0$ 【e 在劃分塊 $V_{from}$ 已經沒有頂點了】
        如果 $V_{from} \not\in \Zeta(u)$ ，則優先隊列 $Q_{from}$ 移除頂點 u ；【如果劃分塊 $V_{from}$ 不在是 u 的鄰居塊】
        否則，優先隊列 $Q_{from}$ 更新頂點 u 的增益 $G_{from}(u)=G_{from}(u)-\omega(e)$ ；
      - 如果 $\Phi(e,V_{to})=1$ 【頂點 v 移動后對 e 產生了新的劃分塊連接】
        如果 $V_{to} \not\in \Zeta(u)$ ，則依據公式 G_i(v) 計算 $G_{to}(u)$ 并插入到優先隊列 $Q_{to}$ 中；【如果對于 u 來說， $V_{to}$ 是不是其鄰居劃分塊】
        否則，優先隊列 $Q_{to}$ 更新頂點 u 的增益 $G_{to}(u)=G_{to}(u)+\omega(e)$ ；
      - 如果 $b(u)=V_{from} \wedge \Phi(e,V_{from})=1$ ，更新頂點 u 的所有增益 $G_i(u)=G_i(u)+\omega(e)$ ；【對于 e 來說，其在劃分塊 $V_{form}$ 只剩下頂點 u 了，所以 u 移動到其他頂點就可以減少其的連接數】
      - 如果 $b(u)=V_{to} \wedge \Phi(e,V_{to})=2$ ，更新頂點 u 的所有增益 $G_i(u)=G_i(u)-\omega(e)$ ；【對于 e 來說，原本 $V_{to}$ 只有 u 一個頂點，所以它移動到其他劃分塊可以減少連接；但是 v 移動過來后，u 在移動到其他劃分塊就不會減少連接數，所以移動增益要減去 $\omega(e)$ 】
- 增益緩存
  - 對于每個頂點 v ，用 $\Omicron(k)$ 的空間來存放鄰居劃分塊和移動到該塊的增益。【可以在 $\Omicron(1)$ 時間內添加和刪除一個塊，在 $\Omicron(\big|\Zeta(v)\big|)$ 內遍歷所有鄰居塊，此外，還可以在 $\Omicron(1)$ 時間內完成更新】
  - 具體做法：
    - 用 $C_v[i]$ 表示頂點 v 和劃分塊 $V_i$ 的緩存條目。
    - 在初始劃分結束后，計算每個頂點所有可能的移動增益。【每輪局部搜索都要重新計算相應頂點的移動增益（不需要全部頂點重新計算）】
    - 每次激活頂點時，使用緩存增益值來激活頂點；
    - 移動頂點后，緩存增益更新操作如下：【移動后頂點 v 的鄰居劃分塊，有可能新增 $V_{from}$ ，一定減少 $V_{to}$ 】
      - 刪除 $C_v[to]$ ; 【因為頂點 v 移動到了劃分塊 $V_{to}$ 】
      - 如果 $V_{from} \in \Zeta(v)$ ，則 $C_v[from]=-C_v[to]$ ；【如果劃分塊 $V_{from}$ 是 v 的鄰居劃分塊】
      - 對于其他鄰居劃分塊 $V_i$ ，遍歷所有超邊 $e\in E_v$
        如果 $\Phi(e,V_{from})=0 \wedge \Phi(e,V_{to})>1$ ，則 $C_v[V_i]=C_v[V_i]-\omega(e)$ 【原本在 from ，移動到其他塊可以減少連接數，而移動到 to 時，超邊 e 在 to 有其他頂點，所以如果要移動到其他塊，就不會減少連接數，所以移動增益要減少】
        如果 $\Phi(e,V_{from})=0 \wedge \Phi(e,V_{to})=1$ ，則 $C_v[V_i]=C_v[V_i]+\omega(e)$ 【原本在 from ，移動到其他塊可以減少連接數，而移動到 to 時，超邊 e 在 to 沒有其他頂點，所以如果要移動到其他塊，就會減少連接數，所以移動增益要增加】
    - 回滾時同時回滾增益緩存
實驗結果：
- 測試用例：
  - the ISPD98 VLSI Circuit Benchmark Suite ^[17]
  - the University of Florida Sparse Matrix Collection ^[18]
  - the international SAT Competition 2014 ^[19]
- 實驗參數
  - $k=\{2,4,8,16,32,64,128\} \cup \{5,23,47,107\}$
  - $\epsilon=0.03$
- 比較對象
  - PaToH-Q
  - PaToH-D
  - hMetis-R
  - hMetis-K