論文の概要: K-SpecPart: A Supervised Spectral Framework for Multi-Way Hypergraph Partitioning Solution Improvement

• arxiv url: http://arxiv.org/abs/2305.06167v1
• Date: Sun, 7 May 2023 00:53:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-11 12:42:29.110005
• Title: K-SpecPart: A Supervised Spectral Framework for Multi-Way Hypergraph Partitioning Solution Improvement
• Title（参考訳）: K-SpecPart:マルチウェイハイパーグラフ分割ソリューション改善のためのスペクトルフレームワーク
• Authors: Ismail Bustany, Andrew B. Kahng, Ioannis Koutis, Bodhisatta Pramanik and Zhiang Wang
• Abstract要約: State-of-the-the-art hypergraph partitionerはマルチレベルパラダイムに従い、複数のレベルの粗いハイパーグラフを構築して、小型化を推進している。 これらのパーティショナーは制限に直面している: (i) 粗いプロセスは局所的な近傍構造に依存し、グローバルなハイパーグラフ構造を無視している; (ii) 局所的なミニマにおけるリスク・エントラップメントを改良する。 一般化固有値問題を解くことにより、これらの制限に対処する教師付きスペクトルフレームワークであるK-Spec-Partを紹介する。
• 参考スコア（独自算出の注目度）: 4.019851137611981
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State-of-the-art hypergraph partitioners follow the multilevel paradigm, constructing multiple levels of coarser hypergraphs to drive cutsize refinement. These partitioners face limitations: (i) coarsening processes depend on local neighborhood structure, ignoring global hypergraph structure; (ii) refinement heuristics risk entrapment in local minima. We introduce K-SpecPart, a supervised spectral framework addressing these limitations by solving a generalized eigenvalue problem, capturing balanced partitioning objectives and global hypergraph structure in a low-dimensional vertex embedding while leveraging high-quality multilevel partitioning solutions as hints. In multi-way partitioning, K-SpecPart derives multiple bipartitioning solutions from a multi-way hint partitioning solution. It integrates these solutions into the generalized eigenvalue problem to compute eigenvectors, creating a large-dimensional embedding. Linear Discriminant Analysis (LDA) is used to transform this into a lower-dimensional embedding. K-SpecPart constructs a family of trees from the vertex embedding and partitions them using a tree-sweeping algorithm. We extend SpecPart's tree partitioning algorithm for multi-way partitioning. The multiple tree-based partitioning solutions are overlaid, followed by lifting to a clustered hypergraph where an integer linear programming (ILP) partitioning problem is solved. Empirical studies show K-SpecPart's benefits. For bipartitioning, K-SpecPart outperforms SpecPart with improvements up to 30%. For multi-way partitioning, K-SpecPart surpasses hMETIS and KaHyPar, with improvements up to 20% in some cases.
• Abstract（参考訳）: State-of-the-the-art hypergraph partitionerはマルチレベルパラダイムに従い、複数のレベルの粗いハイパーグラフを構築し、小型化を推進している。 これらの仕切りは限界に直面します (i)大域ハイパーグラフ構造を無視した局所的近傍構造に依存する粗大化過程 (ii)局所ミニマのリファインメントヒューリスティックスリスク絡み込み K-SpecPartは、一般化固有値問題の解決、低次元頂点埋め込みにおけるバランスの取れた分割目標と大域ハイパーグラフ構造を捉え、高品質なマルチレベル分割解をヒントとして活用することで、これらの制約に対処する教師付きスペクトルフレームワークである。 マルチウェイパーティショニングにおいて、K-SpecPartはマルチウェイヒントパーティショニングソリューションから複数の分割ソリューションを導出する。 これらの解を一般化固有値問題に統合し、固有ベクトルを計算する。 線形判別分析(LDA)は、これを低次元の埋め込みに変換するために用いられる。 K-SpecPartは頂点埋め込みからツリーのファミリーを構築し、ツリースウィーピングアルゴリズムを用いて分割する。 マルチウェイパーティショニングのためのspecpartのツリーパーティショニングアルゴリズムを拡張した。 複数のツリーベースのパーティショニングソリューションはオーバーレイであり、続いて、整数線形プログラミング(ILP)パーティショニング問題を解くクラスタ化されたハイパーグラフにリフトする。 実証研究はK-SpecPartの利点を示している。 分割に関しては、K-SpecPartはSpecPartよりも30%向上している。 マルチウェイパーティショニングでは、K-SpecPartがhMETISやKaHyParを超え、場合によっては最大20%改善されている。

関連論文リスト

• SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning [4.110108749051657]
  大規模ハイパーグラフのためのマルチレベルスペクトルフレームワークSHyParを導入し,ハイパーエッジ有効抵抗とフローベースコミュニティ検出技術を利用した。 SHyParの鍵となるコンポーネントは、ハイパーグラフ粗化のためのフローベースの局所クラスタリングスキームであり、最大フローベースのアルゴリズムを組み込んで、コンダクタンスを大幅に改善したノードを生成する。
  論文  参考訳（メタデータ） (2024-10-09T03:29:47Z)
• PDiscoNet: Semantically consistent part discovery for fine-grained recognition [62.12602920807109]
  画像レベルのクラスラベルのみを用いて,対象部品の発見を推奨する先行情報とともにPDiscoNetを提案する。 CUB,CelebA,PartImageNet で得られた結果から,提案手法は従来手法よりもかなり優れた部分発見性能が得られることがわかった。
  論文  参考訳（メタデータ） (2023-09-06T17:19:29Z)
• Spectrum-guided Multi-granularity Referring Video Object Segmentation [56.95836951559529]
  現在の参照ビデオオブジェクトセグメンテーション(R-VOS)技術は、符号化された(低解像度)視覚言語特徴から条件付きカーネルを抽出し、デコードされた高解像度特徴をセグメンテーションする。 これは、セグメント化カーネルが前方の計算で知覚に苦慮する重要な特徴の漂流を引き起こす。 符号化された特徴に対して直接セグメント化を行い,マスクをさらに最適化するために視覚的詳細を利用するスペクトル誘導多粒度手法を提案する。
  論文  参考訳（メタデータ） (2023-07-25T14:35:25Z)
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
  正規化されたグラフ分割は、グラフ内のノードの集合を$k$ディスジョイントクラスタに分割して、任意のクラスタと他のクラスタ間の全エッジの分画を最小限にすることを目的としている。 本稿では,ノードが異なる階層群に属することを示す分類学的属性によって特徴付けられる分割問題の公平な変種について考察する。 私たちの目標は、正規化されたカット値を最小化しながら、各グループが各クラスタにほぼ比例的に表現されることを保証することです。
  論文  参考訳（メタデータ） (2023-07-22T12:20:46Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Beyond the Prototype: Divide-and-conquer Proxies for Few-shot Segmentation [63.910211095033596]
  少ないショットのセグメンテーションは、少数の濃密なラベル付けされたサンプルのみを与えられた、目に見えないクラスオブジェクトをセグメンテーションすることを目的としている。 分割・分散の精神において, 単純かつ多目的な枠組みを提案する。 提案手法は、DCP(disvision-and-conquer proxies)と呼ばれるもので、適切な信頼性のある情報の開発を可能にする。
  論文  参考訳（メタデータ） (2022-04-21T06:21:14Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。 1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
  論文  参考訳（メタデータ） (2021-02-08T17:27:34Z)
• A Performance Guarantee for Spectral Clustering [0.6445605125467572]
  スペクトルクラスタリングはいつ,最小比カット問題に対する大域的な解を見つけることができるのか? 我々は、グラフラプラシアンの不変部分空間に対して、$k$最小固有値に対応する決定論的2-無限ノルムを開発する。 これら2つの結果を組み合わせることで、スペクトルクラスタリングが保証され、大域的な解を最小比カット問題に出力する条件を与える。
  論文  参考訳（メタデータ） (2020-07-10T22:03:43Z)

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

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