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

• URL: http://arxiv.org/abs/2509.22294v1
• Date: Fri, 26 Sep 2025 12:55:30 GMT
• Title: A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient
• Authors: Yingying Li, Mingxuan Xie, Hailong You, Yongqiang Yao, Hongwei Liu,
• Abstract summary: This paper proposes an efficient accelerated partitioning framework based on a novel non-objective constrained relaxation model.<n>We show that the proposed algorithm achieves reductions in cut size approximately 2%--5% on average compared to KaHyPar.<n>We also show that the proposed refinement strategy improves hMetis partitions by up to 16%.
• Score: 16.76530184605188
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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$-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.

Related papers

• Gromov-Wasserstein Graph Coarsening [36.62418750027048]
  We study the problem of graph coarsening within the Gromov-Wasserstein geometry.<n>We propose two algorithms that leverage a novel representation of the distortion induced by merging pairs of nodes.
  arXiv  Detail & Related papers  (2025-11-11T19:49:51Z)
• A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
  We consider a novel optimization design for multi-waveguide pinching-antenna systems.<n>The proposed GML-JO algorithm is robust to different choices and better performance compared with the existing optimization methods.
  arXiv  Detail & Related papers  (2025-06-14T17:35:27Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Fast and Scalable Semi-Supervised Learning for Multi-View Subspace Clustering [13.638434337947302]
  FSSMSC is a novel solution to the high computational complexity commonly found in existing approaches. The method generates a consensus anchor graph across all views, representing each data point as a sparse linear combination of chosen landmarks. The effectiveness and efficiency of FSSMSC are validated through extensive experiments on multiple benchmark datasets of varying scales.
  arXiv  Detail & Related papers  (2024-08-11T06:54:00Z)
• SliM-LLM: Salience-Driven Mixed-Precision Quantization for Large Language Models [63.118592279833656]
  Post-training quantization (PTQ) is an effective technique for compressing large language models (LLMs)<n>We propose SliM-LLM, a salience-driven mixed-precision quantization framework that allocates bit-widths at the group-wise.<n> Experiments show that SliM-LLM achieves superior performance across various LLMs at low bit-widths.
  arXiv  Detail & Related papers  (2024-05-23T16:21:48Z)
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
  Normalized-cut graph partitioning aims to divide the set of nodes in a graph into $k$ disjoint clusters to minimize the fraction of the total edges between any cluster and all other clusters. We consider a fair variant of the partitioning problem wherein nodes are characterized by a categorical sensitive attribute indicating membership to different demographic groups. Our goal is to ensure that each group is approximately proportionally represented in each cluster while minimizing the normalized cut value.
  arXiv  Detail & Related papers  (2023-07-22T12:20:46Z)
• Clustering with minimum spanning trees: How good can it be? [1.9999259391104391]
  We quantify the extent to which minimum spanning trees are meaningful in low-dimensional partitional data clustering tasks. We review, study, extend, and generalise a few existing, state-of-the-art MST-based partitioning schemes. Overall, the Genie and the information-theoretic methods often outperform the non-MST algorithms.
  arXiv  Detail & Related papers  (2023-03-10T03:18:03Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  The minimum sum-of-squares clustering (MSSC) has been recently extended to exploit prior knowledge on the cardinality of each cluster. We propose a global optimization approach based on the branch-and-cut technique to solve the cardinality-constrained MSSC. For the upper bound, instead, we present a local search procedure that exploits the solution of the SDP relaxation solved at each node.
  arXiv  Detail & Related papers  (2022-09-19T10:19:06Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods.
  arXiv  Detail & Related papers  (2020-12-17T08:58:06Z)
• DyCo3D: Robust Instance Segmentation of 3D Point Clouds through Dynamic Convolution [136.7261709896713]
  We propose a data-driven approach that generates the appropriate convolution kernels to apply in response to the nature of the instances. The proposed method achieves promising results on both ScanetNetV2 and S3DIS. It also improves inference speed by more than 25% over the current state-of-the-art.
  arXiv  Detail & Related papers  (2020-11-26T14:56:57Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.