用ReLU网络精确生成指定编辑距离内的树结构，理论与实证结合。
Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance
- 基于ReLU构造固定深度网络，可生成与目标树编辑距离不超过d的所有树
- 网络规模为O(n³)，在21节点以内能100%生成所有合法树
- 相比随机性模型，本方法生成准确率显著更高，适合精准树数据生成
树编辑距离的指定生成在计算生物学、结构化数据分析和图像处理中有重要应用。现有生成网络在适配特定编辑距离时缺乏理论依据。本文首次证明：对于大小为n+1的有根有序带标签树T（标签来自字母表Σ）及非负整数d，所有与T编辑距离≤d的有根有序带标签树均可由一个尺寸为O(n³)、常数深度的ReLU生成网络实现。所提网络在最多21个节点的测试中成功生成了全部有效树。而主流图生成模型GraphRNN与GraphGDP依赖非确定机制，验证率仅达35%和48%。结果为紧凑生成模型设计提供理论支撑，并开辟精确树结构数据生成的新方向。代码已开源：https://github.com/MGANN-KU/TreeGen_ReLUNetworks。
原文摘要 · Abstract (English)
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 Σ, and a non-negative integer d, we prove that all rooted, ordered, and vertex-labeled trees over Σ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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。