Distributed Evolutionary Graph Partitioning

1 Introduction

• For parallel computing, graph partitioning places computation units into roughly equal-sized blocks while minimizing edges between blocks.The graph models computation with vertices and communication with edges.Source: §1 · p. 1
• KaFFPaE computes partitions comparable to or better than previous Walshaw benchmark entries within minutes for moderate-size graphs.Previous methods by Soper et al. required up to one week on graphs of that size.Source: §1 · p. 1
• The paper presents KaFFPaE, integrating evolutionary search with KaFFPa and its scalable parallelization.Its mutation and combine operators do not require random edge-weight perturbations.Source: §1 · p. 1
• The paper reports that KaFFPaE computes partitions of very high quality and scales to large networks and machines.The reported experiments evaluate its tuning and performance in Section 6.Source: §1 · p. 2

2 Preliminaries

• The graph partitioning objective is to minimize edges between blocks while keeping each block within a size bound.The stated bound is (1 + ϵ)c(V)/k plus the weight of the heaviest node.Source: §2.1 · p. 2
• The multilevel approach contracts matched edges until the graph is small enough to partition, then uncontracts edges and refines the partition.Refinement moves nodes between blocks to improve cut size or balance.Source: §2.1 · p. 2
• A matching is a set of edges with no shared endpoints, and Figure 1 depicts multilevel graph partitioning.The caption identifies the figure’s topic but gives no further visual details.Source: §2.1 · p. 2, Figure 1 · p. 2
• KaFFPa iterates coarsening and uncoarsening, avoiding contraction of cut edges and using at most two recursive calls per level in an F-cycle.Its refinement algorithms guarantee nondecreasing partition quality.Source: §2.1 · p. 2

3 Related Work

• KaFFPa uses flow-based and localized FM searches and obtained the best results for many graphs in Walshaw’s benchmark.Jostle, Metis, and Scotch are also multilevel packages.Source: §3 · p. 3
• Soper et al. first combined evolutionary search with a multilevel partitioner, while Benlic et al. targeted balanced partitioning with ϵ = 0.PROBE is limited to k = 2 and ϵ = 0.Source: §3 · p. 3
• PUNCH uses natural cuts rather than the multilevel principle and computes very good partitions for road networks.The passage says natural cuts are not very helpful for instances without road-network-like natural structure.Source: §3 · p. 3

4 Evolutionary Components

• The steady-state evolutionary algorithm maintains a population of graph partitions, selecting parents, creating one offspring per generation, and evicting a population member.Its operators diversify the search space; cited work connects good local solutions with proximity and quality trends.Source: §4 · pp. 3–4

4.1 Combine Operators

• Combine operators preserve at least the better parent’s partition quality by blocking cut edges during coarsening and refining from the parent partition.The resulting coarse graph corresponds to the quotient graph of the overlay of the partition and clustering.Source: §4.1 · pp. 4–5

4.1.1 Classical Combine using Tournament Selection

• C1 chooses two tournament-selected population members and uses the lower-cut partition as P; its offspring cut is no worse than P’s.Random tie breaking is used when parent cuts are equal.Source: §4.1.1 · p. 5

4.1.2 Cross Combine / (Transduction)

• C2 combines a population individual with a newly generated partition, sampling k′ from [k/4, 4k] and ϵ′ from [ϵ, 4ϵ].The passage notes that larger imbalances generally reduce partition cuts and can yield useful clusterings.Source: §4.1.2 · p. 5

4.1.3 Natural Cuts

• C3 combines a selected partition with natural-cut clusterings, first generating them and then reusing stored elementary natural cuts after at most ten calls.Natural cuts use BFS-grown trees and minimum cuts between contracted core and ring; random centers ensure every vertex eventually enters a core.Source: §4.1.3 · pp. 5–6

4.2 Mutation Operators

• M1 uses an input partition as the coarsest-graph start and guarantees nondecreasing quality; M2 does not guarantee that outcome.Both mutation operators iterate coarsening and refinement with different random tie-breaking seeds.Source: §4.2 · p. 6

5 Putting Things Together and Parallelization

• Each processing element sizes its population so its creation time is approximately ttotal/f, builds it with KaFFPa, then applies mutation or combine operations while time remains.The fraction f is a tuning parameter, and each processing element uses a different random seed.Source: §5 · p. 7
• In each of log p communication rounds, processing elements asynchronously send their local best partition to randomly selected peers that have not yet received it.Incoming individuals are inserted using the stated eviction strategy; no global synchronization is required.Source: §5 · p. 7
• For quick start, processing elements exchange random individuals along a random cyclic permutation until the remaining S − s′ population slots are filled.Each processing element first creates s′ = |S|/p individuals with KaFFPa using different seeds.Source: §5 · p. 7
• The chosen mutation-to-crossover ratio is 1:9, and communication runs every iteration because the test system's network is very fast.The fixed operator ratios are M1:M2 = 4:1 and C1:C2:C3 = 3:1:1.Source: §5 · p. 7

6.1 Parameter Tuning

• With c = 1, larger f values sped convergence and improved final results; f = 10 was chosen, although f = 10 and f = 50 were both reported as best.For the mutation-to-crossover ratio, c = 1 was chosen for a slight advantage; when c exceeded 8, convergence slowed and average results worsened.Source: §6.1 · pp. 8–9

6.2 Scalability

• Up to 128 PEs, more processors sped convergence and improved final quality; at 256 PEs, results worsened because 60 seconds left little time for combine and mutation steps.The comparison divided each instance’s total allotted time by the number of PEs.Source: §6.2 · p. 9, Figure 6 · p. 9

6.3 Comparison with KaFFPa and other Systems

• At k = 128, KaFFPaE produced cuts 3.9% smaller than repeated KaFFPa restarts; Scotch and Metis produced cuts 19% and 28% larger than KaFFPaE, respectively.The authors note that Scotch and Metis were much faster.Source: §6.3 · p. 10, Figure 7 · p. 10

6.4 Combine Operator Experiments

• For large k, the new combine operator improved partition quality in comparable or less time, while edge biases decreased solution quality.The comparison included repeated KaFFPa runs, the new combine operator, and the combine and restart variants using perturbed edge weights.Source: §6.4 · p. 10, Table 1 · p. 10, Table 2 · p. 10

6.5 Walshaw Benchmark

• 550 of 612 Walshaw entries were improved or reproduced by the authors’ systems for 1%, 3%, and 5% imbalance.KaFFPaE alone computed 300 partitions better than previous bests and reproduced equal cuts in 170 further cases.Source: §6.5 · p. 11

6.6 Comparison with PUNCH

• KaFFPaE matched or beat PUNCH’s best cut in 9 of 12 road-network cases, but the authors spent significantly more time and had not tuned the algorithm for road networks.The authors report that average cuts on Germany were already no larger than PUNCH’s best from 100 repetitions.Source: §6.6 · p. 11

7 Conclusion and Future Work

• Table 3 reports road-network results using PUNCH’s best of 100 runs and Buffoon’s average and best cuts, alongside their runtimes.Source: Table 3 · p. 11
• KaFFPaE computes best-known partitions for many standard benchmark instances in only a few minutes, and the authors see it as useful for high-performance computing.The conclusion attributes this performance to its crossover and mutation operators and scalable parallelization.Source: §7 · p. 11
• The authors propose integrating other partitioners that support blocking edges during coarsening and using an existing partition as the initial solution.They also suggest domain-specific combine operators, such as using a modularity clusterer for social networks.Source: §7 · p. 11

A Karlsruhe Fast Flow Partitioner

• KaFFPa separates local edge-rating choices from global matching, and prior work found the expansion*2 rating best among those tested.The matching stage contracts edges until the graph is small enough for initial partitioning.Source: A Karlsruhe Fast Flow Partitioner · p. 14
• KaFFPa uses the Global Path Algorithm to build paths and cycles from high-weight edges, then solves each optimally by dynamic programming.The passage reports a half-approximation in the worst case and better empirical results than Sorted Heavy Edge Matching and Greedy.Source: A Karlsruhe Fast Flow Partitioner · p. 14
• KaFFPa stops coarsening below max(60k, n/(60k)) nodes and uses Scotch for initial partitioning because it empirically outperforms Metis.Source: A Karlsruhe Fast Flow Partitioner · p. 14
• During uncoarsening, KaFFPa uses FM-style local refinement, pairwise max-flow/min-cut improvement, and multi-try FM initialized from one boundary node.The pairwise method considers blocks sharing a boundary and seeks a feasible bipartition within the balance constraint.Source: A Karlsruhe Fast Flow Partitioner · p. 14
• KaFFPa’s F-cycle makes up to two recursive calls per level with different random seeds, while avoiding contraction of edges between blocks to preserve nondecreasing partition quality.Source: A Karlsruhe Fast Flow Partitioner · p. 14

• Larger f values speed convergence and improve the final result, with f = 50 selected as the default.The algorithm is described as not very sensitive to the exact f value.Source: §B.1 · p. 15
• With f = 50, setting c = 10 eliminates crossover and slows convergence, while c = 1 and c = 9 yield comparable final results; c = 1 is chosen for consistency.Source: §B.1 · p. 15
• Figure 8 plots f with c = 1 and c with f = 50, using KaFFPaEco as the base-case partitioner.Source: Figure 8 · p. 15

• Table 4 reports average final values on the middle-sized test set, including KaFFPa (Reps) and KaFFPaE after two hours on 16 PEs per instance and repetition.Metis and Scotch values are averages of their best cuts across ten repetitions.Source: Table 4 · p. 15
• Figure 9 presents convergence plots comparing the algorithm with repeated executions of KaFFPa.Source: Figure 9 · p. 16
• Table 5 compares combine operators by average cut and runtime.Source: Table 5 · p. 16

B.3 Larger Scalability Plots

• Figure 10 presents scalability through convergence, mean minimum cut relative to KaFFPaE using one PE, and pseudo speedup.Source: Figure 10 · p. 17

B.4 Road Networks

• Table 6 gives detailed per-instance road-network results, with PUNCH run 100 times, Buffoon 10 times, and the other listed algorithms 5 times.Source: Table 6 · p. 18

C Instances

• Table 7 lists basic properties of the benchmark set.Source: Table 7 · p. 18

• At 1% imbalance, Table 8 presents KaFFPaE partitions computed from scratch beside current Walshaw cuts in each k-column.Source: Table 8 · p. 19
• At 3% imbalance, Table 9 presents KaFFPaE partitions computed from scratch beside current Walshaw cuts in each k-column.Source: Table 9 · p. 20
• At 5% imbalance, Table 10 presents KaFFPaE partitions computed from scratch beside current Walshaw cuts in each k-column.Source: Table 10 · p. 21