論文の概要: Solving the Tree Containment Problem Using Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2404.09812v2
• Date: Thu, 13 Jun 2024 09:20:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-14 23:16:04.442756
• Title: Solving the Tree Containment Problem Using Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークを用いた木含量問題の解法
• Authors: Arkadiy Dushatskiy, Esther Julien, Leen Stougie, Leo van Iersel,
• Abstract要約: 木含量は、植物遺伝学において、提案された系統ネットワークを検証するのに有用な問題である。 本稿では,グラフニューラルネットワークを用いて大まかに解くことを提案する。 本アルゴリズムは,最大100個の葉を持つインスタンスにおける木封じ込め問題の解法において,95%以上の精度を示す。
• 参考スコア（独自算出の注目度）: 0.6081917632687639
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tree Containment is a fundamental problem in phylogenetics useful for verifying a proposed phylogenetic network, representing the evolutionary history of certain species. Tree Containment asks whether the given phylogenetic tree (for instance, constructed from a DNA fragment showing tree-like evolution) is contained in the given phylogenetic network. In the general case, this is an NP-complete problem. We propose to solve it approximately using Graph Neural Networks. In particular, we propose to combine the given network and the tree and apply a Graph Neural Network to this network-tree graph. This way, we achieve the capability of solving the tree containment instances representing a larger number of species than the instances contained in the training dataset (i.e., our algorithm has the inductive learning ability). Our algorithm demonstrates an accuracy of over $95\%$ in solving the tree containment problem on instances with up to 100 leaves.
• Abstract（参考訳）: 木含量は、特定の種の進化の歴史を表す、提案された系統ネットワークを検証するのに有用な系統学の基本的な問題である。 Tree Containmentは、与えられた系統樹(例えば、木のような進化を示すDNA断片から作られる)が与えられた系統網に含まれるかどうかを問う。 一般の場合、これはNP完全問題である。 本稿では,グラフニューラルネットワークを用いて大まかに解くことを提案する。 特に、与えられたネットワークとツリーを組み合わせて、このネットワークツリーグラフにグラフニューラルネットワークを適用することを提案する。 このようにして、トレーニングデータセットに含まれるインスタンス(つまり、我々のアルゴリズムは帰納的学習能力を持つ)よりも多くの種を表わすツリー封じ込めのインスタンスを解くことができる。 本アルゴリズムは,最大100個の葉を持つ場合の樹木封じ込め問題の解法において,9,5 %以上の精度を示す。

関連論文リスト

• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。 このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
  論文  参考訳（メタデータ） (2023-12-16T14:09:23Z)
• ARTree: A Deep Autoregressive Model for Phylogenetic Inference [6.935130578959931]
  グラフニューラルネットワーク(GNN)に基づく系統推定のための深層自己回帰モデルを提案する。 本研究では,本手法の有効性と効率を,実データツリーのトポロジー密度推定と変分系統推定問題のベンチマークで実証する。
  論文  参考訳（メタデータ） (2023-10-14T10:26:03Z)
• 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)
• Graph Tree Neural Networks [0.43012765978447565]
  グラフツリーニューラルネットワーク(GTNN)は、人間のニューラルネットワークの構造を分析することによって、既存のネットワークの問題を解決するように設計されている。 GTNNでは、情報ユニットはグラフの形式と関連付けられ、その後再び大きな情報の単位となり、他の情報ユニットと関係を持つ。
  論文  参考訳（メタデータ） (2021-10-31T07:58:00Z)
• Dive into Layers: Neural Network Capacity Bounding using Algebraic Geometry [55.57953219617467]
  ニューラルネットワークの学習性はそのサイズと直接関連していることを示す。 入力データとニューラルネットワークのトポロジ的幾何学的複雑さを測定するためにベッチ数を用いる。 実世界のデータセットMNISTで実験を行い、分析結果と結論を検証した。
  論文  参考訳（メタデータ） (2021-09-03T11:45:51Z)
• Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
  本稿では,スタイナーツリー問題に取り組む。 低コストのSteiner木を計算するために4つの学習フレームワークを使用します。 我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
  論文  参考訳（メタデータ） (2021-08-18T19:55:16Z)
• Neural Trees for Learning on Graphs [19.05038106825347]
  グラフニューラルネットワーク(GNN)は、グラフを学習するための柔軟で強力なアプローチとして登場した。 我々はニューラルツリーという新しいGNNアーキテクチャを提案する。 神経木アーキテクチャは無向グラフ上の任意の滑らかな確率分布関数を近似できることを示す。
  論文  参考訳（メタデータ） (2021-05-15T17:08:20Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  本研究では,高次元scRNA-seqデータから意味のある木構造を同定する手法を提案する。 次に、低次元空間におけるデータのツリー構造を強調する木バイアスオートエンコーダDTAEを紹介する。
  論文  参考訳（メタデータ） (2021-02-11T08:48:48Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
  様々なタイプのランダムグラフに対応するアーキテクチャを用いて,ニューラルネットワークの大規模評価を行う。 古典的な数値グラフ不変量は、それ自体が最良のネットワークを選び出すことができない。 また、主に短距離接続を持つネットワークは、多くの長距離接続が可能なネットワークよりも性能が良いことも見出した。
  論文  参考訳（メタデータ） (2020-02-19T11:04:49Z)

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

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