K-SpecPart: Supervised Embedding Algorithms and Cut Overlay for Improved Hypergraph Partitioning

Ismail Bustany, Andrew B. Kahng, Ioannis Koutis, Bodhisatta Pramanik, Zhiang Wang

Research output: Contribution to journalArticlepeer-review

Abstract

State-of-the-art hypergraph partitioners follow the multilevel paradigm that constructs multiple levels of progressively coarser hypergraphs that are used to drive cut refinement on each level of the hierarchy. Multilevel partitioners are subject to two limitations: 1) hypergraph coarsening processes rely on local neighborhood structure without fully considering the global structure of the hypergraph and 2) refinement heuristics risk entrapment in local minima. In this article, we describe K-SpecPart, a supervised spectral framework for multiway partitioning that directly tackles these two limitations. K-SpecPart relies on the computation of generalized eigenvectors and supervised dimensionality reduction techniques to generate vertex embeddings. These are computational primitives that are not only fast, but embeddings also capture global structural properties of the hypergraph that are not explicitly considered by existing partitioners. K-SpecPart then converts the vertex embeddings into multiple partitioning solutions. Unlike multilevel partitioners that only consider the best solution, K-SpecPart introduces the idea of 'ensembling' multiple solutions via a cut-overlay clustering technique that often enables the use of computationally demanding partitioning methods such as integer linear programming (ILP). Using the output of a standard partitioner as a supervision hint, K-SpecPart effectively combines the strengths of established multilevel partitioning techniques with the benefits of spectral graph theory and other combinatorial algorithms. K-SpecPart significantly extends ideas and algorithms that first appeared in our previous work on the bipartitioner SpecPart (Bustany et al., ICCAD 2022). Our experiments demonstrate the effectiveness of K-SpecPart. For bipartitioning, K-SpecPart produces solutions with up to 15% cutsize improvement over SpecPart. For multiway partitioning, K-SpecPart produces solutions with up to 20% cutsize improvement for smaller K, and maintains 2% improvement even when K is increased to 128, over leading partitioners hMETIS and KaHyPar.

Original languageEnglish (US)
Pages (from-to)1232-1245
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume43
Issue number4
DOIs
StatePublished - Apr 1 2024

All Science Journal Classification (ASJC) codes

  • Software
  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design

Keywords

  • Hypergraph partitioning
  • partitioning algorithms
  • physical design (EDA)
  • spectral partitioning

Fingerprint

Dive into the research topics of 'K-SpecPart: Supervised Embedding Algorithms and Cut Overlay for Improved Hypergraph Partitioning'. Together they form a unique fingerprint.

Cite this