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图数据显示，某些结点可能有特别多的边缘，如果执行点分割会导致大量边缘缺失和边缘负载不均匀；边缘分割可以处理此类问题。
图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所示，将一张图分为三部分，先稀释三层，然后将缩小后包含三个顶点的子图分为三部分，最后将三个结点包含的原始图结构还原成子图。
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技术总结 - 知乎