PaperlayerView exact revision on arXiv

Source-linked AI summary

High-Quality Hypergraph Partitioning

Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz, Peter Sanders

arXiv:2106.08696v1cs.DS

TL;DR

Balanced hypergraph partitioning seeks bounded-size k-way partitions with low connectivity cost, but its NP-hardness motivates heuristic methods for large instances. KaHyPar integrates fine-grained multilevel coarsening, preprocessing, portfolio initialization, localized and flow-based refinement, and optional memetic search. It achieves the highest quality among the compared hypergraph partitioners while offering a favorable time-quality tradeoff, including strong results on graph partitioning.

  • Problem

    Balanced hypergraph partitioning must divide vertices into k bounded-size blocks while minimizing connectivity-based cost over hyperedges.

  • Method

    KaHyPar combines n-level multilevel partitioning with locality-sensitive pin sparsification, Louvain-guided coarsening, portfolio initialization, localized k-way and flow-based refinement, and optional memetic search.

  • Results

    KaHyPar achieves the highest quality among the compared hypergraph partitioners and is faster than the previously highest-quality partitioner, while PaToH is faster with typically 7% larger objective values.

  • Takeaways & Limitations

    The integrated design makes KaHyPar suitable for high-quality hypergraph partitioning and extends effectively to traditional graph partitioning tasks.

  • Takeaways & Limitations

    The paper identifies alternative cost-quality tradeoffs on considerably contracted hypergraphs as an open direction for future work.

Abstract

from arXiv · show

This paper considers the balanced hypergraph partitioning problem, which asks for partitioning the vertices into $k$ disjoint blocks of bounded size while minimizing an objective function over the hyperedges. Here, we consider the most commonly used connectivity metric. We describe our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach -- driving it to the extreme of one level for (almost) every vertex. Using carefully designed data structures and dynamic update techniques, this approach offers a very good time-quality tradeoff. We present two preprocessing techniques -- pin sparsification using locality sensitive hashing and community detection based on the Louvain algorithm. The community structure is used to guide the coarsening process that incrementally contracts vertices. Portfolio-based partitioning of the contracted hypergraph already achieves good initial solutions. While reversing the contractions, a combination of highly-localized direct $k$-way local search and flow-based techniques that take a more global view, refine the partition to achieve high quality. Optionally, a memetic algorithm evolves a pool of solution candidates to obtain even higher quality. We evaluate KaHyPar on a large set of instances from a wide range of application domains. With respect to quality, KaHyPar outperforms all previously considered systems that can handle large hypergraphs such as hMETIS, PaToH, Mondriaan, or Zoltan. KaHyPar is also faster than most of these systems except for PaToH which represents a different speed-quality tradeoff. The results even extend to the special case of graph partitioning, where specialized systems such as KaHIP should have an advantage.

1 INTRODUCTION

Balanced hypergraph partitioning assigns vertices to bounded-size blocks while minimizing connectivity across nets, an NP-hard task requiring effective heuristics for large instances. KaHyPar combines fine-grained multilevel coarsening, preprocessing, portfolio initialization, localized and global refinement, and optional evolutionary search to achieve strong time-quality tradeoffs.

  • Problem: Balanced hypergraph partitioning minimizes connectivity across nets while assigning vertices to k bounded-size disjoint blocks.The connectivity metric weights each net by the number of connected blocks minus one.
  • Approach: KaHyPar contributes techniques across preprocessing, coarsening, initial partitioning, refinement, and postprocessing within a multilevel framework.The paper presents the components as an integrated system rather than a single isolated algorithm.
  • Coarsening: Community-aware coarsening restricts contractions to clusters, while n-level coarsening contracts two vertices at a time for finer hierarchy information.Communities are identified with Louvain clustering, and the resulting hierarchy supports refinement.
  • Refinement: Localized FM search begins from the representative and just-uncontracted vertex, then expands through neighboring vertices during refinement.A global 2-way maximum-flow view complements the localized k-way search.
  • Component effects: Pin sparsification can speed difficult instances with negligible quality deterioration, while community-aware coarsening improves quality with negligible time overhead.Flow techniques improve quality further at increased running time, and evolutionary techniques add a smaller improvement at very large expense.
  • Evaluation: KaHyPar achieves the highest quality among the compared systems and is faster than the previous highest-quality partitioner, while PaToH is faster with typically 7% larger objective values.The comparison covers seven other hypergraph partitioners and also reports an advantage over KaFFPa on graph partitioning.

2 PRELIMINARIES

The preliminaries define hypergraphs, balanced k-way partitions, connectivity-based objectives, and the main recursive-bipartitioning alternative. These definitions establish how cut nets, block connectivity, balance, and contraction-related structures are represented.

  • Hypergraphs: A weighted hypergraph consists of vertices and nets, with vertex and net weights; a net may contain more than two vertices.The bipartite representation places vertices and nets on opposite sides and connects incident pairs.
  • Partitions: A balanced k-way partition divides the vertex set into k nonempty disjoint blocks whose weights do not exceed L_max.The balance bound is L_max = (1 + ε)⌈c(V)/k⌉.
  • Connectivity: The connectivity λ(e) counts the blocks touched by net e, and a net is cut when λ(e) > 1.Vertices incident to at least one cut net are border vertices.
  • Contractions: Contracting vertices merges one vertex into another, updates incident nets, removes parallel nets, and aggregates the surviving net weight.The representative’s weight increases by the contraction partner’s weight.
  • Objective: The partitioning problem seeks an ε-balanced k-way partition minimizing an objective over cut nets, including cut-net and connectivity metrics.The connectivity metric additionally accounts for the number of blocks connected by each cut net, and both objectives are NP-hard to optimize.
  • Partitioning strategies: Recursive bipartitioning obtains k blocks through successive bipartitions, requiring log k phases when k is a power of two.Direct k-way partitioning is the alternative approach discussed in the preliminaries.

3 HIGH-QUALITY HYPERGRAPH PARTITIONING

KaHyPar’s core consists of a semi-dynamic hypergraph data structure and algorithms for computing k-way partitions through recursive bipartitioning and related choices.

  • Core framework: KaHyPar uses a semi-dynamic data structure supporting efficient vertex and hyperedge deletions and reversal of those operations.The framework then discusses recursive bipartitioning and the choices involved in computing k-way partitions.

3.1 The Hypergraph Data Structure

KaHyPar represents a hypergraph as a bipartite graph and uses specialized adjacency structures to make contractions and uncontractions efficient. Contraction updates are recorded so the process can be reversed during multilevel refinement.

  • Representation: The bipartite representation treats hypergraph vertices and nets as graph nodes, with incident relationships represented by graph edges.During contraction, the node for the contracted vertex is marked deleted and its incident edges are updated.
  • Data structure: An adjacency list stores incident nets for vertices, while a modified adjacency array stores pins for nets.The design reflects that vertex degrees may grow after contraction whereas nets only shrink.
  • Illustration: Figure 4 illustrates the hypergraph, its bipartite representation, and the adjacency structure, including deletion and relinking for two example nets.E[2] serves as a sentinel during uncontractions.
  • Contraction: Contracting a vertex pair either deletes an incident bipartite edge or relinks it after scanning the affected net’s pins.A memento sequence records each contracted pair so contractions can later be reversed.
  • Uncontraction: Uncontraction restores the representative weight, re-enables the contracted vertex, and reverses the corresponding delete or relink operations.A bit vector marks incident nets relevant to the current uncontraction.

3.2 Computing 𝑘-way Partitions via Recursive Bipartitioning

KaHyPar computes k-way partitions through recursive bipartitioning, while adapting imbalance across levels to preserve the final balance constraint. The approach handles arbitrary k and treats cut-nets according to the optimized objective.

  • Partitioning Strategy: The choice between direct k-way partitioning and recursive bipartitioning remains application- and algorithm-dependent, although direct k-way methods significantly outperform recursive bipartitioning in the reported approach.Recursive bipartitioning remains important because it is used within KaHyPar’s initial partitioning algorithm.
  • Recursive Bipartitioning: Recursive bipartitioning repeatedly splits the hypergraph until it produces k blocks, requiring log k phases when k is a power of two.For non-powers of two, the procedure adapts the recursion to produce appropriately sized partitions.
  • Adaptive Imbalance: Adaptive imbalance restricts the allowed imbalance at each bipartition so the final k-way partition remains ε-balanced.The initial bipartition uses ε′ := (1 + ε)^(1/⌈log k⌉) − 1.
  • Cut-Net Handling: For cut-net optimization, recursion uses section hypergraphs that omit cut-nets because those nets remain cut in the final partition.The section hypergraph H × V_i retains only nets fully contained in block V_i.

3.3 The Preprocessing Phase

KaHyPar preprocesses hypergraphs by reducing expensive neighborhood computations and extracting community structure before multi-level coarsening. It combines locality-sensitive pin sparsification with Louvain-based community detection on a bipartite representation.

  • Pin Sparsification: Pin sparsification contracts vertices with similar neighborhoods, reducing average hyperedge size and accelerating subsequent computations.Similarity is based on overlap between incident-net sets, measured with the Jaccard coefficient and its distance complement.
  • Pin Sparsification: Min-hash locality-sensitive hashing identifies similar vertices because equal fingerprints are more likely for vertices with similar incident-net neighborhoods.Multiple hash values form a vertex fingerprint, and vertices are bucketed when all fingerprint components match.
  • Pin Sparsification: Cluster-size bounds c_min and c_max constrain sparsification clusters so the resulting contractions remain reasonably balanced.Clusters meeting the lower bound become inactive in later passes, while growth stops before exceeding c_max.
  • Community Detection: Community detection supplies global structural information to guide coarsening, complementing local greedy rating decisions.The framework first identifies internally dense and externally sparse communities, then applies coarsening independently within each community.
  • Community Detection: KaHyPar applies Louvain modularity optimization to the hypergraph’s bipartite representation, adjusting edge weights according to edge density.Constant weights are used when δ ≥ 0.75; less dense inputs use a different weighting scheme.

3.4 The Coarsening Phase

KaHyPar’s coarsening phase creates smaller, structurally similar hypergraphs through adaptive n-level contractions. It combines efficient incremental updates with ratings that favor tightly connected vertex pairs and avoids bottlenecks from large hyperedges.

  • n-Level Coarsening: Unlike level-based matching or clustering, n-level coarsening contracts one vertex pair at a time and adapts each decision to the current hypergraph structure.Neighbor priorities are updated after contractions so subsequent choices reflect the changed structure.
  • Contraction Decisions: The algorithm uses a heavy-edge rating that favors vertex pairs sharing many small, high-weight nets.This rating targets contractions that preserve structurally meaningful connectivity while reducing the hypergraph.
  • Dynamic Updates: Incremental fingerprints support continuous removal of single-vertex nets and merging of parallel nets after contractions.Parallel nets are replaced by one net whose weight equals the sum of their weights.
  • Contraction Decisions: Multiple passes randomly order vertices, select each eligible partner with the highest rating, and immediately contract the pair.Coarsening stops when the vertex count falls below t·k or no eligible vertex remains.
  • Performance: The n-level coarsening algorithm is reported to be significantly faster than an engineered hypergraph-specific KaSPar implementation while achieving comparable solution quality.The comparison concerns the coarsening algorithm described for KaHyPar.

3.5 The Initial Partitioning Phase

KaHyPar obtains an initial partition through recursive bipartitioning supported by a portfolio of diverse algorithms. The portfolio combines randomized, traversal-based, greedy-growth, local-search, and label-propagation strategies.

  • Portfolio Construction: The initial partition is computed on the coarsest hypergraph using recursive bipartitioning and a portfolio of nine initial bipartitioning algorithms.Each portfolio algorithm runs 20 times with different random seeds, and the best candidate is selected.
  • Portfolio Components: The portfolio includes random partitioning and BFS-based partitioning alongside greedy hypergraph growing, local search, and label propagation.These methods provide different construction and refinement behaviors for initial solutions.
  • Greedy Hypergraph Growing: Greedy hypergraph growing expands two blocks from pseudo-peripheral seeds using priority queues and score functions such as FM gain or max-net gain.Variants differ in whether they grow both blocks globally, sequentially, or in round-robin order.
  • Label Propagation: Size-constrained label propagation assigns vertices to blocks through labels, with τ = 5 preventing labels from disappearing during the algorithm.After convergence, vertices sharing a label form a bipartition block.

3.6 Localized 2-way and 𝑘-way FM Local Search

KaHyPar’s FM refinement uses highly localized searches during uncontraction, objective-specific gain maintenance, and adaptive stopping to improve 2-way and k-way partitions efficiently.

  • Localized search: FM searches start from the representative and just-uncontracted vertex, then expand through neighboring vertices rather than activating all vertices or border vertices.This localized initialization is used for both 2-way and k-way local search.
  • Dynamic updates: Locked nets and unremovable blocks are excluded from further updates when their gain contributions cannot change during the pass.These exclusions reduce unnecessary update work without affecting feasible improvements.
  • k-way refinement: The k-way algorithm maintains one priority queue per target block and considers moves only to adjacent blocks.This avoids maintaining gains for all k possible destinations while preserving a broader view than restricted pairwise schemes.
  • Dynamic updates: Delta-gain updates modify neighboring move gains when moved vertices change net contributions or connectivity.The updates account for changes in adjacent blocks and incident-net gain contributions.
  • Caching: Gain caches preserve current move gains across local search, while rollback caches restore valid values after undoing moves.The k-way cache stores gains for vertex-to-block moves and updates adjacent-block information during rollback.
  • Adaptive stopping: The adaptive stopping rule limits refinement in the n-level hierarchy, avoiding O(n^2) total local-search steps.Search continues at least log n steps after an improvement and continues while the average gain μ remains positive.

3.7 Flow-Based Refinement

FlowCutter complements local search with a more global refinement method: it restricts movable vertices, solves incremental flow problems, and returns balanced cuts while operating directly on hypergraphs.

  • Motivation: Flow-based refinement addresses the difficulty of improving partitions with large hyperedges, where individual moves often have limited impact.Flow methods provide optimal minimum cuts for fixed source–target separations, although balanced minimum cuts remain NP-hard.
  • Integration: KaHyPar integrates FlowCutter into the n-level framework after every 2^j uncontractions and applies it to block pairs for k-way partitions.This schedule avoids running the more expensive refinement on every hierarchy level.
  • Bipartition refinement: FlowCutter contracts non-movable vertices on each side into source s and sink t, then refines only the selected movable set M.Because s and t remain separated, vertices outside M cannot change blocks.
  • Bipartition refinement: Two BFSs expand M from border vertices within each block until a weight constraint would be violated.Vertices near the cut are selected because they are the most likely to improve the solution when moved.
  • FlowCutter: FlowCutter repeatedly computes maximum flows, transforms the smaller side and a piercing vertex, and searches for different cuts until reaching a balanced bipartition.After the first balanced cut, repetitions seek better balance for subsequent FM refinement.
  • Hypergraph flows: The Lawler network represents each hyperedge with an input-output pair connected by capacity-weighted and infinite-capacity edges, but KaHyPar does not construct it explicitly.Instead, the flow algorithm is adapted to run directly on the hypergraph.

3.8 Memetic Strategies

KaHyPar extends its n-level framework with a memetic algorithm that evolves partition populations through recombination and mutation while using partition-aware coarsening and diversity control.

  • Memetic framework: The memetic method combines the n-level hypergraph partitioner with a genetic algorithm to search beyond local improvements.It is presented as the first multi-level memetic algorithm for hypergraph partitioning.
  • Population evolution: A dynamically sized population of ε-balanced k-way partitions is evolved under a steady-state process using recombination or mutation.Population size depends on the time needed to create one individual and the total time limit.
  • Recombination: Two-point recombination guarantees offspring fitness at least as good as the better parent by constraining coarsening with parent information.Parents are selected through binary tournament selection before recombination.
  • Recombination: Edge-frequency multi-recombination uses cut-net frequencies from the best individuals to guide coarsening toward vertex pairs sharing small, low-frequency nets.The rating function penalizes contractions incident to frequently cut nets.
  • Mutation: V-cycle mutations reuse an existing partition while restricting contractions to vertex pairs within the same block.This carries the existing partition to the coarsest hypergraph for further refinement.
  • Population diversity: Replacement balances fitness and diversity by evicting the least different individual among candidates no better than the offspring.Difference is measured from multisets encoding each net’s connectivity across blocks.

4 EXPERIMENTAL EVALUATION

KaHyPar is evaluated on large benchmark collections through component ablations and comparisons with state-of-the-art hypergraph partitioners. Its advanced configurations improve quality with measured time costs, while KaHyPar generally achieves the strongest quality-time balance.

  • Framework and methodology: The evaluation focuses on connectivity optimization with KaHyPar’s direct k-way approach across benchmark sets containing thousands of test instances.The experiments use 488 real-world hypergraphs in set A and evaluate multiple values of k, imbalance, and random seeds.
  • Algorithmic components: Community-aware coarsening and flow-based refinement substantially improve solution quality, while pin sparsification accelerates some instances with small quality losses.Flow-based refinement increases running time by about a factor of two, whereas community-aware coarsening has negligible time overhead.
  • Algorithmic components: Advanced KaHyPar configurations are always more effective than weaker configurations in virtual-instance tests under equal time budgets.Configurations without flow-based refinement or community-aware coarsening do not outperform their stronger counterparts when given the same amount of time.
  • Comparison with other systems: KaHyPar computes the best partitions for 68.4% of benchmark instances and remains within a factor of 1.1 of the best algorithm in 94% of cases.These figures summarize the performance-profile comparison with competing partitioners.
  • Comparison with other systems: KaHyPar offers higher-quality solutions than hMETIS, Zoltan, Mondriaan, and HYPE while retaining running times comparable to hMETIS and faster than Zoltan-AlgD on average.PaToH variants are considerably faster but typically produce objective values around 7% larger; their median times are more than an order of magnitude smaller than those of other multilevel systems.
  • Memetic algorithm and repeated executions: The memetic KaHyPar-E computes the best partitions for 94.6% of instances, while single-call KaHyPar still computes the best solutions for around 80% in a repeated-execution comparison.KaHyPar-E is evaluated after repeatedly partitioning each instance for eight hours, whereas the single-call comparison uses the first results from KaHyPar.

4.4 Case Study: Graph Edge Partitioning

The case study applies hypergraph partitioning to graph edge partitioning and compares KaHyPar with established partitioners across multiple benchmark sets. KaHyPar generally delivers the strongest solution quality, while runtime advantages depend on the benchmark and competing system.

  • Problem and reduction: Edge partitioning reduces communication overhead by distributing graph edges while minimizing node replications.The edge set is divided into balanced blocks, and nodes incident to edges in multiple blocks must be replicated.
  • Problem and reduction: A graph edge partition is obtained by representing each graph edge as a hypergraph vertex and each graph node as a hyperedge, then optimizing hypergraph connectivity.The resulting hypergraph partition induces an edge partition of the original graph.
  • Edge partitioning results: 82.3% of benchmark-set-D instances received their best edge partition from KaHyPar, which was never more than a factor of 1.13 worse than the best algorithm.The benchmark contains 46 hypergraphs derived from Walshaw, SPMV, and random hyperbolic graph instances.
  • Edge partitioning results: KaHyPar’s running times on benchmark set D were comparable to hMETIS-K, hMETIS-R, and Zoltan-AlgD, while PaToH, HYPE, and Mondriaan were considerably faster.The reported statistical tests found no significant difference between either hMETIS configuration and PaToH-Q on the stated comparison.
  • Traditional graph partitioning: On complex networks, KaHyPar found the best solutions for 58.5% of instances and was slightly faster on average than KaFFPa-StrongS.KaFFPa-StrongS found the best solutions for 29.3% of instances and could not partition one instance within the time limit.
  • Traditional graph partitioning: On DIMACS graphs, KaHyPar found the best solutions in 37% of cases, compared with 29.4% for KaFFPa-Strong and 35.3% for KaFFPa-StrongS.None of the algorithms partitioned all instances within the eight-hour time limit.
  • Traditional graph partitioning: The authors conclude that KaHyPar provides slightly higher-quality solutions than strong KaFFPa configurations on complex networks and similar-quality solutions on DIMACS graphs at comparable time.These results extend KaHyPar’s effectiveness beyond hypergraph partitioning to traditional graph partitioning.

5 CONCLUSIONS AND FUTURE WORK

The conclusion attributes KaHyPar’s quality to combining multiple heuristics within an n-level framework while maintaining practical processing speed. It also identifies a cost–quality boundary and several directions for future improvement.

  • Conclusions: Combining locality-sensitive hashing, Louvain clustering, portfolio initialization, localized k-way search, flow techniques, V-cycles, and memetic algorithms makes KaHyPar the highest-quality hypergraph partitioner.The techniques are integrated within an n-level algorithm rather than used as isolated components.
  • Conclusions: Dynamic hypergraph data structures and lazy updates make KaHyPar fast enough for applications such as VLSI design and quantum circuit simulation.The implementation processes tens of thousands of pins per second according to the conclusion.
  • Scope and trade-offs: PaToH offers a better cost–quality trade-off for sparse matrix multiplication when improved cuts produce relatively small runtime savings.The conclusion states that KaHyPar is warranted in this setting only when its cost can be amortized over many iterations.
  • Future work: Running a KaHyPar-like system on a considerably contracted hypergraph is proposed as a way to seek a different cost–quality trade-off.The conclusion also names machine learning, integer linear programming, and negative-cycle techniques as possible improvements.

A BENCHMARK STATISTICS

Figure 16 summarizes structural properties of hypergraphs from benchmark sets A, B, and C across different sources. It compares size, net-size, and vertex-degree characteristics for individual instances.

  • Benchmark properties: Each point represents one hypergraph, with benchmark properties including vertices, nets, pins, net sizes, and vertex degrees.The figure includes median and maximum values for net size and vertex degree.
  • Benchmark properties: The plotted quantities are |V|, |E|, |P|, median and maximum net size, and median and maximum vertex degree.These statistics describe both overall hypergraph scale and local connectivity structure.
Loading 2106.08696v1…