High-Quality Hypergraph Partitioning

DOI10.1145/3529090MaRDI QIDQ6127837zbMATH OpenOpenAlexFDO

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

Publication date 14 April 2024

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.08696

zbMATH Keywords

community detectionportfoliomemetic algorithmpartitioningmaximum flowsmultilevel algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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.

Recommendations

• k-way hypergraph partitioning via n-level recursive bisection
• Engineering a direct \(k\)-way hypergraph partitioning algorithm
• Shared-memory \(n\)-level hypergraph partitioning

Cited in

(12)

• Cuts, cats, and complete graphs
• FREIGHT: fast streaming hypergraph partitioning
• Scalable high-quality hypergraph partitioning
• Minimum s-t hypercut in (s, t)-planar hypergraphs
• Multi-objective k-way parallel hypergraph partitioning with proximal gradient algorithm
• Splitting-off in hypergraphs
• Hypergraph connectivity augmentation in strongly polynomial time
• Splitting-off in hypergraphs
• A massively parallel interior-point method for arrowhead linear programs with local linking structure
• Optimizing warehouse product allocation at JD.com: a community detection-driven approach
• Shared-memory \(n\)-level hypergraph partitioning
• A direct k-way hypergraph partitioning algorithm for optimizing the Steiner tree metric

This page was built for publication: High-Quality Hypergraph Partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6127837)