# A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient

arXiv: https://arxiv.org/abs/2509.22294 · HTML: https://mlsanity.com/paper/2509.22294/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 44 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 9 of 9)

- [High-Quality Hypergraph Partitioning](https://mlsanity.com/paper/2106.08696/) (2021)
- [Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner](https://mlsanity.com/paper/1707.06665/) (2017)
- [High-Quality Shared-Memory Graph Partitioning](https://mlsanity.com/paper/1710.08231/) (2017)
- [Advanced Flow-Based Multilevel Hypergraph Partitioning](https://mlsanity.com/paper/2003.12110/) (2020)
- [K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning](https://mlsanity.com/paper/2305.06167/) (2023)
- [Scalable Shared-Memory Hypergraph Partitioning](https://mlsanity.com/paper/2010.10272/) (2020)
- [Parallel Flow-Based Hypergraph Partitioning](https://mlsanity.com/paper/2201.01556/) (2022)
- [Scalable High-Quality Hypergraph Partitioning](https://mlsanity.com/paper/2303.17679/) (2023)
- [SDP-based bounds for graph partition via extended ADMM](https://mlsanity.com/paper/2105.09075/) (2021)

## Abstract (arXiv)

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-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.