Incrementalization of graph partitioning algorithms

 

问题描述

设有一个图 $G$ ,用某个算法 $C$ 对它进行划分,得到的结果是 $C(G)$ 。把更新 ${\Delta}G$ 施加到 $G$ ,则划分的结果变成 $C(G+{\Delta}G)$ 。但是直接计算 $C(G+{\Delta}G)$ 太麻烦,于是希望可以求得一个比较容易计算的 ${\Delta}O$ ,使得 $C(G)+{\Delta}O=C(G+{\Delta}G)$ 。同时要求:

  1. Load balance:划分的目的是并行处理,所以划分得到的各部分的规模应该大致相同。
  2. Minimize cut size:使 割的尺寸 最小,比如 边割割集 中边的数量或边上的权和。
  3. Minimize ${\Delta}O$:${\Delta}O$ 越小,迁移数据的消耗就越少。

边割(edge-cut)

图 $G=(V,E)$ 的 k 路边割 $C^k_e(G)$ 是对点集 $V$ 的 划分(partition) $(V_1,V_2,…V_k)$,满足:

  1. $V_1{\cup}V_2{\cup}…{\cup}V_k=V$
  2. $V_i{\cap}V_j=\emptyset$

$V_i$ 称为 划分 的一个 部分(part)

$C^k_e(G)$ 的 割集(cut-set)割边(cut edge)组成, 割边 是连接不同 部分 的边。

$C^k_e(G)$ 的 割的尺寸(cut size)定义为 $C^k_e(G).ct={\lvert}E/{\cup}_iE[V_i]{\rvert}$ 。

点割(vertex-cut)

图 $G=(V,E)$ 的 k 路点割 $C^k_v(G)$ 是对边集 $E$ 的 划分 $(E_1,E_2,…E_k)$,满足:

  1. $E_1{\cup}E_2{\cup}…{\cup}E_k=V$
  2. $E_i{\cap}E_j=\emptyset$

$E_i$ 称为 划分 的一个 部分

$C^k_v(G)$ 的 割集割点(cut vertex)组成,割点 是邻接边分属不同 部分 的点。

$C^k_v(G)$ 的 割的尺寸定义为 $C^k_v(G).ct={\Sigma}_i{\lvert}V[E_i]{\rvert}-{\lvert}V{\rvert}$ 。

负载均衡(load balancing)

如果 $C^k_e(G)$ 满足 ${\lvert}V_i{\rvert}{\leq}{\lceil}(1+\epsilon){\lvert}V{\rvert}/k{\rceil}$ ,则称它是 $\epsilon$负载均衡 的,$\epsilon$ 称为 均衡因子(balance factor)

$\epsilon$ 越小,各部分越均衡。

图的划分(graph partitioning)

输入:$G$ 、 $k$ 、 $\epsilon$

输出:满足 $\epsilon$负载均衡割的尺寸 最小的 $C^k(G)$ 。

增量图划分(Incremental Graph Partitioning)

单位更新(unit update)

插入边,可能带一个新的点。

删除边,包括删除边后度变为0的点。

批量更新(batch update)

批量更新 是一系列 单位更新

增量图划分问题

输入:$G$ 、 $k$ 、 $\epsilon$ 、更新前的划分 $C^k(G)$ 、批量更新 ${\Delta}G$

输出:划分的更新 ${\Delta}O$ ,满足 $C^k(G)+{\Delta}O=C^k(G+{\Delta}G)$ ,并且:

  1. 新的划分是 负载均衡 的;
  2. 割的尺寸 是最小的;
  3. 划分的更新 ${\Delta}O$ 是最小的。

有界的(bounded)

如果有算法能求得满足要求的 ${\Delta}O$ ,并且时间复杂度是关于 ${\lvert}{\Delta}G{\rvert}+{\lvert}{\Delta}O{\rvert}$ 的多项式,则称算法是有界的。

证明:不存在有界的算法

输入:$G$ 、 $k$ 、 $\epsilon$ 、$\lambda$、$\eta$、更新前的划分 $C^k(G)$ 、批量更新 ${\Delta}G$

输出:划分的更新 ${\Delta}O$ ,满足 $C^k(G)+{\Delta}O=C^k(G+{\Delta}G)$ ,并且:

  1. 新的划分是 负载均衡 的;
  2. $C^k(G+{\Delta}G).ct\leq\eta$ ;
  3. ${\lvert}{\Delta}O{\rvert}\leq\lambda$ 。

结论

  1. 如果 ${\lvert}{\Delta}G{\rvert}$ 是常量,$\epsilon$ 或 $\lambda$ 是无穷大,则是 NP-hard问题
  2. 如果 $\eta$ 是无穷大,则是 P类问题
  3. 不存在有界的算法。

证明1

Reduce 图划分问题 to $\lambda$ 是无穷大的增量图划分问题

如果不考虑 ${\lvert}{\Delta}O{\rvert}$ 的限制,那么 “图划分问题” 可以看作 $G$ 为空图、单位更新为 插入边 的 “增量图划分问题”。

因为 “图划分问题” 是 NP-hard问题 ,所以 “ $\lambda$ 是无穷大的增量图划分问题” 也是 NP-hard问题

Reduce 分团问题 to $\epsilon$ 是无穷大的增量图划分问题

如果不考虑 $\epsilon$ 的限制,那么可以先对 ${\lvert}{\Delta}G{\rvert}$ 求解 “K-分团问题” ,然后把这些 的所有节点/边都放进同一个 部分 ,从而解决 “增量图划分问题”。

因为 “分团问题” 是 NP-hard问题 ,所以 “ $\epsilon$ 是无穷大的增量图划分问题” 也是 NP-hard问题

证明2

如果不过考虑 $\eta$ 的限制,那么可以不断把节点/边从最大的 部分 移动到最小的 部分 ,直到 负载均衡 。这是可以在多项式时间完成的。

证明3

解决思路

提出一个方法,对现有的划分算法 $A$ 进行修改,推算出一个新算法 $A_{\Delta}$ 。设有一个图 $G$ ,更新 ${\Delta}G$ ,划分的结果 $A(G+{\Delta}G)$ ,则 $A_{\Delta}$ 可以计算出近似满足要求的 ${\Delta}O$ ,$C(G)+{\Delta}O{\approx}C(G+{\Delta}G)$ 。也就是说,$A_{\Delta}$ 在效率和划分质量中间找一个平衡。

划分质量

$A_{\Delta}$ 保证与 $A$ 在划分质量上有相同的边界。

效率

启发式有界(heuristically bounded):

  1. 时间复杂度只依赖于 ${\lvert}{\Delta}G{\rvert}+{\lvert}{\Delta}O{\rvert}$ ;
  2. ${\lvert}{\Delta}O{\rvert}$ 是关于 ${\lvert}{\Delta}G{\rvert}$ 的多项式。

迭代划分法

迭代划分法通常会建立辅助结构 $D_A$ ,$D_A$ 由关于边集、点集、部分的状态变量组成。把划分过程描述为对 $D_A$ 的不断更新。

$D^t_A$ 表示 t 轮迭代得到的 $D_A$ 。

第 t 轮迭代的 更新区域(update region)$H_t$ 由 $D^t_A$ 中的某些状态变量组成,$H_t=h(D^t_A)$ ,$h$ 是 $A$ 的 作用范围函数(scope function)

第 t+1 轮的 $D_A$ 是对第 t 轮的 $D_A$ 施加一个更新,$D^{t+1}_A=D^t_A+f(H_t)$ ,$f$ 称为 更新函数(update function)

算法一直迭代到收敛,$D^{t_0+1}_A=D^{t_0}_A$,此时,$D^{t_0}_A$ 就是划分的结果。

增量方法

再均衡(rebalancing)

输入 ${\Delta}G$ 之后如果发生了过载,则需要从过载的 $V_i$ 中删掉一些点 $U_i$ ,然后记 $U={\cup}_iU_i$ ,把 $U$ 和 ${\Delta}G$ 作为更新,进行 再迭代

再迭代(resuming iteration)

给定 ${\Delta}G$ 和最终状态 $D^T_A$ 。首先找 ${\Delta}G$ 覆盖的 更新区域,然后把它施加给 $D^T_A$ ,得到新的状态 $D^{T+1}_A$ 。

$H_T=h’(D^T_A)$ , $D^{T+1}_A=D^T_A+f(H_T)$

接着,找 $h$ 覆盖的 更新区域,然后把它施加给 $D^{T+1}_A$ ,得到新的状态 $D^{T+2}_A$ 。

$H_{T+1}=h(D^{T+1}A)$ , $D^{T+2}_A=D^{T+1}_A+f(H{T+1})$

重复直到收敛。

分析

如果:

  1. $f、h、h’$ 是在多项式时间内 可增量计算的可增量计算的 是指 $f(d+{\Delta}d)$ 可由 $f(d)$ 和 ${\Delta}d$ 计算,而不用访问整个 $d+{\Delta}d$ 。例如,一些聚合函数,sum、avg 等。
  2. 计算 $U_i$ 的复杂度是关于 ${\lvert}U_i{\rvert}$ 的多项式。

则:

  1. ${\lvert}{\Delta}O{\rvert}$ 是关于 ${\lvert}{\Delta}G{\rvert}$ 和 $\Sigma_i{\lvert}U_i{\rvert}$ 的多项式。
  2. $\Sigma_i{\lvert}U_i{\rvert}$ 是关于 ${\lvert}{\Delta}G{\rvert}$ 的多项式。
  3. 显然,时间复杂度只依赖于 ${\lvert}{\Delta}G{\rvert}+{\lvert}{\Delta}O{\rvert}$ 。

因此,增量方法可以保证 启发式有界

增量点割

邻居扩展(neighbor expansion, NE)

$E_i$的边界点(boundary vertice)是指 $V[E_i]$ 中有未分配的邻接边的那些点。

  1. 从 $E_i$的边界点 中选出有最少未分配的邻接边的点(如果 $E_i=\emptyset$ 则随机选择)记为 $v$ ;
  2. 把 $v$ 的未分配的邻接边都分配给 $E_i$ ;(one-hop)
  3. 如果 $e_{u,v}$ 在 2 中被分配给了 $E_i$ ,$w{\in}V[E_i]$ ,则把 $(u, w)$ 分配给 $E_i$ 。(two-hop)

如此迭代,直到 $E_i$ 违反均衡限制。然后开始创建 $E_{i+1}$ 。

分布式邻居扩展(distributed neighbor expansion, DNE)

假设有 $k$ 台联网的处理器 $P_1,…,P_k$ ,初始时图 $G$ 随机地分布在这些机器上。 DNE 计算 k 路点割

每台机器独立地进行 扩展分配 ,采用 局部最优 选取 Top-K 个 $v$ ,但迭代是同步的。

当不同的机器想把同一条边分配给不同的部分,执行 CAS(compare-and-swap)

增量DNE(IncDNE)

更新函数

输入:$v、u、w$、未分配的邻接边、候选部分 IDs

  1. 把 ID 分配给边;
  2. 判断是否违反均衡限制;
  3. 更新每个点的未分配边数;
  4. 选取下一次迭代的 $v$。
作用范围函数

输入:$v$

  1. 选取 $u、w$ ;
  2. 选取未分配的 one-hop 、 two-hop 的邻接边;
  3. 得到 $v$ 的邻接边所属的部分 IDs;
增量方法

$part(e)$ 表示边 $e$ 所属的部分;

$sc(v)$ 表示选取 $v$ 所用的分数;

$S(v)$ 表示点 $v$ 的邻接边所属的部分 IDs;

$W(i)$ 表示 $E_i$ 的最终尺寸。

输入:$G$ 在 $P_i$ 上的划分 $(E_1,…,E_j,…E_k)$ 、${\Delta}G$ 、$\epsilon$ 、

增加一台机器充当协调者,记 $P_c$ 。

  1. $P_c$ 从所有机器上收集信息,计算出过载的 $E_j$ ;
  2. 对每个 $E_j$ 计算出一个 $(r_1,…r_k)$ ,$r_i$ 表示从 $P_i$ 上的 $E_j$ 中删除多少条边后可以达到均衡;
  3. 把 $W(j)=W(j)-{\Sigma}r_i$ 发送给所有机器;
  4. 把 $<r_i,j>$ 发送给 $P_i$ ;
  5. 如果 $P_i$ 上有 $v、u$ ,则把 ${\Delta}G$ 中关于 $(v,u)$ 的部分 ${\Delta}G_i$ 发送给 $P_i$ ;
  6. 调用 $P_i$ 的处理程序。

$P_i$ 的处理程序:

  1. 更新本地的 $W(j)$ ;
  2. 把 ${\Delta}G_i$ 施加到本地的图;
  3. 随机选择部分 ID 为 $j$ 的 $r_i$ 条边,放入集合 $E^{\Delta}$ ;
  4. 把 $E^{\Delta}$ 中的边打上标记 $\uparrow$ ;
  5. 比如 ${\Delta}G_i$ 要对 $e$ 进行更新,$e$ 原先分配的部分 ID 是 x,$FilterE(V[{\Delta}G_i])$ 表示 $e$ 的两个端点的所有邻接边中部分 ID 为 x 的那些边;这些边也打上标记 $\uparrow$ ;
  6. 把 $V[{\Delta}G_i]$ 和 $V[E^{\Delta}]$ 中的点放入集合 $L^{\Delta}$ ;
  7. 对 $L^{\Delta}$ 中的每个点计算 $sc(v)、S(v)$ ;
  8. 把 $L^{\Delta}$ 中的点作为边界点,执行 DNE 的作用范围函数和更新函数。

证明

再均衡 和计算 更新区域 的复杂度是 ${\lvert}{\Delta}G{\rvert}$ 的多项式,因为:

  1. IncDNE 随机地从过载的部分中选择需要重新分配的边,这些边的数量是 ${\lvert}{\Delta}G{\rvert}$ 的多项式;
  2. $FliterE(\cdot)$ 只检查 ${\lvert}{\Delta}G{\rvert}$ 涉及的点。

IncDNE 和 DNE 的 割的尺寸 有相同的上界,因为:

$E^t_r$ 表示 t 轮结束后未分配的边; $S^t_i$ 表示 t 轮结束后 $E_i$ 覆盖的点。 记 $\phi_t={\lvert}E^t_r{\rvert}+{\sum}i{\lvert}S^t_i{\rvert}$ 。 初始时, $S^0_i={\empty}$ ;$E^0_r$ 包含图的所有边。即 $\phi_0={\lvert}E{\rvert}$ 。 T 轮时,所有边都已分配,即 $\phi_T={\sum}_i{\lvert}S^T_i{\rvert}$ 。 $c_t$ 表示 t 轮选择的 边界点 的数量。 除了随机选择的 割点 ,每分配一条边,会使 割点 至多重复计数一次,因此有 $\phi_t-\phi{t-1}{\leq}0{\leq}c_t$ 。 展开、求和,有 $\phi_T{\leq}\phi_0+{\sum}^T_{1}c_t$ 。 每个点至多有一次机会被随机选为 边界点 ,因此有 ${\sum}^T_{1}c_t{\leq}{\lvert}V{\rvert}+k$ 。 对更新之后的图来说,有 ${\sum}_i{\lvert}S^T_i{\rvert}{\leq}{\lvert}E[G+{\Delta}G]{\rvert}+{\lvert}V[G+{\Delta}G]{\rvert}+k$ 。 $C^k_v(G).ct={\sum}_i{\lvert}S^T_i{\rvert}-{\lvert}V[G+{\Delta}G]{\rvert}{\leq}{\lvert}E[G+{\Delta}G]{\rvert}+k$ 。

实验

效率

固定 $k$ ,把 ${\lvert}{\Delta}G{\rvert}$ 从 ${\lvert}G{\rvert}$ 的 10% 增大到 50%,观察算法消耗时间的变化、迁移消耗。迁移消耗用 $重新分配的节点数\over{\lvert}V[G]{\cap}V[G+{\Delta}G]{\rvert}$ 或 $重新分配的边数\over{\lvert}E[G]{\cap}E[G+{\Delta}G]{\rvert}$ 衡量。

  1. 增量方法总是比原始方法好;
  2. 增量方法对 ${\lvert}{\Delta}G{\rvert}$ 敏感;
  3. 当 ${\lvert}{\Delta}G{\rvert}\leq30\%{\lvert}G{\rvert}$ ,IncKGGGP 和 IncDNE 比其它方法好;
  4. 增量方法在 倾斜图 上表现也很好;
  5. 增量方法的迁移消耗更少。

固定 ${\lvert}{\Delta}G{\rvert}=10\%{\lvert}G{\rvert}$ ,把 $k$ 从 8 增大到 128,观察算法消耗时间的变化、迁移消耗。

  1. 串行方法的消耗时间会随着 $k$ 增大而增大;并行方法的消耗时间可能会随着 $k$ 增大而减小;
  2. 增量方法总是比原始方法好;

固定 $k$ ,把 ${\lvert}{\Delta}G{\rvert}$ 从 ${\lvert}G{\rvert}$ 的 10% 增大到 50%,观察不同更新对算法消耗时间的影响。

  1. 只有边插入时,增量方法消耗的时间会随着 ${\lvert}{\Delta}G{\rvert}$ 的增大而增大;
  2. 只有边删除时,有些增量方法消耗的时间会随着 ${\lvert}{\Delta}G{\rvert}$ 的增大而增大,而另一些会减小;
  3. 增量方法总是比原始方法好;

伸缩性

固定 $k=128$ ,${\lvert}{\Delta}G{\rvert}=10\%{\lvert}G{\rvert}$ ,把 $G$ 从 14亿 增大到 58亿,观察算法消耗时间。

  1. 增量方法的伸缩性良好;
  2. IncKGGGP 和 IncDNE 比其它的增量方法效率高;
  3. 当 $G$ 增加 8.5 倍后,增量方法就比原始方法好了;

划分质量

算法保证 $\epsilon均衡$ ,所以只比较 归一化的割的尺寸 ,$C^k_e(G).ct\over{\lvert}E{\rvert}$ 或 $C^k_v(G).ct\over{\lvert}V{\rvert}$ 。

固定 $k$ ,把 ${\lvert}{\Delta}G{\rvert}$ 从 ${\lvert}G{\rvert}$ 的 10% 增大到 50%,观察割的尺寸的变化。

  1. 增量方法的割的尺寸与原始方法差不多甚至更小;

固定 ${\lvert}{\Delta}G{\rvert}=10\%{\lvert}G{\rvert}$ ,把 $k$ 从 8 增大到 128,观察割的尺寸的变化。

  1. 所有方法的割的尺寸都随着 $k$ 的增大而增大;
  2. 增量方法的割的尺寸与原始方法差不多甚至更小;