Directed Graph Grammars for Sequence-based Learning
Authors: Michael Sun
Orion Foo
Gang Liu
Wojciech Matusik
Jie Chen
Venue: ICML 2025 poster (2025)
Keywords: graph generative model
graph mining
grammar
neurosymbolic
directed acyclic graphs
DAG
Primary area: deep_learning->graph_neural_networks
TL;DR: We establish a principled bijective problem mapping between DAG modeling and sequence modeling.

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.

Directed Graph Grammars for Sequence-based Learning
Michael Sun Orion Foo?
Gang Liu
Wojciech Matusik
Jie Chen
Abstract
graphs still lacking. For example, current methods pro- pose decoding 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). How- ever, 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 gram- mars, which represent graphs derivations over formal language that views subgraphs "words", have shown en- hanced 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 be- tween 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.
Directed acyclic graphs (DAGs) are class of graphs commonly used in practice, with exam- ples that include electronic circuits, Bayesian net- works, and neural architectures. While many ef- fective encoders exist for DAGs, it remains chal- lenging to decode them in principled manner, because the nodes of DAG can have many differ- ent topological orders. In this work, we propose a grammar-based approach to constructing princi- pled, compact and equivalent sequential represen- tation of a DAG. Specifically, we view graph as derivations over an unambiguous grammar, where the DAG corresponds to a unique sequence of production rules. Equivalently, the procedure construct such description can be viewed as lossless compression of the data. Such a rep- resentation has many uses, including building a generative model for graph generation, learning a latent space for property prediction, and lever- aging the sequence representational continuity for Bayesian Optimization over structured data. Code is available at https: / thub. com/ hww.annguummydaa/nnniiiii.o
In this work, we propose novel and faithful mapping that respects several key properties: it is (I) one-to-one and (2) onto over the observed data, (3) deterministic, (4) valid, and (5) strives for Occam's 's Razor. Our key insight is to parse graphs according to context-free graph grammar that is constrained to exhibit linear parse trees, producing a sequence of graph rewrite rules that serves as an equiv- alent, lossless sequential representation for the graph. We implement this mapping for DAGs, using properties specific to DAGs make the realization of this ideal mapping effi- cient in practice. Our method, DIrected Graph Grammar Embedded Derivations (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:
1. Introduction
Directed acyelic graphs (DAGs) underlie many applications in computer science and engineering, from neural architec- tures (Hutter et al., 2019), Bayesian networks (Koller, 2009), analog circuits, financial transactions, to linearized repre- sentations of molecules (Weininger, 1988). Recently, spe- cialized generative models for graphs have been proposed (Li et al., 2018; 8; Simonovsky Komodakis, 2018; De Cao & Kipf, 2018; Ma al., 2018; Jin et al., 2018; Liu al., 2018b; You et al., 201 8a; Bojchevski al., 2018), with well- motivated encoding schemes that respect graph-specific invariances. However, principled solutions for decoding
Definitions of the properties for ideal mapping between DAGs and sequences;
'MIT CSAIL 'MIT 'University of Notre Dame 'MIT-IBM Watson AI Lab, IBM Research. Correspondence to: Michael Sun <msun4150 @ csail.mi. eit.
Novel grammar induction algorithm which respects these
properties, with theoretical guarantees;
Integration within an autoencoder framework for genera- tion, prediction and optimization;
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Comprehensive experiments on real-world applications in neural architectures, Bayesian Networks, and circuits,

---

Directed Graph Grammars for Sequencc-based Learning
demonstrating better performance and representation qual- ity compared with existing DAG learning frameworks; Case studies to interpret and explain our method, high- lighting built-in advantages of our method.
Despite their usefulness, grammarr cannot model every lan- guage (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.
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.3. Concept Induction on Graphs
Concepts, motifs or subgraphs are related ways of express- ing 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 way to achieve the MDL of graphs is Frequent Subgraph Mining (FSM) (Holder, 1989; Gonzalez et al., 2000; Bandy- opadhyay et al., 2002). FSM, combined with graph gram- mar, has practical uses in graph compression (Maneth & Pe- ternek, 2018; Peternek, 2018; Busatto et al., 2004; Peshkin, 2007) and concept discovery (Holder et al., 1994; Holder & Cook, 1993; Cook & Holder, 2000; Djoko al., 1997; 1995; Cook et al., 1996; 1995; Jonyer et al., 2002), but its use for building modern generative models is unexplored.
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 archi- tecture search. Due to the underlying data being discrete (and the problem often NP-hard (Chickering, 1996)), ex- isting 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) approx- imate search (Heckerman et al., 1995; Gao et al., 2017). (c) continuous relaxation (Liu et al., 2a; Luo et al., 2018; Zheng et al., 2018; Yu et al., 2019), (d) Bayesian Opti- mization (Yackley & Lane, 2012), and (e) autoencoders (Zhang et al., 2019; Thost & Chen, 2021), with (e) being modern approach that we adopt. Autoencoders (Kingma, 2013; Rezende et al., 2014) that build latent space are appealing because they naturally support three downstream tasks: (1) unconditional generation, (2) property predic- tion from encoded latent embeddings, and (3) optimization over a smooth, continuous space (Zhang et al., 2019). For example, the approach of learning surrogates and optimiz- ing within smooth continuous space is common in other domains (Mueller et al., 2017; Kómmez-Bombarele et al., 2018). Graph autoencoders that use popular message pass- ing 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/coomeettins according to an arbi- trary order (Li et al., 2018; You al., 2018b; Zhang al., 2019; Sun et al., 2024).
3. Method
3.1. Preliminaries
Directed Graph Grammar. Edge-directed Neighborhood Controlled Embedding (edNCE) is a family of formal lan- guages over directed graphs with node labels (and optionally edge labels). Each grammar G = (E, N, T, P.S) contains vocabulary of node labels Σ, vocabulary of edge labels T, subset of non-terminal node labels N C Σ, an initial start la- bel S E N, and a set of production rules P. A node-labeled directed graph is a tuple H = (V, E, X) where V is the finite set of nodes, E C {(v, 7, w) v, w E V, & w,y E T} is the set of edges, and À V + Σ is the node-labeling function. We denote nodes and edges of H as Vn and Fn. Each rule is tuple (X, D. I), with "daughter" graph D, applicable to any "host" graph // containing a node n, s.t. X(n) = X E N. Applying the rule removes n from H. replaces it by a copy of D and embeds it to the remainder of H by forming edges following instructions in I. Formally, each instruction is the form (a, 3/7,, xr d/d') (a E Σ, 8, 7 E T, VD, d, d' E {in, out))) which when applied to Hf, has the semantics: "establish a d' eede labeled 7 to node x from each B-labeled d-neighbor with label o".
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 vo- cabulary of subgraphs and a set of rewrite rules. Recently, learning substructure-bbssed graph grammars has become popular for molecules (Jin al., 2018; Guo et al., 2022: Sun et al., 2024), motifs like functional groups provide useful abstractions for enhanced interpretability and modeling effi- ciency over braed representations (Weininger, 1988).
Terminologies. Given a dataset D of node-labeled directed graphs, induction is the task of constructing G from data; parsing the task of finding the derivation, for example, the sequence of rules, which produces given H. G is am- biguous if there is some data Hambigwoss with two distinct derivations, and H itself is labeled as ambiguous accord-
2

---

Directed Graph Grammars for Sequencc-based Learning
old edge
new edge
LHS edge
RHS instruction
Redirections
H1
H2
H3
e
g
2
d
a
C
a
2. Compute possible edge redirections
d
2
Check for compatibility among all occurrences
1. Identify candidate motif
2
2
?
?
4. Extract optimal grammar rule
(LHS
RHS)
non-terminal node 1i
daughter graph D
a²
e
g
d
"For each out-neighbor of add out-edges to both nodes of D
b
C
a'
a'
b
Figure 1. We adopt the edNCE grammar formalism. (Top): Dataset DD = (H,, H2, Hal: (Middle): Step (Sec 3.2.1). Our approximate frequent subgraph mining library finds candidate subgraphs. As an example, the induced subgraph from nodes & 2 in all three DAGs is considered. Its occurrences in Hi, H2, H3 are grounded. Step 2 (Sec 3.2.2). For each possible assignment of gray edge directions, hounds on the set of instructions are deduced. For example, the subgraph occurrence in H, includes into I, "for each green in-neighbor (gray), add out-edge (black) from node 2", and excludes from J, "for each green in-neighbor, add out-edge (black) from node 1". H2 includes into I: "for each green out-neighbor, add out-edges from both nodes 1 and 2". Suppose we had reversed the gray arrow in JT, Then, the exclusion set of case H1 conflicts with the inclusion set of H2, since it's unclear if we should add out-edges from both & 2 each green out-neighbor, or just node Intuitively, cases that differ the precondition of edge direction are labeled with separate letters (e.g. a vs b), inducing different but non-conflicting instructions. Step 3 (See 3.2.2). Given bounds on the instruction set for each motif occurrence, the final set of instructions deduced from the (approxinate) solution a max clique problem. Each node a (motif occurrence, edge redirections) realization. Each edge indicates compatibility. Step 4 (Sec 3.2.3). The candidate motif and the associated solution to Step 3 which minimizes the total data description length is chosen define grammar rule. Then, Steps 1-4 are repeated until convergence. (Bottom): grammar rule consists of a subgraph (gray) and instructions to connect it to the neighborhood. Instructions are grouped by letters, identifying the node label and its directional relationship to the parent gray node.
ing to G. A + B represents one rewriting step, and + the transitive relation, i.e. derivation. The language of G. denoted as L(G), is the set of non-isomorphic directed graphs { | S 4 H). Two directed graphs H1, H2 are isomorphic if there is some bijective mapping f of nodes, f: VH. - VH, s.t. (u, v) E Σd, + (f(w), E EHa- A subgraph H' of H = (V, E, A) is tuple (V', E', E','), X)) s.t. V' C V, E' = [(v, 7, w) E E l,we E VJ, V + Σ and X' is À restricted to V
isolated nodes (each with label S) and [D] parses according to its induced grammar Gp. We describe the main compu- tation steps of each iteration, emphasizing idcas rather than notation. Further details and pseudocode are in App. B.
3.2.1. FREQUENT SUBGRAPH MINING
The first step is to discover common motifs, that is, repeti- tive instances of the same subgraph, within the current H. We adopt the fast, approximate FSM library Subdue (Holder, 1989) on H to obtain a list of common motifs. Our key inno- vation is to process FSM outputs as follows: for components containing non-terminal node, only subgraphs with that non-terminal node are considered. This simplifies the parse tree to a rooted path. For each motif, we then ground the occurrences by running subgraph isomorphism, parallelized
3.2. Unsupervised Grammar Induction
Given a dataset D {H, | i 1.....|||]; we create the composite graph H = (U, Vn, U, Fn,)) with [D] con- nected components. Through an iterative lossless compres- sion algorithm, the description for H is refined to only [D]
3

---

Directed Graph Grammars for Sequencc-based Learning
across connected components of H, resulting in list of occurrences D1, D2,.... Dx, for each common motif D.
3.2.4. DISAMBIGUATION PROCEDURE
The final step of grammar induction is resolve ambigu- ity in G over D by modifying G + G'. Preventing this in general is impossible because determining whether given graph grammar G is ambiguous is undecidable (see App. C). Nevertheless, we can find all derivations for a given graph H, E D. This problem, in general, is NP-hard (Engelfriet & Rozenberg, 1997). We present a dynamic parsing programming algorithm that is the DAG counterpart to the well-known CYK algorithm (Cocke, 1969; Younger, 1967; Kasami, 1966) and takes advantage of two proper- ties specific to DAGs and our grammar. The first exploits the theoretical insight that DAGs have canonical string rep- resentations (more in App- D), enabling hashing-based memoization. The second prunes intermediate graphs that become disconnected or cyclic, as those are not valid in- termediate results (Deterministic property). After finding all derivations, we find the minimal set of rules that, when removed from G, leaves the largest subset of D with one unique derivation over G'. The formulation is in terms of the maximum hitting set problem. The algorithmic details are in App. C.
3.2.2. COMPATIBILITY MAXIMIZATION SOLVER
The second step is to, for each motif, find the maximal sub- set of occurrences that can be consistent with the same set of connection instructions. In Figure I, we see each occurrence of the candidate motif includes an incoming edge to node 1 from a red neighbor, so instruction (c) states: "establish an in-edge to node 1 from each in in-neighbor with label red".. From the second DAG, it appears the same instruction but for node 2 is needed. However, adding such an instruction would create a conflict with the motif"s occurrences in DAGs H2 and H3. as the red neighbor doesn't it connect to node 2 in those instances. Instead, our compatibility solver finds different set of instructions (two instructions with group label (d)) for which all three occurrences are compatible. Formally, the solver finds the optimal assignment to the vari- ables U [dg. By) Er E D2 s.t. x' neighbors y} where dy E {in, out). By E T, representing the direction and edge labels (if any) of the gray edges. The solver is formulated as a maximum-cliquee problem, where each node represents a possible assignment to 3y)) } for a specific occurrence k and an edge is created between two nodes if the variable assignments they contain are not in conflict with each other. At high level, each node carries with it an "inset" and "outset", representing the set of instructions that must be present and the set of instructions that must not be present, as deduced from the redirection assignments. Determining whether a node exists equates to checking Vinett O Voutset = 0 and whether an edge exists for u and v equates checking (Masse U Umsea) n (Moutset U Voutsa) = 0 (with some additional minor considerations). After obtaining the clique solution C== {v}, an or-reduction UPeC Vinset yields the minimal instruction set to include in a rule compatible with all oc- currences, and similarly Uvec Voutset yields the minimal instruction set to exclude. Any instruction set in-between permissible, and we apply dataset-specific heuristics in selecting the final instruction set for inducing rule.
3.3. Properties
We elaborate on how DIGGED addresses the limitations of existing methods (Table 1). We will analyze two broad cate- gories of methods: autoregressive generation (AG), which builds up graph incrementally, tracking the intermediate graph to decide the next action, and sequential decoding (SD), which directly generate descriptors that encode the adjacency information of the graph using some permutation of the nodes.
Table 1. DIGGED offers comprehensive guarantees that existing methods fail to partially address.
Methods
One-to-one?
Onto?
Deterministie?
Valid?
Stateless?
AG
SD
/
/
DIGGED
/
/
3.2.3. MINIMUM DESCRIPTION LENGTII
The third step follows after the previous step is repeated over all candidate motifs. We select the solution and its accompanying maximally compatible rule, based on the greedy objective: max [C[([D] - 1).. The contraction is the reverse operation of a rule application: for each k, remove DE. replace it by non-terminal node nig, and add edges according to the solution's 's assignment for { (dy }. This step is motivated by prior work that uses MDL as the princi- ple behind unsupervised objectives for graph compression. Assuming the rule has size (1), the greedy objective is the difference in description length (A) HD. The algorithm terminates when |C| < 2 over all clique solutions.
1. One-to-one (over D). For every H E DD our unambigu- ous procedure assures there is only one way to parse it. AG methods can generate the same graph in many (up to exponential) ways. SD methods rely on an arbitrary ordering of the nodes.
2. Onto (over D). The proof in the appendix shows that the grammar induction algorithm is concurrent parsing algorithm for each H E DD so D C L(G.. Both AG and SD can generate any graph. 3. Deterministic. That reconstruction is deterministic fol- lows immediately from properties of the grammar. We also show additional desiderata, namely that each inter-
4

---

Directed Graph Grammars for Sequencc-based Learning
mediate graph is always an unambiguous DAG, respect- ing the properties of L(G). AG methods can take many action trajectories arrive at the same final state.
Rule Sequence Decoder. We adopt a Transformer decoder with causal attention masking autoregressively decode sequence of rule tokens from latent space. Due to the one-to-one guarantee, reconstruction equates to exact match of the sequence. During training, we pad each rule sequence to the maximum length in the batch and do batched cross- entropy loss. jointly train the encoder and decoder using standard reconstruction and KL divergence loss.
4. Validity. edNCE grammars are context-free, so an ar- bitrary derivation still produces a valid directed graph. An arbitrary adjacency string (SD) is not guaranteed to encode a valid graph.
5. Stateless. Context-free grammars are stateless. Genera- tion terminates when a selected rule contains no further non-terminals. AG methods require tracking the interme- diate graph as the state, to filter out invalid actions.
Inference. Our edNCE grammar is context-free (Engelfriet & Rozenberg, 1997), so each rule can be independently ap- plied one after another. On the first step, we mask out all rules whose LHS is not S. On subsequent steps, we mask out all rules whose LHS label is not the same as the current non-terminal node. The sampling terminates when there are no more non-terminals. Facilitated by deterministic de- coding, we can constrain the sampling to guarantee validity. For example, in analog circuits, we can ensure only valid op-amps are decoded, because the stabilization constraint (each +gm- and -gm- transconductance unit must be in par- allel with a resistor and capacitor) can be translated into a predicate over the set of new nodes and edges that would be introduced by each rule. These incremental validity checks ensure inference remains efficient, while showcasing our fontext-free grammar's flexibility for domain-specinn cus- tomization (see Sec. 6.4 for a case study).
See App. A for full proofs of above properties 1-4 and more remarks. DIGGED also meets two soft desiderata that are appealing to downstream use cases.
Controllable. Due to context-free, sequential represen- tation, it is easy to add sontext-sensitive constraints at each step to enforce domain-specific validity. We use a real-world example in Section 3.4.
Compositional. Each DAG is compact program com- posed from reusable primitives learned for efficient loss- less compression. Compositionality provides lens to understand generalization downstream tasks, clabo- rated on in App. G.
3.4. Sequence- based Learning
Once have converted each H D into a sequential description, we jointly train an encoder and decoder within an autoencoder framework. As visualized in Figure 2, we decode a sequence of individual rules, which, when con- catenated together, reconstructs the input. Standard to VAE training, we maximize the evidence lower bound. See App. I for hyperparameters used.
4. Experiments
4.1. Datasets
1. Neural Architectures (ENAS). The ENAS dataset con- tains 19,020 neural architectures from the ENAS soft- ware and their weight-sharing accuracy (WS-Acc) on CIFARIO (Pham et al., 2018). We compare with the same baselines reported in Thost & Chen (2021).
Graph Encoder (Option 1). We support using DAGNN (Thost & Chen, 2021) as an encoder from DAG to latent space. This combines existing SOTA architectures for DAG- specific encoding, while supporting the additional use case of parsing DAGs & L(G) to a similar DAG E L(G).
2. Bayesian Networks (BN). The BN dataset contains 200,000 random, 8-node Bayesian networks from the R package bnlearn (Scutari, 2009) and their Bayesian Information Criterion (BIC) score for fitting the Asia dataset (Lauritzen & Spiegelhalter, 1988). We compare with the same baselines as for ENAS.
Rule Sequence Encoder (Option 2). We also support
Transformer encoder with full attention to encode a se- quence of rule tokens to latent space. Simultaneously, we learn a dictionary of embeddings, one for each rule, as is standard for generative pretraining (Achiam et al., 2023).
3. Analog Circuits (CKT). The CKT dataset contains 10000 operational amplifiers (op-amps) released by Dong et al. (2023) and their simulated metrics: gain, bandwidth (BW), phase margin (PM), and figure of merit (FoM). We compare with the same baselines reported in Dong et al. (2023).
We include comparisons between these two options in our experiments, where we show a GNN encoder constructs a richer latent space for unconditional generation and property prediction. Therefore, we use GNN encoder for obtaining the final results and analyses. Analogous to progress in language modeling, we believe full attention Transformer encoder is the natural and scalable approach. For instance, we show rule token frequency also follows Zipf's Law (Zipf, 2013). Please refer to App. H for an illuminating discussion.
4.2. Task Setup
1. Unconditional Generation. For unconditional genera- tion, we sample from a Gaussian prior. For each latent point, we perform constrained decoding of a sequence of rules, then derive the DAG. For all datasets, we evaluate
5

---

Directed Graph Grammars for Sequencc-based Learning
Grammar Induction
110
OF
Iriisl Symbbl
Sequence Representation
Grammar
95
77
52
15
PAA
EnGrnn Grodde
95
77
52
15
Figure 2. (Top) Our grammar induction framework iteratively minimizes the total description length of D, contracting common and compatible motifs, producing grammar rules while parsing the input according to the grammar. (Bottom-left) Our induction algorithm builds the token dictionary, where individual rules are the tokens used in faithful sequential representation of the DAG. [Bottom-right We experiment with two ways to encode the DAG: 1) using a full attention Transformer encoder vs 2) using a GNN tailored to DAGs (Thost & Chen, 2021); in both cases, causal, autoregressive Transformer decoder within autoencoder framework, while jointly learning the embedding dictionary.
the reconstruction, validity and novelty. For circuits, we also evaluate circuit validity, defined in the same way as Dong et al. (2023).
4.3. Baselines.
We compare with prior AG methods and SD methods (see Sec. 3.3 for descriptions). Methods under both categories can be analyzed by how nodes are ordered: S-VAE, D-VAE and DAGNN use topological order; PACE uses canonical order; GraphRNN uses BFS order; CkIGNN defines total order on a basis of subcireuits. Transformer-based methods (Graphormer and PACE) rely on well-chosen ordering and use positional encoding improve encoding efficiency. These baselines choose various ordering criteria to meet the one-to-one property, via traversal algorithm or canonical- ization. We hypothesize these steps do not overcome inher- ent limitations in the representation. We show DIGGED's theoretically sound and compact sequential descriptions translate into practical performance advantages.
2. Predictive Performance. For property prediction, we train a Sparse Gaussian Process (SGP) regressor, follow- ing the same setup and hyperparameters as Zhang al. (2019); Thost & Chen (2021); Dong et al. (2023).
3. Bayesian Optimization. We run batched Bayesian Op- timization based on the SGP model for 10 rounds with 50 acquisition samples per round. We follow the same setup as Zhang et al. (2019) for ENAS and BN and Dong et al. (2023) for CKT, reproducing the same Cadence SPECTRE simulation environment, adopting the same DAG-to-netlinn conversion logic, and run the same simu- lation script.
6

---

Directed Graph Grammars for Sequencc-based Learning
5. Results
BN. We observe an interesting case of high Pearson but more modest RMSE. We conduct closer, visual, and quantitative investigation of this result in App. F, showing global, linear trend. We believe this to be a consequence of our sequence learning framework, where there is rep- resentation continuity in the latent space. This showcases the downstream representation learning advantages of train-
Table Prior validity, uniqueness and novelty (%). We follow the
same settings as Zhang et al. (2019).
Matteeb
Nesral archietreee
Accerscy
Vildayy
Litapaonss
Nurcly
Accuncy
Viliday
Unsgareos
Novecyy
D-VAE
190,00
37.25
108.00
38.98
96.01
SAVA
196,00
37.03
190:00
33.51
90:70
OCN
95.70
09.55
31.00
108
59.00
12.84
$9.40
in a modern Transformer architecture on a principled and congruous sequence representation.
Deeptiba
94.95
18.09
45.37
09533
42:34
18.36
57.27
93.49
DOGERED (EaN0o
1001
108
19.7
09.9
100
180
140
DOGGED TOKEN)
100
100
25.4
37.8
100
180
98.67
26:67
5.3. Bayesian Optimization
Table Effectiveness in real-world electronic circuit design. Training data is CktBench101 (Dong et al., 2023) for all baselines except top group. CkIGNN also has an option to use CktBench301 as pivots in the BO. We also include top 90/95/max designs from CkiBench101 and CkIBench301.
input
-gm+
Mithode
DAGs C5)
clestic (S)
Novel cheeltcc (53)
(FaM)
DAGNN VAE
14.21
97.19
R
-gm+
73.90
97.15
E
B
OCN GIN
$1.02
72.03
97.01
524634
$0.92
12.17
96.88
32,624
NGNN
$2.17
73.22
95.29
32.2927
output
$2.51
72.70
94.50
32.2427
DIONN (Col
CRIGNN
96.92
08.92
92.29
19042554
33.4354
(a) ENAS (WS-Ace: (b) BN (Ground-truth) 74.8, 74.9)
(c) CKT (FoM:
306.32)
mas)
DoRkeea0001 101 (905, 995,, max)
100
100
100
119 50011
913779
Figure 3. We visualize the best discovered designs from BO. We
197.2296
reproduce the same BO and evaluation setup as Zhang al. (2019);
DIDGED (GNN) DIOGED (TOREN)
92.2
108
92.2
800
78.60
60.7
318.2635
Pham et al. (2018); Dong et al. (2023).
5.1. Unconditional Generation
In Figure 3, we visualize the best, novel designs found during BO.
ENAS& & BN. Shown in Table 2, DIGGED ensures Validity and achieves near 100% Uniqueness on ENAS and BN, > 50% and > 40% higher than the second best method. On BNs, it's the only method achieving 100% Novelty, showing ability to sample diverse, combinatorial structures.
CKT. DIGGED generated novel designs that exceeded the best design in CktBench301, with the best one only 5% lower in FoM than the best design in CktBench101. Visu- alized in Fig. 3, we see simple but effective double-stage amplifier, with a parallel resistor configuration, with a FoM of 306.32. We visualize additional designs in App. E, and observe that they all have short derivation lengths, implicitly capturing simplicity, an essential requirement for real-world circuit design. More details on baselines are in App. E.3.
CKT. Shown in Table 3, DIGGED ensures 100% Validity both at the syntax (DAG) and semantic (circuit) level, serv- ing as powerful complement to synthetic data generation pipelines.
5.2. Predictive Performance
ENAS. In Fig. 3, we see novel architecture that combines the overall topology of the best designs found by Zhang et al. (2019) with the consecutive avg. pooling layer design found by Bowman et al. (2015). We also recover one of the best (top I 1%) designs in the dataset, with a weight-sharing accuracy of 74.9. This shows the model is versatile, able to reconstruct existing designs and combine aspects of designs found by different previous models.
CKT. As shown in Table 4, DIGGED produces discrimina- tive latent representations when combining dedicated DAG encoder with sequence-base based decoding with Transformers. achieves 26.5% lower RMSE and 60% higher Pearson r on the holistic metric, FoM, over the next best (CKIGNN), which is domain-specific GNN that uses hand-selected motifs to form subgraph basis.
ENAS. As shown in Table 5, DIGGED slightly underper- forms the best generative model encoder (DAGNN). We suspect that this is due to the large number of rules (7504) in grammar, making dictionary learning cumbersome.
BN. In Fig. 3, we were able to recover all the dependen- cies in the ground-truth model ((Lauritzen & Spiegelhalter, 1988)). This is impressive considering that DIGGED dis- covered it on the 5th round of BO.
7

---

Directed Graph Grammars for Sequencc-based Learning
Table 4. Predictive Performance of Latent Representations on CktRench101. We follow the same settings as Dong al. (2023).
Exaluation Metric
Gain
BW
PM
FoM
RMSE J
Pearson's
RMSE 1
Pearson'sT
RMSE
Pearson's S
RMSE
Peurson's ' 1
PACE
0.644 0.003
0,762 0.002
0.896 =: 0.003
0.442 0.001
0.970 0.003
0.226 0.001
0.889 0.005
0.423 = 0.001
DAGNN
0.695 + 0.002
0.707 + 0.001
0.881 + 0.002
0.453 + 0.001
0.969 + 0.003
0.231 0.002
0.877 + 0.003
0.442 + 0.001
D-VAE
0.681 0.003
0.739 + 0.001
0.914 0.002
0.394 0.001
0.956 0.003
0.301 0.0002
0.897 = 0.003
0.374 0.001
GCN
0.976 & 0.003
0.140 a 0.002
0,970 a: 0.003
0.236 s: 0.001
0,993 a 0.002
0,171 0.001
0.974 a 0.003
0.217 + 0.001
GIN
0.890 0,003
0.352 1: 0.001
0.926
0.001
0.985 0.004
0.187 0.002
0.910 0.003
0.284 1: 0.001
NGNN
0.882 : 0.004
0,433 + 0.001
0.933 + 0.003
0.247 = 0.001
0,984 4: 0.004
0.196 2 0.002
0.926 2: 0.002
0.267 : 0.001
Pathformer
0.816 0.003
0.529 0.001
0.895 + 0.003
0.410 0.001
0.967 0.002
0.297 0.001
0.887 0.002
0.391 0.001
CRIGNN
0.607 = 0.003
0,791 +: 0.001
0.873 =: 0.003
0.479 = 0.001
0,973 4: 0.002
0.217 0.001
0,854 2 0.003
0.491 : 0.002
DIGGED (GNN)
0.630 0.005
0,771 + 0.004
0.635 0.006
0.784 0.001
0.990 0.000
0.314 0.001
0,627 0.002
0.787 + 0.001
DIGGED (TOKEN)
1.005 + 0.0002
0.199 + 0.001
Table 5. Predictive performance of latent representation on ENAS BN test set. We follow same settings as Zhang et al. (2019).
Table 6. Results of our controlled study comparing with simpler
node-order encodings. Only FoM reported for CKT.
Model
ENAS
BN
Valid
Urique
Novel
RMSE
Posson'ar '
1st
2nd
3rd
RMSE 1
Pearson's
RMSE 1
Pearson's 1
Deapt2NS-Deisall
BN
ENAS
59.8
56.1
94.8
100
0199%
0.746
0.656
0.800
0.346
-11580
-11685
0.743
-11891
S-VAE
0,644 = 0.003
0.762 0.002
0.896 + 0.003
0.442 = 0.001
CKT
71.0
96.8
0.685
0.718
230.96
177.29
148.93
GraphRNN
0,695 a: 0.002
0,707
a 0,001
0.881 #: 0.002
0.453 a: 0.001
GeppLZNS-BFS
ENAS
100
100
0.926
0.595
0.346
0.745
GCN
0.681 000003
0.739 0.001
0.14 0.002
0.394 0.001
BN
2.2
102
100
0.591
0.819
-11601
-11892
-11950
CKT
0.19
100
100
0.676
0.751
DeepGMG
0.966 0.003
0,140 + 0.002
0.970 # 0.003
0.236 = 0.001
BNAS
D-VAE
0,890 0.003
0.352 + 0.001
0.926 + 0.013
0:251 0.000
100
-11935
-11636
DAGNN
0,882 = 0.004
0.433 + 0,001
0.933 # 0.003
0.247 = 0.001
CKT
0%
0.760
DIGGED (GNN)
0.912 0.001
0.386
0.001
0.953 + 0.052
0.712 0.013
DIOCED
ENAS
98.7
99.9
0.396
0.549
0.748
DIGGED (TOKEN)
0.987 1 0.001
0,049 0,006
0.989 0.0001
0.129 0.002
BN
97.6
100
0,712
11110
-1150
-11293
100
78.8
0.767
906.32
206
53
6. Discussion
Since subgraph isomorphism, max clique, and hitting set are all NP-hard, we toggle between brute, approximate or heuristic solvers based on problem size. We state our choice of approximation and heuristic variants, along with any hy- perparameters to control solution quality, in App. B. We an- ticipate the setting of larger data sizes, where faster solvers must be chosen out of necessity. Our main results on CKT (the smallest dataset) already reflect exact solutions or high- quality approximations, so we use this dataset to benchmark the performance & efficiency impact of using coarser ap- proximations. We separately conduct four possible changes to the DIGGED algorithm: (1) For Subdue (FSM),
6.1. Ablation Study on Simpler Sequential Descriptions.
We perform a controlled ablation in Table 6 fixing DAGNN as the encoder and the same Transformer decoder architec- ture used to train DIGGED. We vary various node-order encodings as the output targets to test whether simpler SD encodings suffice. We target three node node-orderings default order (that is, the order provided by the data, normally a topological order with domain-specing criteria), BFS from a randomly chosen seed node (as in You et al. (2018))) or a random order- for comparison. We see the default order is unique in most cases, but its unguaranteed validity results in lower BO optimization results (following Zhang et al. (2019) to deal with invalid samples). BFS or random ordering destroys the decoder's ability to generate valid examples. BFS is do-able for mostly linear path graphs in ENAS but is entirely infeasible for BNs, due to dense dependencies making the order unpredictable. Imposing position on inherently position-invarian graphs causes de- coding failures- even DAGs can admit exponentially many valid orders. DIGGED instead is position-less; it learns a unique, position-free sequential "change-of-basiss that encodes a graph as its construction steps. Each token in- cludes a set of instructions to recreate the graph. For further explanations and deeper analysis, please refer to App. G.
beam_widde winth = 3 instead of 4: (2) for max clique, we use the greedy algorithm with K = 10 random starting nodes; (3) for hitting set, we do beam search with beam_width = 10 instead of exact; (4) we skip disambiguation for early con- vergence. We find Ablation did not introduce meaningful changes, as beam search equates to an exact procedure for small input sizes. Table 7 shows Ablations 2, speed up execution with minimal quality loss; max clique offers the best accuracy/speed trade-off. Latent space quality and top 3 results benefit slightly from more accurate FSM and max clique solutions, but results are still reasonably close.
6.3. Case Study on Lossless Compression Rate.
We empirically analyze how much the total size [/] is com- pressed relative to the number of rules. We see in Fig. 4 that DIGGED achieves 2.2%, 2.6%, 1.56% compression ratio (initial | to pre-termination HH, when every initial
6.2. A Ablation Study on Speed- Elasticity.
For each solver module for the sub- uub-problems in Sec. 3, we offer brute force, approximation, and heuristic algorithms.
8

---

Directed Graph Grammars for Sequencc-based Learning
kintrr byttem
Table Results of ablation study, quantifying speed-accuracy tradeoff's for each module. RMSE (left) and Pearson r t (right) reported for FoM. Compress ratio is defined in Sec. 6.3.
Unique
Nevel
FrM
14
2nd
Tel
Compuss Ralio
A
65.6
69.1
0.624
0.785
267.55
253.61
246.78
5621
2.04
ABL2
91.3
85.1
0.617
0.797
278.91
278.5 93
267.51
184495
2.13
ABL5
97.3
100
0.625
0.785
306.52
29042
260.97
-3005
2332
DIOGBD
96.7
95.9
306
296
263.5
0%
2188
Intial, Torminate and Ainll [V] for each Dataset
[0] LCR, enis. 15000, 29220, 200000!
Paee Leidn
Figure 5. We stratify the test error distribution across the parse length. For reference, also include count of the number of test set examples of cach parse length.
1s 545
405
topologies, and existing graph-baser approaches rely on predefined substructures. DIGGED constructs designs step- by-step, enforcing meaningful constraints that ensure stabil- ity and explainability (App. E.1). Expert evaluation of the Seehhesspprformigggg circuits confirms the validity of many designs while highlighting areas for refinement (App. E.2). Compared to standard black-box optimization baselines, DIGGED's s grammar- -uriaar--guddddd-d search provides interpretable solutions with improved structural integrity (App. E.3).
2t5 42837 2207--2200--000
00 02
0.4
0.0
0-8
100
Beratinn e/ Tittl Darations
Figure 4. We show M == H a function of iteration (same as the number rules induced). Axes are scaled 1.0 for standard- ization across datasets. The lower legend follows the format initial [H] + pre-termination
H + post-termination [ (=(D).
6.5. Case study on Representation Continuity.
connected component is contracted to a single node). For convenience, we only show compression for the initial call to Algo. 2 (iter 0 in Algo. 1). prior to disambiguation. We observe the trend: linear structures tend to achieve greater total compression ratio at the tradeoff of higher grammar complexity. For example, ENAS DAGs are linear path-like graphs (with a few skip connections), whereas BN DAGS are graphical models with highly intercomnected topologies. CKT DAGs are somewhere in between, with main stages lined up consecutively but also intricate, parallel configu- rations. Thus, see compression ratio from highest to lowest: ENAS, CKT, BN. For BN, we see a small (845) number of rules relative to its total size (200k) responsible for a large compression ratio. Intuitively, DIGGED uses the neighborhood topology to deduce a maximally compati- ble instruction set, so simpler neighborhood topologies like those found in ENAS graphs makes achieving compatibil- ity across occurrences easier, resulting in much more rules (7504). Meanwhile, complex neighborhood topologies in BN may be inherently incompatible with any rule, so there exists some limit on how much compression is possible.
We also use BN case study for the relationship be- tween per-sample compression, i.e. the length of its rule sequence, and downstream predictive performance, i.e. the error from a fitted SGP regressor. In Fig. 5, we find that longer rule sequences are more informative, resulting in an inverse relationship between the description length and the test error. By viewing grammar induction as lossless compression (Section 6), we can use the length estimate of per-sample compression ratio. The BN dataset is also apt for this study because every DAG has a fixed set of nodes, so we don't need to normalize for the initial size [H. We find in Fig. that the representations, in gen- eral, become more discriminative with longer parses. We believe this is attributed to compression being an explicit form of information bottleneck (Tishby et al., 2000), where our MDL-guided compression explicitly optimizes for rep- resentation compactness, via compositionality. to form a richer representation space amenable for downstream tasks.
rough
7. Conclusion
We introduce DIGGED, a principled and efficient mapping from DAGS to sequences via graph grammar parsing. The resulting compact, unambiguous derivations enable one-to- one problem mapping to sequence modeling. Experiments on real-world optimization problems demonstrate superior performance. An exciting direction is to explore composi- tional reasoning capabilities with DIGGED representations.
6.4. Case study on Real-World Use Case.
DIGGED successfully generates high-perforning analog circuit designs by inducing a data-driven grammar, balanc- ing generalization with domain specificity. The case study (App. E) shows its ability to optimize op-amp topologies, where traditional methods focus on device sizing for fixed

---

Directed Graph Grammars for Sequencc-based Learning
Acknowledgements
Cook, D. J. and Holder, L. B. Graph-based data mining. IEEE Intelligent Systems and Their Applications, 15(2):
Michael and Gang completed internships at the MIT-IBM Watson AI Lab. Gang supported by the IBM Fellowship. The authors thank Dr. Xin Zhang from IBM Research for helpful discussions circuit design use case.
2004.
Cook, J. Holder, L. B., and Djoko, S. Knowledge dis- covery from structural data. Journal of Intelligent Infor- mation Systems, 5:229-248. 1995.
Impact Statement
Cook, D. J., Holder, L. B., and Djokok, S. Scalable dis- covery of informative structural concepts using domain knowledge. IEEE expert, 11(5):59-66) 1996.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
De Cao, N. and Kipf, T. Molgan: An implicit genera- tive model for small molecular graphs. arXiv preprint arXiv: 1973, 2018.
References
Devlin, J. Bert: Pre-training of deep bidirectional trans- formers for language understanding. arXiv preprint arXiv:1810.04800 2018.
Achiam, J., Adler, S., Agarwal, S., Ahmad, L.,, Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08771 2023.
Djoko, S., Cook, D. J., and Holder, L. B. Analyzing the benefits of domain knowledge in substructure discovery. In KDD, pp. 75-80, 1995.
Bandyopadhyay, S., Maulik, U., Cook, D. J., Holder, L. B., and Ajmerwala, Enhancing structure discovery for data mining in graphical databases using evolutionary programming. In FLAIRS, pp. 232-236, 2002.
Djoko, S., Cook, J., and Holder, L. B. An empirical study of domain knowledge and its benefits to substructure discovery. IEEE Transactions on Knowledge and Data Engineering, 94):575--86, 1997.
Blockeel, H. and Nijssen, S. Induction of node label con- trolled graph grammar rules. In Proceedings of 6th Inter- national Workshop on Mining and Learning with Graphs, 2008.
Dong, Z., Cao, W., Zhang, M., Tao, D., Chen, Y., and Zhang, X. Ckignn: Circuit graph neural network for electronic design automation. arXiv preprint MXXi:2308.166406 2023.
Bojchevski, A., Shchur, O., Zügner, D., and Günnemann, S. Netgan: Generating graphs via random walks. In International conference on machine learning, pp. 610- 619. PMLR, 2018.
Engelfriet, J. and Rozenberg, G. Node replacement graph grammars. In Handbook Of Graph Grammars And Com- puting By Graph Transformation: Volume 1: Foundations, pp. 1-94. World Scientific, 1997.
Bowman, S. R., Vilnis, L., Vinyals, O., Dai, A. M., Joze- fowicz, R., and Bengio, S. Generating sentences from continuous space. arXiv preprint 2015.
Gao, T., Fadnis, K., and Campbell, M. Local-to-global bayesian network structure learning. International Con- ference on Machine Learning, pp. 1193-1202. PMLR, 2017.
Brabrand, C., Giegerich, R., and Møller, A. Analyzing am- biguity of context-frree grammars. Science of Computer Programming, 75(3): 1961 2010.
Kömez-BBobareed R., Wei, J. N., Duvenaud, D., Hernández-Lobate M., Sánchez-Lengeling. B., She- berla, D., R. P., and Aspuru-Guzi A. Automatic chemical de- sign using a data-driven continuous representation of molecules. ACS central science, 4(2):268-27) 2018.
J., Hirzel, T. D., Adams,
Busatto, G., Lohrey, M., and Maneth, S. Grammar-basee tree compression. 2004.
Chickering, D. M. Learning bayesian networks np- complete. Learning from data: Artificial intelligence and statistics V. pp. 121-130, 1996.
Gonzalez, J., Jonyer, I., Holder, L. B., and Cook, D. J. Efficient mining of graph-based data. In Proceedings of the AAAI Workshop on Learning Statistical Models from Relational Data, pp. 21-28, 2000.
Chomsky, N. On certain formal properties of grammars. Information and control, 2(2):137-167, 1959.
Guo, M., Thost, V., Li, B., Das, P., Chen, J., and Matusik, W. Data-efficient graph grammar learning for molecular generation, arXiv preprint arXiv:2203. 08031, 2022.
Cocke, J. Programming languages and their compilers: Preliminary notes. New York University, 1969.
10

---

Directed Graph Grammars for Sequencc-based Learning
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning large graphs. Advances in neural information processing systems, 30, 2017.
Koller, D. Probabilistic graphical models: Principles and techniques, 2009.
Kusner, M. J., Paige, B., and Hernández-Lobato J. M.
Heckerman, D., Chickering, D., and Geiger, D. Learning bayesian networks: Search methods and experimental results. In Proceedings of Fifth Conference on Artificial Intelligence and Statistics, volume 112, pp. 128, 1995.
Grammar variational autoencoder. In International con- ference on machine learning, pp. 1945-1954, PMLR, 2017.
Lauritzen, and Spiegelhalter, D. J. Local computa- tions with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statis- tical Society: Series B (Methodological), 50(2):157-194, 1988.
Helbling, C. Directed graph hashing. arXiv preprint 20X1::0002.06653, 2020.
Holder, L. B. Empirical substructure discovery. In Pro- ceedings of the sixth international workshop Machine learning, pp. 133-136. Elsevier, 1989.
Li, Y., Vinyals, O., Dyer, C., Pascanu, R., and Battaglia, P. Learning deep generative models of graphs arXiv preprint arXiv: 1803.0338333 2018.
Holder, L. B. and Cook, J. Discovery of inexact concepts from structural data. IEEE Transactions on Knowledge and Data Engineering, 5(6):992-99))) 9904 1993.
Liu, H., Simonyan, K., and Yang, Y. Darts: Differentiable architecture search. arXiv preprint arXiv:/806.1 09055, 2018a.
Holder, L. B., Cook, D. J., Djoko, S., et al. Substucture discovery the subdue system. In KDD workshop. pp- 169-180. Washington, DC, USA, 1994.
Liu, Q., Allamanis, M., Brockschmidt, M., and Gaunt, Constrained graph variational autoencoders for molecule design. Advances in neural information processing sys- tems, 31, 2018b.
Hutter, F., Kotthoff, L., and Vanschoren, Automated ma- chine learning: methods, systems, challenges. Springer Nature, 2019.
Luo, R., Tian, F., Qin, T., Chen, E.,, and Liu, T.-Y. Neural ar- chitecture optimization. Advances in neural information processing systems, 31, 2018.
Janssens, D. and Rozenberg, G. Graph grammars with neighbourhoodd-comtrllee embedding. Theoretical Com- puler Science, 21(1):55-74, 1982.
Ma, T., Chen, J., and Xiao, C. Constrained generation of semantically valid graphs via regularizing variational au- toencoders. Advances in Neural Information Processing Systems, 31, 2018.
Jin, W., Barzilay, R., and Jaakkola, T. Junction tree vari-
ational autoencoder for molecular graph generation. In International conference on machine learning. pp. 2323- 2332. PMLR, 2018.
Maneth, S. and Peternek, F. Grammar-based graph com- pression. Information Systems, 76: 16-19,5,, 2018.
Jonyer, I., Holder, I.., and Cook, D. Concept formation using graph grammars. In Proceedings of the KDD Workshop on Stutii-Relations Data Mining, volume 2, pp. 19 19-43. Citeseer, 2002.
Mikolov, T., Chen, K., Corrado, G., and Dean, J. Efficient estimation of word representations in vector space. arXiv preprint arXiv: 130..7811. 2013.
Mueller, J., Gifford, D., and Jaakkola, T. Sequence to better sequence: continuous revision of combinatorial structures. In International Conference on Machine Learning, pp- 2536 2534.2544. PMLR, 2017.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
D. Pennington, J., Socher, R., and Manning, D. Glove:
Kasami, T. An efficient recognition and syntax-analysis al- gorithm for context-free languages. Coordinated Science Laboratory Report no. R-257, 1966.
Global vectors for word representation, In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Kingma, D. P. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
Peshkin, L. Structure induction by lossless graph compres- sion. In 2007 Data Compression Conference (DCC'07), pp. 53-62. IEEF, 2007.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: 02907, 2016.
Peternek, F. H. A. Graph compression using graph gram- mars. 2018.

---

Directed Graph Grammars for Sequencc-based Learning
Pham, H., Guan, M., Zoph, B., Le, Q., and Dean, J. Efficient neural architecture search via parameters sharing. In International conference machine learning, pp. 4095- 4104. PMLR, 2018.
Weininger, D. Smiles, chemical language and information system. introduction methodology and encoding rules. Journal of chemical information and computer sciences, 28(1):31-36, 1988.
Powers, D. M. Applications and explanations of zipf"s s law. In New methods in language processing and computa- tional natural language learning, 1998.
Yackley, B. and Lane, T. Smoothness and structure learning by proxy. In Proceedings of the... International Confer- ence Machine Learning. International Conference on Machine Learning, volume 2012, pp. 1663. NIH Public Access, 2012.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21 (140):1-67, 2020.
You, J., Liu, B., Ying, Z., Pande, V., and Leskovec, Graph convolutional policy network for goal-directed molecu- lar graph generation. Advances in neural information processing systems, 31, 2018a.
Rezende, D. J., Mohamed, S., and Wierstra, D. Stochastic backpropagation and approximate inference in deep gen- crative models. In International conference machine learning, pp. 1278-1286 PMLR, 2014.
You, J., Ying, R., Ren, X., Hamilton, W., and Leskovec, J. Graphrmn: Generating realistic graphs with deep auto- regressive models. In International conference on ma- chine learning, pp. 5708-5717. PMLR, 2018b.
Scutari, M. Learning bayesian networks with the bnlearn package. arXiv preprint arXiv:0908.38/7, 2009.
Younger, D. H. Recognition and parsing of context-free languages in time n3. Information and control, 10(2): 189-208, 1967.
Simonovsky, M. and Komodakis, N. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning- ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pp. 412-422. Springer, 2018.
Yu, Y.. Chen, J., Gao, T., and Yu, M. Dag-gnn: Dag structure learning with graph neural networks. In International conference machine learning, pp. 7154-7163. PMLR, 2019.
Yuan, C. and Malone, Learning optimal bayesian net- works: A shortest path perspective. Journal of Artificial Intelligence Research, 48:23-65 66, 2013.
Singh, A. P. and Moore, W. Finding optimal Bayesian networks by dynamic programming. Camegie Mellon University. Center for Automated Learning and Discov- ery, 2005.
Yuan, C., Malone, B., and Wu, X. Learning optimal
bayesian networks using a search. Twenty-second international joint conference on artificial intelligence, 2011.
Sun, M.. Guo. M., Yuan, W., Thost, V., Owens, C. E., Grosz, A. F., Selvan, S., Zhou, K., Mohiuddin, H., Pedretti, B. J., Smith, Z. P., Chen, J., and Matusik, W. Representing molecules as random walks over interpretable grammars. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, (eds.), Pro- ceedings of the 4/st International Conference on Ma- chine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 46988-47016. PMLR, 21-27 Jul 2024. URL https: / http///prceeeenngssee mlr ptees v235 1233//uunde 4un24c..... html.
Zhang, M., Jiang, S., Cui, Z., Garnett, R., and Chen, Y. D- vae: A variational autoencoder for directed acyclic graphs. Advances neural information processing systems, 32, 2019.
Zheng, X., Aragam, B., Ravikumar, P. K., and Xing, E. P. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018.
Thost, V. and Chen, J. Directed acyclic graph neural net- works. arXiv preprint arXiv:2101.07965, 2021.
Zipf, G. K. The psycho-biology of language: An introduc- tion to dynamic philology. Routledge, 2013.
Tishby, N., Pereira, F. C., and Bialek, W. The informa- tion bottleneck method. arXiv preprint physics/0004057, 2000.
Vaswani, A. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
12

---

Directed Graph Grammars for Sequencc-based Learning
A. Grammar Properties
In this section, we discuss, at high-level, the nice properties our grammar-induced sequence representation for DAGs.
One-to-one. Theorem C.2 shows that testing if grammar one-to-one is. in general, undecidable. Instead, we resort to using the data itself as "test cases" for ambiguity. If there exists two derivations for some H D, Algorithm 4 to disambiguate the grammar by removing minimal set of rules that leaves H unambiguous.
Proof. in App. C.
Onto. Our mapping is onto D by construction because our unsupervised grammar induction algorithm simultaneously outputs parse of each H E D. This parse is equivalent to lossless compressed representation of D. Details are in App.
Deterministic. In addition to ensuring E D being onto and one-to-one w.r.t. its parse, grammar also, by definition ensures that each intermediate graph can be reconstructed. i.e. H' s.t. A H' 3 H E also one-to-one and onto over D. Furthermore, we show the following.
Lemma. It possible to restrict each intermediate graph, i.e. H' s.t. S + H' 3 to unambiguous.
Proof. claim that given parse for H E DD of the form S... 3 H(O + H, H If H was ambiguous, then clearly И ambiguous too because the first - 1 steps can replaced with a different parse. This is a contradiction to the one-to-one property.
Lemma. is possible to restrict each intermediate graph, i.. H' s.t. S A H' to be a DAG during grammar induction.
Proof. We proceed by induction.
Denote H ((T), where T' is the number of steps in the derivation. H E D is by assumption DAG.
Suppose (t) is DAG during Algorithm 1. Then, show (t-1 can also be constrained to be DAG, based on the redirections chosen. Let S be the subgraph we contract. Since S is subgraph, it is also a DAG. There can also be no cycles in (7) (V Vs). Then, we can choose choose every redirection to be "out" or every redirection to be "in" relative to the neighborhood of S. This way, cycle cannot form using both nodes in S and in v(())
Remarks. In practice, we don't It restrict every redirection to be the same (either "out" or "in"). We compute a "precedence graph" using the nodes in the neighborhood of S, based on reachability without S, i.e. path finding algorithm with S as the obstacles. Then, we ensure the redirections don't violate this precedence graph. Intuitively, the precedence graph itself is a DAG (otherwise there's 's a cycle), so there are many permissable redirection sets.
B. Grammar Induction Algorithm
We delve deeper into the key computation steps of Algorithm 2. The first subsection discusses our implementation choices for the approximate and heuristic variants of the frequent subgraph mining ('fast_subgraph hwt.graaphisooophhiiiite max clique papprox_max_cliqqeee
and hitting set ('quick_hittingsse' problems. The second and third subsections elaborate further on the insets and outsets and find iso functions. They are non-standard problems that we formulated so we feel they require further elaboration.
B.1. Solver Options
1. Frequent subgraph mining
(a) Approximate: We use the Subdue library. It has various options for pruning the search. Parameter: beam width (used for subgraph expansion).
2. Max clique
(a) Exact (O(cxp(n))): networkx's 's cliques library
(b) Approximate (O(poly(n))): We use networkx's ([VV)/(lg /V])²) approximation algorithm.
(c) Heuristic (O(n)): (Repeat K times) Initialize a random node, iterate over all remaining nodes in random order, adding any that satisfies clique condition. Parameters: K
3. Hitting set problem during disambiguation
13

---

Directed Graph Grammars for Sequencc-based Learning
(a) Exact: implementation
(b) Approximate: Beam search. Parameters: beam beam_width
Our datasets have variable sizes from 47877 (CKT), 152160 (ENAS), 2,000,000 nodes (BN), which span the range of real-world use cases. We use the size of the input toggle between different options, trading off accuracy and efficiency. Roughly speaking, CKT mostly uses exact/approximate solutions, ENAS approximatccheuurstic solutions and BN heuristic solutions.
B.2. Compute Insets and Outsets
To understand why Algorithm losslessly compresses D, we must understand what the function insets_and outsets does in the logic of Algorithm 3. The concept of insets and outsets were introduced in (Blockeel & Nijssen, 2008) for a simpler grammar formalism, but we extend it to general edNCE grammars. Here, we restate it here for completeness. Given a subgraph S in a graph G, we need to infer 1, the set instructions that can induce a grammar rule while ensuring G can be reconstructed. Recall that each instruction in / of the form (a, 3/7,22 d/d") which has the semantics "if neighbor has edge direction d, edge label B, and label a, form edge with direction d' labeled y to node Vs"" during one-step derivation. Thus, each instruction carries precondition (d, B, o)) and postcondition (d' 7.)) Given G, S, and possible realization G' (G but with S replaced with a non-terminal), we can immediately deduce which (precondition, postcondition) pairs are respected and which are not. Due to mutual exclusivity of the preconditions, we can deduce which rules must be in / from the respected pairs and which rules must not be in I from the disrespected pairs. These form the lower bound and upper bound of and are defined as the insets and outsets, respectively. The function insets_and _outsets and_oussess therefore enumerates all possible realizations G' (the product over all edge directions for each adjacent neighbor of Vs G), then computes the inset and outset for each realization.
Algorithm 1: function inniimmaarninuucttioodaaatttts
Input: D = [H, Ax) i = I,...., | 2; // dataset of DAGs labeled by X, vocabulary of labels
N < []: + [black]: : P - (
=
P.lack:: // initialize grannar
SS= + [0], E [P|]::
iter + 0;
while len D) 0 do
G_iter +- learn_grand (aamn_rammmr(D))
G.iter, D, S iter + disambiguate(G.ieer D);
for i E S iter do
L Sti] + Sliter[i];
10
for (X, D, E G iter. do
L G.P G.PU iter, D,I);
11
12
iter+ 1;
13
while iter > 0 do
14
iter- = 1;
15
G.P + G.P (black, black iter, //
abbrev: graph with single node labeled black: iter
16
Out: S
B.3. Find Compatible Isomorphisms
Given way compute the insets and outsets for given subgraph occurrence S and potential edge redirection, need way reconcile different such instances [St.] subgraph occurrence i, redirections using their inset and outset. We introduce the notion of a isomorphism compatibility graph, where each node represents a specific occurrence, and edges indicate compatibility, i.e. there exists an instruction set that compatible with both. We can define compatibility between St, and Sy. as: "there exists some set 152 which includes insets of St,5 and Sv.j and excludes outset SJ,5 and Sy as on line 29 of 3. Given S, we also determine whether St,, should be added ism graph for the case = j. Once we have
14

---

Directed Graph Grammars for Sequencc-based Learning
Algorithm 2: function learn grammar(datasee)
Input: D= [H, A,) i= 1,..... [P]]; 2; // dataset of DAGs labeled by X, vocabulary of labels
H disjoint union of D:
N f- {gray, black); < [black]; P 0
G (E,, N, black)) // initialize grammar
.M [ + 1; f-
while H| M do
M <- |H]:
m f [ +
while H < m do
m f H
best_clique t- I]:
10
best < H:
for II) in P do
ism-graph t- find D,I);
max max.clique + approx best clsg.el graph);
|max_clique| |D] > [best_clique] |best] then best clique < max clique; best <
16
18
for d E best_elique do
19
rewire(H. d);
motif's +- fiequem..shggrph..nnnnnnl.. best_clique - [
21
22
best -- H:
23
for E motifs do
24
ism ism_graph < find iso (H, D): max_clique if max clique| [D |best cliquel |best] then best.clique +- max_elique;
25
pearox.bet.cllqueeismm
best + D;
I + Udebest.liquee d.inset; P PU (gray, best, [)];
30
31
for d E best.elique do
32
rewire(H,d))
33
++1;;;
34
for D E connected components(H) do
35
P PU ((black, D, ()));
36 Out:
ism-graph, extract the maximum clique of this graph, as that maximizes the compression for this given isomorphism equivalence class.
C. Disambiguation Algorithm and Analysis
C.1. Pseudocode
In Algo. 4, we give the pseudocode of the disambiguation algorithm.
15

---

Directed Graph Grammars for Sequencc-based Learning
Algorithm 3: function find iso(H,D,I=None)
Input: H; (D, AD); // background graph, subgraph
isms -- fast fast.suubgrah hta.ssubbrrppp.ssoophismmm
D);
term_only < all (x) E N, Va E D);
isms allowed - []:
for ism E isms do
D_ism, Apm ism;
if !term only then
isms isms_allowed alllowed += [ism]; continue;
has_nt + any(Aism (1) E N, N,Yr E DLism);
10
Thas nt then
11
isms isms_allow allowed += [ism]; continue;
12
13
V + (1:E+ < // uncirected graph
14 ism E illowell
15
redirections + insets and outsets( H, ism); for inset, outset, dirs redirections do if I! None then
16
if lempty(inset - /) then continue;
if lempty n T) then continue;
else
if inset O outset then
continue;
new_node {ins inset, out outset, ism ism, dirs dirs);
26
- U [new_
27 for i do
28
for j V do
overlap (i.inset U j.inset) O (i.outset U j.outset); if loverlap then
E + ((t,))
Out: V, E
C.2. Proof of Correctness
Lemma. The output G of Algorithm is unambiguous w.r.t. D n L(G).
Proof. To see this, we work backwards from the definition of minimal rule set selection, which is assumed to solve the problem in Theorem C.3. Therefore, elim_rules will superset of at least one element in elim_rule_sete for each i. Each element of elim rule sets is consisting of all rules which should eliminated to ensure H, becomes unambiguous. This ensured by construction because for each derivation whose of rules unique, we try excluding all other derivations. Consider two derivations A and B with rule sets set(A) and set(B), where want to keep A valid but invalidate B. Then, we can eliminate rules set ()) \ set( A). This is possible because there does not exist two derivations where one's rule set is a subset of the other's rule set. This is because each rule application adds positive number of nodes, since the RHS of any rule contains at least two nodes. Therefore, we construct elim_sets, set of rule set differences for keeping keep deriv. We then find a hitting set of clim_sets (rules which invalidates other derivations but keeps the current derivation valid). Therefore, the solution from minimal rule selection will be the minimal set of rules which disambiguates all H, which
16

---

Directed Graph Grammars for Sequencc-based Learning
can be made unambiguous.
Theorem, The output G' of Algorithm is unambiguous w.r.t D.
Proof. Algorithm 1 constructs compound grammar which make consist of multiple sub-gra aub-grammars that each guarantees unambiguity for a partition of 'D. Each sub-grammar's non-terminals are identified by iter so any derivation over G stays strictly within one sub-gramman Thus, showing All E s.t. H; is ambiguous w.r.. G, reduces to showing AH; E L(G.tter) n which is ambiguous w.r.t G. itter for given iteration.
C.3. Undecidability of Detecting Ambiguity
Theorem. Given edNCE grammar G = NI,,, testing if it is ambiguous is undecidable.
Proof. Suppose determining whether is ambiguous is decidable. Then we can reduce determining whether string grammar ambiguous is decidable by reducing it to equivalent edNCE grammar (Engelffrit & Rozenberg, 1997). However, determining whether string grammar is undecidable (Brabrand et al., 2010), which is contradiction.
C.4. Formulation of Disambiguation
Theorem. Given universe U and collection of sets of subsets, S S2, Su,.. Determining whether 3H C U such that |H] S and
J. S, 22". Lett & be an integer.
Vi
M). E S. T.
NP-complete.
Proof. Let HSS = ((U,S,A) s.t. | S and 1 is satisfied.
HSS is in NP: For each 5, E S, non-deterministically guess T, E S. Let H == U,T, If kt accept, else reject.
HSS is NP-hard: Let HS == {U,, (,) s.t. H3 C s.t. |H| < k and H S.S: + 0 for every S; E S be the Hitting Set problem, which is known to be No-coppee We will show HS Sm HSS Given an instance of the HS problem, let f be the computable mapping ((U,,, k)) = (U, (f(s), Vs E S.], vS, E (). ). If (U, S, E HS, then we can choose 8; E S E n S, to be T; for each i. Then we can choose H' { so is satisfied by construction, and since 8; E for each i, H' S so H4| S If f((U, U, k)) E HSS, then let H' satisfy [H'|
and 1. Then T. H' where [T]] 1 equivalent to 3s; E H' for each i, or H' nS + U. since H' < k. (U,S, k) E HS.
Corollary. The problem celimmal_uue_sstt_eee
is solving is NP-Complete
D. Grammar Enumeration Algorithm
is well-known node-labeled DAGs can be hashed by recursively aggregating hashes of children. We use simple approach in our implementation (Algo. 5). Note that edge-labeled DAGs can be polynomial-tine reduced nabella DAGs, so our approach works in the general edNCE case. For recent discussion of hashing directed graphs, refer to Helbling (2020).
D.1. Dynamic Programming with Memoization.
We use memoization to make the brute force enumeration tractable, along with efficient pruning. our implementation (Algo. 7), intermediate derivations are pruned if a) they are not DAGs, or b) not node-induced subgraphs of the desired DAG. mem stores all derivations "to-go" for a given intermediate, the given intermediate is memoized.
D.2. Computational Efficiency.
The worse-case complexity is, in the general case, NP-hard, because parsing edNCE grammars are NP-hard (Engelfriet & Rozenberg, 1997). Intuitively, there be exponential number of connected subgraphs for given DAG (tight for the case of star graphs), though isomorphisms and sparsity means the actual number is lower. In our practical experiments of pith-like structures, the algorithm is very efficient (the multi-process version of Algo. 7 takes few minutes per DAG for BN and CKT). For ENAS, the much larger number of rules creates a large branching factor, but the sparser, path-like structures enables more pruming, still making the algorithm tractable. We also run Algo. 7 in order from the smallest to largest DAGs, as smaller DAGs likely have shorter derivations that enable more rules be pruned before enumerating
17

---

Directed Graph Grammars for Sequencc-based Learning
derivations for the larger DAGs.
D.3. Remarks on Scalability
Our datasets BN, CKT, ENAS are all upper-bounded in the number of nodes, which makes the brute force approach tractable. Further optimizations are required for variable-size DAGs, where domain knowledge can further prune intermediates.
In cases where brute-force approaches not feasible, we have the following suggestions:
1. If the issue lies in the large [D), we suggest partitioning D based on some semantic criterion, then rumning Algo. I on those individual partitions, then aggregating the individual grammars into a compound grammar much like how we did for Algo. 1. The drawback is this pre-partitioning scheme loses the injectivity property when viewing D as a whole, but retains injectivity for the individual "sub-datasets".
2. In cases where individual graphs in are too large, we suggest increasing the "motif size" for Subdue, as larger candidate motifs produce shorter derivations. The ideal derivation length somewhere between 2-8, in our empirical experience. The drawback is this may result in lower compression ratios, depending on the characteristics of the data. We encourage future work to explore this further.
E. Case Study: Analog Circuits
Background. Operational amplifiers (op-amps) are a DAG generation and optimization problem because their circuit topologies inherently form DAG structures. The design of op-amps involves both topology selection and device parameter optimization, making it highly complex, combinatorial problem. Traditionally, op-amp optimization has focused primarily on device sizing (component-wise parameters) given a fixed topology, but recently graph generative models have shown promise in optimizing the DAG topology. (Dong et al., 2023) However, general methods that navigate the combinatorial search space without domain-specife knowledge is challenging, whereas specialized methods will not generalize to other problem domains. For example, Dong et al. (2023) used a two-level GNN on top of a predefined basis of circuit subgraphs, facilitating domain-specific representation learning. DIGGED, by contrast, combines the flexbility of a general method with data-driven grammar induction. Essentially, DIGGED infers the expert knowledge indirectly, through its unsupervised MDL objective.
F. Case Study Example
We visualize the novel design with highest simulated FoM generated by DIGGED during BO in Fig, Shown in 6a, DIGGED derives this design by decoding three tokens. In the first step, decodes one of the common initial rules to initialize the input and output, leaving the middle a placeholder. In the second step, it decodes rule which adds resistor, stabilizing mechanism for the yet-to-be decoded structure. In the final step, it decodes the rule which contains two -gm+ op-amp stages. This is interesting, because the final token decoded is inspired by its previous token. Using a parallel resistor configuration is one of the common ways to provide stability to a two-stage op-amp. In Fig. 6c, we visualize the instruction set for Rule 56, which controls what neighborhood topology should surround the two -gm+ cells. This instruction set the solution to the compatibility maximization (Section B), so contains some redundancy in the context of this specific example. For example, both -gm+ cells in Fig. 6c have preconditions for connecting to input and output nodes, but in the context of any specific derivation, most one will be active. However, only the upper -gm+ cell has preconditions for resistor, capacitor and other gm nodes. This captures important constraints, notably: we don't want other gm cells to connect to both -gm+ stages, because we want cascaded gain blocks and sequential separation of the units. This is significant from a methodology perspective because DIGGED is inducing symbolic rules such as these directly from examples, so it won't I construe unintended topology, whereas other autoregressive graph decoders might. Furthermore, these step-by-step derivations provide explainability into the designs, whereas decoding a DAG in an arbitrary order might miss this information.
E.2. Expert Feedback
We visualize the four novel designs with highest FoMs in Figs. 7a-7c. We consulted an expert with decades of experience in circuit design, and include the feedback in the captions.
18

---

Directed Graph Grammars for Sequencc-based Learning
E.3. More Details on Baselines
Similar to the setup for ENAS and BN Zhang et al. (2019); Thost & Chen (2021), we retrain the SGP model each round and acquire latent points using the Greedy Expected Improvement heuristic. For each latent point, decode a DAG using the decoder and convert it to circuit. We refer to this as unconstrained BO, and adapt the existing implementations by Zhang et al. (2019); Thost & Chen (2021). We also include their reported BO results in Table 3. However, we could not find support for this in the codebase of Dong et al. (2023). Instead, they provide instructions to run BO with pivots, where they first generate latent encodings of all circuits in their benchmark dataset, CktBench301, then snap each acquisition point to the closest circuit in the dataset. Thus, it's unclear how they obtained the numbers in their Table 1. For completeness, we ran their code and include the results as CkIGNN [CktBench301] in Table 3. Despite using large enumerated dataset as pivots, they were unable produce designs close to the max FoM in CkrBench301.
E.4. Summary
DIGGED demonstrates, through a domain-agnoss and unsupervised paradigm, it capable of achieving greater perfor- mances than domain-specific methods. It does so by autonomously discovering domain-specifie patterns, automatically inducing principled and compact sequential descriptions over those patterns, and harnessing purrrol- sequence learning.
F. Case Study: Bayesian Networks
In Section 5.2, we observed an interesting finding, where DIGGED achieves extraordinary Pearson r (nearly 1.6x that of the next best method and 2.9x that of other VAE encoders) despite a modest RMSE. To understand this phenomenon, we visualize the trained SGP's test set predictions (one of the ten seeds) in Fig 8. We then stratify the test set across the number of rules in the sequence representation, and plot the mean absolute error per strata.
Findings. We indeed see a tight, linear trend of the predictions across the entire ground -ruth value range in Fig. 8, despite the error residues being high. We also see this test error is highest for examples with parse length 1. Fortunately, there are very few of those. We then observe a generally decreasing trend in the test error as parse length increases. Notably, 2 and are the most common parse lengths, but exhibits relatively low test errors. We attribute the linear trend to the unique properties of our representation. In contrast with node-by-node or edge-by-edge sequential decoding schemes, DIGGED uses compatible and consistent rules to linearize DAG. This reparameterizes the DAG representation space into sequence representation space, where Transformers have shown strong generalization abilties (Vaswani, 2017). Thus, although individual residue errors are still large, a global linear trend emerges from this representation space. This shows how theoretical properties of our grammar translate into more congruous representations that are amenable for downstream tasks.
G. Further Discussion of Results
Relation to Compositional Generalization. In addition to recognizing our method "converting graph into sequence", there is a deep motivation from the objectives of compositional generalization. Contrary to what a "sequential" representation may imply, DIGGED is intrinsically compositional (see 2). In fact, DIGGED is trained to embed DAGs with similar hierarchical compositions to similar points in latent space. For example, consider DAG represented (uniquely) as W + X + and DAG 2 as W + X + Z. DIGGED's decoder must predict shared initial tokens for both graphs, naturally clustering these related graphs in latent space. Combined with the relational inductive bias of our DAGNN encoder, the autoencoder objective can be viewed as combining both the relational and hierarchical inductive bias to learn expressive and generalizable representations.
How Choice of Datasets Affect Interpretation of Results. ENAS and BN both impose special constraints: all DAGs have the same number of nodes; ENAS DAGS must follow consecutively numbered nodes, and BN DAGS must contain exactly one node of each type (8 types). Such simplifying conditions allow naive positional encodings to overcome the shortcomings we discussed earlier, making predictive tasks relatively easier. We initially chose these datasets due to the limited availability of standardized benchmarks for DAGs, By contrast, the CKT dataset involves significant diversity in both graph topology and node types, making it better testhed for evaluating the true strengths of DIGGED's compositional, position-free encoding approach. At the same time, we note predictive accuracy (RMSE, Pearson's 's r) does not reflect decoder effectiveness. For example, BN-Random, CKT-BFS, and CKTTRandom achieve reasonable scores on predictive
19

---

Directed Graph Grammars for Sequencc-based Learning
metrics (RMSE and Pearson's r), yet fail fundamental decoder sanity checks, rendering them ineffective for subsequent optimization tasks. DIGGED prioritizes end-to-end optimization results, which requires the ability navigate and decode from the latent space.
Explanation for Better Optimization, Worse Predictive Accuracy. The opportunities and challenges of hierarchical, compositional generalization also explains the behavior we observe in Ablation 6.1. DIGGED is intentionally designed for compositionality its outputs. Unlike naive sequential encodings, DIGGED places DAGs with shared hierarchical structures (intermediate derivations) close together in the latent space. Learning both the token vocabulary embeddings and latent space compositional structure jointly indeed poses a more challenging training task reflected partly in predictive metrics- but strongly supports compositional generalization and decoder reliability. This trade-off underscores DIGGED's core strength: effectively navigating compositional design space to reliably generate diverse and valid DAG structures optimized for practical performance. DIGGED is also design language, combining hierarchical inductive biases and can uncover domain-specific insights (case studies in App. E).
H. Choice of Encoder
In Fig. 9, we plot the frequency of rule tokens, sorted by rank (from most least common) against Zipf"s s Law (Zipf, 2013), cornerstone of modern linguistics. Zipf"s 's Law states that the frequency of the k'th most common word is inversely proportional to its rank, and this arises in many natural settings (Powers, 1998). It's encouraging to see that our unsupervised MDL-based compression scheme also gives rise to such an underlying relationship. Similar to natural language, we believe the formal language behind DIGGED also shares similar governing laws, which would be fascinating to study in its own right.
Despite the theory and intuitions, transferring modern practices in NLP directly onto our framework did not strike gold on the first try. We showed in our ablations in Section 5 that using a full transformer encoder (TOKEN) did worse than using GNN tailored to the inductive biases of DAGs. We postulate two reasons for this:
1. Transformer encoders require more investment in training. This is supported by our hyperparameter experiments in I, where we noticed the encoder required twice as many layers as our decoder. Because the focus of our work not pretraining, we did not invest the time to pretrain the encoder separately.
2. Jointly training an encoder, decoder, and dictionary is data-intensive. For this reason, pretrained word embeddings (Mikolov et al., 2013; Pennington et al., 2014) are used out-of-the-bon for joint encoder-decoder training (Vaswani, 2017; Raffel et al., 2020). However, distributed embeddings for our rule-based tokens do not exist. However, since we are, to our knowledge, among the first to train generative models by representing graphs as sequences of tokens, such solutions do not currently exist.
We believe standard encoder pretraining practices like masked language modeling (Devlin, 2018) will be effectivve We encourage future works to explore this direction further with larger datasets, and we believe there will be scaling laws akin to those we have seen in modern language models (Kaplan et al., 2020). We also encourage future works to explore distributed embeddings by viewing graphs as documents and neighborhood topologies as context windows. Another promising way to bootstrap token embeddings is to leverage the inductive bias of its definition (daughter graph D and instruction set I). We hope our work opens the Pandora's 's Box of graph language modeling using lossless, sequential deseriptions!
Hyperparameter Scan
The optimal parameters for our model were determined using a hyperparameter scan sweeping over various properties of the VAE, using validation loss as the guide. During the sean, we explore varying architecture properties such as: number of encoder layers, number of decoder layers, latent dimension, embedding dimension, batch size, and KL divergence loss coefficient. We employed the validation loss of the VAE to guide parameter selection, updating one hyperparamter at a time while keeping all others fixed baseline values. After each scan, we locked in the best-performing setting before moving on to the next parameter type. The ordering and description of each hyperparameter that was optimized is as follows. We also include the default setting of each parameter in parenthesis:
20

---

Directed Graph Grammars for Sequencc-based Learning
1. Number of Decoder Layers: Depth of the Transformer decoder. (4)
2. Number of Encoder Layers: Depth of the Transformer encoder. (4)
3. KL Divergence Loss Coefficient: Scalar coefficient of the KLL divergence term in the typical VAE loss function (Evidence Lower Bound, ELBO). Controls how closely the encoder's latent distribution matches the prior. (0.5)
4. Batch Size: Number of training examples processed simultaneously for a gradient update. (256)
5. Latent Dimension: Size of the representation of input sequences in the latent space of the variational autoencoder. (256)
6. Embedding Dimension: Size of the embeddings that the encoder and decoder use represent tokens. (256)
The chosen parameters values from each experiment are highlighted in green in Table 8 and Table 9.
Interestingly, for the "Sequence Rule" encoder on the CKT dataset, we achieve the lowest validation loss with just 4 Transformer decoder layers, whereas the Transformer encoder requires 8. This shows that DIGGED works well with a lightweight decoder. We attribute this to compactness of the grammar. Given good sequential description, decoding can be streamlined significantly.
It is worth noting that due time and resource constraints, only able to fully the hyperparameters for subset of the possible encoder-type dataset combinations.
21

---

Directed Graph Grammars for Sequence-based Learning
Algorithm 4: function disambiguate(G.S)
Input: G;D/ // learned grannat, dataset
all_elim_rule cele_rrul_sets < (::
all derivs - II:
for (H4, A,) E D do
derivs t enumerate derivations(H:))
deriv_nule_setLlookupp- (
for deriv derivs do
key +- sorted (intee((is((se((drriv/)) (de(vviv)))
deriv.rule.set.ooouuukkyyy = [deriv];
umabig-poot -aolig-poss---- False;
10
for key E Meriv_rulc.set.oooki do
deriv rule set lookup/ke) == then
11
12
umabig
umasig_poss poss +- True;
break;
14
lumabig poss then
// impossible to make unambiguous, later will be lost all_derivs <- umabig-poss + [0]:
16
continue;
17
all derives + all_derivs + [derivs];
18
rulc_seess < {}:
19
for key E deriv rule set lookup do /een///rii.uulc.sse.oooookkksss
20
then
21
continue;
keep_deriv +- deriv www.iirrule.eet.looeeeo deriv.mlle.setlooouupke////
22
23
clim sets ():
24
for deriv derivs do
if deriv == keepy then continue;
elim_sets elim U {deriv) \ set(kcep_deriv)):
elim rule set quick hitting set(elim sets):// inner hitting set problem // elim_rule_sets t elim_rule_sets U felim_rule.set);
lincar greedy implomentation
29
all elim ruw. sets + all elim_rule rule sets U sets:;
elim-rules +-
(al.eelim.mulleeettts.... given set of set of subsets, find
minimml rules to eliminate each set of subsets has at least one subset. included
32 G.P + G.P rlimmr
33 dataset + []:
34 unique + ():
35 for (H,, >,) E D do
36 lost True;
for deriv all derivs[i] do
if empty(set(deriv) n nelim_rules then
lost 4 False;
40
unique derivs[i] +- deriv;
41
break;
42
if lost then
43
dataset + dataset + ((H; Ad)];
Out: G, dataset, unique derivs
22

---

Directed Graph Grammars for Sequencc-based Learning
Algorithm 5: function w| wlLhash(HH
Input: H; // DAG
G deepcopy(H);
G relabel nodes(G,, (ettrcCCdddtttissseecCCCCddll) (ange(GG))))
< [G.dges]];
edge innex_idxxxx + (2
edge_index(::; m] t array(G.edges).II
roots + setdiff( (0....,, |G] 1), edge index(1]) // Nodes with no predecessors
colors+ - 0
for r E roots do
wl_hash_node coloors:
10 f- - join(sorted(((oooos///]] |r E roots])):
11 hash_value +- sha256(ans.encodd) (ee.ccodded(...eieess(((((( hexdigest((;;
Out: value
Algorithm 6: function hashash nodee(, n, colors)
Input: G; n; colors
if' n E colors then
Out: colors[n]:
if G[n)] / then cs f
colors) c G(n]]):
val < G.nodes(m) ("abeel"") symbol NUT
val val + +' (oin(:s);
else
val < G (odess[n] labbee]]);;;
colors[n] < val:
10 Out: colors[m]
Algorithm 7: function enumerate cnumerate_derrvatioonsn derivatioonsindex, all derivs, grammar, graph)
Input:
index; all derivs; grammar; graph
if index E all_deriv then
log(f'index enumerated"):
Out: all (illdderiviiddee finexx;
G + DiGrraph);;
F.add_node('00 label = "black");
hash +- ha)h
stack - [deepeopy(()), init hash)];
mem 0
while stack * 0 do worker.single(sttak,, grammar, graph, init hash, mem):// Bere multi mitt-pprccessngg, omitted for simplicity
11 derivs +- mem
12 all derivs/index] <- derivs;
13 Out: derivs
23

---

Directed Graph Grammars for Sequencc-based Learning
Algorithm 8: function worker worker.single(stack grammar, graph, init mem) stack; grammar; graph; hnit, mem
Input:
while True do
stack = 0 then
if hash mem memminitthhshh * 0 then
break;
(H, val) stack.popO;
if val E mem then
if memmmvva |va] * then
continue;
else
mem vvl] <- O:
(v H u NJ:
11
if nts 0 then if iss iisiosooo H, graph, node_match) then mem[val] + [0]:
15
else
mem [val] < []:
16
17
continue;
done True; res f []:
18
19
for nt E nts do
20
for rule E grammar.rules do
21
rule = None then
continue:
23
label < Hy lalaell]:
24
if rule.nt label then
c rule (H, nt):
if is wit..iinneteeeccecc......... (Grahh(c))) then continue; if -ss iis_direeted dcyllcceeddaccclicc (ocrii/rrrag))))/ then continue; if --iiddpartial(ggrappaa hash. val + wl hash(c);
c) then continue;;
29
30
hash_val & mem then if done then
stack.append((1), val)); done <- False;
stack.append((c, hash. hash_val)): else
if mem hash val] 0 then if done then stack Buck.appendd(HH) val));
38
39
done + False;
else
for seq E mmm (hah val] do res apsea + decpcopy(seq)):
if done then
mem [ve] <- res;
24

---

Directed Graph Grammars for Sequencc-based Learning
(b) Step-by-step derivation for the design (not shown: instruction set per rule).
(a) Parse (top-to-bottom) representation.
RHS
(c) Visualization of instructions for rule 56. The daughter graph D consists of two -gm++ cells units (with different device placement parameters). We fan out individual instructions, where we use custom half-arrows to visualize redirections (d/d) ). For what each element in the tuple means, see Section 3.1.
Figure Visualization of case study best novel design in Fig.
25

---

Directed Graph Grammars for Sequencc-based Learning
input
input
Ippu
+ gm
+ +gm
gmm
-
+ -m
+
-gm+
R
+gm++
output
output
output
(a) FoM= 265.53, "is possible circuit topol-(b) FoM- 296.82, bit fishy, because +gm+(c) FoM- 243.72, "could good design ogy"
Expert
is in parallel with an edge" Expert
for certain applications" Expert
Figure include three additional novel designs found during BO, For each, we include comment circuit design expert.
Table 8. Hyperparameter scan with "Sequence Rule" encoder type the CKT dataset. Note that the order of parameter optimization follows ordering detailed text above (left - right and top - bottom).
Run enc. layers
Validation loss
Ran
KL Div. coefficient
Validation loss
4.017
3,935
0.1
3,911
Run
# dec. layers
Validation loss
3,882
0.2
3.875
3,885
0.3
3.865
4,000
5
3,888
4
0.4
3,881
3,919
6
3,908
5
0.5
3.894
3,942
7
3.889
0.6
3.871
3,882
3.874
0.7
3.891
0.8
3.893
5
3,909
3.882
0.9
3,899
6
3,942
3,888
10
L.0
3,893
7
3.897
11
3,883
11
1.1
3,884
8
3.917
12
12
3,874
12
1.2
3.885
3,884
3,879
14
1.4
3,908
3,894
15
1.5
3.891
16
16
3.876
Run #
Batch size
Validation loss
16
3,959
Run #
Latent dim.
Validation loss
Run
Embedding dim.
Validation loss
3,940
32
3.862
1
32
3.957
3
64
3.896
2
64
3,858
2
64
3.910
4
128
3.919
3
128
3.862
3
128
3.862
5
256
3.863
4
256
3.844
4
256
3.844
512
3.882
3.873
5
3.851
7
1024
3.844
1024
3.914
6
1024
3.872
8
2048
3.851
26

---

Directed Graph Grammars for Sequencc-based Learning
Sparse GP Predictions on Test Set
Predictions
Perfect Prediction (y=x)
1
Standardized Predicted Values
0
-1
-2
Pearson R = 0.71
-3
RMSE 0.93
-3
-2
-1
Standardized True Values
Figure visualize test set predictions trained SGP model against the ground truth.
27

---

Directed Graph Grammars for Sequencc-based Learning
Sorted Occurrence Counts
Zipf's Law
Occurrences
20000
15000
Count
10000
5000
0
Rules (most least occurring)
Figure 9. We sort all rule tokens by the frequency of occurrence across all sequential descriptions in the BN dataset, henchmarked by Zipf's Law.
Table Hyperparameter sean with "Graph" encoder type on the CKT dataset. Note that the order of parameter optimization follows the ordering detailed in the text above (left + right and top + bottom).
Run #
# dec. layers
Validation loss
Ran
KL Div. coefficient
Validation loss
Run #
enc. layers
Validation loss
0.1
3.919
4.014
3.919
0.2
3,900
2
3,932
2
3.925
0.3
3.901
3
3.936
3
3.937
4
0.4
3,965
4
3.937
4
3.894
5
0.5
3,919
5
3,930
3.924
3,951
6
3.894
0.7
3,959
7
3.915
3,936
0.8
3,949
8
3.965
8
3,939
0.9
3.979
10
1.0
3.988
Run #
Batch size
Validation loss
Run #
Latent dim.
Validation loss
Run
Embedding dim.
Validation loss
16
3.981
3,912
3.962
3.957
3
64
3.926
3.915
2
3.918
3
128
3.898
3
128
3.894
4
128
3.900
256
3.882
4
256
3.882
5
256
3,900
5
512
3.900
5
512
3.913
512
3.882
6
1024
4.405
6
1024
3.908
7
1024
3.883
28


Reviews:
[{"review_id": "tz4QoXZDdO", "reviewer": "Reviewer_ymms", "summary": "This paper proposes representing directed acyclic graphs as sequences of production rules. These sequence-based representations enable generative modeling using language-like models, such as transformers. The authors train and evaluate these models in various scenarios, including neural architecture search, Bayesian networks, and analog circuit design.\n\n## Update after rebuttal (copied from the corresponding comment below)\nGenerally, I think the authors approach is interesting and the authors could show the relevance of DIGGED in the manuscript and the rebuttal. The authors proposed to improve their manuscript, still, I am not fully convinced the clarity issues can be fully solved in an updated/extended manuscript version. However, I evaluate the proposed method as interesting and relevant for the community. Therefore, I tend towards accepting the paper which is why I increased my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing our strong experimental results and asking insightful questions!\n\n*The proposed representations appear quite complex… a more detailed rationale for why simpler alternatives (e.g., positional encoding) are insufficient would have been valuable…. the authors should compare these strategies using the same model architectures... would have been important to demonstrate the relevance of DIGGED.*\n\n* Good question! Simpler alternatives can be classified into by whether they 1) sequentially decode a graph node-by-node or 2) output a **sequential encoding** of the graph (e.g. ordered adjacency info). \n* Methods under 1) add one node at a time and predict edges, requires keeping the state of the intermediate graph to check whether edges can be added, making implementation cumbersome.\n* Methods under 2) are naive encodings, and we argue they are insufficient.\n* We decided to do the ablation study you suggest. First, a few notes:\n  * We fix DAGNN as the encoder as it is tailored for DAGs.\n  * We fix the same decoder Transformer architecture and try different node-order encodings as the output targets.\n  * (Note: it is not really possible to fix the same model architecture to compare with category 1) methods, since keeping the state of the graph requires a fundamentally different architecture.)\n* We tried several common ways to define an ordering over nodes:\n  * Default order (most baselines): whatever order the data comes in, topological\n  * BFS (e.g. GraphRNN): a BFS traversal from a random initial node\n  * Random order: a random order to the nodes\n\n|||Valid|Unique|Novel|RMSE|Pearson's r|1st|2nd|3rd|\n|-|-|:-:|:-:|:-:|:-:|:-:|-|-|-|\n|Graph2NS-Default|ENAS|96.1|99.17|100|0.746|0.656|0.746|0.744|0.743|\n||BN|95.8|96.4|94.8|0.498|0.869|-11590|-11685|-11991|\n|Graph2NS-BFS|ENAS|40.8|100|100|0.806|0.595|0.746|0.746|0.745|\n||BN|2.2|100|100|0.591|0.819|-11601|-11892|-11950|\n|Graph2NS-Random|ENAS|0%|-|-|0.859|0.508|-|-|-|\n||BN|8.4|100|100|0.535|0.857|-11523|-11624|-11909|\n|DIGGED|ENAS|100|98.7|99.9|0.912|0.386|0.749|0.748|0.748|\n||BN|100|97.6|100|0.953|0.712|-11110|-11250|-11293|\n\n*  The default order is unique in most cases, but its unguaranteed validity results in lower BO optimization results. We added **additional** logic to re-attempt sampling for each latent point until a valid DAG is obtained (or fall back to a training example).\n* Meanwhile, ordering nodes via BFS or randomly completely destroys the decoder’s ability to generate valid examples. BFS order is do-able for the mostly linear path graphs of ENAS but is entirely infeasible for BNs, due to the dense dependencies making the order unpredictable. \n* Simple node order positional encoding cannot simult. satisfy all the principles outlined in 3.2. This incomplete representation can lead to issues with decoding and efficacy of downstream optimization. We think the fundamental issue is imposing position onto data that is by definition invariant to it. Even for DAGs, there can be an exponential number of topological orderings.\n* Meanwhile, DIGGED is a position-**less** sequential representation. DIGGED finds the optimal ``change-in-basis\" which casts the graph as a unique, sequential procedure. Each token codes for a set of instructions to recreate the graph, going beyond positional encoding. DIGGED is also a design language, combining hierarchical inductive biases (see DetZ) and can uncover domain-specific insights (case studies in App. E and F)!\n\n*Using graph grammar for graph generation tasks has been done before.... clarify unique, novel contribution to the field.*\n* We are familiar with [1]. They learn primarily on small datasets, containing just a few dozen examples. Our experience using [1] is it can take days to learn on moderate datasets (100s samples). It is slow because it has to learn the optimal way to downsample the data, requiring reward supervision from downstream generation metrics to reinforce the grammar. Our induction procedure, meanwhile, has a much simpler, unsupervised objective, based on minimizing description length. In our response to 7hpe, we benchmark options to trade-off accuracy for efficiency, enabling scaling to larger datasets. \n* More crucially, it is unclear whether grammar-based generation generalizes or scales with pretraining. Our work bridges the expressiveness and scalability of Transformers with the unique representation challenges of graph structures. We hope our proposed representation, theoretical insights and validation of its necessity lays the first steps towards embracing modern sequence-learning architectures for the graph generation community!\n\n*the metrics validity, uniqueness, and novelty….*\n* You’re absolutely right. The unconditional generation results aren’t meant to evaluate the model’s overall quality. It is a basic sanity check. We will write a disclaimer. The much more essential evaluation is the latent space quality for prediction and Bayesian optimization (Tables 3 & 4, Fig. 3).", "claims_and_evidence": "This paper is built around the hypothesis that the proposed unique way of representing graphs is necessary, particularly to address issues related to ambiguous graph representations.\n* The authors demonstrate good results with their method, which can be interpreted as evidence for the hypothesis above.\n* Still, I miss an extended, thorough motivation for this claim. The proposed representations appear quite complex, which could be a drawback. Additionally, a more detailed rationale for why simpler alternatives (e.g., naively mapping graphs to sequence representations using positional encoding) are insufficient would have been valuable. Why are unambiguous representations necessary? Couldn’t the model learn invariance through data augmentation strategies?\n\nSection 3.3 outlines a set of guaranteed properties. As far as I can tell, these claims are well supported by the corresponding sections in the appendix.", "methods_and_evaluation_criteria": "The included experiments make sense because a) they show that the proposed way of representing graphs can be applied to completely different domains and b) the proposed method achieves good performance values indicating that DIGGED might be relevant. Also the authors compare their method to baselines with other strategies to represent graphs as sequences, including positional encoding, topological ordering, and canonical ordering.\n\nTo properly assess the impact of different graph-as-a-sequence representation strategies, the authors should compare these strategies using the same model architectures (with individual hyperparameter tuning). Could the authors please clarify whether this was done?\n\nNotably, the metrics validity, uniqueness, and novelty, generally,  have inherent limitations in evaluating a model’s overall quality since any method can achieve perfect scores by adding a simple symbolic rule as a filter that memorizes seen sequences and permits only new, valid ones.", "theoretical_claims": "The formulas related to directed graph grammar in Section 3 have been reviewed and appear to align with existing literature.\n\nI have briefly read through the proofs for the grammar properties in the appendix but have not checked them in detail.", "experimental_designs_or_analyses": "The proposed experiments seem relevant.\n\nHowever, experiments, which directly compare the proposed method with alternative graph-as-a-sequence representation strategies might miss (see question above) but would have been important to demonstrate the relevance of DIGGED.", "relation_to_broader_scientific_literature": "Using graph grammar for graph generation tasks has been done before, e.g., here [1] (for molecules). However, [1] uses domain-specific knowledge, while the proposed method is context-free.\n\nSince [1] also discusses other domain-independent techniques to mine grammar from real data (see page 3, section: Generative Models using Graph Grammars.), the authors might clarify their unique, novel contribution to the field. \n\n[1] Guo, Minghao, et al. \"Data-efficient graph grammar learning for molecular generation.\" arXiv preprint arXiv:2203.08031 (2022).", "essential_references_not_discussed": "--", "other_strengths_and_weaknesses": "Strengths: The experiment section presents strong, significant results for DIGGED, suggesting that the proposed method might be relevant and valuable to the research community.\n\nWeaknesses - clarity: Several crucial points remain unclear, making it difficult to fully assess the novelty (see: *Relation To Broader Scientific Literature*) and relevance of the proposed method (see *Claims And Evidence* and *Methods And Evaluation Criteria*).", "other_comments_or_suggestions": "* LHS and RHS are used without being defined.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KJyP8pcLb5", "reviewer": "Reviewer_5waZ", "summary": "This paper describes a graph grammar approach for mapping graphs to strings in a principled way.\nGiven a set of graphs, the underlying grammar induction is deterministic and determines grammar production rules able to reconstruct an in principle unbounded graph ensemble, containing the \"training\" graph set.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing our paper as well-written and the attention to detail in your review!\n\n*... combination with transformers… and thus a weakness of the paper is not spending some more time on this…. what do you think can be hurdles that this would face?*\n\n* To clarify: we **did** use Transformers as our architecture (see, e.g., Sec. 5.1). Our findings show Transformer decoders are powerful graph generative models when coupled with DIGGED’s principled, sequential derivations as a representation. In our response to ymms, we add an ablation study that shows, controlling for model architecture, other graph-as-a-sequence representations show less potential when combined with Transformers.\n* In Sec. 3.4, we explain the most natural setup is to use a Transformer as the encoder as well, but we found in practice this results in lower performance ((Token) vs (GNN)). In App. G., we discuss why we think that is the case and additional outlook on the future prospects.\n\n*I feel that a weakness is that it restricts to toy models, with only small mention of scaling (as opposed to spending a paragraph/appendix on that).*\n* Thank you for the comment. We do have a paragraph on scaling in App. D.3. We will elaborate further, given the results from the new ablation study in our response to 7hype. Our datasets have a size ranging from 47877 (CKT), 152160 (ENAS), to 2,000,000 nodes (BN); which span diverse real-world use cases. For each module of our algorithm, we have exact, approximate and heuristic solvers, with a number of parameters exposed to trade-off accuracy vs efficiency. The new ablation quantifies this trade-off, revealing good performance-speed elasticity.\n\nNow, we address your detailed comments one-by-one.\n\n*Line 030 : …make it clear what kind of validity that refers to*\n* Validity means the output has to be a connected DAG, and additionally satisfy domain-specific criteria. Defined in prior works, CKT DAGs need a stabilizing transconductance unit, BN need one node for each random var., and ENAS need a consecutive-numbered path from input to output. We will add these definitions to the paper.\n\n*Figure 1 : … in the upper 3 pictures of DAGs + grey motives…. shouldn't the arrow go the opposite way? picture 2)...*\n* Thank you for the attention to detail. The grey edge directions are actually variables we **solve** for (in step 2. Compute possible redirections) to maximize rule definition **compatibility** among occurrences of the subgraph. Currently, the occurrence in DAG 1 induces the instruction: “for each green in-neighbor, add out-edge from node 2”. DAG 2 induces the instruction: “for each green **out**-neighbor, add out-edges from **both** nodes 1 and 2”. If in DAG 1, we reverse the gray arrow, the two cases are no longer compatible. Should we add out-edges from both 1 & 2 to each green out-neighbor? or just node 2? Either way, there is a conflict. Semantically, these two cases are different (hence labeled a vs b), requiring different but consistent instructions.\n\n*...lines 155-158, ... why would that rule create a conflict, can you expand some more on the explanation?*\n* There is a similar explanation for picture 2. Reversing the edge would create incompatibility between the occurrences in DAG 2 vs DAGs 1 & 3.\n\n*The dags in the figure are not numbered, so what does “two” and “three” mean?*\n* We apologize for not numbering the top three DAGs. We will add it.\n\n*Line 140 “linearizes”…*\n* Good suggestion! We will replace it with “This simplifies the parse tree to a rooted path”.\n\n*Line 170 - 183 : from ‘At a high level’ onwards…*\n* Thank you. We will try to simplify the wording, keep the formulas and refer interested readers to the more elaborate explanation in App. B.1.\n\n*what does”‘the clique solution” mean?*\n* Sec. 3.2.2. describes how we solve for the optimal set of grey edge redirections, formulated as a graph. Each node is one way to set the edge directions for a subgraph occurrence. Each edge means the occurrences are compatible. The clique solution is the maximal set of nodes on this graph that are all compatible.\n\n*“the or-reduction” is followed by a formula which I don't follow… can you explain a bit?*\n* Right. In the graph, each node is an assignment to the grey edge directions for an occurrence, and from it we deduce an inset: the set of instructions that must be in the rule definition for that node. After we obtain a maximal set of compatible nodes, we OR all the insets to obtain the lower bound on the final instruction set.\n\n*section 3.3, point 3 has an \"i)\"*\n* Removed.\n\n*Line 207…*\n* We propose a CYK-like **dynamic** programming algorithm for DAGs, to find all derivations, where we memoize intermediate results. See App. D. for details.\nLine 211 \"memoization\".\nFixed!\n\n*Relate to objectives of compositional generalization*\n\n*Expand on scaling issues for much larger graphs... complexity of algorithm*\n\nDue to char limit, we will answer your two remaining questions in our responses to DetZ & 7hpe!", "claims_and_evidence": "The claims are partly theoretical, and partly about usefulness in practice.\n\nThe theoretical claims about the parsings (subjacent to the proposed grammar induction) that are produced by the algorithms are \n1) uniqueness of the parsing of each graph in the dataset\n2) surjectivity of the production from the obtained grammar (i.e. that we can recover the dataset as a subset of the grammar-produceable graphs)\n3) that DAG property is valid for the produced graphs.\nThese are proved/verified in the appendix. \n\nThe practical applications of the proposed parsing are for Neural Architecture Search, Bayesian Networks and Analog Circuit Design. \nCompared to other methods, this algorithm gives 100% validity of the DAGs and very high validity of the constructed cycles. The novelty of the  graphs produced is lower than the benchmarks. \n- The 100% validity is to be expected given the theoretical guarantees, but it's important to have a practical confirmation of that.\n- On the other hand, the low novelty compared to other methods seems to be a negative aspect for the method. \n\nSeveral case studies are presented, in which a positive point is slightly higher interpretability due to deterministic decoding. \nHowever, the presented examples are extremely simple, and I don't see how the claim for better interpretability would scale to applications in which the grammar / parsing encoding shows all its compositional generalization capability.", "methods_and_evaluation_criteria": "I think that the evaluation criteria are alike the literature, and they have the same flaws as the ones of competing approaches, which is that the examples are often oversimplified.", "theoretical_claims": "I think that the proofs are correct.", "experimental_designs_or_analyses": "I did not fully check them in full detail, but at a cursory look they look OK.", "relation_to_broader_scientific_literature": "I think that this principled and deterministic approach to parsing graphs is an important new addition to the literature, as also highlighted by comparisons in tables 1 and 2.", "essential_references_not_discussed": "I am not aware of works that have not been cited.", "other_strengths_and_weaknesses": "I think that the paper is well written and clear.\nThere are some points that can be easily improved, mentioned below in the comments part.\n\nI feel that a weakness is that it restricts to toy models, with only small mention of scaling (as opposed to spending a paragraph/appendix on that).\n\nAlso, there is a cursory mention of use of the underlying encoding in combination with transformers, but perhaps this combination will have issues and hurdles, and thus a weakness of the paper is not spending some more time on this direction, which to me seems like one of the main future prospects for this line of research.", "other_comments_or_suggestions": "See strengths/weaknesses part.\n\nHere are some more comments / typos.\n\nLine 030 : about positive properties of the approach, producing \"valid\" outputs is mentioned and puzzling at this point, I think it'd be good to expand and make it clear what kind of validity that refers to\n\nFigure 1 : there are some things I am not following, in the upper 3 pictures of DAGs + grey motives. Maybe can you explain so I can be sure I understand?\n picture 1) : there is a puzzling grey arrow from \"(b)\" to the grey oval -- shouldn't the arrow go the opposite way?\n picture 2) : there is a puzzling grey arrow from \"(d)\" to the grey oval -- shouldn't the arrow go the opposite way?\n\nAbout the explanation of Figure 1, lines 155-158, I don't follow this part \n\"However, adding such an instruction would create a conflict with the motif’s occurrences in DAGs two and three\"\n- The dags in the figure are not numbered, so what does \"two\" and \"three\" mean? \n- Why would that rule create a conflict, can you expand some more on the explanation?\nI tend to think that the reference to the subpictures of Figure 1 is wrong, so can you verify/explain?\n\nLine 140 \"linearizes\" -- can you replace it by another word or remove it? this has nothing to do with linear algebra, so it may be confusing.\n\nLine 170 - 183 : from \"At a high level\" onwards, I don't follow some of the wording of the explanation (the formulas are OK and would be fine if you remove the words mentioned below, but the wording is what I care about here): \n- what does \"the clique solution\" mean?\n- \"the or-reduction\" is followed by a formula which I don't follow why is some \"or-reduction\".. can you explain a bit?\n\nIn the beginning of section 3.3, point 3 has an \"i)\" which probably should be removed\n\nLine 207 \"but we present a linear programming\" : what does that even mean?\n\nLine 211 \"memoization\" lacks an \"r\" I guess.", "questions_for_authors": "1) See also \"strengths and weaknesses\" part, what do you think about those comments?\n\n2) Can you relate your proposed method to the objectives of compositional generalization?\n\n3) I return to the use of your framework in combination with transformer architectures. What do you think can be hurdles that this would face?\n\n4) Can you expand on scaling issues for extending your envisaged applications to much larger graphs? And when the graph size grows to infinity in some regime on the valence and graph structure, can you predict the complexity guarantees for your algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YFGn16G4A3", "reviewer": "Reviewer_DetZ", "summary": "This paper discusses how to convert a directed acyclic graph (DAG) into a sequence, allowing for sequence decoding based on autoregressive models. The paper proposes a method to transform a graph into a sequence in the form of a context-free grammar. The core idea is to induce the grammar from existing data using statistical methods, and then use the statistically derived grammar to convert the DAG into a sequence. Experimental results show significant improvements on certain tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Thank you for recognizing the reasonableness and positive experimental results of our work!*\n\n* In addition to recognizing our method as “converting a graph into a sequence”, we want to add there is a deep motivation from the objectives of **compositional generalization**! Contrary to what a “sequential” representation may imply, DIGGED is intrinsically compositional (Fig. 2 top). In fact, DIGGED is trained to embed DAGs with similar hierarchical compositions to similar points in latent space. For instance, if DAG 1 is (uniquely) represented as W->X->Y and DAG 2 as W->X->Z, the autoregressive decoder has to predict the same first two tokens, which moves the two DAGs to similar points in latent space. Combined with the relational inductive bias of our DAGNN encoder, the autoencoder objective can be viewed as combining both the relational and hierarchical inductive bias to learn expressive and generalizable representations.\n\n*“My main concern is that the entire grammar induction process is based on symbolic statistics rather than end-to-end representation learning. The limitation of this approach is that the entire learning process is pipelined, thus creating a certain gap with the subsequent neural module.”*\n\nThanks for raising this point! Here are some of our thoughts:\n\n1. The symbolic-neural divide is to some extent unavoidable when working with discrete, irregular data like DAGs. Our main reference point is existing methods that still generate a graph sequentially without any symbolic statistics, using naive sequential representations. The core contribution of our work is showing there is a principled, sequential representation that outperforms such methods and is agnostic to the domain.\n2. The same limitation exists in language models, where an algorithm like byte-pair encoding (BPE) is the standard way to build a vocabulary building up from the character level. Practice shows larger tokens improve downstream performance [1] and efficiency [2].\n3. Although seemingly a limitation, pipelining does have a few advantages. It allows the vocabulary derived from symbolic statistics to be transferred across models. It doesn’t require re-training end-to-end representations from scratch. Lastly, the mined vocabulary can be an inductive bias that can capture domain-specific insights, as shown in our case study (App. E.1).\n4. An ongoing effort of ours is optimizing grammar induction beyond unsupervised objectives like minimizing description length. End-to-end learning of the vocabulary and propagating feedback will be essential for further improvements.\n\n*Simply analyzing the effectiveness of grammar induction through case studies might not be comprehensive enough. Evaluation on some real-world benchmarks could be introduced to make the results more intuitive. For instance, text can be treated as a graph, and the F1 score can be calculated by comparing the statistically derived structures with manually annotated syntax.*\n\n* Great idea! The main challenge in this study is that DAG domains like circuits or neural architectures lack high-level annotations. Thus, for circuits, we resorted to case studies with experts. A systematic evaluation of the grammar quality is an active direction for us, especially when manual annotations are available. Natural language does have such annotations, and we are looking into it! In particular, we’re looking to induce grammars of phrase structures from Penn TreeBank, then generate novel, diverse phrase structure trees that can be evaluated by its plausibility. For example, by substituting words for POS tags, we can also evaluate how natural and grammatical the sentences are. We hope to get around to finishing this soon! For extra motivation, we hope you can endorse this study, which opens multiple avenues of future research!\n\n[1] Large Vocabulary Size Improves Large Language Models. arXiv:2406.16508\n\n[2] Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies. NeurIPS 2024.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "See Strengths And Weaknesses", "theoretical_claims": "NA", "experimental_designs_or_analyses": "This method achieves notable improvements on downstream tasks.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n1. How to convert a graph into a sequence and integrate it with an auto-regressive model is a question worth exploring. Moreover, uncovering the intrinsic relationships between nodes through grammar induction and linearizing the graph is a reasonable approach.\n\n2. The experimental results are quite positive. By converting graphs into sequences, the existing autoregressive models can be fully utilized, achieving relatively notable results in downstream tasks.\n\nWeaknesses:\n1. My main concern is that the entire grammar induction process is based on symbolic statistics rather than end-to-end representation learning. The limitation of this approach is that the entire learning process is pipelined, thus creating a certain gap with the subsequent neural module.\n\n2. Simply analyzing the effectiveness of grammar induction through case studies might not be comprehensive enough. Evaluation on some real-world benchmarks could be introduced to make the results more intuitive. For instance, text can be treated as a graph, and the F1 score can be calculated by comparing the statistically derived structures with manually annotated syntax.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O6s666rZec", "reviewer": "Reviewer_7hpe", "summary": "In this paper, the authors propose a novel framework for mapping Directed Acyclic Graphs (DAGs) to sequences via directed graph context-free grammars. Importantly, the authors formulate graph grammar induction as a Minimum Description Length (MDL)-based compression, achieved through an intricate sequence of graph optimization problems. The obtained grammar enables subsequent sequence-based learning tasks using transformers (possibly opening a new bridge between graph-based problems and the emerging LLM technologies) and variational autoencoders (VAEs). Empirical results are demonstrated on small- to medium-scale datasets involving neural architectures, Bayesian networks, and circuit designs.\n\n## Update after rebuttal\nI believe the clarifications and additional experiments promised by the authors constitute a good improvement of the present manuscript. While I still find the presentation very dense and technical, I will raise my score to a 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging the novelty and strengths of our interesting, theoretically principled framework!\n\n*There are some clear scalability concerns due to NP-hard grammar induction, and the authors propose a brute-force approach…. There is a list of possible adjustments and heuristics in the appendix, but they are never tested (if I understand correctly). Moreover, this crucial discussion is largely ignored in the main text…. theoretical limitations, particularly the NP-hardness of grammar induction, are relegated to the appendix…*\n\n* The adjustments and heuristics are in fact used in our implementation. In many places, we resort to approximate approaches wherever needed. For example, Subdue is a well-known and fast approx. subgraph mining library. The pseudocodes ``fast_subgraph_isomorphism, approx_max_clique, quick_hitting_set” mean approximation algorithms. We will explicitly say these are approximate/heuristic algorithms in the paper, along with known complexity guarantees.\n* Here are the NP-hard submodules used within grammar induction, and the exact/approximate/heuristic options, along with any parameters which tradeoff accuracy vs speed:\n  * Frequent subgraph mining (FSM): \n    * Approximate: We use the Subdue library. It has various options for pruning the search. Parameter: beam_width (used for subgraph expansion).\n  * Max clique:\n    * Exact (O(exp(n))): networkx’s cliques library\n    * Approximate (O(poly(n))): We use networkx’s O(|V|/(log|V|)^2) approximation algorithm.\n    * Heuristic (O(n)): (Repeat K times) Initialize a random node, iterate over all remaining nodes in random order, adding any that satisfies clique condition. Parameters: K\n  * Hitting set problem during disambiguation:\n    * Exact: our own implementation\n    * Approximate: Beam search. Parameters: beam width\n* Our datasets have variable sizes from 47877 (CKT), 152160 (ENAS), to 2,000,000 nodes (BN), which span the range of real-world use cases. We use the size of the input to toggle between different options, trading off accuracy and efficiency. Roughly speaking: CKT mostly invokes exact/approximate solutions, ENAS approximate/heuristic solutions and BN heuristic solutions.\n* We apologize for relegating the discussion around complexity to the Appendix and will bring the major conclusions to the main text.\n\n*...there is no clear study on the scalability of the grammar induction process to large datasets… lacks controlled experiments showing the downstream performance loss if pruning heuristics over the brute-force MDL algorithm are introduced in larger datasets…. potentially it would be nice to see some tests where the downstream effects of an imperfect grammar induction are studied.*\n* Thanks for proposing this additional control study. We agree it is crucial to quantify how approximations/heuristics chosen to speed up the NP-hard submodules will affect the downstream performance.\n* Due to CKT being the smallest dataset, the main paper results already reflect the exact and approximate settings. Thus, we can measure the performance gap and efficiency gains by using heuristic settings for one submodule at a time. Specifically, we tried the following ablations:\n  1. For Subdue (FSM), use beam width=3 instead of 4\n  2. Always use heuristic (max clique) instead of approx., with K=10\n  3. Always do beam search instead of exact, with beam_width=10.\n  4. Skip Algo. 7 (disambiguation), losing property 1.\n\n* Ablation 3 did not affect any of the samples. Due to small input (derivation) sizes, it is not a bottleneck and does not introduce meaningful changes.\n* Here are the results for Abl’s 1 and 2.\n\n||Unique|Novel|Gain|BW|PM|FoM|1st|2nd|3rd|%Faster|Compress Ratio|\n|-|:-:|:-:|-|-|-|-|-|-|-|-|-|\n|Abl.1|65.6|69.1|0.623,0.777|0.628,0.783|1.003,0.258|0.624,0.786|267.55|253.61|246.78|562\\%|2.04|\n|Abl.2|91.3|85.1|0.629,0.773|0.629,0.788|1.005,0.251|0.617,0.797|278.93|278.93|267.61|1844\\%|2.13|\n|Abl.3|97.3|100|0.635,0.793|0.630,0.785|0.993,0.316|0.625,0.785|306.32|290.42|260.97|~300\\%|2.32|\n|DIGGED|98.7|99.9|0.630,0.791|0.635,0.784|0.990,0.314|0.627,0.787|306.32|296.82|265.53|0%|2.18|\n* We see these modifications provide significant speedups over the original runs. The latent space quality and Bayesian optimization results slightly benefit from more accurate solutions to the FSM and max clique submodules, but they are still reasonably close. We do note that the max clique submodule has better marginal returns when trading off accuracy for speed, so we recommend starting with that. We will include these findings in the main paper.\n\n*Can you clarify the advantages of grammar-based encoding over simpler encoding schemes for practical tasks?*\n* Please see our response to ymms, where we add a new ablation study, comparing against simpler encoding schemes, while fixing the same model architecture. Our findings show the naive encoding experience issues with decoding and lowers downstream performance.\n\nWe hope we've addressed your concerns!", "claims_and_evidence": "The authors claim that their grammar-based approach provides a compact, principled, and lossless sequential representation of DAGs, which could improve subsequent generative modeling, property prediction, and Bayesian optimization tasks. The mapping to an abstract context-free grammar seems very interesting, although some of the derivation details are hard to grasp for a non-expert, especially given the extremely dense and technical presentation.\nThe authors provide convincing evidence that, once the induction is completed, DIGGED outperforms several baseline models.", "methods_and_evaluation_criteria": "DIGGED relies on an MDL-based grammar induction algorithm, encompassing different graph optimization problems, including frequent subgraph mining, compatibility maximization, and rule disambiguation. The evaluation focuses on the downstream performance once the grammar is derived, and the metrics include graph validity, uniqueness, novelty, predictive performance, and effectiveness in Bayesian optimization. However, there is no clear study on the scalability of the grammar induction process to large datasets, and the study lacks controlled experiments showing the downstream performance loss if pruning heuristics over the brute-force MDL algorithm are introduced in larger datasets.", "theoretical_claims": "The authors claim theoretical guarantees of one-to-one and onto mappings between DAGs and the graph-grammar produced sequences. However, critical theoretical limitations, particularly the NP-hardness of grammar induction, are relegated to the appendix, reducing transparency on the true bottle-neck of the proposed approach.", "experimental_designs_or_analyses": "The presented experiments span multiple real-world DAG datasets, but primarily focus on relatively small or moderate sizes. The paper shows strong empirical results in these controlled environments (where the authors claim the grammar induction takes \"few minutes\"),  but lacks rigorous scalability analyses of the grammar derivation for larger, real-world datasets. For example, it is entirely unclear how the brute-force approach for the grammar induction could be applied to a large molecule-/protein-structure dataset.", "relation_to_broader_scientific_literature": "The work is well placed in the scientific context of graph generative modeling.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "*STrenghts:*\n* The authors propose an interesting and theoretically principled grammar-based framework for graph generative modeling.\n* The proposed (lossless) mapping enables sequence-based learning and might allow new LLM-based approaches.\n* The downstream performance is very competitive varied (medium sized) benchmarks\n\n*Weaknesses:*\n* The presentation is dense and overly technical. Given this conference is a general ML conference, I would think it is best to write the paper to be readable by a researcher working on related fields, while in this case, a non-expert reader will struggle in deciphering the technical terminology and the dense visual representations.\n* There are some clear scalability concerns due to NP-hard grammar induction, and the authors propose a brute-force approach (at least in the experiments in the main). There is a list of possible adjustments and heuristics in the appendix, but they are never tested (if I understand correctly). Moreover, this crucial discussion is largely ignored in the main text.", "other_comments_or_suggestions": "* I believe a major restructuring of exposition is needed to enhance readability and accessibility for non-expert readers.\n* Essential NP-hardness and complexity discussions should be moved to the main text, to provide transparency about the computational bottleneck of this novel approach.\n* Scalability and computational analyses for large-scale data must be explicitly discussed, and potentially it would be nice to see some tests where the downstream effects of an imperfect grammar induction are studied.", "questions_for_authors": "* Given the NP-hardness of grammar induction, how practical is your method for datasets significantly larger or more complex than those demonstrated?\n* How does grammar induction complexity grow empirically with dataset size and graph complexity?\n* Have you explored heuristic or approximate methods to improve scalability, like the ones proposed in the appendix?\n* Can you clarify the advantages of grammar-based encoding over simpler encoding schemes for practical tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: After considering the rebuttal, all reviewers propose to accept this paper for ICML. 
They highlight the convincing empirical evidence as well as the theoretical contributions of the paper (really, the appendix).
Decision: Accept (poster)