PaperlayerView exact revision on arXiv

Source-linked AI summary

More Recent Advances in (Hyper)Graph Partitioning

Ümit V. Çatalyürek, Karen D. Devine, Marcelo Fonseca Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, Dorothea Wagner

arXiv:2205.13202v3cs.DScs.LG

TL;DR

Balanced (hyper)graph partitioning is a key technology for scalable applications, but practical algorithms face trade-offs in quality, runtime, and scale. This survey reviews recent algorithms and their evaluation, extending earlier coverage to hypergraphs and streaming while emphasizing parallel methods. It finds strong quality for established objectives alongside open challenges for other objectives and constraints.

  • Problem

    Scalable applications need balanced (hyper)graph partitions, while real-world instances with uneven vertex weights can challenge multilevel algorithms.

    Source: §1 · p. 2, §5.2 · p. 10

  • Method

    The paper surveys recent practical algorithms and evaluation methods for balanced (hyper)graph partitioning, including streaming and parallel approaches.

    Source: §1 · p. 2

  • Results

    Established edge-cut and hypergraph connectivity/cut objectives support very high-quality partitions, while streaming methods produce much lower-quality partitions than internal-memory methods.

    Source: §8 · p. 36

  • Takeaways & Limitations

    Open challenges remain for optimizing other or multiple objectives and handling multiple constraints, including in repartitioning.

    Source: §8 · pp. 35–36

    Taşyaran et al.’s repartitioning algorithms were not compared against other state-of-the-art repartitioning algorithms.

    Source: §5.5 · p. 18

Abstract

from arXiv · show

In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the last decade in practical algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic. In particular, the survey extends the previous survey by also covering hypergraph partitioning and streaming algorithms, and has an additional focus on parallel algorithms.

1 INTRODUCTION

Balanced (hyper)graph partitioning is a key subroutine for scalable applications, but its NP-hardness makes practical methods heuristic. This survey updates an earlier overview with recent work and broader coverage.

1 INTRODUCTION

  • Partitioning divides a (hyper)graph into roughly equal-sized blocks while minimizing edges between blocks, supporting scalable algorithms across many applications.Examples include social networks, route planning, scientific simulations, neural-network training, and VLSI design.Source: §1 · p. 2
  • Because partitioning is NP-hard, practical solutions rely on heuristic algorithms rather than exact optimization.The problem remains NP-hard even for unweighted trees of maximum degree three, and no constant-factor approximation algorithms exist.Source: §1 · p. 2
  • This survey updates the previous generic survey with work from the last decade and extends its scope to hypergraph partitioning.Earlier overviews also covered related topics, including practical hypergraph algorithms and streaming methods.Source: §1 · p. 2
  • The survey proceeds from problem preliminaries and newer applications to sequential and parallel algorithms, experimental methodology, and future challenges.Its coverage emphasizes key ideas and recent work missing from other overviews.Source: §1 · p. 2

2 OVERVIEW/CLASSIFICATION

Partitioning methods span fast, low-memory streaming approaches through higher-quality internal-memory methods and algorithms for parallel or specialized hardware, with trade-offs in quality, scale, and runtime.

2 OVERVIEW/CLASSIFICATION

  • Streaming algorithms are fast and use little memory, but typically produce lower-quality solutions by assigning vertices as they and their neighborhoods are read.They require memory proportional to the number of vertices, not enough memory to hold all graph edges.Source: §2 · p. 3
  • Sequential internal-memory methods often achieve high-quality partitions, while memetic or evolutionary methods spend more time to pursue still higher quality.These resource-intensive methods are typically used on graphs with a few hundred thousand nodes; they may also be parallel or distributed.Source: §2 · p. 3
  • Exact solvers handle only very small instances, take substantial time, and currently perform poorly for larger numbers of blocks.Source: §2 · p. 3
  • Distributed parallel methods can partition huge instances quickly on inexpensive machines, but typically deliver lower quality than internal-memory or shared-memory counterparts.The quality gap remains even with multilevel strategies, according to the survey.Source: §2 · p. 3
  • GPU partitioners use existing hardware capabilities, but limited memory accompanies partitions with significantly more cut edges than high-quality internal-memory schemes.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define the graph and hypergraph objects, partition constraints, and objective functions used throughout the survey. They distinguish vertex partitions from edge partitions and explain how cut costs are measured.

3.1 Notation

  • A hypergraph has weighted vertices and nets, each net is a vertex subset; a graph is the special case where every edge has size two.The notation also defines incident nets, neighbors, and vertex degree.Source: §3.1 · p. 3
  • A balanced k-way partition divides vertices into k nonempty disjoint blocks, each within the stated maximum block weight; connectivity counts the blocks touched by each net.A cut net touches multiple blocks, and a border vertex is incident to at least one cut net.Source: §3.1 · p. 4
  • A k-way edge partition instead divides the edge set into k nonempty blocks, balances their weights, and measures the total weight of vertices spanning multiple blocks.Source: §3.1 · p. 4

3.2 The 𝑘-way (Hyper)Graph Partitioning Problem

  • The k-way (hyper)graph partitioning problem seeks a balanced vertex partition that minimizes an objective over cut nets.The cut-net metric sums weights of cut nets, while the connectivity metric weights each cut net by the number of blocks it touches minus one; for graphs these reduce to edge cut.Source: §3.2 · p. 4

4 APPLICATIONS

Graph and hypergraph partitioning support both established applications and newer uses across computing, data systems, and scientific workloads. The examples connect partition objectives to communication, query, latency, or computational costs.

4 APPLICATIONS

  • Partitioning remains established in parallel processing, VLSI design, route planning, and image segmentation, while newer applications have emerged.Figure 1 illustrates graph edge cut and hypergraph connectivity and cut-net objectives on partitions with equally weighted blocks.Source: §4 · p. 4, Figure 1 · p. 5
  • In database sharding, records are vertices, queries are hyperedges, and minimizing connectivity reduces the average number of shards involved per query.The stated connection is to query latency and processing time.Source: §4 · pp. 4–5
  • Partitioning supports search-backend cache utilization and similarity-search indexing, where cut size is correlated with pruning efficiency.The search-backend approach uses simulation and refinement to further boost voting-table prediction accuracy.Source: §4 · p. 5
  • Applications in data distribution and scheduling include accelerating molecular-dynamics density-matrix computation, balancing simulation workloads, and sparse matrix-vector multiplication on NUMA systems.Source: §4 · p. 5
  • Parallel graph-processing systems use balanced vertex or edge partitions across machines, and streaming label-propagation approaches outperform traditional range- or hash-based partitioning.Source: §4 · p. 5
  • Other uses include SAT branching, independent-set recombination, video-object trajectories, control-unit placement, quantum-chemical subsystem construction, and quantum-circuit simulation.For quantum chemistry, small edge cuts correspond to small introduced calculation errors; nested dissection on hypergraphs is used to find contraction trees for circuit simulation.Source: §4 · pp. 5–6

5.1 Classic (Hyper)Graph Partitioning Techniques

Classic partitioning techniques combine multilevel coarsening and refinement with local-search methods that improve a partition by moving vertices. The section outlines label propagation and Fiduccia–Mattheyses as recurring refinement or search techniques.

The Multilevel Paradigm

  • The multilevel paradigm coarsens the graph, partitions the smallest instance, then projects and locally improves the partition during uncoarsening.Contracting vertices aggregates their weights; removing duplicate edges while aggregating their weights preserves balance and cut properties when projecting back.Source: §5.1 · p. 6

The Label Propagation Algorithm

  • Label propagation repeatedly assigns each visited vertex the most frequent label in its neighborhood, starting with one unique label per vertex.It can cluster vertices during coarsening or serve as local search from an existing k-way partition.Source: §5.1 · p. 7, Figure 2 · p. 7

The Fiduccia-Mattheyses Algorithm

  • Fiduccia–Mattheyses moves the highest-gain boundary vertex that respects balance, updates neighboring gains, and restores the best solution seen in the pass.Allowing negative-gain moves lets the algorithm escape local optima.Source: §5.1 · p. 7

5.2 Recent Advances in Multilevel Partitioning

Recent multilevel advances explore new coarsening and partitioning schemes and improve refinement, balance handling, and coarsening decisions. The survey highlights flow-based refinement as a particularly cost-effective way to improve partition quality.

Deep Multilevel Partitioning

  • Deep multilevel partitioning coarsens to 2^X vertices, then recursively bipartitions blocks during uncoarsening while retaining opportunities for k-way local search.It combines aspects of recursive bipartitioning and direct k-way partitioning.Source: §5.2 · p. 8, Figure 3 · p. 8

n-Level (Hyper)Graph Partitioning

  • n-level partitioning contracts one vertex per level, using localized FM search, a gain cache, and adaptive stopping to make the deep hierarchy practical.The gain cache reduces FM running time by 45%, and adaptive stopping reduces it by an order of magnitude; a parallel version uncontracts a fixed number of vertices per level.Source: §5.2 · p. 8

Coarsening

  • Coarsening advances include recomputing edge weights to protect edges likely to lie in a good partition's cut, and restricting contractions to densely coupled regions.Proposed weights include minimum spanning-tree bipartition conductance and maximum algebraic distance; clustering can also constrain which vertices may be contracted.Source: §5.2 · p. 9
  • Aggregation-based coarsening schemes are at least as effective as traditional matching-based schemes with the same refinement, and outperform them on many instances.The schemes use algebraic multigrid or stable matching to combine nodes; preference lists determine combinations in the stable-matching approach.Source: §5.2 · p. 9

Initial Partitioning

  • Recursive multilevel partitioning often initializes k-way partitions with recursive bipartitioning, which produces better initial partitions than flat techniques.A portfolio of flat bipartitioning runs can be followed by label propagation or FM search; adaptive stopping criteria account for instance-dependent coarsening needs.Source: §5.2 · p. 9

Refinement

  • Flow-based (hyper)graph refinement has a better cost-benefit ratio for improving quality than ILPs, evolutionary techniques, restarts, or V-cycles.FlowCutter explores incremental flow problems to trade cut size for better balance, and this approach leads to partitions with smaller cuts/connectivity.Source: §5.2 · p. 10, Figure 4 · p. 10

Partitioning With Unevenly Distributed Vertex Weights

  • Unevenly weighted vertices pose a challenge because multilevel algorithms struggle when heavy vertices are already present in the input.Real-world instances often contain such vertices, while the research community commonly uses unweighted instances.Source: §5.2 · p. 10
  • Two approaches to tight balance—enforcing it during initial partitioning and refinement, or rebalancing after intermediate violations—do not guarantee a balanced result.A practical technique for recursive bipartitioning preassigns some of the heaviest vertices to a block, then optimizes the remaining vertices.Source: §5.2 · pp. 10–11

5.3 Evolutionary Computation

Evolutionary and memetic partitioners recombine existing partitions, often using multilevel or matching-based structure, and preserve diversity through selection and eviction. The survey describes extensions to hypergraphs and other constrained partitioning problems.

Evolutionary algorithms

  • Genetic algorithms select and recombine fit partitions over generations; memetic algorithms add local search, while mutation and similarity-aware eviction help preserve population diversity.Source: §5.3 · p. 11

Memetic algorithms

  • Benlic and Hao cluster vertices assigned to the same block across individuals for recombination, combining the operator with tabu search.The approach is motivated by recurring groups of vertices across high-quality solutions.Source: §5.3 · p. 11

Evolutionary algorithms

  • KaFFPaE recombines two partitions with a modified multilevel solver that preserves edges cut in either input, and guarantees offspring no worse than the better parent.The better input partition initializes the search, which can exchange good solution parts across hierarchy levels.Source: §5.3 · p. 11

Memetic algorithms

  • A matching-based recombination forms offspring from intersections between matched blocks, with the most similar population member evicted when offspring enter.The bipartite matching weights block pairs by their intersection size; local search with negative-cycle detection further reduces edge cut.Source: §5.3 · pp. 11–12
  • An ILP-based recombination contracts vertices sharing blocks across multiple parents, then solves the smaller overlap-graph problem initialized from the lowest-cut parent.Ties among lowest-cut parents are broken randomly.Source: §5.3 · p. 12

Evolutionary algorithms

  • KaHyParE extends KaFFPaE to hypergraphs with multi-point recombination that penalizes contracting vertices in nets cut by many parents.An adaptive coarsening-stopping scheme was later added.Source: §5.3 · p. 12

Other problem variations

  • Other evolutionary variants address acyclic (hyper)graph partitioning with an acyclicity constraint and distributed computation of k-way vertex separators.Source: §5.3 · p. 12

5.4 Streaming

Streaming partitioners make permanent assignments from partial graph information under memory constraints, using vertex or edge streams and different batching strategies. The surveyed work spans one-pass, repeated-pass, buffered, hypergraph, and edge-partitioning methods, with tradeoffs among partition quality, memory, runtime, and application performance.

5.4.1 One-Pass Streaming Vertex Partitioning.

  • LDG favors blocks containing more neighbors while penalizing heavy blocks; Fennel cuts fewer edges than LDG and sometimes matches offline partitioning.AKIN permits vertex migration when the graph size is unknown in advance; with up to 100 neighbors per vertex, it cuts fewer edges than Fennel at equivalent imbalance but uses 10% more running time.Source: §5.4.1 · pp. 13–14

5.4.2 Restreaming Vertex Partitioning.

  • Restreaming methods iteratively reduce edge-cut, while prioritized ReLDG obtains its minimum overall edge-cut with dynamic ordering based on ambivalence.ReFennel is proved to converge after finitely many restreams even without increasing its balancing penalty.Source: §5.4.2 · p. 14

5.4.3 Buffered Streaming Vertex Partitioning.

  • Buffered vertex partitioners improve on LDG: WStream cuts fewer edges, and HeiStream beats LDG, Fennel, and Jafari et al.'s method.Jafari et al.'s shared-memory multilevel method scales better than offline partitioners; HeiStream is faster than Fennel for large numbers of blocks.Source: §5.4.3 · pp. 14–15

5.4.4 Streaming Vertex Partitioning for Hypergraphs.

  • Min-Max assigns hypergraph vertices using net overlap under a hard balance constraint, but its O(mk) memory exceeds typical streaming use.It recovers hidden co-clustering with high probability and outperforms five intuitive streaming approaches on imbalance, while being up to five times more imbalanced than internal-memory algorithms; variants trade memory and speed against cut-net quality.Source: §5.4.4 · p. 15

5.4.5 Streaming Edge Partitioning.

  • Edge-partitioning formulations connect to vertex partitioning: aggregation cost is no greater in expectation, and the basic formulations have a one-to-one correspondence.The authors also give an edge-partitioning approximation matching the best known vertex-partitioning ratio and report practical advantages for edge partitioning.Source: §5.4.5 · pp. 15–16
  • Edge-streaming systems target different tradeoffs: HDRF leads on replication factor, HoVerCut speeds partitioning while roughly retaining vertex-cut, and CuSP handles graphs with billions of vertices.ADWISE dynamically adjusts its edge window to improve quality while keeping average assignment latency under a given upper bound.Source: §5.4.5 · p. 16

5.4.6 Experimental Studies.

  • Across streaming evaluations, Fennel achieves the lowest edge-cuts, HDRF the lowest replication factors, and application performance depends on workload.Edge-cut and vertex-cut indicate network communication but do not always predict application performance; hashing can trade partitioning speed for performance in workloads where data locality has limited impact.Source: §5.4.6 · p. 17

5.5 Repartitioning

Repartitioning addresses changing graphs, where updates can unbalance blocks or worsen cut quality; surveyed approaches trade solution quality, migration, and runtime in different ways. The studies describe methods ranging from historical-information reuse to vertex replication and theory-backed transformations.

5.5 Repartitioning

  • Hash-initialized label propagation by Vaquero et al. improves edge-cut and application performance after graph changes versus hashing, but lacks comparison with other state-of-the-art repartitioners.Source: §5.5 · pp. 17–18
  • LogGP combines historical partitions with the graph in a hypergraph, then uses streaming pin partitioning and log-based statistical inferences; it outperforms state-of-the-art streaming and repartitioning algorithms on edge-cut and runtime.Source: §5.5 · p. 18
  • Hermes maintains roughly the same edge-cut as Metis-from-scratch while migrating up to an order of magnitude less data, and improves aggregate throughput around 1.7 times over hashing.Its local balance and edge-cut improvements are completed before associated data is moved.Source: §5.5 · p. 18
  • Leopard without replication matches Metis-from-scratch partition quality, while replication further reduces edge-cut by up to an order of magnitude.The method integrates vertex replication with repartitioning; replication also provides fault tolerance and improves locality.Source: §5.5 · p. 18
  • Kiefer et al.’s hybrid strategy refines locally after balance violations and periodically replaces the partition only when improved edge-cut compensates migration overhead.Its penalized block weights model nonlinear resource consumption; experiments report low imbalance, edge-cut, and migration time through graph updates.Source: §5.5 · p. 18
  • Up to an order of magnitude faster than their original counterparts, Fan et al.’s transformed algorithms retain comparable or better partition quality in experiments against Hermes and from-scratch methods.Their strategy converts successful partitioning algorithms into repartitioners while preserving their partition-quality bounds and ensuring small migration cost.Source: §5.5 · pp. 18–19

5.6 Objective Functions and Problem Variations

The section surveys partitioning variations that adapt objectives and constraints to application needs, including communication-aware process mapping. It covers experimental findings, exact formulations, specialized heuristics, and mapping algorithms for particular topologies and workloads.

5.6.1 Objective Functions.

  • The best sparse matrix partition model and metric depend on processing-element count, SpMxV implementation, and matrix structure; checkerboard generally yields the lowest runtime, while message count matters especially at 64 or more PEs.Source: §5.6.1 · p. 19
  • UMP a uses a single phase to optimize primary, secondary, and tertiary hypergraph objectives, using lower-priority metrics to break ties among moves that optimize higher-priority metrics.The authors describe efficient gain computations for communication volume and message count, including per-block forms.Source: §5.6.1 · p. 19

5.6.2 Multi-constraint Graph Partitioning.

  • Recalde et al.’s branch-and-bound exact algorithm solves real-world multi-constraint instances with 30 vertices in about half a minute; proven inequalities reduce search vertices and optimality gap.They provide two integer-programming formulations and prove associated families of inequalities.Source: §5.6.2 · pp. 19–20

5.6.3 Directed Acyclic (Hyper)graph Partitioning.

  • DAG partitioning requires an acyclic quotient; it is NP-complete for perfectly balanced partitions, with no constant-factor approximation for k≥3, and multilevel methods adapt clustering and refinement to preserve acyclicity.Methods include acyclic clustering and restricting FM vertex moves to those that do not violate the constraint.Source: §5.6.3 · p. 20

5.6.4 Symmetric Rectilinear Matrix Partitioning.

  • Heuristics for symmetric rectilinear matrix partitioning address two NP-complete objectives; sparsification enables partitioning a Twitter graph with about 1.5 billion edges in under 3 seconds on a modern 24-core system.Source: §5.6.4 · p. 20

5.6.5 Process Mapping.

  • Process mapping replaces edge-cut as the target when PE communication speeds differ; its total communication cost weights each cut edge by the distance between endpoint PEs.Algorithms may combine mapping and partitioning or partition first and then map the quotient graph.Source: §5.6.5 · pp. 20–21
  • For hierarchical topologies, Predari et al. report lower communication cost than ParMetis and ParHIP and comparable cost to a state-of-the-art sequential method; Deveci et al. report 43% and 23% performance increases on two applications versus the system default mapper.Source: §5.6.5 · pp. 21–22
  • Specialized mapping methods exploit geometric data, scaled distances, and topology structure; reported results include up to two orders of magnitude faster stencil mapping and 6%–34% lower communication cost on partial cubes.Faraj et al.’s hierarchical single-phase multilevel method also improves communication cost and mapping time over two-phase alternatives.Source: §5.6.5 · pp. 21–23

6 PARALLEL ALGORITHMS

The section surveys parallel methods for balanced graph partitioning across shared-memory, distributed, GPU, geometric, and specialized-hardware settings, covering multilevel coarsening, initial partitioning, refinement, and balance-maintenance strategies. It describes their approaches to scalability and balance alongside tradeoffs in solution or cut quality, synchronization, and runtime.

6.1 Shared Memory

  • Shared-memory algorithms retain a global graph view and can match sequential solution quality, but cannot handle graphs that exceed one machine’s memory.Source: §6 · p. 23

6.1.1 Coarsening.

  • Lock-based parallel matching matches sequential cardinality and heavy-edge quality, whereas conflict-resolution matching loses 10% on the heavy-edge metric; two-hop matching addresses skewed-degree inputs.Two-hop matching can connect non-adjacent vertices sharing a neighbor when too few vertices are matched.Source: §6.1.1 · p. 24

6.1.2 Initial Partitioning.

  • Parallel initial partitioning uses recursive trials, independent k-way partitions, work stealing, and repeated diversified solutions to expose parallelism while addressing load imbalance and sequential bottlenecks.The deep multilevel approach forks at different coarsening levels, where graphs may be too small to use parallel (un)coarsening efficiently.Source: §6.1.2 · p. 24

6.1.3 Refinement.

  • Localized FM parallelizes independent seeded searches with private move sequences, then recomputes gains and applies the best balance-feasible, cut-improving prefix.Private moves let searches retain negative-gain moves without confusing other searches; sequential gain recalculation selects the prefix that minimizes edge cut subject to balance.Source: §6.1.3 · p. 25
  • Flow-based refinement matches the partition quality of the highest-quality sequential code, KaHyPar, while running an order of magnitude faster with 10 threads.The method parallelizes searches across block pairs, including overlapping pairs under restrictions, and uses parallel push-relabel flow.Source: §6.1.3 · p. 26
  • Deterministic Mt-KaHyPar is a factor of 1.16 slower and has a factor of 1.029 higher connectivity than an equivalent nondeterministic configuration; the degradation stems from coarsening.Both factors are aggregated using geometric mean.Source: §6.1.3 · p. 27

6.2 Distributed-Memory

  • Distributed partitioners must balance communication overhead against up-to-date global state; concurrent moves can conflict, and stale block weights require safeguards to preserve balance.Label propagation commonly uses bulk-synchronous computation and communication, while some systems use asynchronous updates.Source: §6.2 · pp. 28–29
  • A distributed method builds a tree-clustering vertex order, improves it through iterative two-stage MapReduce, then partitions the order into equal ranges and performs cut-reducing swaps.Source: §6.2 · p. 29
  • Distributed balance strategies use approximate block weights with local limits, while balance phases make moves to underloaded blocks more attractive.Slota et al. alternate balance and refinement phases; a later extension handles multiple weights per vertex.Source: §6.2 · p. 30
  • Probabilistic distributed methods preserve balance in expectation by matching expected moves between blocks and communicate only counts of vertices preferring another block.The Social Hash Partitioner aggregates proposed moves at a master process; another method makes move probabilities depend on target-block capacity.Source: §6.2 · p. 30
  • On complex networks, ParHIP computes edge cuts 38% smaller than ParMetis on average and runs more than twice as fast.ParHIP uses parallel size-constraint label propagation for coarsening and refinement, with KaFFPaE for the coarsest graph’s initial partition; distributed multilevel scalability is often limited to a few hundred processors.Source: §6.2 · p. 30
  • Geometric partitioners trade partition quality for simpler, faster, and more scalable methods, while balanced parallel k-means adjusts cluster influence factors and prunes distance computations.Methods include space-filling curves and recursive cuts; MultiJagged uses multisectioning and hybrid MPI/Kokkos execution, while k-means initializes clusters from a space-filling curve order.Source: §6.2 · pp. 31–32
  • Sequential KaHyPar produces vertex cuts more than 20% better than the best graph-based edge-partitioning approach, but runs an order of magnitude slower than the distributed algorithms.The evaluated distributed graph partitioners outperform distributed hypergraph partitioners.Source: §6.2 · p. 32

6.3 GPU

  • GPU-based multilevel partitioning is approximately 1.9 times faster than Mt-Metis, while producing slightly worse edge cuts across 16 benchmark graphs.The later approach improves heavy-edge matching with Warp Segmentation and resolves conflicting candidate moves before applying them.Source: §6.3 · pp. 32–33
  • Sphynx produces cuts approximately 20% higher on regular graphs and 70% higher on irregular graphs than ParMETIS, but is approximately 19 times faster on irregular graphs using 24 GPUs.On regular graphs, ParMETIS is approximately 3 times faster than Sphynx, even when using one CPU core per Sphynx GPU.Source: §6.3 · p. 33

6.4 Approaches for Other Types of Hardware

  • Fujitsu Digital Annealer outperforms KaFFPaE on an identified dense network and on most similar instances, and outperforms Gurobi on most similar instances.The approach models partitioning as a quadratic unconstrained binary optimization problem via a spectral method; D-Wave-based work uses the same general formulation, running directly on small graphs and hybridly on large ones.Source: §6.4 · p. 33

7 EXPERIMENTAL METHODOLOGY

The section presents performance profiles, significance tests, parameter estimation, and effectiveness tests as ways to make comparisons across many partitioning instances more interpretable. Its examples show that aggregate metrics can obscure per-instance patterns and that runtime differences can affect quality comparisons.

Experimental Results

  • Tables of running time and solution quality can be difficult to interpret, while aggregated numbers can lead to misleading conclusions.The section discusses alternative presentation methods for experimental results.Source: §7 · p. 34

Performance Profile

  • Performance profiles plot the fraction of instances within a factor τ of the best solution against τ; higher fractions at smaller τ are better.At τ=1, the fraction indicates the percentage of instances on which an algorithm performs best.Source: §7 · p. 34
  • At τ=1, algorithms A and C produce the best solutions on roughly 40% of instances, compared with 10% for B and D.Algorithm C is closer to the best solution than D on most instances, despite being only 0.2% better by geometric mean.Source: §7 · p. 34

Effectiveness Tests

  • Effectiveness tests address runtime imbalance by repeating runs of the faster algorithm and comparing solution quality across similar running times.The quality metric is the minimum over the runs.Source: §7 · pp. 34–35
  • After effectiveness testing, Figure 9 (right) shows no significant difference between algorithms A and B.The test compares solution quality when algorithms receive similar running time.Source: §7 · pp. 34–35

Significance Tests

  • Significance tests assess whether observed differences are statistically significant, while parameter estimation can show their practical effect size.For running-time comparisons, parameter estimation can use per-instance time ratios and a confidence interval containing 95% of measurements.Source: §7 · p. 35

8 FUTURE CHALLENGES

The survey identifies open challenges despite substantial progress in balanced (hyper)graph partitioning. They concern scalability across hardware, difficult problem variants, multilevel methods, and whether partitioning models predict application performance.

Future Challenges

  • The field has progressed considerably, but the survey identifies a wide range of remaining challenges.It raises whether some areas have matured enough that further improvements become less likely, while noting that others retain considerable potential.Source: §8 · p. 35

Parallelism and Other Hardware Issues

  • High-quality parallel partitioning remains difficult to scale on distributed-memory machines and to many shared-memory threads, while GPUs and SIMD add challenges for irregular algorithms.Good memory locality also depends on the input (hyper)graph already being reasonably well partitioned.Source: §8 · p. 35
  • Future parallel algorithms must account for supercomputer hierarchies and heterogeneous nodes, while considering energy efficiency and future hardware.The survey mentions multi-recursive approaches and adapting deep multilevel partitioning to distributed memory as possible ways to account for hierarchy.Source: §8 · pp. 35–36

Problem Variations

  • Current solvers handle partitions with vastly different node weights poorly, and open problems remain for multiple objectives, constraints, streaming quality, and directed variants.Streaming algorithms produce worse-quality partitions than internal-memory methods, partially because they lack a global view of the optimization problem.Source: §8 · p. 36

Multilevel Partitioning

  • Future multilevel work includes more sophisticated coarsening, edge ratings, node-similarity metrics, and rigorous analysis.Instance-aware coarsening stopping rules and input-dependent sub-algorithm parameters may be more fruitful than simple formulas.Source: §8 · p. 36

Modeling and Experiments

  • For complex networks such as social networks, edge cut and communication volume are less correlated, leaving open how partitioning models translate into application performance.Source: §8 · p. 36

Related papers

Loading 2205.13202v3…