Research map / Graph learning / Graph algorithms and clustering
Directed Graph Grammars for Sequence-based Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DIGGED, which maps DAGs to unambiguous edNCE grammar derivation sequences via MDL-based grammar induction, then trains a VAE with Transformer rule decoder for DAG generation, property prediction, and Bayesian optimization.
Problem
Decoding DAGs in a principled way is hard because DAGs have many topological orders; existing autoregressive and sequential decoders are ambiguous, unvalid, or order-dependent.
Approach
Parse DAGs with an unambiguous context-free directed graph grammar (edNCE) induced by iterative MDL-driven frequent subgraph mining and compatibility max-clique solving, so each DAG maps to a unique sequence of production rules that is then modeled by a sequence VAE.
Key results
- On ENAS and BN, DIGGED (GNN) reaches 100% validity and 98.7% / 97.6% uniqueness, with 100% novelty on BN.
- On CKT, DIGGED (GNN) achieves 26.5% lower FoM RMSE (0.627) and ~60% higher Pearson r (0.787) than CktGNN.
- Bayesian optimization on CKT finds a novel design with FoM 306.32, exceeding the best CktBench301 design.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DIGGED grammar-rule sequences rather than default node ordering (ablation) | DAGNN encoder with Transformer decoder · ENAS | Validity (%): 96.1 -> 100 | Helped |
| Use DIGGED grammar-rule sequences rather than default node ordering (ablation) | DAGNN encoder with Transformer decoder · BN | Validity (%): 95.8 -> 100 | Helped |
| Use BFS node ordering instead of DIGGED rule sequences (ablation) | DAGNN encoder with Transformer decoder · ENAS | Validity (%): 100 -> 40.8 | Hurt |
| Use BFS node ordering instead of DIGGED rule sequences (ablation) | DAGNN encoder with Transformer decoder · BN | Validity (%): 100 -> 2.2 | Hurt |
| Use random node ordering instead of DIGGED rule sequences (ablation) | DAGNN encoder with Transformer decoder · ENAS | Validity (%): 100 -> 0% | Hurt |
| Use random node ordering instead of DIGGED rule sequences (ablation) | DAGNN encoder with Transformer decoder · BN | Validity (%): 100 -> 8.4 | Hurt |
| Reduce Subdue beam_width from 4 to 3 (ablation) | DIGGED · CKT | FoM RMSE: 0.627 -> 0.624 | No clear effect |
| Reduce Subdue beam_width from 4 to 3 (ablation) | DIGGED · CKT | FoM Pearson r: 0.787 -> 0.786 | No clear effect |
| Use greedy max clique with K=10 random starts (ablation) | DIGGED · CKT | FoM RMSE: 0.627 -> 0.617 | No clear effect |
| Use greedy max clique with K=10 random starts (ablation) | DIGGED · CKT | FoM Pearson r: 0.787 -> 0.797 | No clear effect |
| Use beam search with beam_width=10 for hitting set instead of exact search (ablation) | DIGGED · CKT | FoM RMSE: 0.627 -> 0.625 | No clear effect |
| Skip disambiguation for early convergence (ablation) | DIGGED · CKT | FoM | Mixed |
Surprising findings
- Simpler node-order sequence encodings (BFS, random) destroy the decoder's ability to produce valid DAGs, e.g. 0% validity on random ordering for ENAS.
- DIGGED (TOKEN) latent space underperforms on ENAS property prediction (Pearson r 0.049), attributed to the large rule count (7504).
Limitations
- Grammar induction and disambiguation rely on NP-hard subroutines (subgraph isomorphism, max clique, hitting set), requiring approximations for large data.
- Deciding ambiguity of an edNCE grammar is undecidable, so one-to-one is only enforced over the data, not the full language.
- Token-based latent space underperforms on ENAS property prediction due to the large rule vocabulary (7504 rules).
Experimental setup
Datasets: ENAS Bayesian networks (bnlearn) CktBench101 CktBench301
Benchmarks: ENAS Bayesian networks CktBench101
Metrics: validity uniqueness novelty RMSE Pearson r FoM accuracy
Baselines: D-VAE S-VAE GraphRNN GCN DeepGMG DAGNN PACE CktGNN Graphormer GIN
Builds on: edNCE graph grammar Subdue DAGNN D-VAE CktGNN
Closest papers by meaning
- Directed Acyclic Graph Neural Networks (ICLR 2021 · similarity 0.89)
- Transformers over Directed Acyclic Graphs (NeurIPS 2023 · similarity 0.88)
- D-VAE: A Variational Autoencoder for Directed Acyclic Graphs (NeurIPS 2019 · similarity 0.88)
- ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.85)
- Learning Representations for Hierarchies with Minimal Support (NeurIPS 2024 · similarity 0.85)
- DAG-Math: Graph-Guided Mathematical Reasoning in LLMs (ICLR 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.