2013SEA-(Kahip两级图分区调优算法)Think Lo

2021-07-30 本文已影响0人 Caucher

是比较新的一篇图分区算法，针对传统问题。ArxIV也有同名文章，更为详细。
标题：局部地思考，全局地执行：高度平衡的图分区

Abstract

本文提出的仍然是图分区算法中经典的局部提升模式（类似KL思想）。
让每个局部搜索，各自宽松地，可以放松平衡参数，得到一个更合适的分区，然后用一个负环检测算法，把这些不平衡的局部分区组合起来。
整个算法是多级的，并行的，称为KaFFPaE。

1 Introduction

KaHIP是一个图分区的算法家族。
最初的KaFFPa对于小型图来说性能不佳；KaFFPaE利用粗粒度的并行，达成了最佳效果，但是当平衡因子比较苛刻的时候，性能退化还是比较严重。

2 Preliminaries

block：一个分区称为一个block
k：分区个数
边界节点：和其它分区至少有一条边相连。

本文暂假定所有点权重为1，但可以扩展到有权节点图上。

分区权重：分区点的个数
分区过载：分区权重超过了指定阈值

4 Globalized Local Search by Negative Cycle Detection

算法整体分为两个部分，第一部分是在成对的block（有边连接）之间做局部搜索。第二部分是基于第一部分收集到的信息构建模型，确定最终哪些movement（移动/交换节点）会被采纳，以维护整体平衡。

4.1 Basic Idea – Using a Negative Cycle Detection Algorithm

这一节首先用一个简单的例子来讲思路。每一次移动只移动单个节点。每个节点有标记和未标记两种状态，初始时未标记。当一个节点不和之前标记过的节点相邻时，该节点是有资格的。
基于图的一种分区，构建图的模型，如下图，每个block是模型图的一个点，模型图是个有向图。

定义模型图中的有向边：只要原图中有一条桥边跨越两个分区，有向边就存在。也就是说模型图中的有向边永远是成对出现的。
定义模型图中有向边的权重：比如说有向边(A,B)，在A的所有有资格的边界节点中，选择移动到B收益最大的那一个，把这个收益取相反值（负数）作为边的权重，然后这个节点就被标记。

仍然要注意两个问题：

成对的有向边权重通常都不一样，这个很好理解，因为是从两个block里面选的节点；
边的权重赋值不只有一种，改变随机取有向边的顺序，可能模型图的有向边权重就不一样了。

image.png

正如标题所说，构建好这个模型图，我们就要去在其上找负环。注意到，一个负环代表一组节点的移动，这个移动给整个图分区带来正收益。最关键的是，这组节点的移动，完全不改变各分区权重，因为总是一个节点出，一个节点进。

负环检测算法：引入一个节点s，和模型图的所有点连接起来，边权重均为0，通过最短路算法（可以容忍负边的）检测负环。
检测到一个负环，就进行一组移动，直到找不到为止。
进一步，我们还可以定位到那些即使多一个节点，也不会破坏平衡的节点，让s和它们以0权边相连，在模型图里寻找包含s的负权环，再次移动。
再进一步，如果这两种负权环都找完了，可以找一些0权环，然后移动起来。使得模型图的边权再次发生变化，重复该过程。

作者还提到，像FM这种在相邻的block做节点交换的，实际上就是本文思想的特例，只不过FM这个负权环太小了。

4.2 Advanced Model

上面其实是一个简化的模型，真正用于负环探测的，不是一个节点，而是一坨节点（节点集合），边的权重，也是这一坨节点移动带来的收益的相反数。边的赋权是随机顺序的，而且每条边都要赋权。

4.3 Directed Local Search

这一节其实就是讲如何去给模型图的边赋权，只不过这时赋权不是找一个顶点，而是一坨。

对于模型图的有向边（A,B），我们在A分区里面找移动到B收益最大的节点，可能不止一个，我们把它们放到一个优先级队列pq里面去，优先级队列按照收益排序。
每次从优先级队列取出一个节点，执行移动，标记，然后把该节点在A分区有资格的邻居也加入到优先级队列里。
这种移动最多执行 $\tau$ 步， $\tau$ 是集合大小上界的参数。

注意到，由于标记机制，所有节点至多被移动一次。
回想起有资格节点的定义，所有在这一次Directed Local Search中移动的节点的邻居，都失去了资格。也就是说它们不会在之后的Directed Local Search被移动。这是为了收益计算的精确性。一旦它们被移动，之前计算的收益就不对了。

最后所有刚才移动的节点再移回来，只留下计算出来的权重和节点标记即可。

4.3.1 Multiple Directed Local Searches

这个思想也很简单，所有block对的边都赋权之后，也许对于某个block对，还有一些有资格的节点，他们还可以做一次Directed Local Search，甚至不止再做一次，再做 $\miu$ 次也是可能的。我们最后只要取增益最大的做边权重就好了。

4.4 The Model Graph

现在这个模型图的意义更加明朗了。一个负环，实际上就是若干次Directed Local Search的全局组合，使得全局收益增加。但问题在于，这个负环不一定能保证平衡性，因为移动的不是单个节点了，而是一坨，这一坨的大小只有上界，却并不一定都相等。这一节，核心问题就在于如何设计模型图，来保证平衡性。

新的模型图，可以视作老模型图的多层，每一层代表Directed Local Search的一次移动，层数最多为 $\tau$ 。每一层里，都是具体到一次移动的两两收益。但注意高层是依赖低层的。比如在d层里找到一个负环，执行之，那将不是在两个分区之间移动1个点，而是d个点。
但是考虑到初始的分区未必是平衡的，或者至少未必是完美的。所以不能只有分区等权重的移动，分区权重适当的增减，有助于整体的平衡性。为了增加移动的可能，又在新模型图中引入了三类边：
- 前向边：同一块底层指高层，边权重为0，不代表任何移动。
- 后向边：对于d层的有向边(A,B)，如果B能承受 $l$ 个节点而不过载的话，就增加一条d层的A指向 $d-l$ 层B的有向边。这条边所代表的和d层的有向边(A,B)意义是一样的，都代表了d次移动。注意这种不均衡的移动不会削弱图的平衡性。
- 指向s的边：如果在d层的某个block可以承受d个节点而不过载，那这个block对应的节点有一条边指向s。
  
  image.png
  
  注意到，如果初始分区是均匀的，那后向边和指向s的边就都不要加到模型图上去。（编者注：此时前向边似乎也没有用，因为只有前向边单向跨层，是构不成跨层环的）

4.5 Conflicts

相信读者读到这里，和编者有一样的疑惑，就是跨层的环路还有很多移动是说不清楚的，作者也提到了两种矛盾，是上面的构建无法解释的。

4.5.1 Conflict 1: duplicate movement

如下图，在下面的负权回路里，注意两条红色边，它们明明就是一次Directed Local Search的移动，底层是高层的子集，怎么能移动两次？

image.png

4.5.2 Conflict 2: overload caused by 2 ways

如下图，回路里的两条红色边，一个是通过点s增加了B的权重，一个是通过跨层增加了B的权重，在同一个回路里，导致B过载。

image.png

4.5.3 Conflict resolution

作者首先说冲突情况在实验中较少遇见，一旦遇见了，也很容易检测，检测之后，随机删掉这个环的一条边，然后重新找负权环即可。
另外，如果删除了跨层的所有边，那么必然不会产生冲突，但是移动的可能就少了。但是换个角度，也就是如果初始分区是均匀平衡的，就不会有冲突。

4.6 Balancing

刚才介绍的算法可以保证在初始分区均衡时，均衡性不被打破，但是对于初始不均衡的分区，就要在负权环处理完毕之后，补充一个平衡算法。

目标：这个平衡算法可以将刚才的模型图稍作改造，使得每次移动至少减少一个过载节点，同时最小化对edge cut的增长影响。
结构：这里在模型图中引入新节点t，对于第 $l$ 层的block，如果能承受 $l$ 个节点不过载，那让这个节点指向t。对于之前的s节点，只指向过载节点，而不是全部节点。
算法：从s到t找最短路，得到的这条最短路，正好能完成上述目标。
新问题：至少得有一条s-t路径，这个算法才有效，如果图是连通的，那肯定是有的，但是如果某对block之间实在没剩下有资格的节点，那图就有可能不连通，算法就有可能无效。
解决方法：这个时候就想到之前4.1节的结论了，改变给边赋权的顺序，有可能多构造一些边。
具体方案：【暂时略过，文字太长了看不下去】

4.7 Putting Things Together

算法实际上是一轮一轮进行的。
在每一轮中：

计算成对的边权重（directed local search）
构造模型图，找负权环，执行之，直到没有负权环。
找0权环，执行之，打破平衡以获得多样性。
对上述3步进行 $\lambda$ 次迭代，之后如果图是平衡的，就停止，否则用平衡算法对其进行平衡。
平衡算法一般会引入新的负权环，由此可以开启新的一轮。

本文提出的这种细化技术，称为Karlsruhe Balanced Reﬁnement (KaBaR).

5 Experiments

主要专注于效果的实验，有空再补充。