1. 简介

图分割是将一个大图均匀的分成一系列的子图去适应分布式应用.

每个子图存储在一台机器上，子图之间可以并行化执行，

如果当前子图需要其他子图的信息就需要通讯开销，而图分割的质量影响着每台机器存储代价和机器之间通讯代价。

粗略地按照分割的内存开销大小分类，可以分为离线offline和流式streaming两类分割算法 [1]。

• offline是将整个图数据一次性载入内存中然后根据图的结构进行切分；
• streaming是按批次读取图数据，实时的将图的边或者结点分配到指定的子图中。对于大规模图数据来说，单机的内存无法满足分割算法的需求这个时候流式分割显得尤为重要。

按照对图数据的切分方式分类，可以分为点分割（vertext partitioning or edge-cut partitioning）和边分割（edge partitioning or vertex-cut partitioning）。如图1所示，

• 点分割是将图的结点分配到各个子图中，维持结点之间子图的完整性，这个时候可能造成某些结点之间的边被切掉(edge-cut)；
• 边分割是将图的边分配到各个子图中，每组分配的边构成子图，这个时候造成某些结点的冗余（vertex-cut）。

对于服从幂律分布power-law的图数据，某些结点的边可能特别多，如果执行点分割会造成大量边的缺失以及边的负载不均匀；而边分割可以处理这类问题。[2]

图1 点分割（左）和边分割（右）的示例

图分割的两个目标是负载均衡load balancing（减少存储代价）和最小化切边或点minimum cuts（减少通讯代价），同时优化这两个目标是平衡图分割（balanced graph partitioning）问题，这是一个NP难的问题[2]。通常情况下松弛为优化load balancing的同时尽可能保证minimum cuts。

给定一个图 G=(V, E) 包含|E|条边和 |V| 个顶点，将它分割成  k 份，

点分割表示如下：

 

其中 |Vi| 表示每份子图中结点的个数，表示了点load balancing，参数  α 控制平衡率。

边分割表示如下：

 

V(Ei) 表示子图中所有边  Ei 关联的结点集合， RFv  表示结点的重复率replication factor，衡量vertex-cut的数量。

下面我们按照切分方式来介绍系列分割算法。

2. 点分割

2.1 METIS

METIS[3]是一种层次化的分割算法（multi-level partitioning），核心思想对于给定原图结构持续的稀疏化融合结点和边来降低原图的大小，然后达到一定程度对于缩减后的图结构进行分割，最后将分割后的小图还原成原始的图结构保证每份子图的均衡性。

如图2所示，将一个图分割为3份，首先进行3层的稀疏化然后对于缩小后包含3个顶点的子图切分成3份，最后将这三个结点所包含的原始图结构还原成子图。

METIS在稀疏化阶段采用heavy edge matching策略，在分割缩减后子图的时候随机初始化一个节点进行宽度优先遍历breadth-first fearch得到最小切边的子图，最后将子图映射到原始的图结构。由于METIS需要对整个图结构进行遍历和缩放，对于大规模图来说内存消耗大分割效率低。

图2 层次化分割的三切分示意图

2.2 Random Hash

随机哈希的点分割就是将结点通过一个给定的哈希函数映射到不同的分割子图中， f(v)=hash(v)mod(k).

 最简单的hash函数就是给每个结点分配不同的id，然后通过分割分数k进行取模，最后分配到指定的子图中。

这种分割方法可以拓展到边分割上，将每条边进行id话然后取模进行分割。

基于hash的分割方法不需要任何图结构的先验知识虽然高效但是随机化造成划分后子图内结点点的局部性很难得到维持，被切掉的边会非常多。

2.3 LDG

Linear Deterministic Greedy partitioning (LDG)[4]考虑在分割的时候将邻居结点放置在一起，以减少edge-cut。它采用贪心算法将一个结点放置在包含其邻居最多的子图中，同时保证每个子图的结点负载均衡，整个算法流程图如下：

图3 LDG算法流程图

其中 C=|V| 表示结点容量，w(i)  表示当前子图在平衡状态下剩余容量，g(v,Pi)  表示再考虑负载的情况下结点 v 和子图 Pi 中结点邻居个数的交集，该打分函数作为将结点 v 分配到最大分数的子图中。

2.4 Fennel

Fennel分割[5]与LDG相比，其打分函数对子图中结点数量的约束从乘法换成了减法操作，进行了松弛：

图4 Fennel算法流程图

3. 边分割

3.1 NE

NE（neighbor expansion）[2]边分割其实也是考虑邻居的局部性进行切分，对于一个节点 x 如果期望他的所有邻居边都被分配到一个子图中，那么这个结点x作为核心集 C ，对于边界集 S 表示一个节点的部分邻居边被分配到了当前子图中，核心集 C 永远包含在 S 中。其核心思想如下，当  S\C  为空，从  V\ C 中随机选取一个节点，否则选取结点的规则如下：

 

对于边界结点，从中选取一个其邻居在边界外最少的作为候选结点，能够保证分配邻居边的最大化，这样保证了最小化结点的重复率。选取候选节点后将其加入核心集，然后查找他的邻居，将不在候选集的邻居加入候选集；对于每个邻居继续查找他的邻居和候选集的交集，将这些有交集的邻居所关联的边加入当前子图，知道满足负载均衡，算法流程图如下：

图5 NE算法

该方法需要总览全局，提前计算每个结点的邻居集合，对于每次分配边都要动态改变核心集和候选集，以及边集。这对于大图来说内存消耗大。

3.2 DBH

Degree Based Hashing (DBH)[6]分割通过判断结点的度信息来切分结点分配边。对于幂律图来说低度结点的局部性很容易保持，高度结点因为关联太多结点如果将边全部分配在一个子图上不太可能，因此该算法尽最大可能保持低度结点的局部性。整个算法如下所示：

图6 DBH算法

对于一条边 e 的两个节点 v1,v2 ，计算这两个点的度信息也就是他的邻居总数，根据度小的结点计算哈希函数返回分配的子图id，将该条边分配到对应子图。该算法融合了度信息和随机哈希的特征，高效且保持了局部性。

3.3 HDRF

HDRF[7]和DBH类似，也是根据结点的度信息判断其关联的边分配到哪个子图中，只不过DBH是观察结点在全图中的邻居个数，而HDRF是观察结点在每个子图中部分邻居个数来决定分配。DBH希望将边直接分配到度小的结点所关联的子图上，而HDRF是观察所有子图的信息将边分配到其度最大的结点所在子图上，整个算法流程图如下：

图7 HDRF算法

根据图中6-8行可以看出HDRF的打分函数不仅关注结点的度信息还考虑了当前子图的负载均衡。

4. 图分割的新进展

4.1 GAP

GAP（Generalizable Approximate Partitioning）[8]是一个基于图神经网络的点分割算法，框架图如下：

图8 神经网络的框架图

该网络结构利用邻接矩阵、结点特征、度信息作为组合输入图神经网络获得最终的结点特征，通过一个分类器判别属于哪一个分割子图，网络的损失函数考虑了edge-cut，最小化边割。

4.2 聚类

聚类其实和分割有一定的联系，分割的目标是让边或者结点均匀分配，且保证子图的局部性，子图间通讯开销最小化；聚类则是希望将图中相似语义和结构化信息的点聚集在一起，不考虑每个簇的结点数量，这相当于是松弛的点分割。

4.3基于属性驱动的流式边分割算法

考虑到目前的大规模图数据中结点都自带属性，对于这类属性图我们可以利用这些信息辅助分割，能够更好的服务下有节点分类、边预测等任务，同时考虑对大图的可扩展性我们提出了属性驱动的流式边分割，具体的算法将稍后公布。

5. 图分割的实现

对于有需求的同学，可以参考github连接实现的分割算法。目前包含上述涉及的分割方法，对于流式点分割LDG和Fennel由于精力有限没有优化，对于大图可能运行速度缓慢。另外KaHIP也实现了一系列基于层次化分割的算法。

[1] I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12, pages 1222–1230, New York, NY, USA, 2012. ACM.

[2] C. Zhang, F. Wei, Q. Liu, Z. G. Tang, Z. Li, Graph edge partitioning via neighborhood heuristic, in: Proceedings of the 23rd ACM SIGKDD, 2017.

[3] Karypis, G., Kumar, V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359–392 (1998)

[4] I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12, pages 1222–1230, New York, NY, USA, 2012. ACM.

[5] C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In Proceedings of the 7th ACM International Conference on Web Search and Data Mining, pages 333–342. ACM, 2014.

[6] C. Xie, L. Yan, W.-J. Li, and Z. Zhang. Distributed power-law graph computing: Theoretical and empirical analysis. In Advances in Neural Information Processing Systems, pages 1673–1681, 2014.

[7] F. Petroni, L. Querzoni, K. Daudjee, S. Kamali, and G. Iacoboni. Hdrf: stream-based partitioning for power-law graphs. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 243–252. ACM, 2015.

[8] Nazi, A., Hang, W., Goldie, A., Ravi, S. and Mirhoseini, A., 2019. Gap: Generalizable approximate graph partitioning framework.arXiv preprint arXiv:1903.00614.

图分割Graph Partitioning技术总结 - 知乎