論文の概要: Multilevel Acyclic Hypergraph Partitioning

• arxiv url: http://arxiv.org/abs/2002.02962v2
• Date: Thu, 15 Oct 2020 11:36:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-03 12:48:27.235080
• Title: Multilevel Acyclic Hypergraph Partitioning
• Title（参考訳）: 多レベル非巡回ハイパーグラフパーティショニング
• Authors: Merten Popp, Sebastian Schlag, Christian Schulz, Daniel Seemaier
• Abstract要約: 我々は、非巡回超グラフ分割問題に対する最初のnレベルアルゴリズムに貢献する。 我々の焦点は、ハイパーエッジが1つの頭部と任意の多くの尾を持つことができる非巡回ハイパーグラフである。 そこで我々は,通信コストをさらに削減するために,メメティックアルゴリズムを設計した。
• 参考スコア（独自算出の注目度）: 1.3190581566723918
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A directed acyclic hypergraph is a generalized concept of a directed acyclic graph, where each hyperedge can contain an arbitrary number of tails and heads. Directed hypergraphs can be used to model data flow and execution dependencies in streaming applications. Thus, hypergraph partitioning algorithms can be used to obtain efficient parallelizations for multiprocessor architectures. However, an acyclicity constraint on the partition is necessary when mapping streaming applications to embedded multiprocessors due to resource restrictions on this type of hardware. The acyclic hypergraph partitioning problem is to partition the hypernodes of a directed acyclic hypergraph into a given number of blocks of roughly equal size such that the corresponding quotient graph is acyclic while minimizing an objective function on the partition. Here, we contribute the first n-level algorithm for the acyclic hypergraph partitioning problem. Our focus is on acyclic hypergraphs where hyperedges can have one head and arbitrary many tails. Based on this, we engineer a memetic algorithm to further reduce communication cost, as well as to improve scheduling makespan on embedded multiprocessor architectures. Experiments indicate that our algorithm outperforms previous algorithms that focus on the directed acyclic graph case which have previously been employed in the application domain. Moreover, our experiments indicate that using the directed hypergraph model for this type of application yields a significantly smaller makespan.
• Abstract（参考訳）: 有向非巡回ハイパーグラフは、有向非巡回グラフの一般化概念であり、各ハイパーエッジは任意の数の尾と頭部を含むことができる。 有向ハイパーグラフは、ストリーミングアプリケーションにおけるデータフローと実行依存性のモデル化に使用できる。 したがって、ハイパーグラフ分割アルゴリズムはマルチプロセッサアーキテクチャの効率的な並列化を実現するのに利用できる。 しかし、この種のハードウェアのリソース制限のため、ストリーミングアプリケーションを組み込みマルチプロセッサにマッピングする場合、パーティションに対する非循環的な制約が必要である。 非巡回ハイパーグラフ分割問題は、有向非巡回ハイパーグラフのハイパーノードを、対応する商グラフが非巡回であるように、その分割上の目的関数を最小限に抑えながら、ほぼ等しい大きさのブロックに分割することである。 本稿では,非巡回超グラフ分割問題に対する最初のnレベルアルゴリズムを提案する。 ハイパーエッジは1つの頭部と任意の多くの尾を持つことができる。 これに基づいて,通信コストをさらに削減し,組み込みマルチプロセッサアーキテクチャのスケジューリング効率を向上させるためのmemeticアルゴリズムを考案した。 実験により,従来アプリケーション領域で用いられてきた有向非巡回グラフケースに着目した従来のアルゴリズムよりもアルゴリズムが優れていることが示された。 さらに,このタイプのアプリケーションに対して有向ハイパーグラフモデルを用いることで,makespanが大幅に小さくなることを示す実験を行った。

関連論文リスト

• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  この研究はグラフ局所クラスタリングに重点を置いており、様々なモダリティの内部接続性のため、グラフ以外の幅広い応用がある。 非近似型Andersen-Chung-Lang(ACL)アルゴリズムを離散グラフを超えて拡張し、その二次最適性をより広い範囲のグラフに一般化する。 理論的には、2つの穏やかな条件下では、両方のアルゴリズムが少なくとも1/2確率のコンダクタンスの観点から2次最適局所クラスターを識別できることが証明される。
  論文  参考訳（メタデータ） (2024-12-04T03:56:14Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  パラメータ化されたハイパーグラフ正規化エネルギー関数の表現型族を示す。 次に、これらのエネルギーの最小化がノード埋め込みとして効果的に機能することを実証する。 提案した双レベルハイパーグラフ最適化と既存のGNNアーキテクチャを共通的に用いている。
  論文  参考訳（メタデータ） (2023-06-16T04:40:59Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
  非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。 本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-27T01:14:06Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  本稿では,ハイパーグラフのスペクトル(構造)特性を保存するために,効率的なスペクトルハイパーグラフ粗大化手法を提案する。 提案手法は,ハイパーグラフクラスタリングのマルチウェイコンダクタンスを大幅に向上させることができることを示す。
  論文  参考訳（メタデータ） (2021-08-17T22:20:23Z)
• Hypergraph Partitioning using Tensor Eigenvalue Decomposition [19.01626581411011]
  我々は、k-ユニフォームハイパーグラフの分割のための新しいアプローチを提案する。 既存の手法のほとんどは、ハイパーグラフをグラフに還元し、次に標準的なグラフ分割アルゴリズムを適用することで機能する。 我々は、テンソルベースのハイパーグラフ表現を利用することでこの問題を克服する。
  論文  参考訳（メタデータ） (2020-11-16T01:55:43Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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