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

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

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

    点分割是将图的结点分配到各个子图中，维持结点之间子图的完整性，这个时候可能造成某些结点之间的边被切掉(edge-cut)；同理边分割是将图的边分配到各个子图中，每组分配的边构成子图，这个时候造成某些结点的冗余（vertex-cut）。对于服从幂律分布power-law的图数据，某些结点的边可能特别多，如果执行点分割会造成大量边的缺失以及边的负载不均匀；而边分割可以处理这类问题。

    图分割的两个目标是负载均衡load balancing（减少存储代价）和最小化切边或点minimum cuts（减少通讯代价），同时优化这两个目标是平衡图分割（balanced graph partitioning）问题。
    image.png image.png
    由于工业场景下的图较大所以实际使用的还是低复杂度的随即划分算法。实际场景中图大部分符合幂律分布，这样就不可避免的影响到了划分子图的局部聚集性，使得大量的采样通信和特征拉取通信发生。为了减少通信AliGraph提出热数据缓存策略。由于幂律分布，使得一些hub节点被频繁的采样到，那这部分节点的特征就会被频繁的访问到。对于这部分节点以及其1-hop的neighbor以及其特征，AliGraph选择静态的缓存在所有机器节点上。为此他对每个节点定义重要度，当该节点重要度较高时缓存其各个Hop的拓扑信息和特征信息。

    点分割：

    • METIS
    • Random Hash
    • Linear Deterministic Greedy partitioning (LDG)
    • Fennel
    • GAP（Generalizable Approximate Partitioning）
    • ……

    边分割：

    • NE（neighbor expansion）
    • Degree Based Hashing (DBH)
    • HDRF
    • ……