A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

• 概
• METIS
  • Coarsening
  • Partitioning phase
  • Uncoarsening phase

Karypis G. and Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM, 1998.

概

本文提出了一种 multilevel graph partitioning 方法.

METIS

• METIS 的思想比较简单:
  1. 首先对原本的图 \(G_0\) 进行 coarsening;
  2. 到一定程度后, 利用一些传统的二分方法切分;
  3. 分完之后映射回去, 在这过程中, 对之前的二分进行微调.

Coarsening

• 作者给出了几种基于 maximal matching 的 coarsening 方法:
  1. Random matching (RM): 遇到一个没有 matched 的节点, 随机选择它的一个邻居作为 matching, 类似推广到所有节点;
  2. Heavy edge matching (HEM): 之前的过程是完全随机的, 但是这种方式所选择的 matching 不一定能够很好的最小化 edge-cut, 所以顺序按照 edge weight 来安排;
  3. Heavy clique matching (HCM): ...

Partitioning phase

• 这一阶段, 作者采用一些二分方法进行切分, 常用的方法都可以用在这里, 比如: Spectral bisection (SB), KL (Kernighan-Lin) algorithm, 作者建议采用后者.

Uncoarsening phase

• 这一阶段, 逐步映射回原本的节点. 在细粒度的过程中, 切分可以进一步通过 KL algorithm 进行微调. 与之前不同的时候, 因为有一个了初步的微调, 所以这一步的迭代次数可以大大降低.