  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: (i) hypergraph coarsening processes rely on
local neighborhood structure without fully considering the global structure of
the hypergraph; and (ii) refinement heuristics risk entrapment in local minima.
In this paper, we describe K-SpecPart, a supervised spectral framework for
multi-way 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 fast and 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. 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 ILP (integer linear
programming). 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. Our
experiments demonstrate the effectiveness of K-SpecPart. For bipartitioning,
K-SpecPart produces solutions with up to 15% cutsize improvement over SpecPart.
For multi-way partitioning, K-SpecPart produces solutions with up to 20%
cutsize improvement over leading partitioners hMETIS and KaHyPar.

Machine Learning