Directed Graph Grammars for Sequence-based Learning

Thank you for acknowledging the novelty and strengths of our interesting, theoretically principled framework!

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…

• 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.
• 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:
  • Frequent subgraph mining (FSM):
    • Approximate: We use the Subdue library. It has various options for pruning the search. Parameter: beam_width (used for subgraph expansion).
  • Max clique:
    • Exact (O(exp(n))): networkx’s cliques library
    • Approximate (O(poly(n))): We use networkx’s O(|V|/(log|V|)^2) approximation algorithm.
    • 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
  • Hitting set problem during disambiguation:
    • Exact: our own implementation
    • Approximate: Beam search. Parameters: beam width
• 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.
• We apologize for relegating the discussion around complexity to the Appendix and will bring the major conclusions to the main text.

...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.

• 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.

• 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:

  1. For Subdue (FSM), use beam width=3 instead of 4
  2. Always use heuristic (max clique) instead of approx., with K=10
  3. Always do beam search instead of exact, with beam_width=10.
  4. Skip Algo. 7 (disambiguation), losing property 1.

• 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.

• Here are the results for Abl’s 1 and 2.

• 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.

Can you clarify the advantages of grammar-based encoding over simpler encoding schemes for practical tasks?

• 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.

We hope we've addressed your concerns!

Thank you for recognizing the reasonableness and positive experimental results of our work!

• 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.

“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.”

Thanks for raising this point! Here are some of our thoughts:

1. 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.
2. 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].
3. 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).
4. 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.

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.

• 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!

[1] Large Vocabulary Size Improves Large Language Models. arXiv:2406.16508

[2] Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies. NeurIPS 2024.

Thank you for recognizing our paper as well-written and the attention to detail in your review!

... 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?

• 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.
• 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.

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).

• 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.

Now, we address your detailed comments one-by-one.

Line 030 : …make it clear what kind of validity that refers to

• 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.

Figure 1 : … in the upper 3 pictures of DAGs + grey motives…. shouldn't the arrow go the opposite way? picture 2)...

• 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.

...lines 155-158, ... why would that rule create a conflict, can you expand some more on the explanation?

• There is a similar explanation for picture 2. Reversing the edge would create incompatibility between the occurrences in DAG 2 vs DAGs 1 & 3.

The dags in the figure are not numbered, so what does “two” and “three” mean?

• We apologize for not numbering the top three DAGs. We will add it.

Line 140 “linearizes”…

• Good suggestion! We will replace it with “This simplifies the parse tree to a rooted path”.

Line 170 - 183 : from ‘At a high level’ onwards…

• 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.

what does”‘the clique solution” mean?

• 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.

“the or-reduction” is followed by a formula which I don't follow… can you explain a bit?

• 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.

section 3.3, point 3 has an "i)"

• Removed.

Line 207…

• We propose a CYK-like dynamic programming algorithm for DAGs, to find all derivations, where we memoize intermediate results. See App. D. for details. Line 211 "memoization". Fixed!

Relate to objectives of compositional generalization

Expand on scaling issues for much larger graphs... complexity of algorithm

Due to char limit, we will answer your two remaining questions in our responses to DetZ & 7hpe!

Thank you for recognizing our strong experimental results and asking insightful questions!

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.

• 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).
• 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.
• Methods under 2) are naive encodings, and we argue they are insufficient.
• We decided to do the ablation study you suggest. First, a few notes:
  • We fix DAGNN as the encoder as it is tailored for DAGs.
  • We fix the same decoder Transformer architecture and try different node-order encodings as the output targets.
  • (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.)
• We tried several common ways to define an ordering over nodes:
  • Default order (most baselines): whatever order the data comes in, topological
  • BFS (e.g. GraphRNN): a BFS traversal from a random initial node
  • Random order: a random order to the nodes

• 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).
• 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.
• 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.
• 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)!

Using graph grammar for graph generation tasks has been done before.... clarify unique, novel contribution to the field.

• 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.
• 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!

the metrics validity, uniqueness, and novelty….

• 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).