Fugu-MT 論文翻訳(概要): Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search

論文の概要: Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search

arxiv url: http://arxiv.org/abs/2305.00535v1
Date: Sun, 30 Apr 2023 17:15:38 GMT
ステータス: 処理完了
システム内更新日: 2023-05-02 14:46:45.524969
Title: Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search
Title（参考訳）: グラフニューラルネットワークを用いたモンテカルロ木探索によるほぼ最適スタイナー木
Authors: Reyan Ahmed, Mithun Ghosh, Kwang-Sung Jun, Stephen Kobourov
Abstract要約: グラフニューラルネットワークとモンテカルロ木探索を組み合わせたステイナツリーの計算手法について述べる。まず、部分解として入力されるグラフニューラルネットワークをトレーニングし、出力として追加される新しいノードを提案する。このニューラルネットワークはモンテカルロ探索でスタイナー木を計算するのに使用される。
参考スコア（独自算出の注目度）: 9.061356032792952
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Graph neural networks are useful for learning problems, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing Steiner Trees by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a Steiner tree. The proposed method consistently outperforms the standard 2-approximation algorithm on many different types of graphs and often finds the optimal solution.
Abstract（参考訳）: グラフニューラルネットワークは、学習問題だけでなく、部分グラフ同型問題やトラベルセールスマン問題といった組合せ問題やグラフ問題にも有用である。本稿では,グラフニューラルネットワークとモンテカルロ木探索を組み合わせたスタイナー木計算手法について述べる。まず,部分解を入力とするグラフニューラルネットワークを訓練し,新たなノードを出力として追加することを提案する。このニューラルネットワークはモンテカルロ探索でスタイナー木を計算するのに使用される。提案手法は,多種多様なグラフの標準2近似アルゴリズムを一貫して上回っており,最適解を求めることが多い。

関連論文リスト

LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文参考訳（メタデータ） (2024-07-18T22:05:21Z)
Solving the Tree Containment Problem Using Graph Neural Networks [0.6081917632687639]
木含量は、植物遺伝学において、提案された系統ネットワークを検証するのに有用な問題である。本稿では,グラフニューラルネットワークを用いて大まかに解くことを提案する。本アルゴリズムは,最大100個の葉を持つインスタンスにおける木封じ込め問題の解法において,95%以上の精度を示す。
論文参考訳（メタデータ） (2024-04-15T14:10:06Z)
GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection [51.608147732998994]
グラフニューラルネットワークは、グラフベースの機械学習の選択フレームワークになりつつある。本稿では,古典的メッセージパッシングに代えて,ノード特徴の局所分布を解析するグラフニューラルネットワークアーキテクチャを提案する。
論文参考訳（メタデータ） (2024-01-17T13:04:23Z)
Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search [9.128418945452088]
グラフニューラルネットワークとモンテカルロ木探索を組み合わせたグラフスペーサーの計算手法について述べる。まず、部分解として入力されるグラフニューラルネットワークをトレーニングし、出力として追加される新しいノードを提案する。このニューラルネットワークはモンテカルロ探索に使われ、スペーサーを計算する。
論文参考訳（メタデータ） (2023-11-17T03:59:50Z)
NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文参考訳（メタデータ） (2023-06-14T09:21:15Z)
Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
ノードの集合が与えられるグラフ上のスタイナー木問題を考える。目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
論文参考訳（メタデータ） (2022-08-25T10:31:00Z)
Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
論文参考訳（メタデータ） (2022-07-21T04:47:21Z)
Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
本稿では,スタイナーツリー問題に取り組む。低コストのSteiner木を計算するために4つの学習フレームワークを使用します。我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
論文参考訳（メタデータ） (2021-08-18T19:55:16Z)
Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks [74.26734952400925]
ノード埋め込み次元選択(NEDS)のための最小グラフエントロピー(MinGE)アルゴリズムを提案する。ミンゲは、グラフ上の特徴エントロピーと構造エントロピーの両方を考えており、それらはそれらのリッチな情報の特徴に従って慎重に設計されている。ベンチマークデータセット上で人気のグラフニューラルネットワーク(GNN)を用いた実験は,提案したMinGEの有効性と一般化性を示す。
論文参考訳（メタデータ） (2021-05-07T11:40:29Z)
Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文参考訳（メタデータ） (2020-10-20T05:54:31Z)
Neural Subgraph Matching [57.05893848555512]
NeuroMatchは、サブグラフマッチングに対する正確で効率的で堅牢な神経アプローチである。 NeuroMatchは、既存の幾何学的アプローチよりも100倍高速で、既存のサブグラフマッチング手法よりも18%精度が高い。
論文参考訳（メタデータ） (2020-07-06T22:06:38Z)

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