論文の概要: Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance

• arxiv url: http://arxiv.org/abs/2510.10706v1
• Date: Sun, 12 Oct 2025 17:07:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:30.07816
• Title: Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance
• Title（参考訳）: 木編集距離を持つ木を列挙するReLU生成ネットワークの設計
• Authors: Mamoona Ghafoor, Tatsuya Akutsu,
• Abstract要約: 我々は,木編集距離に関して,所定の木に類似した木を生産できる生成ネットワークの存在と構築を確立する。 ネットワークは、指定されたツリー編集距離内で有効な木を全て生成した。 これらの知見は、コンパクトな生成モデルの構築と、正確かつ有効な木構造データ生成のための新しい方向を開くための理論的基盤を提供する。
• 参考スコア（独自算出の注目度）: 3.746431245783676
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The generation of trees with a specified tree edit distance has significant applications across various fields, including computational biology, structured data analysis, and image processing. Recently, generative networks have been increasingly employed to synthesize new data that closely resembles the original datasets. However, the appropriate size and depth of generative networks required to generate data with a specified tree edit distance remain unclear. In this paper, we theoretically establish the existence and construction of generative networks capable of producing trees similar to a given tree with respect to the tree edit distance. Specifically, for a given rooted, ordered, and vertex-labeled tree T of size n + 1 with labels from an alphabet \Sigma, and a non-negative integer d, we prove that all rooted, ordered, and vertex-labeled trees over \Sigma with tree edit distance at most d from T can be generated using a ReLU-based generative network with size O(n^3 ) and constant depth. The proposed networks were implemented and evaluated for generating trees with up to 21 nodes. Due to their deterministic architecture, the networks successfully generated all valid trees within the specified tree edit distance. In contrast, state-of-the-art graph generative models GraphRNN and GraphGDP, which rely on non-deterministic mechanisms, produced significantly fewer valid trees, achieving validation rates of only up to 35% and 48%, respectively. These findings provide a theoretical foundation towards construction of compact generative models and open new directions for exact and valid tree-structured data generation. An implementation of the proposed networks is available at https://github.com/MGANN-KU/TreeGen_ReLUNetworks.
• Abstract（参考訳）: 特定の木編集距離を持つ木の生成は、計算生物学、構造化データ解析、画像処理など、様々な分野に重要な応用をもたらす。 近年、生成ネットワークは、元のデータセットによく似た新しいデータを合成するためにますます使われてきている。 しかし、木編集距離を指定したデータを生成するのに必要な生成ネットワークのサイズと深さは未定である。 本稿では,木編集距離に関して,木に類似した木を生産できる生成ネットワークの存在と構築を理論的に確立する。 具体的には、アルファベット \Sigma と非負整数 d のラベルを持つ n + 1 の大きさの根付き順序付き頂点ラベル付き木 T に対して、T から d までのツリー編集距離が最大であるすべてのルート付き、順序付き、頂点ラベル付き木は、サイズ O(n^3 ) と定数深さを持つ ReLU ベースの生成ネットワークを用いて生成可能であることを証明している。 提案したネットワークは,21個のノードを持つ木を生成するために実装され,評価された。 決定論的アーキテクチャのため、ネットワークは指定された木編集距離内で有効な木を全て生成することができた。 対照的に、非決定論的メカニズムに依存している最先端グラフ生成モデルであるGraphRNNとGraphGDPは、それぞれ35%と48%のバリデーション率しか達成できない、極めて少ない有効木を生み出した。 これらの知見は、コンパクトな生成モデルの構築と、正確かつ有効な木構造データ生成のための新しい方向を開くための理論的基盤を提供する。 提案されたネットワークの実装はhttps://github.com/MGANN-KU/TreeGen_ReLUNetworksで公開されている。

関連論文リスト

• Hierarchical Quantized Diffusion Based Tree Generation Method for Hierarchical Representation and Lineage Analysis [49.00783841494125]
  HDTreeは階層的潜在空間内の木関係を、統一的な階層的コードブックと量子化拡散プロセスを用いてキャプチャする。 HDTreeの有効性は、汎用データセットと単一セルデータセットの比較によって示される。 これらの貢献は階層的な系統解析のための新しいツールを提供し、より正確で効率的な細胞分化経路のモデリングを可能にする。
  論文  参考訳（メタデータ） (2025-06-29T15:19:13Z)
• Autoregressive Generation of Static and Growing Trees [49.93294993975928]
  本稿では,ツリー生成のためのトランスフォーマーアーキテクチャとトレーニング戦略を提案する。 アーキテクチャはデータを複数の解像度で処理し、1時間ガラスの形状を持ち、中間層は外側層よりも少ないトークンを処理する。 我々は,この手法を拡張して,イメージ・ツー・ツリーとポイント・クラウド・ツー・ツリー条件生成を行い,木の成長過程をシミュレートし,4D木を生成する。
  論文  参考訳（メタデータ） (2025-02-07T08:51:14Z)
• Heterogeneous Graph Neural Network on Semantic Tree [11.810900066591861]
  HetTreeは、グラフ構造とヘテロジニアスの両方をスケーラブルで効果的な方法でモデル化する、新しいHGNNである。 セマンティックツリーを効果的にエンコードするために、HetTreeは、親子関係をエンコードするのに役立つメタパスを強調するために、新しいサブツリーアテンションメカニズムを使用している。 さまざまな実世界のデータセット上でのHetTreeの評価は、既存のすべてのベースラインをオープンベンチマークで上回っていることを示す。
  論文  参考訳（メタデータ） (2024-02-21T03:14:45Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Improving the Validity of Decision Trees as Explanations [2.457872341625575]
  葉ノード間の最大誤分類誤差を最小限に抑えるために,浅い木を訓練する。 浅い木の全体的な統計性能は最先端の手法に匹敵する。
  論文  参考訳（メタデータ） (2023-06-11T21:14:29Z)
• DeepTree: Modeling Trees with Situated Latents [8.372189962601073]
  そこで本研究では,木を手作業で定義するのではなく,分岐構造に対する発達規則を学習する手法を提案する。 我々は、その振る舞いが本質的な状態によって決定されるため、潜伏状態にあるディープニューラルモデル(deep Neural model)と呼ぶ。 本手法では,複雑なパラメータを定義することなく,多様な木形を生成することができる。
  論文  参考訳（メタデータ） (2023-05-09T03:33:14Z)
• Structure-Unified M-Tree Coding Solver for MathWord Problem [57.825176412485504]
  従来,数式表現の2次木構造を考慮に入れたモデルでは,性能が向上した。 本稿では、出力構造を統一するために、任意のM枝(M-tree)を持つ木を適用した構造統一M-Tree符号化(S-UMCr)を提案する。 広く使われているMAWPSとMath23Kデータセットの実験結果は、SUMC-rが複数の最先端モデルを上回るだけでなく、低リソース条件下でもはるかに優れた性能を発揮することを示した。
  論文  参考訳（メタデータ） (2022-10-22T12:20:36Z)
• 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)

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

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