Nov 12, 2019

图划分算法概述

图结构的数据存储与计算离不开图划分算法，尤其是数据量上去之后在分布式环境下需要将大规模图数据划分成为多个子图放到不同的节点处理，本文通过离线划分、在线划分与动态划分三个分类对常见的图划分算法进行简单的介绍。

概述

其实根据面向图本身的结构，可以将图划分方法分为边划分与点划分。在分布式系统中边划分节省存储空间，但网络通信压力较大，点划分则恰好相反。

这里通过划分时机将图划分算法分为离线划分、在线划分与动态划分，其中离线划分是指将图数据加载后进行划分，在线划分一般是流处理，在图数据加载进集群的同时进行划分，动态划分是指在系统运行过程中根据负载动态调整数据划分的分布。

离线划分

Metis

Metis 是一个多级划分算法库，其中划分流程由 Coarsening, Initial Partitioning, Uncoarsening 三个阶段组成，属于对边对划分。

划分阶段

对于 Coarsening 阶段，主要完成以下三个步骤：

  • 寻找最大匹配
  • 重叠最大匹配顶点生成新图新（获得顶点子集）
  • 重新计算权重

寻找最大匹配是为了将不同的顶点两两合并，这样就不会产生多个顶点合并的情况，保证 Coarsening 的均匀性。

Metis 提供了两种最大匹配的计算方法：

  • 1 随机
    • 对于顶点 u，如果未匹配则随机选择一个邻接点 v 作为匹配，如果没有未匹配的邻接点则不匹配 u
  • 2 权重优先
    • 对于顶点 u，如果未匹配则选相连边权重最高的顶点作为匹配，如果没有未匹配的邻接点则不匹配 u

最大匹配 Coarsening

由于需要计算最大匹配，所以 Coarsening 阶段成为了算法的主要开销点。

然后是 Initial Partitioning 阶段，这个阶段是对一个缩小了的图进行切分，常见的气氛方法有谱聚类划分、几何划分及组合方法划分。

最后是 Uncoarsening 阶段，该阶段对应于第一个阶段，将缩小的并划分好的图还原回原来的图，由于 Coarsening 阶段每次计算图的最大匹配进行压缩，因此在这个阶段通过合并的顶点子集还原为上一级的图。且上一级的图更大更精细，所以在还原的过程中使用 KL 局部细化算法细微调整划分后子图的权重，使不同子图的权重尽量相等以保证划分的均匀性。

此外，Metis 还有并行实现 ParMetis。

MLP

MLP 与 Metis 一样由 Coarsening, Initial Partitioning, Uncoarsening 三个阶段组成，但其使用标签传播算法代替了 Metis 在 Coarsening 阶段使用的最大匹配计算，在划分结果与 Metis 相当的情况下大大减小了计算开销。由于 MLP 相当于一个改进，这里只对其使用到的标签传播算法进行展开。 标签传播算法设置3个参数：

  • a：剩下 a 个标签时候算法收敛
  • b：算法最多经过 b 次标签传播迭代
  • n：每个标签分区最多包含 n 个顶点

经过两个步骤完成：

  • Step1：为每个顶点随机初始化一个标签
  • Step2：迭代 每个顶点将自己的标签更新为邻接顶点中出现次数最多的标签
  • 如果邻接点标签出现量相同，则：
    • 方法1：随机选择
    • 方法2：选择顶点权值最小的顶点标签

MLP图例

如上图，只要设定好算法参数，经过标签传播迭代之后原本的图相关度高的顶点将拥有相同的标签，然后将相同标签的顶点合并就完成了 Coarsening 阶段，其余阶段同 Metis。

当然，因为是在原图上进行标签传播，所以只要使 a = num(node)，即标签数量等于节点数量或者说划分的子图数量，在标签传播算法完成之后已经生成了一个划分。

JA-BE-JA

JA-BE-JA 的特点是不需要知道全局的图形拓扑信息，其对顶点着色并交换颜色（这有点像标签，但一种标签在迭代过程中是有可能消失的，这里只是交换颜色），使用模拟退火算法获得到最优的划分。

JA-BE-JA

首先 JA-BE-JA 对问题进行了建模，定义系统的能量是具有不同颜色的节点之间的边数，并且节点的能量是具有不同颜色的其邻居的数量。优化的目标是通过交换节点的颜色将系统推向低能量状态。也就是说相同的颜色总会在聚在相邻的节点上，也就是找到相关性较高的节点簇。其中，顶点具有关于其相邻节点的本地信息，以及图中的一小部分随机节点的信息。 算法经过两个步骤：

  • Step1：为每个顶点随机初始化一个颜色
  • Step2：迭代 每个顶点通过与周围顶点交换的方式，尝试将其颜色更改为其邻居中最主要的颜色，使系统的能量变小
  • 交换的选择有：
    • 1 邻接点
    • 2 随机样本（可以使用集群中的主节点维护一个足够大的随机样本）

在线划分

LDG

LDG 是一种启发式的边划分方法，它接收由顶点和其相关边组成的顶点流，通过启发式规则将顶点放置到集群的节点分区上，顶点放置后将不再移动。 这里列举几个其中的顶点分配启发式规则：

  • Balance
    • 1 分配到分区内容最小的分区
    • 2 按照到达时间顺序分配
  • Greedy
    • 3 分配发哦相邻边最大的分区，采用惩罚函数加权，如果分区过大则采用 Balance 的规则
    • 4 分配到与顶点构成三角形子图的分区
  • Buffer
    • 5 维护一个单分区大小的 buffer，对高度数顶点采用 Balance，然后再接收顶点流，如果 buffer 中全部为低度数顶点则使用 Greedy-3 规则

PowerGraph

PowerGraph 通过分析社交网络、网页信息等称为 Natural Graph 的图，发现这些图往往满足幂律分布（2-8分布，长尾效应），提出了顶点切分的方法。 之前的边切分策略顶点能够看到所有的邻居信息，可以完成所有的计算，但边切分将会使不同顶点副本只能看到部分的邻居信息。为了在这种情况下使系统能够并行处理，powerGraph 提出混合节点中心计算模型 GAS 解决数据一致性的维护问题。GAS 之前有介绍，具体见「初识图数据库」。

PowerLyra

PowerLyra 结合了边划分和点划分两种算法的优点，提出 Hybrid-cut 方法，解决了高度顶点的节点负载不均衡的问题，并且最小化低度顶点的节点间通信开销。 由于只采用顶点划分的策略会使低度顶点产生更多的副本，但是一个图中很难保证所有顶点的度数相近（例如微博中的大 V 关注量往往远超过普通用户，这样的顶点度数会大很多），只采用边划分会对存储高度顶点的节点负载十分不友好。

ProblemOfSingle-cut

所以 PowerLyra 采取以下策略：

  • 对于低度顶点采用边划分
  • 对于高度顶点采用点划分

具体实现分为了 Low-cut 和 High-cut 两种切分方法（或者说是步骤）：

  • Low-cut：通过 Hash 目标顶点，沿着他们的边（只能是一个方向的边，如入边）平均分配低度的顶点
  • High-cut：通过 Hash 他们的 source 顶点平均分配高度的入边到每个节点

Hybrid-cut

动态划分

动态划分主要针对系统在运行时候的动态变化，比如在算法计算时候的节点访问负载不平衡，图拓扑结构动态改变等。 Mizan 基于 BSP 并行计算框架，通过监控传入传出消息总数，响应时间等系统指标判断节点负载情况，然后按照负载配对 worker，对图顶点进行迁移。

Migration

BSP 之前有介绍，具体见「初识图数据库」。可以看到除了 BSP 本来的同步阻塞之外 Mizan 的迁移过程也是一个阻塞。

其中经过以下步骤（假设选择系统监控指标是响应时间）：

  • Step1 使用运行时间计算 z-score = |Ti - Tmax| / standard deviation ，如果大于默认设置则认为 worker 负载不均衡
  • Step2 每个 worker 使用统计信息来计算平衡目标。默认目标是平衡响应时间，若两个目标高度相关，选择相关度高的作为均衡目标
  • Step3 按照平衡目标（如响应时间）排序并并配对 worker，负载最高的与负载最低的配对
  • Step4 按照平衡目标选择迁移的顶点使得两个 worker 平衡目标几乎相同
  • Step5 迁移 worker 开始发送选定的版本，其它迁移目标 worker 在阻塞处等待（迁移顶数据量很大的情况下延迟迁移，使用两个 superSteps 完成迁移）

DelayedMigration

总结

图划分是图计算进行分布式或并行处理必不可少的步骤，除了上面介绍的算法以外，还有如Chaco、Scotch、PuLP等的离线划分，还有 Metis 和 Scotch 的并行化版本 ParMetis、PT-Scotch；如Fennel、Restreaming等的在线划分等。

良好的划分机制不仅需要减少划分时的开销，还要考虑到划分之后系统的计算存储开销、网络通信开销及节点负载均衡等，是十分值得研究的领域。

参考