論文の概要: Quadratic Binary Optimization with Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2404.04874v2
• Date: Sat, 23 Aug 2025 08:08:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:44.966328
• Title: Quadratic Binary Optimization with Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークを用いた擬似二元最適化
• Authors: Moshe Eliasof, Eldad Haber,
• Abstract要約: グラフニューラルネットワーク(GNN)と擬似非制約バイナリ最適化(QUBO)の相関について検討する。 本稿では,グラフ表現学習技術とQUBO認識機能を統合するアーキテクチャであるQUBO-GNNを提案する。
• 参考スコア（独自算出の注目度）: 20.497024298986883
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems, laying the groundwork for GNNs to approximate solutions for these computationally challenging tasks. By analyzing the sensitivity of QUBO formulations, we frame the solution of QUBO problems as a heterophilic node classification task. We then propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently. Additionally, we introduce a self-supervised data generation mechanism to enable efficient and scalable training data acquisition even for large-scale QUBO instances. Experimental evaluations of QUBO-GNN across diverse QUBO problem sizes demonstrate its superior performance compared to exhaustive search and heuristic methods. Finally, we discuss open challenges in the emerging intersection between QUBO optimization and GNN-based learning.
• Abstract（参考訳）: 本稿では,グラフニューラルネットワーク (GNN) と準非拘束バイナリ最適化 (QUBO) 問題との関係を考察し,GNN がこれらの計算的課題の解を近似するための基礎となる課題について述べる。 QUBOの定式化の感度を解析することにより、QUBO問題の解をヘテロ親和性ノード分類タスクとしてフレーム化する。 次に,QUBO-GNNを提案する。グラフ表現学習技術とQUBO認識機能を統合し,効率的に解を近似するアーキテクチャである。 さらに,大規模QUBOインスタンスに対しても,効率的かつスケーラブルなトレーニングデータ取得を可能にする自己教師型データ生成機構を導入する。 多様なQUBO問題サイズに対するQUBO-GNNの実験的評価は、徹底的な探索法やヒューリスティック法よりも優れた性能を示した。 最後に,QUBO最適化とGNNに基づく学習の交わりにおけるオープンな課題について論じる。

関連論文リスト

• Binarizing Physics-Inspired GNNs for Combinatorial Optimization [2.5782973781085383]
  PI-GNNの性能は問題グラフの密度の増大とともに低下することを示す。 本稿では,ファジィ論理とバイナライズニューラルネットワークの洞察を基盤として,PI-GNNにおけるナイーブ戦略の原則的代替案を提案する。 提案手法のポートフォリオがPI-GNNの性能を大幅に向上することを示す実験を行った。
  論文  参考訳（メタデータ） (2025-07-18T07:11:50Z)
• Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
  NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。 AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
  論文  参考訳（メタデータ） (2024-06-05T02:43:41Z)
• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  グラフニューラルネットワークは、様々なアプリケーションにまたがる強力なパフォーマンスで認識されている。 BPには、その生物学的妥当性に挑戦する制限があり、グラフベースのタスクのためのトレーニングニューラルネットワークの効率、スケーラビリティ、並列性に影響を与える。 半教師付き学習のケーススタディを用いて,GNNに適した新しい前方学習フレームワークであるDFA-GNNを提案する。
  論文  参考訳（メタデータ） (2024-06-04T07:24:51Z)
• Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
  我々は、弱い情報(GLWI)を用いたグラフ学習問題に対する原則的アプローチを開発する。 非完全構造を持つ入力グラフ上で長距離情報伝搬を行うデュアルチャネルGNNフレームワークであるD$2$PTを提案するが、グローバルな意味的類似性を符号化するグローバルグラフも提案する。
  論文  参考訳（メタデータ） (2023-05-29T04:51:09Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Binary Graph Convolutional Network with Capacity Exploration [58.99478502486377]
  ネットワークパラメータと入力ノード属性の両方を二項化するバイナリグラフ畳み込みネットワーク(Bi-GCN)を提案する。 我々のBi-GCNは、ネットワークパラメータと入力データの両方で平均31倍のメモリ消費を削減でき、推論速度を平均51倍に加速できる。
  論文  参考訳（メタデータ） (2022-10-24T12:05:17Z)
• Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems [24.63675651321079]
  BP(Breief Propagation)は、グラフィカルモデル上の様々な推論タスクのための重要なメッセージパッシングアルゴリズムである。 本研究では, DABP をスムーズなソリューションコストで自己教師付き学習する手法を提案する。 我々のモデルは最先端のベースラインを大きく上回る。
  論文  参考訳（メタデータ） (2022-09-24T13:03:46Z)
• Belief Propagation Neural Networks [103.97004780313105]
  信念伝播ニューラルネットワーク(BPNN)を紹介する。 BPNNは因子グラフ上で動作し、信念伝播(BP)を一般化する BPNNはIsingモデル上で1.7倍高速に収束し、より厳密な境界を提供することを示す。 挑戦的なモデルカウント問題に関して、BPNNは最先端の手作り手法の100倍の速さを推定する。
  論文  参考訳（メタデータ） (2020-07-01T07:39:51Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  低次元問題に対する高密度固定グラフ上のGNNと高次元問題に対するサンプリングベースGNNの2つの手法を提案する。 RRT(Rapidly-Exploring Random Trees)におけるクリティカルノードの特定やサンプリング分布の学習といった計画上の問題にGNNが取り組む能力について検討する。 臨界サンプリング、振り子、6つのDoFロボットアームによる実験では、GNNは従来の分析手法の改善だけでなく、完全に接続されたニューラルネットワークや畳み込みニューラルネットワークを用いた学習アプローチも示している。
  論文  参考訳（メタデータ） (2020-06-11T08:19:06Z)

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

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