Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance

• URL: http://arxiv.org/abs/2510.10706v1
• Date: Sun, 12 Oct 2025 17:07:49 GMT
• Title: Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance
• Authors: Mamoona Ghafoor, Tatsuya Akutsu,
• Abstract summary: We establish the existence and construction of generative networks capable of producing trees similar to a given tree with respect to the tree edit distance.<n>The networks successfully generated all valid trees within the specified tree edit distance.<n>These findings provide a theoretical foundation towards construction of compact generative models and open new directions for exact and valid tree-structured data generation.
• Score: 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.

Related papers

• TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees [73.0940890296463]
  probabilistic values are used to rank features for explaining local predicted values of decision trees.<n>TreeGrad computes the gradients of the multilinear extension of the joint objective in $O(L)$ time for decision trees with $L$ leaves.<n>TreeGrad-Ranker aggregates the gradients while optimizing the joint objective to produce feature rankings.<n>TreeGrad-Shap is a numerically stable algorithm for computing Beta Shapley values with integral parameters.
  arXiv  Detail & Related papers  (2026-02-12T06:17:12Z)
• Hierarchical Quantized Diffusion Based Tree Generation Method for Hierarchical Representation and Lineage Analysis [49.00783841494125]
  HDTree captures tree relationships within a hierarchical latent space using a unified hierarchical codebook and quantized diffusion processes.<n> HDTree's effectiveness is demonstrated through comparisons on both general-purpose and single-cell datasets.<n>These contributions provide a new tool for hierarchical lineage analysis, enabling more accurate and efficient modeling of cellular differentiation paths.
  arXiv  Detail & Related papers  (2025-06-29T15:19:13Z)
• Autoregressive Generation of Static and Growing Trees [49.93294993975928]
  We propose a transformer architecture and training strategy for tree generation.<n>The architecture processes data at multiple resolutions and has an hourglass shape, with middle layers processing fewer tokens than outer layers.<n>We extend this approach to perform image-to-tree and point-cloud-to-tree conditional generation and to simulate the tree growth processes, generating 4D trees.
  arXiv  Detail & Related papers  (2025-02-07T08:51:14Z)
• Heterogeneous Graph Neural Network on Semantic Tree [11.810900066591861]
  HetTree is a novel HGNN that models both the graph structure and heterogeneous aspects in a scalable and effective manner.<n>To effectively encode the semantic tree, HetTree uses a novel subtree attention mechanism to emphasize metapaths that are more helpful in encoding parent-child relationships.<n>Our evaluation of HetTree on a variety of real-world datasets demonstrates that it outperforms all existing baselines on open benchmarks.
  arXiv  Detail & Related papers  (2024-02-21T03:14:45Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• TreeFormer: a Semi-Supervised Transformer-based Framework for Tree Counting from a Single High Resolution Image [6.789370732159176]
  Tree density estimation and counting using single aerial and satellite images is a challenging task in photogrammetry and remote sensing. We propose the first semisupervised transformer-based framework for tree counting which reduces the expensive tree annotations for remote sensing images. Our model was evaluated on two benchmark tree counting datasets, Jiangsu, and Yosemite, as well as a new dataset, KCL-London, created by ourselves.
  arXiv  Detail & Related papers  (2023-07-12T12:19:36Z)
• Improving the Validity of Decision Trees as Explanations [2.457872341625575]
  We train a shallow tree with the objective of minimizing the maximum misclassification error across all leaf nodes. The overall statistical performance of the shallow tree can become comparable to state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-06-11T21:14:29Z)
• DeepTree: Modeling Trees with Situated Latents [8.372189962601073]
  We propose a novel method for modeling trees based on learning developmental rules for branching structures instead of manually defining them. We call our deep neural model situated latent because its behavior is determined by the intrinsic state. Our method enables generating a wide variety of tree shapes without the need to define intricate parameters.
  arXiv  Detail & Related papers  (2023-05-09T03:33:14Z)
• Structure-Unified M-Tree Coding Solver for MathWord Problem [57.825176412485504]
  In previous work, models designed by taking into account the properties of the binary tree structure of mathematical expressions at the output side have achieved better performance. In this paper, we propose the Structure-Unified M-Tree Coding Coding (S-UMCr), which applies a tree with any M branches (M-tree) to unify the output structures. Experimental results on the widely used MAWPS and Math23K datasets have demonstrated that SUMC-r not only outperforms several state-of-the-art models but also performs much better under low-resource conditions.
  arXiv  Detail & Related papers  (2022-10-22T12:20:36Z)
• A Tree-structured Transformer for Program Representation Learning [27.31416015946351]
  Long-term/global dependencies widely exist in programs, and most neural networks fail to capture these dependencies. In this paper, we propose Tree-Transformer, a novel tree-structured neural network which aims to overcome the above limitations. By combining bottom-up and top-down propagation, Tree-Transformer can learn both global contexts and meaningful node features.
  arXiv  Detail & Related papers  (2022-08-18T05:42:01Z)
• GTNet: A Tree-Based Deep Graph Learning Architecture [8.50892442127182]
  We propose a deep graph learning architecture with a new general message passing scheme that originates from the tree representation of graphs. Two graph representation learning models are proposed within this GTNet architecture - Graph Tree Attention Network (GTAN) and Graph Tree Convolution Network (GTCN)
  arXiv  Detail & Related papers  (2022-04-27T09:43:14Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.