arXiv:2509.22294cs.LGmath.CO2025-09

提出多目标超图划分新框架,兼顾质量与效率。

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

  • 融合最小生成树与近端梯度法,生成多样化顶点特征。
  • 2-4路划分下切边数平均减少2%~5%,个别实例降35%。
  • 适合大规模超图划分,对hMetis等方法有显著优化作用。

本文提出一种基于新型多目标非凸约束松弛模型的高效超图划分框架。采用改进的加速近端梯度算法生成多样化的k维顶点特征,避免局部最优并提升划分质量。针对不同数据规模设计两种基于最小生成树(MST)的策略:小规模数据用Prim算法构建MST后剪枝聚类;大规模数据则选取代表性节点构建小规模MST,其余节点按规则分配以降低复杂度。为进一步优化结果,引入贪婪迁移、交换及递归MST聚类等精修策略。在公开基准集上的实验表明,该算法在2、3、4路划分中相较KaHyPar平均减少2%–5%的切边数,特定实例最高降低35%。尤其在加权顶点集上,优于KaHyPar、hMetis、Mt-KaHyPar和K-SpecPart等先进划分器,展现更优划分质量与竞争力。此外,其精修策略使hMetis划分结果提升最多达16%。通过虚拟实例方法与参数敏感性分析的综合评估,验证了算法的竞争力并刻画了性能权衡。

原文摘要 · Abstract (English)

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.

超图划分多目标优化最小生成树图算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。