論文の概要: K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning

• arxiv url: http://arxiv.org/abs/2305.06167v2
• Date: Sat, 3 Jun 2023 19:26:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 01:28:45.162860
• Title: K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning
• Title（参考訳）: K-SpecPart: ハイパーグラフパーティショニング改善のための改良された埋め込みアルゴリズムとカットオーバーレイ
• Authors: Ismail Bustany, Andrew B. Kahng, Ioannis Koutis, Bodhisatta Pramanik and Zhiang Wang
• Abstract要約: マルチレベルパーティショナーは, (i) ハイパーグラフのグローバルな構造を十分に考慮せずに, 局所的な近傍構造に依存している。 本稿では,これら2つの制約に直接対処するマルチウェイ分割のためのスペクトルフレームワークK-SpecPartについて述べる。
• 参考スコア（独自算出の注目度）: 4.019851137611981
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State-of-the-art hypergraph partitioners follow the multilevel paradigm that constructs multiple levels of progressively coarser hypergraphs that are used to drive cut refinement on each level of the hierarchy. Multilevel partitioners are subject to two limitations: (i) hypergraph coarsening processes rely on local neighborhood structure without fully considering the global structure of the hypergraph; and (ii) refinement heuristics risk entrapment in local minima. In this paper, we describe K-SpecPart, a supervised spectral framework for multi-way partitioning that directly tackles these two limitations. K-SpecPart relies on the computation of generalized eigenvectors and supervised dimensionality reduction techniques to generate vertex embeddings. These are computational primitives that are fast and capture global structural properties of the hypergraph that are not explicitly considered by existing partitioners. K-SpecPart then converts the vertex embeddings into multiple partitioning solutions. K-SpecPart introduces the idea of ''ensembling'' multiple solutions via a cut-overlay clustering technique that often enables the use of computationally demanding partitioning methods such as ILP (integer linear programming). Using the output of a standard partitioner as a supervision hint, K-SpecPart effectively combines the strengths of established multilevel partitioning techniques with the benefits of spectral graph theory and other combinatorial algorithms. K-SpecPart significantly extends ideas and algorithms that first appeared in our previous work on the bipartitioner SpecPart. Our experiments demonstrate the effectiveness of K-SpecPart. For bipartitioning, K-SpecPart produces solutions with up to 15% cutsize improvement over SpecPart. For multi-way partitioning, K-SpecPart produces solutions with up to 20% cutsize improvement over leading partitioners hMETIS and KaHyPar.
• Abstract（参考訳）: 最先端のハイパーグラフパーティショナは、階層の各レベルのカットリファインメントを促進するために使用される、段階的に粗いハイパーグラフの複数のレベルを構築するマルチレベルパラダイムに従っている。 マルチレベルパーティショナには2つの制限がある。 (i)ハイパーグラフの全体構造を十分に考慮せずに、局所的な近傍構造に依存し、 (ii)局所ミニマのリファインメントヒューリスティックスリスク絡み込み 本稿では,これら2つの制約に直接対処するマルチウェイ分割のためのスペクトルフレームワークK-SpecPartについて述べる。 K-SpecPartは、頂点埋め込みを生成するために一般化固有ベクトルの計算と教師付き次元減少技術に依存している。 これらは高速で、既存のパーティショナによって明示的に考慮されていないハイパーグラフのグローバル構造特性をキャプチャする計算プリミティブである。 K-SpecPartは、頂点埋め込みを複数のパーティショニングソリューションに変換する。 K-SpecPartは、ICP(整数線形プログラミング)のような計算的に要求されるパーティショニング手法の使用を可能にするカットオーバーレイクラスタリング技術によって、複数のソリューションを'センスブリング'するというアイデアを導入している。 標準分割器の出力を監督ヒントとして、k-specpartは確立されたマルチレベル分割技術の強みとスペクトルグラフ理論と他の組合せアルゴリズムの利点を効果的に結合する。 K-SpecPartは、かつての分割器SpecPartに関する研究で初めて現れたアイデアとアルゴリズムを著しく拡張した。 K-SpecPartの有効性を実証した。 分割のために、K-SpecPartはSpecPartよりも最大15%削減されたソリューションを生成する。 マルチウェイパーティショニングでは、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)

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

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