論文の概要: Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes

• arxiv url: http://arxiv.org/abs/2004.03819v1
• Date: Wed, 8 Apr 2020 05:30:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-25 11:51:13.520393
• Title: Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes
• Title（参考訳）: 102,400ノードの疎ハードウェアグラフを持つ大規模アニールプロセッサの最小埋め込みヒューリスティックス
• Authors: Yuya Sugie, Yuki Yoshida, Normann Mertig, Takashi Takemoto, Hiroshi Teramoto, Atsuyoshi Nakamura, Ichigaku Takigawa, Shin-ichi Minato, Masanao Yamaoka, Tamiki Komatsuzaki
• Abstract要約: 最小の埋め込みは、二次的に制約のないバイナリ最適化において問題をコンパイルするのに必須のツールとなっている。 適度なサイズ(約2000ノード)アニール用最近の埋込み装置の開発 最新のCMOSアニーリングプロセッサ(102,400ノード)のサイズは、埋め込みに全く新しい要求をもたらす。
• 参考スコア（独自算出の注目度）: 4.615728097564293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minor embedding heuristics have become an indispensable tool for compiling problems in quadratically unconstrained binary optimization (QUBO) into the hardware graphs of quantum and CMOS annealing processors. While recent embedding heuristics have been developed for annealers of moderate size (about 2000 nodes) the size of the latest CMOS annealing processor (with 102,400 nodes) poses entirely new demands on the embedding heuristic. This raises the question, if recent embedding heuristics can maintain meaningful embedding performance on hardware graphs of increasing size. Here, we develop an improved version of the probabilistic-swap-shift-annealing (PSSA) embedding heuristic [which has recently been demonstrated to outperform the standard embedding heuristic by D-Wave Systems (Cai et al., 2014)] and evaluate its embedding performance on hardware graphs of increasing size. For random-cubic and Barabasi-Albert graphs we find the embedding performance of improved PSSA to consistently exceed the threshold of the best known complete graph embedding by a factor of 3.2 and 2.8, respectively, up to hardware graphs with 102,400 nodes. On the other hand, for random graphs with constant edge density not even improved PSSA can overcome the deterministic threshold guaranteed by the existence of the best known complete graph embedding. Finally, we prove a new upper bound on the maximal embeddable size of complete graphs into hardware graphs of CMOS annealers and show that the embedding performance of its currently best known complete graph embedding has optimal order for hardware graphs with fixed coordination number.
• Abstract（参考訳）: 最小埋め込みヒューリスティックスは、量子およびCMOSアニールプロセッサのハードウェアグラフに二次的に制約のないバイナリ最適化(QUBO)の問題をコンパイルするのに欠かせないツールとなっている。 最近の埋め込みヒューリスティックは、中程度のサイズ(約2000ノード)のアニーラー向けに開発されたが、最新のCMOSアニーリングプロセッサ(102,400ノード)のサイズは、埋め込みヒューリスティックに全く新しい要求をもたらす。 これは、最近の組込みヒューリスティックが、サイズが増大するハードウェアグラフに有意義な組込みパフォーマンスを維持できるかどうかという疑問を提起する。 そこで本研究では, D-Wave Systems (Cai et al., 2014) による確率的スワップシフトアニーリング (PSSA) 埋め込みヒューリスティック (最近, D-Wave Systems による標準埋め込みヒューリスティックを上回り, ハードウェアグラフへの埋め込み性能の評価を行った。 ランダムキュービックグラフとバラバシ・アルベルトグラフでは、改良PSSAの埋め込み性能は102,400ノードのハードウェアグラフまで、それぞれ3.2と2.8の係数で最もよく知られた完全グラフ埋め込みのしきい値を超えている。 一方、一定のエッジ密度を持たないランダムグラフに対して、PSSAは最もよく知られた完全グラフ埋め込みの存在によって保証される決定論的しきい値を克服することができる。 最後に, CMOSアンナーのハードウェアグラフへの完全グラフの最大埋め込み可能なサイズに関する新たな上限を証明し, 現在知られている完全グラフの埋め込み性能は, 固定座標数を持つハードウェアグラフに対して最適であることを示す。

関連論文リスト

• What Can We Learn from State Space Models for Machine Learning on Graphs? [11.38076877943004]
  グラフ構造化データに対する状態空間モデル(SSM)の原則拡張として,グラフ状態空間畳み込み(GSSC)を提案する。 グローバルな置換同変集合アグリゲーションと分解可能なグラフカーネルを活用することにより、GSSCはSSMの3つの利点を全て保持する。 グラフ機械学習のパワフルでスケーラブルなモデルとしてのGSSCの可能性を明らかにする。
  論文  参考訳（メタデータ） (2024-06-09T15:03:36Z)
• Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces [4.928791850200171]
  グラフネットワークにおける長期コンテキストモデリングを強化する最初の試みであるGraph-Mambaを紹介する。 グラフ中心のノード優先順位付けと置換戦略を定式化し、文脈認識推論を強化する。 10のベンチマークデータセットの実験により、Graph-Mambaは長距離グラフ予測タスクにおいて最先端の手法より優れていることが示された。
  論文  参考訳（メタデータ） (2024-02-01T17:21:53Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  この研究は、モデルの特徴と重要な設計制約を識別することに焦点を当てた、単一の大規模グラフでの表現学習を前進させる。 この研究の重要な革新は、局所的な注意機構と組み合わされた高速な近傍サンプリング技術の作成である。 ogbn-products と snap-patents の3倍の高速化と16.8%の性能向上を報告し、ogbn-100M で LargeGT を5.9% の性能改善で拡張した。
  論文  参考訳（メタデータ） (2023-12-18T11:19:23Z)
• Distributed Graph Embedding with Information-Oriented Random Walks [16.290803469068145]
  グラフ埋め込みはグラフノードを低次元ベクトルにマッピングし、機械学習タスクで広く採用されている。 数十億のエッジグラフを埋め込むためにスケール可能な,汎用的で分散された情報中心のランダムウォークベースのグラフ埋め込みフレームワークであるDistGERを提案する。 D DistGERは2.33x-129x加速、機械間通信の45%削減、下流タスクの10%改善を示す。
  論文  参考訳（メタデータ） (2023-03-28T03:11:21Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Graph Encoder Embedding [11.980640637972266]
  本稿では,高速なグラフエンコーダ埋め込み方式を提案する。 提案手法は、線形計算複雑性と、標準PC上で数分で数十億のエッジを処理する能力を有する。 スピードアップは埋め込み性能を犠牲にすることなく達成される。
  論文  参考訳（メタデータ） (2021-09-27T14:49:44Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale(GAS)は、任意のメッセージパスGNNを大規模グラフにスケールするためのフレームワークである。 ガスは、前回のトレーニングの繰り返しから過去の埋め込みを利用して計算グラフのサブツリー全体を掘り起こします。 ガスは大規模グラフ上で最先端のパフォーマンスに達する。
  論文  参考訳（メタデータ） (2021-06-10T09:26:56Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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