Engineering a Scalable High Quality Graph Partitioner

• The partitioning objective is to minimize edges crossing blocks while keeping each block within (1 + ϵ) times the average size.The introduction notes that this cut-size objective is commonly used because it usually correlates with more realistic formulations.Source: §1 · p. 1
• The paper focuses on partitioning a graph into k roughly equal blocks for parallel processing on k processing elements.Source: §1 · p. 1
• The paper presents its algorithm through contraction, initial partitioning, refinement, experiments, related work, and conclusions.Source: §1 · p. 1

• A valid partition divides V into disjoint blocks, limits each block’s weight by Lmax, and minimizes the total weight of edges crossing blocks.By default, inputs have unit edge and node weights, though the algorithm translates them into weighted problems.Source: §2 · p. 2
• A matching is a set of edges that share no endpoints, and contracting a matched edge replaces its endpoints with one node while combining their weights and duplicate incident edges.Source: §2 · p. 2
• Multilevel partitioning repeatedly contracts matched edges, partitions the smaller graph, then uncontracts matchings and refines block assignments to reduce cut size or restore balance.Source: §2 · p. 2

3 Contraction

• Contraction repeatedly computes and contracts matchings until the graph is small enough for initial partitioning.Source: §3 · p. 2

3.1 Edge Rating

• Edge ratings extend the common edge-weight rating with heuristics favoring heavy edges, fewer outgoing edges, and lighter nodes.These principles aim to reduce cut size and keep node weights reasonably uniform across contraction levels.Source: §3.1 · p. 3

3.2 Sequential Matching Algorithms

• The Global Path Algorithm (GPA) gives considerably better empirical results than the other tested matching algorithms, while the alternatives have at least 2.5% worse edge cuts.GPA builds paths and even cycles from descending-weight edges, then finds optimal solutions for each using dynamic programming; more sophisticated 2/3-approximation algorithms were not tried because prior tests found them much slower and not much better.Source: §3.2 · p. 3

3.3 Parallel Matching Algorithms

• Parallel matching combines a sequential matcher on each partition with a matcher on the gap graph, iteratively accepting edges locally heaviest at both endpoints.The preliminary partition, which may use coordinates or node numbering, is intended to increase matching locality rather than directly determine the final partition.Source: §3.3 · p. 4

• Initial partitioning starts when some processor has fewer than max (20, n/(αk^2)) remaining nodes.The small graph is partitioned on one processor using pMetis or Scotch; the sequential algorithm is run repeatedly across processors with different random seeds, and the best solution is broadcast.Source: §4 · p. 4
• The best of several fast initial-partitioning runs is broadcast to all processors.Each processor uses a different random seed, and the sequential runs occur simultaneously.Source: §4 · p. 4

5 Refinement

• Each PE refines its assigned block with a neighbor in quotient graph Q; matchings schedule non-overlapping block pairs, and global iterations eventually search every edge of Q.The better partitioning of each pair is adopted after local search.Source: §5 · p. 5

5.1 Choosing Matchings

• The parallel coloring algorithm assigns quotient-graph edges to matchings using free-color lists and local active/passive requests, requiring at most twice the optimal number of colors.The paper reports that this coloring-based strategy performs slightly better than its randomized local alternative.Source: §5.1 · p. 5

5.2 Refinement Between Two Blocks

• Before local search, bounded breadth-first searches from block boundaries exchange boundary-region copies with partner PEs, limiting search scope and communication for large graphs.A later outer-loop iteration can reach beyond the exchanged boundary area if that would improve the search.Source: §5.2 · p. 6
• The two-block local search uses FM-style priority queues ordered by move gain, with TopGain defaulting to MaxLoad when a block is overloaded.Nodes begin at the boundary, are moved at most once per search, and ties are broken randomly by default.Source: §5.2 · p. 6
• Search stops after more than α min {|A|, |B|} moves without improvement and rolls back to the state best by imbalance, then cut value.Source: §5.2 · p. 6

6 Experiments

• The benchmark uses graph suites spanning geometric, FEM, road, sparse-matrix, and social-network graphs; runs generally use 10 repetitions and geometric-mean averaging.The Walshaw benchmark seeks minimal cuts for k = 2, 4, 8, 16, 32, and 64 at balance settings 1%, 3%, and 5%.Source: Table 1 · p. 7, §6 · p. 8, §6.3 · p. 10

6.1 Configuring the Algorithm

• Using plain edge weight is up to 8.8% worse than other edge ratings; the authors adopt expansion∗2, while GPA outperforms the other matching algorithms by at least 2.5% in edge cuts.The matching algorithms have about the same overall runtime, with GPA's slower matching offset by less refinement work.Source: §6.1 · pp. 8–9, Table 3 · p. 9
• pMetis is about 4.7% worse than Scotch and only slightly faster, yet is adopted as the default initial partitioner.Source: §6.1 · p. 9
• TopGain yields about 3.2% better solutions than MaxLoad, but MaxLoad is needed in overloaded cases to satisfy the balance constraint.Even using MaxLoad only for tie-breaking performs worse than Alternating.Source: §6.1 · p. 9, Table 4 · p. 9
• More work on iterations, BFS depth, and local search improves solutions with diminishing returns; the fast strategy keeps runtime increases within 20% of minimum settings.The increases for stronger settings add up to 63% more execution time than the fast strategy on average.Source: §6.1 · p. 9

6.2 Comparison with other Partitioners

• parMetis produces cuts 30% larger than strong KaPPa, 27% larger than fast KaPPa, and 18% larger than minimal KaPPa, while running at least an order of magnitude faster.parMetis also does not fully adhere to the balancing constraint; KaPPa scales to 1024 PEs while parMetis reaches its scalability limit around 100 PEs.Source: §6.2 · p. 10, Figure 3 · p. 11

6.3 The Walshaw Benchmark

• 54, 46, and 31 Walshaw entries improve at balance settings 5%, 3%, and 1%, respectively; the largest reported improvement cuts 45% more edges than the previous partition on add32.Improvements occur in 11 of 14 large instances and 9 of 20 small instances; gains are rare for k = 2.Source: §6.3 · pp. 11–12

7 Related Work

• Earlier parallelizations generally incurred a partition-quality penalty, whereas the authors report that their parallelization can improve quality.Source: §7 · p. 12
• Unlike parallel Jostle’s pairwise local searches, which have difficulty maintaining balance, KaPPa runs concurrent searches only on independent partition pairs.Source: §7 · p. 12
• PT-Scotch uses recursive bipartitioning, parallel attempts, and band-refinement; KaPPa also uses band-refinement with a different algorithm and less replicated work.Source: §7 · p. 12
• DiBaP reports the best partitioning results for the largest graphs in, but lacks a scalable parallelization.Source: §7 · p. 12
• Fast approximate weighted-matching algorithms offer guarantees of 1/2 or 2/3; the paper tests these approaches in a graph partitioner.Source: §7 · p. 13

8 Conclusions and Future Work

• 8.8% average improvement in Section 6.1 came from edge ratings; matching quality and FM-style local search also improved solutions, with pairwise refinement enabling parallelism and outperforming global search.Source: §8 · p. 13
• KaPPa remains a research prototype rather than a widely usable tool, and the authors aim to support inputs from small graphs to graphs with billions of nodes.Source: §8 · p. 13
• A key conceptual task is separating the number of partitioning PEs from the number of blocks; for k < P, assigning more PEs to one local search reduces scalability and may fail when blocks exceed local memory.Source: §8 · p. 13
• The authors also seek support for graphs without coordinates or prepartitioning, including a fast graph-theoretic prepartitioner for very large systems.Source: §8 · p. 13
• Further work includes more systematic edge-rating studies and testing flow- or diffusion-based refinement within pairwise refinement.Source: §8 · p. 14

A Detailed Results for the Large Instances.

• The large-instance tables cover KaPPa-Minimal, KaPPa-Fast, KaPPa-Strong, KMetis, and parMetis configurations.The supplied table titles do not include performance values or comparative outcomes.Source: Table 6 · p. 17, Table 9 · p. 18, Table 12 · p. 20
• KaPPa tables report results for k = 16, 32, and 64 blocks across the supplied configurations.KMetis and parMetis table titles are also provided for each of those block counts.Source: Table 6 · p. 17, Table 7 · p. 17, Table 8 · p. 18
• Walshaw benchmark tables report results at balance tolerances ϵ = 1%, 3%, and 5%.Their captions mark Expansion, Expansion∗2, and InnerOuter variants.Source: Table 21 · p. 25, Table 22 · p. 26, Table 23 · p. 27