論文の概要: Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2111.10810v1
• Date: Sun, 21 Nov 2021 12:53:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-24 07:41:35.395970
• Title: Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
• Title（参考訳）: vulcan: グラフニューラルネットワークと深層強化学習によるsteiner tree問題の解法
• Authors: Haizhou Du and Zong Yan and Qiao Xiang and Qinqing Zhan
• Abstract要約: 我々は,新しいグラフネットワークと深層強化学習に基づく新しいモデルVulcanを設計する。 ヴァルカンはまた、幅広いNPハード問題に対する解を見つけることもできる。
• 参考スコア（独自算出の注目度）: 2.419365674940108
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Steiner Tree Problem (STP) in graphs aims to find a tree of minimum weight in the graph that connects a given set of vertices. It is a classic NP-hard combinatorial optimization problem and has many real-world applications (e.g., VLSI chip design, transportation network planning and wireless sensor networks). Many exact and approximate algorithms have been developed for STP, but they suffer from high computational complexity and weak worst-case solution guarantees, respectively. Heuristic algorithms are also developed. However, each of them requires application domain knowledge to design and is only suitable for specific scenarios. Motivated by the recently reported observation that instances of the same NP-hard combinatorial problem may maintain the same or similar combinatorial structure but mainly differ in their data, we investigate the feasibility and benefits of applying machine learning techniques to solving STP. To this end, we design a novel model Vulcan based on novel graph neural networks and deep reinforcement learning. The core of Vulcan is a novel, compact graph embedding that transforms highdimensional graph structure data (i.e., path-changed information) into a low-dimensional vector representation. Given an STP instance, Vulcan uses this embedding to encode its pathrelated information and sends the encoded graph to a deep reinforcement learning component based on a double deep Q network (DDQN) to find solutions. In addition to STP, Vulcan can also find solutions to a wide range of NP-hard problems (e.g., SAT, MVC and X3C) by reducing them to STP. We implement a prototype of Vulcan and demonstrate its efficacy and efficiency with extensive experiments using real-world and synthetic datasets.
• Abstract（参考訳）: グラフにおけるシュタイナー木問題(stp)は、与えられた頂点の集合を連結するグラフの最小重みの木を見つけることを目的としている。 これは古典的なNPハード組合せ最適化問題であり、多くの実世界の応用(VLSIチップ設計、輸送ネットワーク計画、無線センサーネットワークなど)がある。 多くの正確なアルゴリズムと近似アルゴリズムがSTP向けに開発されているが、それぞれ高い計算複雑性と弱い最悪の解保証に悩まされている。 ヒューリスティックアルゴリズムも開発されている。 しかし、それぞれが設計にアプリケーションドメインの知識を必要とし、特定のシナリオにのみ適合します。 最近報告された、同じnp-hard combinatorial問題の例が、同一または類似の組合せ構造を維持できるが、そのデータは主に異なるという観測結果に動機づけられ、stpの解法に機械学習技術を適用する可能性と利点について検討した。 そこで我々は,新しいグラフニューラルネットワークと深層強化学習に基づく新しいモデルVulcanを設計する。 Vulcanのコアは、高次元グラフ構造データ(すなわち、パス変更情報)を低次元ベクトル表現に変換する、新しくてコンパクトなグラフ埋め込みである。 STPインスタンスが与えられた場合、Vulcanはこの埋め込みを使用してパス関連情報をエンコードし、二重深度Qネットワーク(DDQN)に基づいた深度強化学習コンポーネントに符号化されたグラフを送信する。 STPに加えて、VulcanはSTPに還元することで、幅広いNPハード問題(SAT、MVC、X3Cなど)の解決策を見つけることができる。 Vulcanのプロトタイプを実装し、実世界および合成データセットを用いた広範囲な実験により、その有効性と効率を実証する。

関連論文リスト

• GradINN: Gradient Informed Neural Network [2.287415292857564]
  物理情報ニューラルネットワーク(PINN)にヒントを得た手法を提案する。 GradINNは、システムの勾配に関する事前の信念を利用して、予測関数の勾配を全ての入力次元にわたって制限する。 非時間依存システムにまたがる多様な問題に対するGradINNの利点を実証する。
  論文  参考訳（メタデータ） (2024-09-03T14:03:29Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• DRGCN: Dynamic Evolving Initial Residual for Deep Graph Convolutional Networks [19.483662490506646]
  我々はDRGCN(Residual Graph Convolutional Network)と呼ばれる新しいモデルを提案する。 実験結果から, 深部GCNの過密化問題を効果的に解消できることが示唆された。 我々のモデルはOpen Graph Benchmark (OGB) の大規模ogbn-arxivデータセット上で新しいSOTA結果に達する。
  論文  参考訳（メタデータ） (2023-02-10T06:57:12Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  我々は、最近のニューラルネットワークが実際に重要なグラフ問題にどのように適用できるのか、その分析を行う。 距離問題の構造的表現を増大させることは、多目的自律型問題解決者を学ぶという、まだ曖昧な目標に向けた有望なステップであることを示す。
  論文  参考訳（メタデータ） (2022-01-03T14:14:28Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
  本稿では,スタイナーツリー問題に取り組む。 低コストのSteiner木を計算するために4つの学習フレームワークを使用します。 我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
  論文  参考訳（メタデータ） (2021-08-18T19:55:16Z)
• An Introduction to Robust Graph Convolutional Networks [71.68610791161355]
  本論文では, 誤りのある単一ビューあるいは複数ビューのデータに対して, 新たなロバストグラフ畳み込みニューラルネットワークを提案する。 従来のグラフ畳み込みネットワークにAutoencodersを介して余分なレイヤを組み込むことで、典型的なエラーモデルを明示的に特徴付けおよび処理します。
  論文  参考訳（メタデータ） (2021-03-27T04:47:59Z)
• Geometrically Principled Connections in Graph Neural Networks [66.51286736506658]
  我々は、幾何学的深層学習の新興分野におけるイノベーションの原動力は、幾何が依然として主要な推進力であるべきだと論じている。 グラフニューラルネットワークとコンピュータグラフィックスとデータ近似モデルとの関係:放射基底関数(RBF) 完全連結層とグラフ畳み込み演算子を組み合わせた新しいビルディングブロックであるアフィンスキップ接続を導入する。
  論文  参考訳（メタデータ） (2020-04-06T13:25:46Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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