Graph Edge Partitioning via Neighborhood Heuristic

• 概
• 符号说明
• Vertex vs Edge partitioning
• NE (Neighbor Expansion)
• 代码

Zhang C., Wei F., Liu Q., Tang Z. G. and Li Z. Graph edge partitioning via neighborhood heuristic. KDD, 2017.

概

本文提出了一种图分割方法 (edge partitioning), 保证只有少量的重复结点.

符号说明

• \(G = (V, E)\), 无向无权图;
• \(n = |V|, m = |E|\);
• \((x, y) \in E\), edge;
• \(N(x) = \{y| (x, y) \in E\}\), 节点 \(x\) 的一阶邻接矩阵;
• \([p] := \{1, 2, \ldots, p\}\)

Vertex vs Edge partitioning

• 图分割里面有两种分割类型:

  1. vertex partitioning: 旨在将点集分割成不相交的子集, 代价是会有部分边被舍弃;
  2. edge partitioning: 旨在将边集分割成不相交的子集, 代价是会有重复的节点 (即两个子图可能会有相同的节点).

• 本文主要关注的是第二个问题, 严格来说:

  1. 假设我们将 \(G\) 分成 \(p\) 个子图 \(G_i = (V_i, E_i), i \in [p]\), 满足:
     \[E_i \subset E, \quad \bigcup_{i \in [p]} E_i = E, \quad E_i \cap E_j = \empty. \]

  2. 定义节点重复率 (replication factor) 为
     \[\text{RF}(E_1, \ldots, E_p) := \frac{1}{|V|} \sum_{i \in [p]} |V(E_i)|. \]

  3. 则我们称该 \(p\) edge partitioning 是最优的, 如果满足
     1. \(\alpha\)-balanced:
        \[\max_{i \in [p]} \{|E_i|\} \le \lceil \alpha |E| / p \rceil. \]

     2. minimal replication factor: 在所有 \(\alpha\)-balanced 的分割中, 节点重复率最低.

NE (Neighbor Expansion)

• 上述的问题是 NP-hard 的, 作者给出一个启发式的算法.

  • 初始化:

    \[C, S, E_k \leftarrow \empty \]

  • 挑选核心节点:

    \[x \leftarrow \left \{ \begin{array}{ll} \text{selected randomly in } V \setminus C & S \setminus C = \empty, \\ \text{argmin}_{v \in S \setminus C} |N(v) \setminus S| & S \setminus C \not= \empty. \end{array} \right . \]

  • 更新:

    1. \(C \leftarrow C \cup \{x\}\);
    2. \(S \leftarrow S \cup N(x)\);
    3. \(E_k \leftarrow \{(x, y) | x, y \in S\}\).

  • 如果 \(|E_k| > \alpha m / p\), 则停止, 否则回到第二步.

• 这里的重点是核心节点的选择, 它旨在选择那些尽可能引起少量重复边出现的节点 (即该节点的邻居最好已经都在 \(S\) 中了), 从而保证最后的分割的节点重复是少的.

代码

[zongshenmu/GraphPartitioners]