Directed Graph Grammars for Sequence-based Learning
Michael Sun, Orion Foo, Gang Liu, Wojciech Matusik, Jie Chen · 2025
Read Directed Graph Grammars for Sequence-based Learning by Michael Sun, Orion Foo, Gang Liu, Wojciech Matusik, Jie Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22949.txt.
Introduction
Michael Sun, Orion Foo, Gang Liu, Wojciech Matusik, and Jie Chen turn directed acyclic graphs into sequences so sequence models can learn from them. Their 2025 paper notes that graphs with no cycles appear everywhere: circuits, Bayesian networks, and neural architectures among them. Encoding such graphs is well solved, but decoding them is awkward, because a graph's nodes admit many valid orderings and no canonical sequence.
The authors impose a grammar on graph construction. Each graph becomes the unique sequence of production rules that builds it, like a sentence parsed from a grammar. That sequence is a lossless compression of the graph. With it, researchers can train generative models of graphs, learn latent spaces for property prediction, and run Bayesian optimization over structured objects. Code is public.
Catalog record
| CREATOR | Michael Sun, Orion Foo, Gang Liu, Wojciech Matusik, Jie Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22949
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Directed Graph Grammars for Sequence-based Learning Michael Sun, Orion Foo, Gang Liu, Wojciech Matusik, Jie Chen Abstract 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 . 1 Introduction Directed acyclic graphs (DAGs) underlie many applications in computer science and engineering, from neural architectures ( Hutter et al., 2019 ) , Bayesian networks ( Koller, 2009 ) , analog circuits, financial transactions, to linearized representations of molecules ( Weininger, 1988 ) . Recently, specialized generative models for graphs have been proposed ( Li et al., 2018 ; Simonovsky & Komodakis, 2018 ; De Cao & Kipf, 2018 ; Ma et al., 2018 ; Jin et al., 2018 ; Liu et al., 2018b ; You et al., 2018a ; Bojchevski et al., 2018 ) , with well-motivated encoding schemes that respect graph-specific invariances. However, principled solutions for decoding graphs are still lacking. For example, current methods propose decoding a graph autoregressively by adding nodes and edges, or fragments and connections, at every time step according to some arbitrary ordering ( Kusner et al., 2017 ; Li et al., 2018 ; Zhang et al., 2019 ; Thost & Chen, 2021 ) . However, these methods lack rigor and suffer from combinatorial intractability because there can be an exponential number of possible decoding orders. On the other hand, graph grammars, which represent graphs as derivations over a formal language that views subgraphs as “words”, have shown enhanced modeling ( Jin et al., 2018 ) and data efficiency ( Guo et al., 2022 ; Sun et al., 2024 ) , but their decoding ability remains limited, lacking behind the progress of generative models for sequential data like natural language. The heart of this issue lies in the absence of a rigorous mapping between the space of graphs and the space of sequences. Given an ideal tokenization strategy, graph modeling reduces to sequence modeling, where innovations like Transformers ( Vaswani, 2017 ) and generative pretraining ( Achiam et al., 2023 ) have made significant progress. In this work, we propose a novel and faithful mapping that respects several key properties: it is (1) one-to-one and (2) onto over the observed data, (3) deterministic, (4) valid, and (5) strives for Occam’s Razor. Our key insight is to parse graphs according to a context-free graph grammar that is constrained to exhibit linear parse trees, producing a sequence of graph rewrite rules that serves as an equivalent, lossless sequential representation for the graph. We implement this mapping for DAGs, using properties specific to DAGs to make the realization of this ideal mapping efficient in practice. Our method, DI rected G raph G rammar E mbedded D erivations ( DIGGED ) seeks to compress a dataset of given DAGs into parse sequences, incrementally constructing the underlying graph grammar and invoking the principle of Minimum Description Length (MDL). Our contributions include: • Definitions of the properties for an ideal mapping between DAGs and sequences; • Novel grammar induction algorithm which respects these properties, with theoretical guarantees; • Integration within an autoencoder framework for generation, prediction and optimization; • Comprehensive experiments on real-world applications in neural architectures, Bayesian Networks, and circuits, demonstrating better performance and representation quality compared with existing DAG learning frameworks; • Case studies to interpret and explain our method, highlighting built-in advantages of our method. By establishing a theoretically motivated mapping between DAGs and sequences, our work offers a new perspective on graph generative modeling and an opportunity to integrate graph data natively into natural language models. 2 Related Works 2.1 Learning and Optimization of DAGs DAGs underlie core problems in computer science, such as Bayesian Network structure learning and neural architecture search. Due to the underlying data being discrete (and the problem often NP-hard ( Chickering, 1996 ) ), existing works can be categorized into at least one of the following categories: (a) exact search ( Singh & Moore, 2005 ; Yuan et al., 2011 ; Yuan & Malone, 2013 ) , (b) approximate search ( Heckerman et al., 1995 ; Gao et al., 2017 ) , (c) continuous relaxation ( Liu et al., 2018a ; Luo et al., 2018 ; Zheng et al., 2018 ; Yu et al., 2019 ) , (d) Bayesian Optimization ( Yackley & Lane, 2012 ) , and (e) autoencoders ( Zhang et al., 2019 ; Thost & Chen, 2021 ) , with (e) being a modern approach that we adopt. Autoencoders ( Kingma, 2013 ; Rezende et al., 2014 ) that build a latent space are appealing because they naturally support three downstream tasks: (1) unconditional generation, (2) property prediction from encoded latent embeddings, and (3) optimization over a smooth, continuous space ( Zhang et al., 2019 ) . For example, the approach of learning surrogates and optimizing within a smooth continuous space is common in other domains ( Mueller et al., 2017 ; Gómez-Bombarelli et al., 2018 ) . Graph autoencoders that use popular message passing paradigms have gained widespread adoption ( Kipf & Welling, 2016 ; Hamilton et al., 2017 ) , but graph decoders have not evolved beyond strategies that incrementally add atoms/edges or fragments/connections according to an arbitrary order ( Li et al., 2018 ; You et al., 2018b ; Zhang et al., 2019 ; Sun et al., 2024 ) . 2.2 Graph Grammars Graph Grammars ( Engelfriet & Rozenberg, 1997 ; Janssens & Rozenberg, 1982 ) are precise and formal descriptions of graph transformations. Analogous to string grammars, graph grammars are formal languages that include a vocabulary of subgraphs and a set of rewrite rules. Recently, learning substructure-based graph grammars has become popular for molecules ( Jin et al., 2018 ; Guo et al., 2022 ; Sun et al., 2024 ) , as motifs like functional groups provide useful abstractions for enhanced interpretability and modeling efficiency over string-based representations ( Weininger, 1988 ) . Despite their usefulness, grammars cannot model every language ( Chomsky, 1959 ) , whereas probabilistic Language Models can model arbitrary distributions of sentences. We show how Transformers ( Vaswani, 2017 ) can be adopted for grammar-based graph decoding, combining the best of both worlds. 2.3 Concept Induction on Graphs Concepts, motifs or subgraphs are related ways of expressing patterns on graphs. Unsupervised induction of these patterns takes many forms, but the common theme which guides these approaches is Minimum Description Length (MDL), an example of Occam’s Razor. The most common