論文の概要: Graph Partitioning with Fujitsu Digital Annealer

• arxiv url: http://arxiv.org/abs/2311.16559v1
• Date: Tue, 28 Nov 2023 06:59:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-29 19:36:52.712132
• Title: Graph Partitioning with Fujitsu Digital Annealer
• Title（参考訳）: 富士通デジタルアニールによるグラフ分割
• Authors: Yu-Ting Kao, Hsiu-Chuan Hsu
• Abstract要約: 本研究は,富士通デジタルアナーラーの性能と走行時間を評価する。 DAはケース1354ペガゼの電力グリッドネットワークを45のサブグループに分割し、60,930のバイナリ変数を要求した。 その結果,Fujitsu DAはグラフ分割の高速かつ効率的な最適化に有効であることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph partitioning, or community detection, is the cornerstone of many fields, such as logistics, transportation and smart power grids. Efficient computation and efficacious evaluation of communities are both essential, especially in commercial and industrial settings. However, the solution space of graph partitioning increases drastically with the number of vertices and subgroups. With an eye to solving large scale graph partitioning and other optimization problems within a short period of time, the Digital Annealer (DA), a specialized CMOS hardware also featuring improved algorithms, has been devised by Fujitsu Ltd. This study gauges Fujitsu DA's performance and running times. The modularity was implemented as both the objective function and metric for the solutions. The graph partitioning problems were formatted into Quadratic Unconstrained Binary Optimization (QUBO) structures so that they could be adequately imported into the DA. The DA yielded the highest modularity among other studies when partitioning Karate Club, Les Miserables, American Football, and Dolphin. Moreover, the DA was able to partition the Case 1354pegase power grid network into 45 subgroups, calling for 60,930 binary variables, whilst delivering optimal modularity results within a solving time of roughly 80 seconds. Our results suggest that the Fujitsu DA can be applied for rapid and efficient optimization for graph partitioning.
• Abstract（参考訳）: グラフ分割、またはコミュニティ検出は、ロジスティクス、輸送、スマートパワーグリッドなど、多くの分野の基盤となっている。 地域社会の効率的な計算と効果的な評価は、特に商業的・工業的な環境では不可欠である。 しかし、グラフ分割の解空間は頂点と部分群の数によって劇的に増加する。 大規模なグラフ分割などの最適化問題を短時間で解くことに目を向け、改良されたアルゴリズムを特徴とする特殊なcmosハードウェアであるdigital annealer(da)が富士通によって考案された。 本研究は,藤津田の性能と実行時間を測定する。 モジュラリティは、ソリューションの目的関数とメトリクスの両方として実装されました。 グラフ分割問題は、DAに適切にインポートできるように、擬似非制約バイナリ最適化(QUBO)構造にフォーマットされた。 daは、空手クラブ、レス・ミゼラブルズ、アメリカンフットボール、ドルフィンを分割する他の研究の中で、最も高いモジュラリティを得た。 さらにDAは、ケース1354ペガゼパワーグリッドネットワークを45のサブグループに分割し、60,930のバイナリ変数を要求し、約80秒の問題解決時間内に最適なモジュラリティ結果を提供することができた。 その結果,Fujitsu DAはグラフ分割の高速化と最適化に有効であることが示唆された。

関連論文リスト

• GCoder: Improving Large Language Model for Generalized Graph Problem Solving [38.9131866084555]
  大規模言語モデル(LLM)は強力な推論能力を示しており、グラフ計算のような複雑なタスクに適している。 本稿では,一般化グラフ問題における問題解決の強化を目的とした,コードベースのLLMであるGCoderを紹介する。 本手法では,多種多様なグラフ形式とアルゴリズムを特徴とする広範囲なトレーニングデータセットであるGraphWildを構築する。
  論文  参考訳（メタデータ） (2024-10-24T18:40:36Z)
• Graph Adversarial Diffusion Convolution [49.974206213411904]
  本稿では,グラフ信号デノイング(GSD)問題に対する min-max 最適化の定式化を提案する。 Graph Adversarial Diffusion Convolution (GADC)と呼ばれる新しいGraph Diffusion Convolutionアーキテクチャを導出する。
  論文  参考訳（メタデータ） (2024-06-04T07:43:04Z)
• Solving Combinatorial Optimization Problems on Fujitsu Digital Annealer [0.0]
  ディジタルアニール (DA) は、制約のないバイナリ最適化 (QUBO) を用いた最適化問題を解くために開発された。 DAはIEEE 33-busとIEEE 118-busネットワークのコミュニティ構造を効果的に特定した。
  論文  参考訳（メタデータ） (2023-11-09T08:20:50Z)
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar [0.0]
  本稿では,現在のモジュラリティアルゴリズムが最大モジュラリティ分割を返却する成功度について検討する。 既存の8つのアルゴリズムを、モジュラリティを世界規模で最大化する正確な整数計画法と比較する。 以上の結果から, ほぼ最適分割は任意の最適分割と不均等に異なることが示唆された。
  論文  参考訳（メタデータ） (2023-02-28T16:11:08Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers [65.60007071024629]
  本稿では,Adaptive SGDが4つの最先端ソリューションよりも精度が高いことを示す。 本稿では,Adaptive SGDが時間と精度で4つの最先端ソリューションより優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-13T20:58:15Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  グラフパーティションは、ワークロードバランスを達成し、並列グラフ処理システムにおけるジョブ完了時間を短縮するための重要なコンポーネントです。 本稿では,本問題の局所探索アルゴリズムについて検討し,既存の手法による分割結果をさらに改善する。
  論文  参考訳（メタデータ） (2020-12-17T08:58:06Z)
• Fast Convex Relaxations using Graph Discretizations [13.977100716044102]
  マッチングと視覚問題はコンピュータ・コンピューティング・アプリケーションの基本である。 応用技術は、実用的な応用においてその実現可能性を減らすための重要な計算努力が伴う。 このセットアップにより、SLICやCut-Pursuitによって構築された問題に忠実に取り組むことができます。
  論文  参考訳（メタデータ） (2020-04-23T11:14:38Z)
• Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of Partitioned Edge Learning [73.82875010696849]
  機械学習アルゴリズムは、人工知能(AI)モデルをトレーニングするために、ネットワークエッジにデプロイされる。 本稿では,パラメータ(計算負荷)割り当てと帯域幅割り当ての新しい共同設計に焦点を当てる。
  論文  参考訳（メタデータ） (2020-03-10T05:52:15Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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