A Hypergraph Partitioner Utilizing a Novel Graph Generative Model

This paper introduces GenPart, a novel hypergraph partitioner that utilizes a variational graph convolutional network-based generative model to significantly enhance partitioning performance. Traditional partitioning approaches, including multi-level and spectral partitioning, often struggle to preserve the intrinsic structure of hypergraphs, resulting in suboptimal cut performance. GenPart addresses these challenges by creating a sophisticated embedding space, compliant with normalized cut and balance constraints, and further refined by incorporating the V-cycle method. Through generative modeling, GenPart explores a variety of new and diverse partitioning configurations within this embedding space, demonstrating superiority on several VLSI circuit benchmarks and notably outperforming well-established partitioners. Rigorous testing on ISPD98, Titan23, and ISPD2005 benchmarks under varied balance constraints has proven GenPart's efficacy. Notably, on the ISPD98 benchmarks, GenPart has demonstrated the best records on 16 out of 18 instances for a balance factor of 2% and on all 18 instances for a balance factor of 10%, outperforming other state-of-the-art methods such as hMETIS, SpecPart, K-SpecPart, and MedPart. These impressive gains not only confirm GenPart's effectiveness but also suggest that it may serve as a pioneering approach in hypergraph partitioning.