Fugu-MT 論文翻訳(概要): Computing Steiner Trees using Graph Neural Networks

論文の概要: Computing Steiner Trees using Graph Neural Networks

arxiv url: http://arxiv.org/abs/2108.08368v1
Date: Wed, 18 Aug 2021 19:55:16 GMT
ステータス: 処理完了
システム内更新日: 2021-08-21 04:45:50.830720
Title: Computing Steiner Trees using Graph Neural Networks
Title（参考訳）: グラフニューラルネットワークを用いたステイナツリーの計算
Authors: Reyan Ahmed, Md Asadullah Turja, Faryad Darabi Sahneh, Mithun Ghosh, Keaton Hamm, and Stephen Kobourov
Abstract要約: 本稿では,スタイナーツリー問題に取り組む。低コストのSteiner木を計算するために4つの学習フレームワークを使用します。我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
参考スコア（独自算出の注目度）: 1.0159681653887238
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problems such as subgraph isomorphism, detecting cliques, and the traveling salesman problem. However, many NP-complete problems are as of yet unexplored using this method. In this paper, we tackle the Steiner Tree Problem. We employ four learning frameworks to compute low cost Steiner trees: feed-forward neural networks, graph neural networks, graph convolutional networks, and a graph attention model. We use these frameworks in two fundamentally different ways: 1) to train the models to learn the actual Steiner tree nodes, 2) to train the model to learn good Steiner point candidates to be connected to the constructed tree using a shortest path in a greedy fashion. We illustrate the robustness of our heuristics on several random graph generation models as well as the SteinLib data library. Our finding suggests that the out-of-the-box application of GNN methods does worse than the classic 2-approximation method. However, when combined with a greedy shortest path construction, it even does slightly better than the 2-approximation algorithm. This result sheds light on the fundamental capabilities and limitations of graph learning techniques on classical NP-complete problems.
Abstract（参考訳）: グラフニューラルネットワークは多くの学習問題や現実世界の応用で成功している。グラフニューラルネットワークの最近の研究は、グラフの同型性、傾きの検出、旅行セールスマン問題といった組合せアルゴリズムとグラフアルゴリズムの問題を解くための力を探っている。しかし、NP完全問題の多くは、この方法を用いてまだ解明されていない。本稿では,スタイナー木問題に取り組む。フィードフォワードニューラルネットワーク,グラフニューラルネットワーク,グラフ畳み込みネットワーク,グラフアテンションモデルという,低コストなSteinerツリーの計算に4つの学習フレームワークを採用している。 1)モデルに実際のSteinerツリーノードを学習させる、2)モデルに優れたSteinerポイント候補を学習させる、という2つの基本的な方法で、最も短いパスを使って構築されたツリーに接続する、という方法です。我々はいくつかのランダムグラフ生成モデルとSteinLibデータライブラリにおけるヒューリスティックスの堅牢性を説明する。以上の結果から,gnn法の適用範囲が従来の2近似法よりも低くなることが示唆された。しかし、欲望の短い経路構成と組み合わせると、2近似アルゴリズムよりもわずかに良い結果が得られる。この結果は、古典的なnp完全問題に対するグラフ学習技術の基本能力と限界に光を当てている。

関連論文リスト

LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文参考訳（メタデータ） (2024-07-18T22:05:21Z)
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)
Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search [9.061356032792952]
グラフニューラルネットワークとモンテカルロ木探索を組み合わせたステイナツリーの計算手法について述べる。まず、部分解として入力されるグラフニューラルネットワークをトレーニングし、出力として追加される新しいノードを提案する。このニューラルネットワークはモンテカルロ探索でスタイナー木を計算するのに使用される。
論文参考訳（メタデータ） (2023-04-30T17:15:38Z)
Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
論文参考訳（メタデータ） (2022-10-30T19:38:23Z)
Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文参考訳（メタデータ） (2022-10-27T16:00:45Z)
Graph-level Neural Networks: Current Progress and Future Directions [61.08696673768116]
グラフレベルのニューラルネットワーク(GLNN、ディープラーニングベースのグラフレベルの学習法)は、高次元データのモデリングにおいて優れているため、魅力的である。本稿では,深層ニューラルネットワーク,グラフニューラルネットワーク,グラフプール上でのGLNNを網羅する系統分類法を提案する。
論文参考訳（メタデータ） (2022-05-31T06:16:55Z)
Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning [2.419365674940108]
我々は,新しいグラフネットワークと深層強化学習に基づく新しいモデルVulcanを設計する。ヴァルカンはまた、幅広いNPハード問題に対する解を見つけることもできる。
論文参考訳（メタデータ） (2021-11-21T12:53:50Z)
Deep Neural Network for DrawiNg Networks, (DNN)^2 [1.5749416770494706]
本稿ではDNN(Deep Neural Network for DrawiNg Networks)と呼ばれる新しいグラフ描画フレームワークを提案する。グラフ描画におけるDeep Learningアプローチが新規であり,今後の作業における多くの手がかりが特定されているため,(DNN)2が良好に機能していることが示される。
論文参考訳（メタデータ） (2021-08-08T13:23:26Z)
Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-06-07T15:05:59Z)
Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
今回提案するグラフネットワーク層であるNode2Seqは,隣接ノードの重みを明示的に調整可能なノード埋め込みを学習する。対象ノードに対して,当手法は注意メカニズムを介して隣接ノードをソートし,さらに1D畳み込みニューラルネットワーク(CNN)を用いて情報集約のための明示的な重み付けを行う。また, 特徴学習のための非局所的情報を, 注意スコアに基づいて適応的に組み込むことを提案する。
論文参考訳（メタデータ） (2021-01-06T03:05:37Z)

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

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