論文の概要: Learning to Compare Nodes in Branch and Bound with Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2210.16934v1
• Date: Sun, 30 Oct 2022 19:38:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-01 15:39:58.020511
• Title: Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークによる分岐と境界におけるノードの比較学習
• Authors: Abdel Ghani Labassi and Didier Ch\'etelat and Andrea Lodi
• Abstract要約: 整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。 本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。 本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
• 参考スコア（独自算出の注目度）: 5.08128537391027
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural network model to tackle this problem, where the nodes are represented as bipartite graphs with attributes. Similar to prior work, we train our model to imitate a diving oracle that plunges towards the optimal solution. We evaluate our method by solving the instances in a plain framework where the nodes are explored according to their rank. On three NP-hard benchmarks chosen to be particularly primal-difficult, our approach leads to faster solving and smaller branch- and-bound trees than the default ranking function of the open-source solver SCIP, as well as competing machine learning methods. Moreover, these results generalize to instances larger than used for training. Code for reproducing the experiments can be found at https://github.com/ds4dm/learn2comparenodes.
• Abstract（参考訳）: 整数プログラミングにおける分岐とバウンドのアプローチは、次を探索するために空間の順序付け部分を必要とする。 本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。 以前の作業と同様、私たちはモデルをトレーニングして、最適なソリューションに向かうダイビングオラクルを模倣します。 本手法は,ノードのランクに応じて探索される平易なフレームワークを用いて,インスタンスを解くことで評価する。 NPハードな3つのベンチマークにおいて,提案手法は,オープンソースソルバSCIPのデフォルトランキング関数よりも高速に解き,分岐木や分岐木を小さくし,競合する機械学習手法も実現している。 さらに、これらの結果はトレーニングに使用するインスタンスよりも大きなインスタンスに一般化される。 実験を再現するためのコードはhttps://github.com/ds4dm/learn2comparenodesにある。

関連論文リスト

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
  論文  参考訳（メタデータ） (2023-09-29T19:55:56Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  本稿では,グラフ埋め込みを学習可能なGNNと互換性のあるモデリングフレームワークであるGNNRankを紹介する。 既存の手法と比較して,我々の手法が競争力があり,しばしば優れた性能を発揮することを示す。
  論文  参考訳（メタデータ） (2022-02-01T04:19:50Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。 また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。 木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-01-25T17:37:34Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。 そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
  論文  参考訳（メタデータ） (2021-11-19T08:54:21Z)
• Evaluating Node Embeddings of Complex Networks [0.0]
  agood embeddedはグラフトポロジー、ノード間関係、およびグラフに関する他の関連情報をキャプチャする。 主な課題は、埋め込みがグラフの特性をうまく記述することを保証する必要があることである。 実世界のネットワーク上でも人工的に生成されたものでも、選択したグラフ埋め込みアルゴリズムを用いて一連の実験を行う。
  論文  参考訳（メタデータ） (2021-02-16T16:55:29Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  今回提案するグラフネットワーク層であるNode2Seqは,隣接ノードの重みを明示的に調整可能なノード埋め込みを学習する。 対象ノードに対して,当手法は注意メカニズムを介して隣接ノードをソートし,さらに1D畳み込みニューラルネットワーク(CNN)を用いて情報集約のための明示的な重み付けを行う。 また, 特徴学習のための非局所的情報を, 注意スコアに基づいて適応的に組み込むことを提案する。
  論文  参考訳（メタデータ） (2021-01-06T03:05:37Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)
• Neural Bipartite Matching [19.600193617583955]
  本稿では,ニューラルネットワークが複雑なアルゴリズムに適用される方法について述べる。 単一のGNNから生成された機能のみに基づいて、ニューラル実行によって実現される。 評価の結果,ネットワークがほぼ100%の時間で最適なマッチングを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-05-22T17:50:38Z)

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

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