acceptodds
Under review as a conference paper at ICLR 2027

Unsupervised Induction of Neural Graph Grammars

Abstract

Probabilistic graph grammar provide a principled framework for modeling graphs through latent compositional processes, yet existing approaches have largely remained confined to statistical models and linguistic applications. We introduce neural graph grammars, establishing a flexible neural parameteriztaion while preserving exact inference over latent derivations. We show that structural encoding improves generalization through parameter sharing across structurally related rules. We further demonstrate the applicability of learned graph grammars beyond language, using them for graph generation and molecular property prediction. Together, these result show neural graph grammars as a compositional model for learning, generating, and analyzing graphs across domains.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
unsupervised learning, graphs, compositional structure

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_gAnCOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces neural parameterizations of probabilistic graph grammars while retaining exact inference over derivations. It evaluates likelihood and generalization on semantic graphs, graph generation, and molecular property prediction.

Critical strengths

Sharing information across structurally similar rules makes sense, especially for rare productions. Keeping exact inference is useful, and the experiments show applications beyond fitting linguistic graphs.

Critical weaknesses
  1. The handling of unseen rules is unclear. Appendix E says the grammar comes from training derivations, so how do the unseen rules in Table 3 enter the inventory? Appendix F also says its grammar is extracted “from the corpus” without specifying whether this uses only training data.

  2. The molecular comparisons use the same grammar-admitted molecules, but the paper does not report how much of each dataset is excluded. Table 5 also lacks a uniform-rule grammar baseline to separate the benefit of learning rule probabilities from the grammar itself.

  3. The related work should discuss recent neuro-symbolic graph generation works like ConStruct [1] and NSGGM [2]. Both incorporate structural constraints into graph generation.

Reference:

[1] Madeira et al. (2024). Generative Modelling of Structurally Constrained Graphs. NeurIPS 37, 137218–137262.

[2] Geng et al. Neural Proposals, Symbolic Guarantees: Neuro-Symbolic Graph Generative Modeling. NeurIPS, 2026. arXiv:2602.16954.

Questions for authors
  1. How are unseen rules handled in Table 3, and is the Appendix F grammar extracted strictly from training data?

  2. What fraction of each molecular dataset does the grammar admit, and how does a uniform-rule version perform in Table 5?

  3. Can you compare your approach with [1] and [2]? If a direct comparison is not feasible, please explain how the methods differ in supported graph structures, generation procedure, and computational cost.

Reviewer_B9V3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors rely on existing framework of hyper-edge replacement grammars to decompose an undirected acyclic graph into a tree of subgraphs. They define a probability distribution over a graph as a sum (mixture) of products (factorizations), where the sum goes over all possible trees, and the product decomposes each tree into all rule applications in that tree. To address the intractability of this construction, they assume conditional independence based on left-hand-side nonterminal rules in the product distribution and follow existing works that rely on dynamic programming to share the computations among the trees. They continue by proposing to parameterize this distribution by a deep neural network. The authors' model is then evaluated on a range of small-scale synthetic and real-data examples, presenting a short ablation study on recovering latent rule probabilities, generalization for different parameterizations of their model, and a comparison with a few selected approaches in the context of graph property prediction and generation.

Critical strengths

The paper presents an interesting construction of a probabilistic model over an undirected acyclic graphs that can be of value to the community; however, its experimental validation and comparison with the current state-of-the-art models is weak.

Critical weaknesses

Major issues:

The experimental study in Sections 4 and 5 is very limited. The scale and the number of datasets used in these sections is small and the number of compared models is very low for the common standards in the community. Certain fundamental datasets and benchmarks that have become crucial to the community are missing, including the standard molecular generation benchmark, e.g., QM9 and Zinc250k. It is unclear whether the results in Sections 4 and 5 were obtained as an average over multiple random seeds except Table 5 (which is the only one that states this). It is unclear how the uncertainty values in Table 1 were computed. More on this in the questions below.

The related work on graph generative models covers no work older than 2023. The second part of the related work, i.e., probabilistic and neural grammars, contains only one paper from 2025. There were many new models that should be covered in the related work. For this reason, the paper's positioning is rather narrow and could benefit from better contextualization of the related models, especially those that are architecturally similar and also interested in designing tractable probabilistic distributions over graphs, including

Loconte, Lorenzo, Nicola Di Mauro, Robert Peharz, and Antonio Vergari. "How to turn your knowledge graph embeddings into generative models." Advances in Neural Information Processing Systems 36 (2023): 77713-77744.

Papez, Milan, Martin Rektoris, Vaclav Smidl, and Tomas Pevny. "Sum-product-set networks: Deep tractable models for tree-structured graphs." In International Conference on Learning Representations, vol. 2024, pp. 28633-28662. 2024.

Papez, Milan, Martin Rektoris, Vaclav Smidl, and Tomas Pevny. "Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs." In 41st Conference on Uncertainty in Artificial Intelligence, pp. 3416-3450. 2025.

Errica, Federico, and Mathias Niepert. "Tractable probabilistic graph representation learning with graph-induced sum-product networks." In International Conference on Learning Representations, vol. 2024, pp. 24981-25000. 2024.

The paper is missing additional references that broadly represent more recent developments in the flow matching for graph generation, e.g.,

Eijkelboom, Floor, Grigory Bartosh, Christian A. Naesseth, Max Welling, and Jan-Willem van de Meent. "Variational flow matching for graph generation." Advances in Neural Information Processing Systems 37 (2024): 11735-11764.

Roos, Daan, Oscar Davis, Floor Eijkelboom, Michael M. Bronstein, Max Welling, İsmail İlkan Ceylan, and Jan-Willem van de Meent. “Categorical Flow Maps.” In Proceedings of the Forty-Third International Conference on Machine Learning, 2026.

Minor issues:

Section 1 contains improperly defined or undefined mathematical symbols that are defined only very late in the remaining text, e.g., defining a symbol in parentheses, (D)(D) is very nonstandard, the mechanism behind ∑yield(D)=G\sum_{yield(D)=G} in undefined. What is meant by r∈Dr\in D and how it relates to Figure 1? This is defined later on in the text, indeed, but using all such concepts without proper definitions when opening the paper is hard to follow.

The factorization of the joint probability over the "vertex- and edge-level decisions" in Section 1 is clearly wrong, containing undefined indices and having fatally wrong summation over the indices.

The quality of Figure 1 is very poor, containing many overlapping symbols and arrows.

The paper could use a more thorough spellcheck, e.g., "consective" (Section 1), etc.

The space of possible graphs grows super-exponentially, not only exponentially as claimed in Section 1.

"A production is A→RA\rightarrow R" is incompletely defined in Section 2.1 and then redefined in Section 3.2. This is confusing on the first reading.

The equations in the opening of Section 5 were already stated before.

Questions for authors

Please, see above.

Can you be more specific on what each of the distinct approaches to parameterizing the grammar in Table 2 are about? Their names suggest something the reader can only guess.

If the results in Sections 4 and 5 were obtained as an average over multiple seeds (which is unclear based on the comment in Section E), then where are the standard deviations? What are the uncertainty intervals in Table 1? How were they obtained?

Why using only 4 datasets from the MoleculeNet benchmark? Given their small size, it should not be a problem to include all the datasets. There is plenty of other methods over the literature that the authors can include into the comparison.

Reviewer_mcrsOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes neural parameterization of probabilistic hyperedge replacement grammars (HRGs), using learned or structural rule embeddings while retaining exact inference over latent derivations. Experiments cover synthetic grammar recovery, NLP semantic graphs, graph generation, and molecular property prediction.

Critical strengths

The framework is mathematically coherent and demonstrates that neural rule scoring can be integrated with existing HRG inference algorithms. However, this is a modest extension of established techniques rather than a compelling new contribution.

Critical weaknesses

Severely deficient literature review and insufficient novelty. The paper's characterization of learned graph grammars beyond NLP as largely unexplored is untenable. It overlooks an entire established line of work, including:

Data-Efficient Graph Grammar Learning for Molecular Generation (Guo et al., ICLR 2022). Hierarchical Grammar-Induced Geometry for Data-Efficient Molecular Property Prediction (Guo et al., ICML 2023). Representing Molecules as Random Walks Over Interpretable Grammars (Sun et al., ICML 2024). Foundation Molecular Grammar (Sun et al., ICML 2025). Directed Graph Grammars for Sequence-based Learning (Sun et al., ICML 2025).

These works already thoroughly investigate grammar induction, molecular generation, and property prediction, including HRG-based approaches. Omitting this literature fundamentally misrepresents the state of the field and substantially undermines the claimed novelty. The technical contribution is nearly non-existent. Chiang et al. (2013) already established HRG parsing and packed-forest inference. The paper largely reuses this machinery and introduces neural scoring of production rules, an idea already well established in neural PCFGs. Worse, despite claiming grammar induction, the method assumes a fixed rule set and learns only its probabilities rather than induce rules end-to-end like the cited works.

Weak experiments that fail to substantiate the claims. The evaluation concentrates on synthetic grammars and NLP semantic graphs, settings where the underlying techniques are already well established. The purported extension beyond NLP is supported by shallow experiments with conspicuously inadequate baselines. Molecular generation omits established grammar-based generators such as DEG and FMG, while molecular prediction omits Geo-DEG and RandomWalk. The reported results are mixed even against the limited baselines selected. The experimental design therefore fails at demonstrating an advance over existing methods addressing the same problems. Without comparisons to the relevant graph-grammar literature, there is little evidence that the proposed neural parameterization offers a meaningful contribution to molecular generation, prediction, or graph-grammar learning more broadly.

Questions for authors

How can the authors justify their novelty claims while omitting DEG, Geo-DEG, RandomWalk, FMG, and DIGGED, which have already established learned graph grammars beyond NLP? Beyond neural rule scoring, what is technically new relative to Chiang et al. (2013) and established neural PCFGs? Why is this called grammar induction when the grammar's symbolic rule set is fixed? Why are established grammar-based methods excluded from the molecular experiments? What evidence supports the claimed advances without these essential comparisons?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.