A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient
Yingying Li, Mingxuan Xie, Hailong You, Yongqiang Yao, Hongwei Liu · 2025
Read A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient by Yingying Li, Mingxuan Xie, Hailong You, Yongqiang Yao, Hongwei Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22294.txt.
Introduction
Yingying Li and four co-authors present a new framework for splitting a hypergraph into balanced parts while cutting as few hyperedges as possible. Partitioning matters for circuit design and parallel computing, where hyperedges connect many vertices at once. Their 2025 approach works at multiple levels and pursues several objectives together, through a non-convex constrained relaxation of the problem. A modified accelerated proximal gradient method generates varied vertex features, which helps the search avoid poor local answers.
The coarsening step builds a minimum spanning tree of the vertices. For large data, a tree over representative vertices stands in for the whole, and the rest are assigned to it. Refinement passes then migrate and swap vertices, sometimes re-clustering with fresh trees. On public benchmarks, the method cut hyperedges by a few percent on average against the leading partitioner KaHyPar, with much larger gains on some instances.
Catalog record
| CREATOR | Yingying Li, Mingxuan Xie, Hailong You, Yongqiang Yao, Hongwei Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22294
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient Yingying Li, Mingxuan Xie, Hailong You, Yongqiang Yao, Hongwei Liu Abstract This paper proposes an efficient hypergraph partitioning framework based on a novel multi-objective non-convex constrained relaxation model. A modified accelerated proximal gradient algorithm is employed to generate diverse k k -dimensional vertex features to avoid local optima and enhance partition quality. Two MST-based strategies are designed for different data scales: for small-scale data, the Prim algorithm constructs a minimum spanning tree followed by pruning and clustering; for large-scale data, a subset of representative nodes is selected to build a smaller MST, while the remaining nodes are assigned accordingly to reduce complexity. To further improve partitioning results, refinement strategies including greedy migration, swapping, and recursive MST-based clustering are introduced for partitions. Experimental results on public benchmark sets demonstrate that the proposed algorithm achieves reductions in cut size of approximately 2%–5% on average compared to KaHyPar in 2, 3, and 4-way partitioning, with improvements of up to 35% on specific instances. Particularly on weighted vertex sets, our algorithm outperforms state-of-the-art partitioners including KaHyPar, hMetis, Mt-KaHyPar, and K-SpecPart, highlighting its superior partitioning quality and competitiveness. Furthermore, the proposed refinement strategy improves hMetis partitions by up to 16%. A comprehensive evaluation based on virtual instance methodology and parameter sensitivity analysis validates the algorithm’s competitiveness and characterizes its performance trade-offs. Emails: Yingying Li: [email protected], Mingxuan Xie: [email protected], Hailong You: [email protected], Yongqiang Yao: [email protected], Hongwei Liu: [email protected] Keywords: Hypergraph Partitioning; Multi-objective Optimization; Minimum Spanning Tree; Clustering; Constrained Optimization; Proximal Gradient 1 Introduction Hypergraphs are a generalization of graphs where each hyperadge can connect more then two vertices. A weighted undirected hypergraph \mathcal{H}=(\mathcal{V},\mathcal{E},B,\varpi) consists of a set of n vertices \mathcal{V}=\{v_{1},v_{2},\dots,v_{n}\} , a set of m hyperedges \mathcal{E}=\{e_{1},e_{2},\dots,e_{m}\} , a weight function of the vertex B:\mathcal{V}\to\mathbb{R} , and a net weight function \varpi:\mathcal{E}\to\mathbb{R} . In practical applications, the hypergraph partitioning problem is widely used to optimize circuit layout performance [ 1 ] , data center network design [ 2 ] , distributed database storage [ 3 ] , and transaction cost optimization in distributed systems [ 4 ] . Specifically, it aims to divide the vertex set \mathcal{V} into k mutually disjoint subsets {\Pi_{1},\Pi_{2},\dots,\Pi_{k}} , such that the cut cost is minimized while satisfying load balance constraints. The mathematical formulation is as follows: \displaystyle\text{cutsize}=\sum_{e\in\mathcal{E}}\varpi_{e}(\mu_{e}-1), (1.1) where \mu_{e} is the number of partitions spanned by the hyperedge E . Simultaneously satisfying the constraint conditions, a: \bigcup_{i=1}^{k}\Pi_{i}=\mathcal{V} , and \Pi_{i}\cap\Pi_{j}=\emptyset for all i\neq j ; b: \sum_{v\in\Pi_{i}}B(v)\leq U_{i}:=(1+\varepsilon)\left\lceil\frac{\sum_{v\in\mathcal{V}}B(v)}{k}\right\rceil , where \varepsilon is a balance factor, U_{i} is the upper bound constraint of resources. 1.1 Related works As early as 1970, Kernighan and Lin [ 5 ] proposed the classical graph bisection algorithm (KL algorithm), which begins with an initial partition obtained through breadth-first traversal and iteratively swaps nodes to reduce the number of cut edges. Later, Fiduccia and Mattheyses [ 6 ] extended this approach to hypergraphs and introduced the FM algorithm. This method evaluates each vertex by its gain the estimated reduction in cut cost when moved and greedily selects the vertex with the highest gain in each iteration. It then updates the gains of neighboring vertices and ultimately applies the sequence of moves yielding the highest cumulative gain. Building upon this foundation, numerous studies have enhanced and extended the FM algorithm for more complex scenarios. For instance, Dasdan et al. [ 7 ] proposed an efficient bidirectional FM algorithm, while Dutt et al. [ 8 ] refined the cluster-based partitioning strategy. Others have extended FM to k -way partitioning [ 9 , 10 ] , improving gain computation and node assignment mechanisms. In multilevel partitioning frameworks, FM is widely adopted in the refinement stage to locally adjust vertex placement and improve partition quality. These frameworks typically consist of three stages: coarsening, initial partitioning, and refinement. Representative tools include hMetis [ 11 ] and KaHyPar [ 12 , 13 , 14 ] and so on. In recent years, with the widespread application of hypergraphs in circuit design, parallel computing, and data management, the demand for efficient and high quality hypergraph partitioning methods has significantly increased. Traditional multilevel partitioning frameworks are known for their high computational efficiency, especially on large-scale datasets. However, they often fall short in solution quality particularly in complex scenarios involving heterogeneous constraints or global optimization objectives due to their susceptibility to local optima. To address these limitations, researchers have increasingly explored optimization driven paradigms, such as integer linear programming (ILP), structural modeling, and continuous optimization, to formulate more expressive models for hypergraph partitioning and achieve better solutions. In 2024, Bustany et al. [ 15 ] proposed K-SpecPart, which first constructed a path graph through vertex embedding and generated a minimum spanning tree (MST) or a low-stretch spanning tree (LSST). Dynamic programming was then employed to reassign edge weights, better reflecting the original hypergraph’s cut structure. Based on this weighted tree, the method performed multi-way partitioning using recursive bisection, METIS tools, or VILE heuristics. Furthermore, ILP was applied to integrate multiple candidate solutions and enhance the final partition quality. Experimental results showed that the method achieved up to a 50% reduction in cut cost while maintaining strong scalability on large-scale datasets, significantly improving both efficiency and partitioning quality. More clustering methods based on minimum spanning tree can be found in the literature [ 16 , 17 , 18 ] . Building upon the structural modeling paradigm, TritonPart [ 19 ] integrated a multilevel framework to enhance both modeling expressiveness and solution quality. In its coarsening phase, multiple candidate coarse hypergraphs were generated via various vertex ordering strategies and edge aggregation heuristics. For initial partitioning, TritonPart leveraged ILP solvers (e.g., OR-Tools as an open-source alternative to CPLEX), guided by spectral embeddings provided by SpecPart. In the refinement stage, FM (Fiduccia–Mattheyses) or greedy hyperedge refinement (HER) algorithms were employed to improve partition quality locally. To further enhance global structure, TritonPart adopted a cut-overlay clustering strategy to fuse multiple candidate partitions into a new reduced hypergraph, enabling recursive refinement under a V-cycle framework. While TritonPart offered strong support for practical constraints such as fixed nodes, grouping, and balance control, our focus in this work was on evaluating general-purpose multilevel partitioners; hence, we limited our empirical comparisons to well-established baselines such as KaHyPar and hMetis. It is noteworthy that although ILP models theoretically provide globally optimal solutions for hypergraph partitioning problems, their NP-hard nature often leads to prohibitively long computation times and excessive memory usage in large-scale practical applications. Mainstream commercial solvers such as CPLEX and Gurobi struggle to efficiently handle instances with rapidly growing numbers of variables and constraints. To overcome these difficulties, researchers have widely adopted continuous optimization techniques as alternatives, relaxing the original ILP formulations into LP, semidefinite programming (SDP), or unconstrained optimization problems, and employing numerical methods such as gradient descent, Lagrangian multipliers, and conjugate gradient methods for efficient solving. For example, Nguyen et al. [ 20 ] transformed graph partitioning ILPs with knapsack constraints into compact LP models and combined heuristic strategies to construct upper bounds; Wu et al. [ 21 ] proposed a continuous relaxation model based on Deterministic annealing neural networks (DANN), introducing an entropy potential function and