.png){kind=icon}
.png){kind=icon}
Return
A multilevel framework for multi-objective hypergraph partitioning: combining minimum spanning tree and proximal gradient
.png){kind=icon}
PRE
AI
DOI：10.1007/s11227-026-08738-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In very large-scale integration (VLSI) physical design, traditional partitioning methods face increasing computational pressure due to the rapid growth of circuit scale and integration density. High-performance computing (HPC) and parallel processing have become key enablers for large-scale hypergraph partitioning. Targeting hypergraphs with millions of vertices and hyperedges, this paper proposes a parallel multilevel hypergraph partitioning framework with potential for HPC applications, based on a multi-objective non-convex constrained relaxation model. In the initial partitioning stage, an improved accelerated proximal gradient method solves the continuous relaxation model to generate vertex embeddings for k-way partitioning. Two adaptive minimum spanning tree (MST) partitioning strategies, combined with an enhanced Prim algorithm, are designed for coarsened hypergraphs of different scales to improve computational efficiency. In the refinement stage, an optimization strategy integrating continuous optimization and MST structures further enhances partitioning quality. To overcome local optima in non-convex optimization, the framework generates and iteratively optimizes multiple initial partitioning candidates in parallel. Experimental results on public benchmarks demonstrate that, compared with KaHyPar, the proposed method reduces the average cut size by approximately 1–6% for two-way, three-way, and four-way partitionings, with improvements reaching up to 29% in some cases. In particular, on weighted benchmark, the proposed method consistently outperforms KaHyPar, hMetis, Mt-KaHyPar, and K-SpecPart in terms of partition quality. Although the proposed framework remains slower than existing state-of-the-art partitioners, the results indicate that it is effective in improving the partition quality of large-scale hypergraph partitioning, and it also has potential for further parallel acceleration in HPC environments.
Keywords:
Hypergraph partitioning
Multi-objective optimization
Minimum spanning tree
Clustering
Proximal gradient
Journal
IF:
2.7
Papers:
990
Citations:
1.0W