用语法生成器将有向无环图转为唯一序列，实现无损压缩与结构化数据优化。
Directed Graph Grammars for Sequence-based Learning
- 基于无歧义语法将DAG转换为唯一序列表示
- 实现图结构的无损压缩与连续序列编码
- 适用于图生成、属性预测和结构化贝叶斯优化
有向无环图（DAG）广泛应用于电子电路、贝叶斯网络和神经架构等领域。尽管已有多种有效的图编码方法，但如何以合理方式解码仍具挑战，因为DAG节点存在多种拓扑排序。本文提出一种基于语法的方法，构建DAG的唯一、紧凑且等价的序列表示：将图视为无歧义语法的推导过程，每个DAG对应唯一的产生式规则序列。该表示等价于数据的无损压缩。该方法可用于构建图生成的生成模型、学习属性预测的隐空间，以及利用序列表示的连续性在结构化数据上进行贝叶斯优化。代码已开源：https://github.com/shiningsunnyday/induction。
原文摘要 · Abstract (English)
Directed acyclic graphs (DAGs) are a class of graphs commonly used in practice, with examples that include electronic circuits, Bayesian networks, and neural architectures. While many effective encoders exist for DAGs, it remains challenging to decode them in a principled manner, because the nodes of a DAG can have many different topological orders. In this work, we propose a grammar-based approach to constructing a principled, compact and equivalent sequential representation of a DAG. Specifically, we view a graph as derivations over an unambiguous grammar, where the DAG corresponds to a unique sequence of production rules. Equivalently, the procedure to construct such a description can be viewed as a lossless compression of the data. Such a representation has many uses, including building a generative model for graph generation, learning a latent space for property prediction, and leveraging the sequence representational continuity for Bayesian Optimization over structured data. Code is available at https://github.com/shiningsunnyday/induction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。