論文の概要: A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient

• arxiv url: http://arxiv.org/abs/2509.22294v1
• Date: Fri, 26 Sep 2025 12:55:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.434629
• Title: A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient
• Title（参考訳）: 多目的ハイパーグラフ分割のためのマルチレベルフレームワーク:最小スパンニングツリーと近位勾配の組み合わせ
• Authors: Yingying Li, Mingxuan Xie, Hailong You, Yongqiang Yao, Hongwei Liu,
• Abstract要約: 本稿では,新しい非目的制約緩和モデルに基づく効率的な高速化分割フレームワークを提案する。 提案アルゴリズムは,KaHyParと比較して,カットサイズを約2%--5%削減できることを示す。 また,提案手法により,hMetisパーティションを最大16%改善することを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,新しい多目的非凸拘束緩和モデルに基づく効率的なハイパーグラフ分割フレームワークを提案する。 局所最適化を回避し、パーティション品質を向上させるために、改良されたアクセラレーションされた近位勾配アルゴリズムを用いて様々な$k$次元頂点特徴を生成する。 小規模データでは、プリムアルゴリズムは最小スパンニングツリーを構築し、大規模データでは、代表ノードのサブセットを選択してより小さなMSTを構築し、残りのノードは複雑さを減らすために割り当てる。 パーティショニングの結果をさらに改善するため、パーティショニングには、グレディマイグレーション、スワップ、再帰的なMSTベースのクラスタリングなどの改善戦略が導入された。 提案アルゴリズムは,KaHyParの2, 3, 4ウェイパーティショニングに比べて, カットサイズを約2\%～5\%削減し, 特定のインスタンスで最大35\%改善することを示した。 特に重み付き頂点集合では,KaHyPar,hMetis,Mt-KaHyPar,K-SpecPartといった最先端のパーティショナよりも優れており,その優れたパーティショニング品質と競争性を強調している。 さらに,hMetisパーティションを最大16倍改善する改良戦略が提案されている。 仮想インスタンス手法とパラメータ感度分析に基づく総合評価は,アルゴリズムの競合性を検証し,その性能トレードオフを特徴づける。

関連論文リスト

• A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
  マルチ導波路ピンチアンテナシステムの新しい最適化設計について検討する。 提案したGML-JOアルゴリズムは,既存の最適化手法と比較して,様々な選択や性能に頑健である。
  論文  参考訳（メタデータ） (2025-06-14T17:35:27Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• SliM-LLM: Salience-Driven Mixed-Precision Quantization for Large Language Models [63.118592279833656]
  後学習量子化(PTQ)は,大規模言語モデル(LLM)の圧縮に有効な手法である 本稿では,SliM-LLMを提案する。SliM-LLMは,グループ単位でビット幅を割り当てるサリエンス駆動の混合精度量子化フレームワークである。 実験により、SliM-LLMは低ビット幅の様々なLLMにおいて優れた性能を発揮することが示された。
  論文  参考訳（メタデータ） (2024-05-23T16:21:48Z)
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
  正規化されたグラフ分割は、グラフ内のノードの集合を$k$ディスジョイントクラスタに分割して、任意のクラスタと他のクラスタ間の全エッジの分画を最小限にすることを目的としている。 本稿では,ノードが異なる階層群に属することを示す分類学的属性によって特徴付けられる分割問題の公平な変種について考察する。 私たちの目標は、正規化されたカット値を最小化しながら、各グループが各クラスタにほぼ比例的に表現されることを保証することです。
  論文  参考訳（メタデータ） (2023-07-22T12:20:46Z)
• Clustering with minimum spanning trees: How good can it be? [1.9999259391104391]
  低次元分割データクラスタリングタスクにおいて、最小分散木が意味のある範囲を定量化する。 我々は、既存の最先端のMSTベースの分割スキームをレビューし、研究し、拡張し、一般化する。 全体として、Genieと情報理論の手法は、MST以外のアルゴリズムよりも優れていることが多い。
  論文  参考訳（メタデータ） (2023-03-10T03:18:03Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。 本稿では,分枝切断法に基づく大域的最適化手法を提案する。 上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
  論文  参考訳（メタデータ） (2022-09-19T10:19:06Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  グラフパーティションは、ワークロードバランスを達成し、並列グラフ処理システムにおけるジョブ完了時間を短縮するための重要なコンポーネントです。 本稿では,本問題の局所探索アルゴリズムについて検討し,既存の手法による分割結果をさらに改善する。
  論文  参考訳（メタデータ） (2020-12-17T08:58:06Z)
• DyCo3D: Robust Instance Segmentation of 3D Point Clouds through Dynamic Convolution [136.7261709896713]
  本稿では,インスタンスの性質に応じて適切な畳み込みカーネルを生成するデータ駆動型アプローチを提案する。 提案手法はScanetNetV2とS3DISの両方で有望な結果が得られる。 また、現在の最先端よりも推論速度を25%以上向上させる。
  論文  参考訳（メタデータ） (2020-11-26T14:56:57Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。