acceptodds
Under review as a conference paper at ICLR 2027

Rule-Guided Graph Synthesis: Integrating First-Order Logic into Deep Generative Models

Abstract

Existing graph generative models produce graphs that are often quite realistic, but sometimes miss domain-specific patterns. Enhancing graph learning with domain knowledge is one of the current frontiers for neural models of graph data. In this paper, we propose a new approach to enhancing deep graph generative models with knowledge that is represented by first-order logic rules. First-order logic provides an expressive formalism for representing interpretable causal knowledge about relational structures. Our conceptual contribution is a new first-order semantic loss function for training a graph generative model on relational data: maximize the model likelihood subject to a rule moment matching constraint, namely that the expected instance count of each rule matches its observed instance count. Our algorithmic contribution is a novel matrix-multiplication-based method for computing the expected instance count of a first-order rule for a Graph Variational Autoencoder model. Empirical evaluation across benchmark datasets shows that rule moment matching substantially improves the quality of generated graphs across multiple graph quality metrics.

Primary area:
generative models
Keywords:
Deep graph generation, First-Order Logic Rules, Neuro-Symbolic AI, Deep Learning

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_k9s4OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper guides graph generation by matching counts of first-order patterns. It computes these counts through matrix operations and adds the objective to GraphVAE, with experiments on six datasets.

Critical strengths

Matching rule counts seems like a reasonable way to tell a generator which structures matter. Keeping the GraphVAE backbone the same also makes the improvements on several datasets more convincing.

Critical weaknesses
  1. Proposition 1 seems incorrect as written. The left-hand penalty uses the unconditional model expectation, while the right averages conditional expectations under the variational posterior. Convexity alone does not justify switching distributions. Appendix A proves Proposition 2, so it does not resolve this.

  2. Both evaluation metrics exclude attributes. This leaves unclear whether the generated graphs actually match the attribute-dependent rule statistics the method is meant to capture.

  3. While the related work section covers some foundational neuro-symbolic and semantic-loss approaches, it provides limited discussion of more recent neuro-symbolic approaches that incorporate symbolic knowledge or structural constraints, like ConStruct [1] and NSGGM [2]. Although these approaches differ in objectives and mechanisms, adding them to the discussion would help better position the proposed method with recent advances in knowledge guided graph generation.

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

[2] Geng et al. (2026). Neural Proposals, Symbolic Guarantees: Neuro-Symbolic Graph Generation with Hard Constraints. NeurIPS 2026. arXiv:2602.16954.

Questions for authors
  1. Can Proposition 1 be corrected, or does it need additional assumptions?

  2. How well do generated graphs match the target rule statistics when attributes are included?

  3. Can the authors clarify how their approaches differ from recent constraints guided graph generation methods in terms of potential tradeoffs and capabilities?

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

This paper introduces first-order logic rules to GraphVAE. For each rule, a commuting matrix records the number of satisfying assignments for each pair of endpoint nodes. The training objective maximizes the model likelihood subject to a moment matching constraint: the expected commuting matrix of each rule should match the observed one. Both matrices are computed by multiplying adjacency matrices, with node features mapped to diagonal matrices. If the graph-state variables in each grounding are conditionally independent given the latent vector, the expected commuting matrix can be computed as the commuting matrix of the expected graph. Empirical evaluation across six datasets shows improved graph realism over the GraphVAE backbone and competitive, though mixed, results against DeFoG and LGD.

Critical strengths
  1. Overall, the paper gives a clear way to turn first-order rules into a trianing loss for GraphVAEs.

  2. The introduces matrix product computes both the observed and the expected rule statistics, which is simple and differentiable.

Critical weaknesses
  1. One point of concern for me is the novelty of the proposed semantic loss. The training objective feels closely related to GraphVAE-MM [1], which already establishes a Gaussian statistic-matching loss integrated with GraphVAE. While the paper introduces rule-based commuting matrices, the overlap with this prior work is not discussed. This makes it tough for me to delineate the exact boundaries of novel contributions against what is already established.

  2. Another concern for me is the experimental soundness. The GraphVAE baseline is cited to [1] (Sec. 1), but its stated objective includes only reconstruction and KL regularization (Sec. 4.1). Against this baseline, Tables 1 and 2 show large gains over this baseline on the three attribute-free datasets, where the rule statistics would reduce to purely structural statistics. This may indicate that the statistic-matching loss of [1] is missing from the baseline, and makes the source of the gains hard to evaluate.

  3. I could not find a proof of Prop. 1, and the claimed bound is not obvious to me.

[1] Kiarash Zahirnia, Oliver Schulte, Parmis Naddaf, and Ke Li. Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoders. NeurIPS 2022.

Questions for authors
  1. Could you clarify the methodological contributions beyond GraphVAE-MM?

  2. Does the GraphVAE baselines include its macro-level loss from GraphVAE-MM? If so, please provide a brief discussion to clarify the performance gains on synthetic graphs; if not, a direct comparison with it is helpful.

  3. Could you please provide a formal proof for Prop. 1?

Reviewer_HimFOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces a new approach for training neural networks that generate graphs. The approach is based on a loss function that minimises the violation of certain constraints (represented as what appear to be chain-like conjunctive queries - although it is called First-Order Logic by the authors) in the generated graphs. The approach ensures both that the likelihood of the expected patterns is high and that the average occurrence of such patterns falls within the expected average. The authors also propose a new algorithm to help in training their model. The experiments show that their approach often produces synthetic graphs that resemble realistic, reference graphs more than the graphs generated by other approaches.

Critical strengths

The experimental results show success in generating more realistic graphs over a majority of the considered benchmarks.

Novelty: as far as I am aware the algorithm suggested in the paper is novel and does not match anything existing before. It is unclear, however, in what ways the current algorithm differs from existing algorithms (the paper does not specify that).

Critical weaknesses

Clarity & Significance. The paper is not easy to read, because it often focuses on describing specific details of the approach but without providing a general intuition or high-level perspective of it. This is most clear (but not exclusive of), for example, in Section 4. Without such explanations, the paper is not accessible to a general ICLR27 audience. Furthermore, without such explanations, the main take-away of the paper is unclear - the algorithm seems effective for the experiments described here, but there appears to be no clear reason to use the algorithm in other settings. I would expect a discussion of what is the key underlying idea of the new algorithm and how it improves over existing algorithms. Furthermore, key concepts in the paper such as "observed" and "expected" commuting matrices are not defined. These terms are critical for the paper, since the novel algorithm is built to compute them.

Technical quality. The definition of the FOL language used in this approach is quite different from standard FOL. Furthermore, it is incomplete as several important symbols or expressions are introduced without definition (see questions below).

Novelty. The authors claim that their work is the first that uses a logic-based training loss with first-order logic, as opposed to propositional logic: "we incorporate knowledge expressed in first-order logic, rather than the less powerful formalism of propositional logic" This is simply not true; for the past few years, there have been many papers that also propose training neural models with loss based on formalisms more expressive than propositional logic, such as Description Logics (which seem particularly suited for relational data as they model explicitly properties and relationships). Moreover, the paper motivation initially suggests that full FOL formulas are allowed in this approach, but by looking at later sections of the paper one can see that this is not true. For example, terms seem to be function-free (including disallowing constants), which already removes an important part of the expressive power of FOL. More importantly, it seems that there is no negation or quantification, essentially reducing further the expressive power of the rules considered, making it much less than FOL. Furthermore, there have been many neuro-symbolic approaches that are inspired in chain-like rules (such as NeuralLP); while I am not aware whether they have been used for graph generation, it would be important to explain the relation between those approaches and the current paper.

In general, the paper is very opaque about the language of rules they use, and does not sufficiently or clearly relate it to relevant existing works. This alone is a major problem and enough to warrant rejection at this stage.

Questions for authors
  1. What exact subset of FOL do you consider in this work?

  2. How does your approach differ from existing neuro-symbolic approaches based on chain-like rules? If the answer to this question is that this is the first approach that applies such rules to graph generation (instead of link prediction or graph classification), then please state so clearly.

  3. Line 34: FOL rules typically do not have any probability; it is strange to see this.

  4. Line 38: this paragraph is rather vague. What is the precise relation between metapaths and rules? What specific subset of rules corresponds to metapaths?

  5. Line 143: why do nodes have only one single label? What does this label represent?

  6. Line 152: Please specify what a "value" is, what is a node attribute, and what precisely (the functor? the individual?) corresponds to the node attribute or label.

  7. Line 155: What is U?

  8. Line 158" What is "Python-style"? This is highly strange as FOL is defined and typically formulated independently of Python.

  9. Please provide a definition of expected and commuting matrix.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.