Paper Name
Web: http://phoenixdai.cn
Citing info.
Solve probs, Merits
Main work
Conclusion
Preliminaries
Super Graph
超图是什么？
简单的来说，对于我们熟悉的图而言，它的一个边（edge）只能和两个点连接；而对于超图来讲，人们定义它的边（这里叫超边，hyperedge, nets）可以和任意个数的顶点连接。
上图看的很清楚，所谓的超图就是每个边连接的顶点数不再是两个，而是任意一个。而均匀超图的概念就是每一个边所连接的点的个数是相同的，即：
- 2-均匀超图 = 图
在数学层面上，超图的定义为\(H = (X, E)\)，其中\(X\)是点（vertices）的集合，\(E\)是边的集合，这里的\(E\)就变成了顶点集合\(X\)的子集，因为每一个边都由若干个点的集合来表示。每一条超边中的点我们称之为针（pin）
加权无向超图：\(H=(V,E,c,\omega)\)，其中\(c\)是顶点权重，\(\omega\)是超边的权重
标签传播算法
标签传播算法简称LPA，是一种常用的半监督学习算法，用于向未标记（unlabel）的样本分配标签。LPA的核心思想非常简单：相似的数据应该拥有同样的标签。标签传播算法通过将所有样本依据相似性构建一个有权重的图，然后各个样本在其相邻的样本之间进行标签传播。
算法图如下所示：
- 红色的数字代表对应节点的权重
- 黑色的数字代表边上的权重。
最终的输出图如下所示：
LPA原理：
对于网络中的每一个节点，在初始阶段，LPA对每个节点初始化一个唯一的标签，在每次的迭代过程中，每个节点根据与其相连的节点所属的标签改变自己的标签，更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签，这便是标签传播的含义。
LPA包括两大步骤：1. 构造相似矩阵；2. 标签传播
构造相似矩阵：
因为LPA依赖图，所以我们第一步要构建一个Graph，图的节点就是我们的数据点，包含了Label和Unlabel的数据；边代表两个节点之间的相似度，相似度的计算公式如下所示，\(\alpha\)是超参： \[ w_{ij}=exp(-\frac{||x_i-x_j||^2}{\alpha^2}) \] 标签传播：
在一开始，每一个节点都有自己的标签，即每一个节点都属于不同的社区，当社区的标签在节点间传播的时候，紧密相连的节点迅速取得一致的标签
- 对于c节点，由于周围节点都属于不同的社区，所以随机选择a社区
- 对于d节点，相邻属于a社区的最多，所以将标签改成a
- 同理对于b节点，相邻的节点中都是属于a社区的，所以标签改变成a
在标签的更新中分为：同步更新；异步更新
同步更新是指对于一个节点\(x\)，在\(t\)时刻的更新，根据的是邻居节点在\(t-1\)时刻的标签。 \[ C_x(t)=f(C_{x_1}(t-1),...,C_{x_k}(t-1)) \] 但是这种问题可能会导致标签震荡如下图：
在第一步的更新中，若左侧节点的标签更改为 a，右侧节点的标签更改为 b，在第二步中，左侧的节点又会更改为 b，右侧的节点又会更改为 a，如此往复，两边的标签会在社区标签 a 和 b 间不停地震荡。
对于异步更新方式： \[ C_x(t)=f(C_{x_{i1}}(t),...,C_{x_{im}}(t),C_{x_{i(m+1)}}(t-1),...,C_{x_{ik}}(t-1)) \] 其中，邻居节点\(x_{i1},...,x_{im}\)的社区标签在第t代已经更新过，则使用其最新的社区标签。而邻居节点\(x_{i(m+1),...,x_{ik}}\)在第\(t\)代时还没有更新，则对于这些邻居节点还是用其在第\(t-1\)代时的社区标签。
FM Algorithm
FM算法是一种改进网络分区的线性时间启发式算法，旨在减少不同分区之间的连接数。
FM主要用在超图的双分区问题。
For Example
我们对下面的电路图进行超图建模：
- (a)图中的每一个导线都连接多个门电路，这就是超图的超边
- 例如a,e,c由一根导线连接
- (b)图即超图的直观表现
步骤如下：
初始化分区
左图为超图，不同的线代表不同的超边，右图是超边集合
现随机将超图进行双分区，节点：a, c, d, g 在左边；节点：d, e, f, h在右边
计算gain值和初始化
- \(FS(i)\)：每当有超边包含节点\(i\)，并且有且仅有\(i\)在\(i\)所属的分区：\(FS(i)=FS(i)+1\)，初始值为0
- \(TE(i)\)：每当有超边包含节点\(i\)，且超边中所有的节点都在\(i\)所属分区：\(TE(i)=TE(i)+1\)，初始值为0
- \(gain(i)\)：\(FS(i)+TE(i)\)
对于元件c，c包含在超边\(n1=\{a,c,e\}，n3=\{c,f,e\}，n2=\{b,c,d\}\)中，其中在超边n3中，只有元件c在左边的集合中，其他的元件都在右边的集合中，因此\(FS(c)+1\)。
并没有超边中所有的元组都在左边，因此\(TE(c)=0\)。
第一次移动
由上面第二步计算出所有元件的gain值，其中元件g和元件e的值都是2是最大的，而且对于g和e都是没有移动约束的。
移动约束：尽量使得两边的元件数量维持一致，不能有太大的偏差，左边的数量和右边的数量要尽量维持相等
根据字母顺序，将e从右边移动到左边，重新计算gain值。
第二次移动
虽然经过了第一次的移动\(gain(f)\)的值是最大的，但是f有区域的移动约束（要是移动了f，便导致了左边的元件数量远远大于右边的元件数量，所以f不能移动），选择d元件进行移动
注意：已经移动过的节点不需要再重新计算gain，避免产生算法不收敛的情况。
一直移动到所有的点都不需要重新计算gain。
Graph Coarsening
图的粗化（graph coarsening）是一种图压缩的算法。
计算出的聚类被压缩以获得一个更粗的图。 收缩聚类的工作方式如下：聚类的每个块收缩为单个节点。
- 节点的权重设置为原来块中所有节点权重的和
- 如果聚类中的两个对应块在G中相邻，则收缩图中的两个节点U和V之间存在边，即块U和块V至少有一条边相连，边的权重设为在聚类的块A和块B之间运行的边的权重之和
复杂网络的平衡图分割
网址：https://ieeexplore.ieee.org/document/7859409
Meyerhenke, Henning, Peter Sanders, and Christian Schulz. "Parallel graph partitioning for complex networks." IEEE Transactions on Parallel and Distributed Systems 28.9 (2017): 2625-2638.
带有尺寸约束的标签传播算法
网址：https://arxiv.org/abs/1402.3281
Meyerhenke, Henning, Peter Sanders, and Christian Schulz. "Partitioning complex networks via size-constrained clustering." International Symposium on Experimental Algorithms. Springer, Cham, 2014.
算法大体流程：先利用标签传播算法进行聚类(有修改)，然后利用图的粗化将图压缩。
本论文意图将图分割成大小相近的多个块，所以定义了一个约束条件，即每一个块不能超过的权重大小\(L_{max}\)。 \[ L_{max}=(1+\epsilon)(\frac{C(v)}{k}) \] 其中\(C(v)\)是图中所有节点权重的和，\(\epsilon\)是一个范围参数
我们对于每一个节点都设置一个属于他们自己的ID，然后随机遍历每一个节点，将这个节点移动到与之最为相连(边的权重最大)的块中。但是我们要对其尺寸进行约束，每一个block的上界规定为上文的\(max(max_vc(v),W)\)。我们定义如果节点\(v\)归入到\(V_l\)块中，这个块的权重并不会超过上限，那么这个块认为是合格的；反之，则认为其不合格。所以在遍历每一个节点，这个节点要被归入到合格的块中关联最紧密的那个。这样在收缩聚类之后，每一个块都符合约束。上文中的\(W=\frac{L_{max}}{f}\)，\(f\)是调优参数。
回忆传统的标签传播算法，LPA算法是随机遍历每一个节点，在这里我们规定：首先遍历度小的节点
聚类+粗化的过程将被递归执行下去，直到图已经变得足够小（每一个粗节点都被划分到了同一个类中）
Parallelization
并行化的标签传播（聚类）：
首先我们将图分成不同的子图放入到每一个PE（处理单元 process element）中，每一个PE获得的子图是节点ID在\([a,b]\)中的节点，以及这些节点相关的边，还有一些边的端点（不在区间范围里）（我们称作为ghost节点）。这就意味着，每一个PE可能有将该子图连接到其他PE中的子图中的边。
每一个PE并不使用输入图的节点ID（\([a,b]\)），而是将其映射到\([0,n_p-1]\)，其中\(n_p\)是子图中的节点数量（这里是包括ghost的）。
-> 区间内节点的映射规律为：\(i-a\)
-> ghost节点的映射到剩下的\([b-a, n_p-(b-a+1)]\)，先后顺序根据遍历顺序确定。
我们将区间内节点，下文称为本地节点存储到一个数组中，其本地ID和全局ID仅仅相差\(a\)；将ghost节点通过哈希表存储全局ID到本地ID的映射，并将其存储到另一个数组中。
我们在每一个PE中都执行PLA，这里注意，由于每一个PE中的节点的ID都被映射到了\([0,n_p-1]\)中，所以节点的集群ID也落在这个区间中。
平衡、尺寸约束：
这里文章中使用了两种不同的办法来保持平衡，一个用在粗化中，另一个用在去粗化中。在粗化的过程中，块比较多，所以约束比较软（\(\frac{L_{max}}{f}\)）；在去粗化中，块比较少，约束比较严（\(L_{max}\)）。
-> 在粗化过程中，PE只维护和更新其本地节点和ghost节点的块的局部节点权重。 由于标签传播算法的初始化方式，每个PE一开始就知道本地节点块和鬼节点块的准确权重。 然后标签传播使用本地信息来绑定块权重。 一旦节点改变其块，本地块权重就会更新。
-> 在去粗化中，每一个PE先本地计算自己块的精确权重，然后将本地块的权重聚合并广播到所有的PE中。现在每个PE都知道所有k个区块的全局区块权重。利用LPA更新本地权重。
并行收缩与去粗化：
-> 并行收缩：每一个PE上聚类的ID可以任意分布在\([0,n-1]\)上（n是当前层次下所有的节点数量），因此通过寻找不同聚类id的数量（粗节点的数量）来启动收缩算法。因此，每个PE \(p\) 计算ID在区间\(I_p=p[\frac{n}{P}]+1...(p+1)[\frac{n}{P}]\)的不同聚类数量（\(P\)是使用PE的总数）对应前文的\([a,b]\)。这也就意味着每个PE要迭代本地的节点，收集非本地的集群ID \(a\)（\(a \notin I_p\)），然后将非本地集群的ID发送给对应的PE。
设\(n'\)是不同聚类ID数，这也是执行收缩后的粗节点数。下一步就是要计算从\(C:[0,n-1] \to [0,n'-1]\)的映射。当映射结束后，新的PE \(p\) 就会负责\(p[\frac{n'}{P}]+1...(p+1)[\frac{n'}{P}]\)的子图。
-> 去粗化：并行去粗化算法实现简单。 每个PE知道子图中所有节点的粗节点（通过映射\(C\)）。 因此，PE从保存相应粗节点的PE请求代表精细节点的粗节点的块ID。
整个并行系统的工作方式如下：
我们使用并行尺寸约束标记传播算法的迭代来计算图簇并并行收缩它们。 我们递归地这样做，直到剩余的图剩下不到20,000个节点。 然后在每个PE上收集分布式粗图，即每个PE拥有的完整最粗图的副本。 将该图作为粗粒度分布式进化算法Kaffpae的输入，得到其高质量的K-划分（我们已经修改了Kaffpae，以使用组合操作，这些操作也使用了上面基于聚类的粗化方案）。 然后将进化算法的最优解广播给所有PEs，这些PEs将解转移到分布粗图的局部。 然后，我们使用并行去粗化算法将当前级的解传递到下一个更细的级，并在原划分问题的大小约束下（设置\(W=L_{max}\))应用并行标记传播算法的r次迭代来改进当前级的解。 我们在层次结构的每一个层次上都这样做，并最终获得输入网络的良好分区。
深度多层图分割
网址：https://arxiv.org/abs/2105.02022
Gottesbüren, Lars, et al. "Deep multilevel graph partitioning." arXiv preprint arXiv:2105.02022 (2021).
Notation
本文章的平衡约束设置为：\(\forall i \in \{1..k\}:c(V_i)\leq L_{max,k}=max\{(1+\epsilon)\frac{c(V)}{k},\frac{c(V)}{k}+max_vc(v)\}\)
- 这里有两个约束，并不在是像其他文章只有第一个约束，这里的最大阈值取了两个值的最大值
- 原因是：找到\((1+\epsilon)\frac{c(V)}{k}\)是一个NP完全问题，而\(L_{max,k}\)则不是
文章的目标：
将图划分成尽可能均匀的子图
切割边的权重是最小的
这里可能和BGFL的思路有一些不同，因为我们进行分组是要尽可能组与组之间的差异足够大，组内的差异足够小，所以应该是让分割边的权重最大。🤔
多层级图划分：
这是许多高质量图划分器采用的范式：1. 粗化阶段；2. 初始划分；3. 细化
-> 粗化阶段：算法建立一个较小的图，根据聚类方法，将同一类的图压缩成一个节点
-> 初始划分：当粗图的节点数低于某一个阈值或粗化算法收敛，计算最粗图的一个划分
-> 细化：撤销粗化执行的操作，在更精细的图上局部改进
使用多层级范式将图划分为k个block，一般有两种办法：1. 直接k-way划分；2. 递归二划分
-> 直接k-way：将图粗化到只剩下\(k·C\)个节点后，计算k-way分区
-> 递归二划分：首先计算一个二划分\(\{V_1, V_2\}\)，然后将\(V_1\)分成\(\frac{k}{2}\)块，同理对待\(V_2\)，之后变成问题：在两个子图中分\(\frac{k}{2}\)块，继续重复操作。
==许多使用直接k-way在初始划分的时候也会选择递归二划分。==
尺寸约束的标签传播算法：
保持平衡约束：
为了满足平衡约束：\((1+\epsilon)\frac{c(V)}{k}\)，这个问题是一个NP完全问题，因此他可以简化为在相同的并行机器上的调度作业问题，因此，人们采用了一些技术：通过惩罚大权重的节点的收缩 / 强制执行节点权重的严格上限 来防止生成重节点。
但是如果我们将\(L_{k}\)更换成\(L_{max,k}\)，则可以在多项式时间找到平衡分区
如果在递归双分区的时候，对每个双分区输入\(\epsilon\)，那么在最后的k-way分区的时候就会违反约束。
Therefore，Kahypar提出了一种办法：通过递归二分法获得k-way分区时单独调整每个二分法的不平衡比\(\epsilon\)来使得最终的k分区平衡。
设\(G[V']\)是当前二分区的一个子图，他应该递归地规划为\(k'<k\)个块。则\(\epsilon'\)为二分区的不平衡比。 \[ \epsilon'=((1+\epsilon)\frac{c(V)}{k}·\frac{k'}{c(V')})^{\frac{1}{log_2(k')}-1} \]
如果每一个二分区都是\(\epsilon’-balanced\)，那么最后的k-way分区就是\(\epsilon-balanced\)。
Generic Deep MGP
大体流程：
输入一个图，然后将其进行粗化，一直到只剩下2C个分区（这里C是输入参数），这就是最粗的图了。
然后，我们将这个最粗的图通过二分区，分成两个块。
在去粗化的过程中（将归并的节点还原成多个节点），要保证\(n'\)个节点要分成\(min\{k,ceil_2(|V_i|/C)\}\)个块，这样每次进行二分区都能在大约2C个点上工作。
直到分出k组。
详细流程：
首先，我们输入图\(G_1=(V_1,E_1)\)，然后建立一系列越来越粗的图\(G_1, G_2,..,G_l\)。图粗化的办法是对每一个\(G_i\)的图进行聚类，然后将类别压缩成一个点来获得\(G_{i+1}\)。这个过程直到步骤收敛或者图节点拥有不超过\(2C\)个节点。对应算法1:2-3
此时图中仅有2C个节点，且此时2C个节点并没有分块。
之后，我们开始以下操作：
- 使用递归二划分来将当前的图划分成\(k_l\)个块；
- 重新平衡分区并利用k-way局部改进；
- 将分区映射到前一个图\(G_{l-1}\)。
在这些操作期间，我们保证以下量不变
- 一个粗图\(G_i\)划分成\(k_i=ceil_2(|V_i|/C)\)个块
- \(G_i\)的\(k_i\)-way分区应该满足平衡约束
解释一下\(ceil_2\)，\(ceil_2(x)\)的意思是，将x向上取到2的幂次。
eg. \(ceil_2(10) \to 16\)
所以1条件，就是每一个图分成的块的数量必须是2的幂，这样才能保证二划分。3C个点就要分成4块。
理想的情况下，算法会产生一个图层次结构，其中节点数在两个层次之间减半，最粗的图有2C个节点。在这种情况下，对最粗的图G进行一次二划分就足以满足1条件。为了在去粗化的时候（将当前图中的节点数增加一倍）后恢复不变量，必须将当前分区的每一个块进行一次二分区。
eg.
现在最大的图有2C个点，此时需要分区\(ceil_2(2C/C)=2\)，所以二分区将其分成两个块
之后映射到前一个图，此时节点变成了4C个，需要分区\(cel_2(4C/C)=4\)，在第一步的时候已经分出了两个块，所以再在两个块中分别进行一次二分区就满足了。
一般的条件下，粗化会将图缩小大于1/2，因此使用递归二划分来保持1条件。也就是说，每当图\(G_i\)的划分不满足1条件，就要递归的对每一个块进行二划分，直到拥有\(k_i\)个块。对应算法1:7-10
eg.
现在最大的图有2C个点，此时需要分区\(ceil_2(2C/C)=2\)，所以二分区将其分成两个块
之后映射到前一个图，此时大概率会变成大于4C个节点，比如说6C个，所以此时分组要分成\(cel_2(6C/C)=8\)，此时就需要递归进行二分区，在已经存在的两块中进行二分区，变成4个块，再在4个块中进行二分区，变成8个块。
因为现实中的节点数量不一定是C的整数倍，所以进行单一二分区是可能没有办法获得\(k'\)个分区，所以不满足约束的话会使用k-way局部改进算法，对应算法1:11
Parallelization
使用方法：并行粗化、局部改进、平衡算法
在很粗的层次上，保持\(p\)个PE在至少有\(pC\)个节点的图上进行并行任务，这是通过在越来越多的粗图副本上运行初始化分区来得到的。
我们使用Notation中的步骤来使得最后的粗图\(G_C\)还有\(pC\)个节点。(下图中的前三个步骤）
我们复制\(G_C\)得到两个副本\(G_C^r\)和\(G_C^l\)，同时将PE进行分割成两组，每一组有\(p'=\frac{p}{2}\)个PE。如果\(p' > 1\)，我们用第一组的PE继续粗化\(G_C^r\)，用第二组的PE粗化\(G_C^l\)，直到每个图中剩下\(p'C\)个节点。（下图三到四的分叉）
我们以这种方式进行递归，直到最后获得\(p\)个有\(2C\)节点的图。（下图四到五的二变四，又进行了一次复制，一次粗化）
然后使用单个PE对这些图中的每一个进行二分区，选择两者中更好的二分区划分，如果就一个可行，那么就用那一个。（下图从五到六）
比如下图从2C的节点进行复制，因为\(p'=2/2=1\)，所以不用再进行粗化，两个PE上各自有一个副本，之后进行二分类，其实就是在两个相同的图上进行二分区。
之后我们继续在4中的二分区的每个块进行二分区，并应用平衡和局部改进算法。（下图从六到七）
递归进行。
对k的处理：
在上文中，我们默认k是2的倍数。对于一般情况，我们要给B个块分k组，此时\(f_V=k\)，我们对B进行二分区\(B_0=\lceil\frac{B}{2}\rceil\)，\(\lfloor\frac{B}{2}\rfloor\)。同时我们将B的权重分割成了\(f_{B_0}\)和\(f_{B_1}\)……我们要计算\(k'=floor_2(k)\)的\(k'-way\)划分。这样就会有\(k-k'\)个重块\(f=2\)，以及有\(2k'-k\)个\(f=1\)的轻块，之后我们只要对重块进行双分区就行了。
eg. k = 7，B = 15
k’=4，所以要进行一个4-分区，用Notation的方法，将15进行4分区，分成了3,4,4,4。
此时有重块3个：4,4,4；轻块1个：3
对重块二分区：2,2,2,2,2,2
最后：2,2,2,2,2,2,3
Merits
它成功地结合了经典的直接k-way划分和递归二划分的优点。 与直接K-way划分相似，深度MGP只对图进行一次粗化和去粗化，并允许使用K-way局部改进算法。 当k较大时，它不会遇到可伸缩性问题，并且比递归二划分具有更好的渐近运行时间