Logic-Guided Graph Denoising Diffusion Models

Logic-Guided Graph Denoising Diffusion Models Samuel Cognolato1,2 , Luciano Serafini2 , Alessandro Sperduti1,2,3 , Andrea Cavallaro4 1

arXiv:2610.23766v1 [cs.LG] 16 Oct 2026

Department of Mathematics “Tullio Levi-Civita”, University of Padova, Padova, Italy 2 Fondazione Bruno Kessler (FBK), Trento, Italy 3 Human Inspired Technology Research Centre (HIT), University of Padova, Padova, Italy 4 École polytechnique fédérale de Lausanne (EPFL), Lausanne, Switzerland

Abstract Graph diffusion models are competitive approaches for generating complex graph-structured data. However, when such distributions have strict structural constraints, diffusion models may fail to capture them exactly, resulting in the generation of invalid graphs. In this paper, we propose a method for grounding graph diffusion models in domain-specific knowledge via First Order Logic (FOL), leveraging its expressive and interpretable formalism to impose structural constraints on the generative process. We incorporate domain knowledge using classifier guidance, a technique that conditions the diffusion model’s distribution on external variables to exert control over the sampled data. During the generative process, classifier guidance steers the denoising trajectory to optimize an objective function, which we define as a fuzzy and differentiable relaxation of the logical rules. Our methodology requires only the specification of constraints in FOL, whose satisfaction is encouraged at inference time to guide a pre-trained generative model. We evaluate our approach by comparing the unconditional generation of knowledge graphs with our logic-guided framework, which incorporates domain ontologies as structural constraints during inference. This approach significantly increases the proportion of generated graphs that satisfy the ontological constraints.

1

Introduction

Graph generation involves learning an underlying data distribution to facilitate the synthesis of novel, realistic graph structures. Graph diffusion models (Jo, Lee, and Hwang 2022; Vignac et al. 2023; Huang et al. 2023; Cognolato et al. 2026; Cognolato, Sperduti, and Serafini 2026) and flowmatching models (Eijkelboom et al. 2024; Qin et al. 2024) can model distributions over graphs with discrete labels and continuous attributes. In some applications, such as biology, graphs need to satisfy domain-specific rules (Rigoni, Navarin, and Sperduti 2020) that define whether a graph is well-formed. However, neural generative models lack a mechanism to explicitly enforce structural constraints, which requires specialized techniques to tackle them. Thus, the problem of constrained graph generation, i.e., sampling Preprint

graphs from a subspace of elements satisfying a set of constraints, has gained traction (Liu et al. 2018; Rigoni, Navarin, and Sperduti 2025; Madeira et al. 2024). First Order Logic (FOL) (Barwise 1977) may serve as a unified approach to encode and combine heterogeneous constraints. FOL can be used to formalize properties in graphs, where node and edge labels are represented as unary and binary predicates, respectively (Cai, Fürer, and Immerman 1992). The rules may act on single nodes, their neighbors, and the type or direction of the relations, e.g., bipartiteness and transitivity. FOL rules may also act considering the whole graph structure, e.g., requiring the presence of a specific node type. The ability to operate both locally and globally provides a tool for controlling the structure and content of graphs. This setup has enabled the definition of ontologies for knowledge graphs, providing a schema for otherwise unstructured data (Gruber 1993). In this paper, we propose LTN-guidance, a methodology for injecting domain knowledge as FOL constraints into the generative process of graph diffusion models (Vignac et al. 2023), without any additional training. Our aim is to increase the probability of sampling valid graphs. First, we propose a graph signature, i.e., the collection of symbols defining the vocabulary of the first order language, enabling the definition of logical formulas over labeled graphs. During generation, we use classifier guidance (Dhariwal and Nichol 2021) to steer a pre-trained diffusion model toward optimizing rule satisfaction (the external objective function). Our method provides the target FOL constraints as Logic Tensor Network (LTN) (Badreddine et al. 2022) differentiable functions. A mechanism based on Focal Loss (Lin et al. 2017) allows adaptive reweighting of constraints, increasing the contribution of less satisfied sentences in the generative process. Finally, we propose cheaper implementations of LTN functions, e.g., for implementing cardinality constraints over edges. Our main contributions are: 1. A graph signature that allows the definition of logical rules over labeled graphs. We integrate the signature with axioms to ensure label exclusivity; 2. A plug-and-play method for steering graph diffusion models with knowledge in FOL. During inference, FOL constraints are translated to differentiable functions through Logic Tensor Network, and used to steer a pretrained unconditional model with classifier guidance.

3. We evaluated a popular graph diffusion model, DiGress (Vignac et al. 2023), with and without our technique, for the generation of small knowledge graphs from the IntelliGraphs benchmark (Thanapalasingam et al. 2023) against knowledge graph embedding and LLMbased approaches. We observe an improvement in validity, achieving > 95% in most datasets. 4. We performed generation with new rules, compatible and conflicting with the data, to evaluate the conditional indistribution and out-of-distribution validity, respectively. LTN-guidance consistently shows responsiveness to input formulas by producing a high fraction of valid graphs. To the best of our knowledge, this is the first inference-time FOL constraints guidance framework for graph diffusion.

2

Related Work

Constrained Graph Generation (CGG) can be based on deep learning or, in the specific case of FOL rules, on Weighted First Order Model Sampling (WFOMS). For deep-learning-based CGG, the application of constraints to deep graph generative models remains in its infancy, as very few works tackle the problem, or are limited to a specific class of constraints. Constrained Graph Variational Auto Encoders (CGVAE) (Liu et al. 2018) and Conditional CGVAE (Rigoni, Navarin, and Sperduti 2020) enforce valency constraints in the molecular domain, closely related to the out-degree of nodes. The model’s generative process is autoregressive, allowing at each step to disable linking with atoms that have filled up their valency. ConStruct (Madeira et al. 2024) is a diffusion model where the whole diffusion and denoising sequences remain in the constrained space, making the samples valid by design. However, the classes of constrains considered are limited to minor-hereditary properties that, if true for a graph, are also true for its minors. The generation of graphs can also be seen as the sampling of variables assignments satisfying the set of FOL rules. This has been explored in Weighted First Order Model Sampling (WFOMS) (Wang et al. 2024), closely related to Weighted First Order Model Counting (WFOMC) (Van den Broeck et al. 2011). Lifted (i.e., polynomial) sampling algorithms exist up to the C 2 fragment of FOL (Wang et al. 2024), that is, allowing sentences with universal and counting existential quantifiers ∀, ∃≥k , ∃≤k , ∃=k with up to two variables per sentence. Although exact in its sampling, lifted WFOMS’s limitation to two variables could render it ineffective for certain applications, such as ontologies with over 3 variables (Thanapalasingam et al. 2023). Regarding Knowledge Graph (KG) generation, where FOL ontologies are usually defined, there are two prominent KG completion methods: (1) entity embedding and probabilistic link prediction (Peng et al. 2023); (2) using Large Language Models (LLM) (Yao et al. 2025). The former is designed to predict missing links by computing the likelihood of new triples from the trained embeddings and not to generate new entities. The latter treats triples sets as a textual sequence, and new triples are generated as new tokens. However, knowledge graph embedding assumes link independence during sampling, limiting the expressiveness of the resulting graph

distributions; at the same time, treating graphs as text negates the inductive biases that facilitate scalability to larger structures. Thanks to the availability of KG data and their ontologies, we will evaluate our methodology on KG generation with FOL constraints.

3

Preliminaries

We present a formal definition of labeled graphs. A labeled graph G is a tuple G = (V, E, Λv , Λe ) where V is the set of nodes, E ⊆ V × V is the set of edges, Λv : V → Lv and Λe : E → Le are the node and edge labeling functions, where Lv and Le are the node and edge labels, respectively. Its tensor representation G = (X, E) is a more generation-friendly format, where X ∈ Rn×Dv is the node tensor, E ∈ Rn×n×De is the edge tensor, n is the number of nodes and Dv = |Lv | and De = |Le | + 1, comprising the absence of an edge as one of the De classes.

3.1

Diffusion Models for Graphs

Diffusion models (Ho, Jain, and Abbeel 2020; Austin et al. 2021) are a class of generative models where the objective is to learn an approximation pθ (G) with parameters θ of an unknown data distribution q(G). DDPMs achieve this as a Markov Chain Monte Carlo (MCMC) process, reaching convergence to the learned distribution after a certain amount of Markov transitions. Diffusion models for graphs (Vignac et al. 2023) jointly generate nodes, edges, and their labels. Two discrete diffusion processes (Austin et al. 2021) randomly flip node and edge labels in X and E, potentially removing or adding connectivity, proceeding from time t = 0 to t = T . The forward and trained reverse processes are defined as: q(G1:T |G0 ) =

T Y

q(X t |X t−1 )q(E t |E t−1 ),

(1)

t=1

pθ (G0:T ) = p(GT )

T Y

pθ (Gt−1 |Gt ).

(2)

t=1

We adopt the discrete graph diffusion formulation of DiGress (Vignac et al. 2023), which corrupts node and edge labels through categorical transitions and learns the reverse transition pθ (Gt−1 |Gt ). Our method leaves training unchanged and modifies this transition only at inference time.

3.2

First Order Logic

First Order Logic (FOL) deals with the formalization of facts, which can be either true or false. FOL operates on a first order language, described by a signature: Σ = (C, F, P),

(3)

where C is a set of constant symbols, F is a set of function symbols, and P is a set of predicate symbols. An interpretation I over Σ maps each constant c to a specific individual I(c) in a domain of discourse D, function symbols f to functions I(f ) : Dn → D of arity n, and predicate symbols P to relations I(P ) ⊆ Dn of arity n. Formulas ϕ are strings composed of variables symbols (e.g., x, y, z), non-logical symbols contained in the signature

Σ, and logical symbols, comprising connectives (conjunction, disjunction, negation) and quantifiers (existential and universal). The semantics of the logic defines the meaning of the logical operators. For example, classical FOL considers only truth values {0, 1} (false and true), while fuzzy logic also considers intermediate values in [0, 1]. A sentence, i.e., a formula with no unquantified variables, is satisfied by an interpretation I if applying I to symbols in Σ evaluates to true given the semantics of the logic.

4

Problem Definition

Generating labeled graphs G with constraints ϕ entails two main challenges: 1. To translate any constraints into the space of graphs, defining relations over nodes, edges and their labels. This requirement allows checking the constraint satisfaction over graphs, and generalize it as a function ϕ(G), which is 1 if the graph G satisfies the constraints, 0 otherwise. 2. To generate with a model pθ (G) graphs that satisfy ϕ. Given an existing knowledge base in FOL, defining rules over graphs can be easily done when there exists a 1:1 correspondence between nodes and the individuals in D of the signature Σ. However, if Lv = D, e.g., the entities in a knowledge graph, this assumption is broken by Λv not being injective in general. This carries to graph generative models, which do not assume exclusivity of labels across nodes. For the second challenge, we want to sample labeled graphs from a constrained distribution, hence restricting the support of a trained generative model pθ (G) depending on constraints ϕ, leading to a conditioned distribution pθ (G|ϕ). Through logic, we can define rules on the existence, the labels and properties of nodes and edges. We focus on FOL formulas as a very general language for expressing constraints in graph generation, and make graph diffusion models applicable in these contexts, e.g., knowledge graph generation (Thanapalasingam et al. 2023). Let pθ (ϕ(G) = 1) be the marginal probability of generated graphs satisfying ϕ. In probabilities, we will also use ϕ as a shorthand to indicate the event {ϕ(G) = 1}. Constrained graph generation entails sampling from a conditional distribution on graphs pθ (G|ϕ) such that ϕ(G) = 1 for all the graphs in its support. The optimal solution p∗θ (G|ϕ) to the constrained graph generation problem can be trivially found by applying the Bayes theorem: p(ϕ|G)pθ (G) ϕ(G)pθ (G) p∗θ (G|ϕ) = P =P . p(ϕ|W )p (W ) θ W W ϕ(W )pθ (W )

(4) Computing Eq. (4) is infeasible, as it amounts to solving Weighted First Order Model Counting (WFOMC) (Van den Broeck et al. 2011), which has computational complexity ♯P (Valiant 1979). We use the exact conditional distribution as an ideal target. Our guided transition is a heuristic approximation designed to increase its support mass on satisfying graphs, so it does not guarantee exact conditional sampling.

5

Expressing FOL Formulas on Labeled Graphs

To evaluate logic formulas on graphs, we define a signature, starting from Eq. 3, translating labeled nodes and edges into predicates: Σ(G) = (V, ∅, Lv ∪ Le ∪ P ∪ R),

(5)

where the constants are all the vertices, no functions are considered, and the predicates are Lv and Le for node and edge labels, and P and R for additional predicates over nodes and edges. Predicates in Lv and P are unary, while those in Le and R are binary. The Herbrand interpretation (Detlovs and Podnieks 2021) I is defined as follows: I(v) = v I(lv ) = {v | v ∈ V, Λv (v) = lv } I(le ) = {e | e ∈ E, Λe (e) = le } I(P ) ⊆ V I(R) ⊆ E

∀v ∈ V ∀lv ∈ Lv ∀le ∈ Le ∀P ∈ P ∀R ∈ R

(6) (7) (8) (9) (10)

With this signature and interpretation, it is now possible to evaluate sentences ϕ in FOL over labeled graphs. We denote the formula given a graph G as ϕ(G), which, when evaluated in FOL, returns values in {0, 1}. To make the formulation consistent with the labeling functions of graphs, we will assume that the following exclusivity axioms are always present in the set of constraints ϕ:    _ _ lv (x) ∧ ¬  lv′ (x) , (11) ∀x lv ∈Lv

 ∀x, y

_

′ ∈L \{l } lv v v



le (x, y) ∧ ¬ 

le ∈Le

 _

le′ (x, y) . (12)

le′ ∈Le \{le }

Informally, these axioms state that each node and edge must have one and only one label. When unary and binary predicates P, R are defined on subset of labels, e.g., a node v with label horror(v) being a genre(v), axioms can be added to the set of rules, of the form: ! _ ∀x P (x) ↔ lv (x) , (13) lv ∈LP

! ∀x, y R(x, y) ↔

_

le (x, y) ,

(14)

le ∈LR

where LP ⊆ Lv and LR ⊆ Le are the subsets of labels for which the predicates hold. These axioms are necessary for a consistent formulation, but have no real consequence on the methodology, nor are they applied. Thus, we mention them now and make them implicit for the rest of the paper.

6

FOL-Constrained Graph Generation

For FOL constrained graph generation, we leverage classifier guidance to steer a pretrained graph diffusion model towards satisfying a formula ϕ. Classifier guidance requires a differentiable objective function for gradient computation, so

Denoising branch

DiGress

Logic Tensor Network Classifier guidance Guidance branch

Rules

in FOL

Figure 1: Our LTN-guidance comprises two branches at each denoising step: (top) the pretrained DiGress model computes the denoising probabilities pθ (Gt−1 |Gt ); (bottom) LTN interprets the given FOL rules ϕ as the differentiable function fϕ , over which the gradient on Gt is computed, producing an approximation of p(ϕ|Gt−1 ). Classifier guidance (right) combines the two with element-wise product, returning the conditional probabilities pθ (Gt−1 |Gt , ϕ). we turn to Logic Tensor Networks (LTN) to interpret ϕ in fuzzy logic. The contributions from each sentence in ϕ are reweighted through a mechanism based on the Focal Loss. An overview of LTN-guidance can be found in Fig. 1. Classifier guidance (Dhariwal and Nichol 2021) is one of the most popular alternative for conditioning diffusion models. Intuitively, the denoising path is steered towards the optimization of a classifier prediction. Although the name suggests the use of a trained classifier, in practice it can be any differentiable function, and may not require training. In our case, the classifier is implemented by the formula satisfaction:

pθ (Gt−1 |Gt , ϕ) ∝ p(ϕ|Gt−1 )pθ (Gt−1 |Gt ) ≈ exp(λGt−1⊤ ∇G log p(ϕ(Gt ) = 1|Gt )) pθ (Gt−1 |Gt ), (15) where pθ (Gt−1 |Gt ) is the unconditional model denoising transition from Eq. 2, and λ is the guidance strength, tunable as a hyperparameter. The approximation comes from the first order Taylor approximation of p(ϕ|Gt−1 ) evaluated at Gt . For a general proof, see Vignac et al. (2023). In classic FOL, p(ϕ(Gt ) = 1|Gt ) is not differentiable, as it is equivalent to ϕ(Gt ), taking values only in {0, 1}. Thus, we propose the use of fuzzy logic, and in particular Logic Tensor Network (LTN) (Badreddine et al. 2022), to provide differentiable fuzzy interpretations of the formulas. We implement log pϕ (ϕ(Gt ) = 1|Gt ) as a differentiable function fϕ (Gt ). Logic Tensor Network (Badreddine et al. 2022) provides differentiable fuzzy semantics for FOL predicates, connectives, and quantifiers. Fuzzy logic allows to specify the semantic S of logical operators to return values in the range [0, 1]. These functions behave exactly the same as the classical FOL semantics in the case of inputs in {0, 1}, but allow intermediate values, usually representing a degree of truth. In the following, we define LTN applied to a tensor graph G. We start from the base case of generic unary and binary

predicates Pi and Rj : SG (Pi (v)) =

X

Xvl ,

(16)

Evv′ l ,

(17)

l∈LPi

SG (Rj (v, v ′ )) =

X l∈LRj

where we remark that V is both the set of nodes in G and the constants of the signature Σ(G). We continue recursively with the semantics of logical connectives in product logic: SG (ϕ ∧ ψ) = SG (ϕ)SG (ψ), (18) SG (ϕ ∨ ψ) = 1 − (1 − SG (ϕ))(1 − SG (ψ)), (19) SG (¬ϕ) = 1 − SG (ϕ), (20) and all quantifiers with the following aggregation functions from Badreddine et al. (2022): !1 p p 1 X SG (∀xϕ(x)) = 1 − 1 − SG (ϕ)v , (21) |V| v∈V !1 p p 1 X SG (ϕ)v . (22) SG (∃xϕ(x)) = |V| v∈V

In the case of quantification over 2 variables, it is sufficient to aggregate the p-mean over all pairs (vi , vj ) ∈ V × V. Some setups (Thanapalasingam et al. 2023) may append non-trivial constraints to FOL statements, whose direct grounding under the standard LTN formulation is computationally impractical. This is the case of edge cardinality constraints, which require to have exactly k edges. This type of constraint can be implemented as a FOL rule for fixed k: ϕcard,k : ∃x1 , y1 , . . . , xk , yk

k ^

R(xi , yi )

i=1

∧

^

¬(xi = xj ∧ yi = yj )

(23)

i̸=j

∧ ∀x, y R(x, y) →

k _

!! (x = xi ∧ y = yi )

i=1

,

but will require the introduction of k + 1 pairs of variables, making checks computationally expensive. Thus, we implement a custom and easy to compute differentiable function for cardinality constraints:  P  | v,v′ ∈V,l∈Le Evv′ l − k|p SG (ϕcard,k ) = exp − , σ (24) where σ is a positive temperature parameter, and p is the same exponent used for the quantifiers. With LTN, a sentence ϕ can now be translated to a differentiable function fϕ (G) = SG (ϕ). Still, the overall constraint may be a conjunction of multiple sentences ϕ1 , . . . , ϕm . Let ϕ be their conjunction. To each sentence ϕi corresponds its fuzzy interpretation fϕi . To aggregate the rules into a single differentiable function, we apply an adaptive reweighting method based on the Focal Loss (Lin et al. 2017): m X fϕ (G) = (1 − fϕi (G)) log(fϕi (G)). (25) i=1

When a sentence is satisfied, i.e., fϕi (G) ≈ 1, then the contribution of log(fϕi (G)) disappears, leaving unsatisfied sentences to steer the generative model. To apply LTN-guidance it is enough to replace ∇G log pϕ (y|Gt ) with ∇G fϕ (Gt ).

7

Experiments

In our experimentation, we consider three research questions: RQ1: Does LTN-guidance increase the satisfaction of dataset rules? RQ2: How does LTN-guidance affect the denoising process? RQ3: Does LTN-guidance allow the addition of new rules to either restrict the support or shift it out of distribution?

7.1

Benchmark

We use the IntelliGraphs benchmark (Thanapalasingam et al. 2023) to evaluate FOL-guided graph generation. IntelliGraphs contains five Knowledge Graphs (KGs) datasets designed to test different forms of semantic validity. syn-paths tests directed path structure; syn-types tests compatibility between entity and relation types together with a fixed-cardinality constraint; and syn-tipr instantiates a time-indexed person-role ontology pattern. The two real-world datasets contain Wikidata-derived subgraphs: wd-movies describes a movie through actors, directors, and genres, whereas wd-articles describes scholarly articles and ordered authorship information. The latter is the most structurally complex because valid graphs must represent consecutive author positions without gaps. This same benchmark was used in Wang et al. (2025), and the amount of available data is substantially larger than existing generic graph datasets (Huang et al. 2023). Graphs in the datasets are in Resource Description Framework (RDF) (Cyganiak et al. 2014) format, i.e., triples T = {(s, r, o) : s, o ∈ D, r ∈ R} where s is the subject entity, r the edge predicate or relation, o the object entity, and D and R are the entity and relation sets, respectively. To make them compatible with our generative model, we converted1 all of them to graphs G. A detailed 1 We identified some irregularities in the datasets, such as the representation of triples T not as sets but as lists, which allows

introduction to knowledge graphs, and how to formally convert them to labeled graphs can be found in Appendix C of the supplementary material. The IntelliGraphs benchmark considers the percentage of graphs that are valid, novel, valid and novel, or empty. Validity is one of the main indicators of the efficiency for generative models, as it directly influences the number of resamples to reach a target number of valid samples. The percentage of valid graphs (i.e., graphs for which ϕ(G) = 1) in a batch of samples S is: 1 X V (ϕ, S) = ϕ(G). (26) |S| G∈S

In IntelliGraphs, the validity computation is implemented with a checker that verifies each rule in the ontology2 . Two KGs are considered equal if their set of triples (subject, predicate, object) are the same. Given this notion, Novelty is computed on a batch S and training set Dtr as the percentage of sampled graphs not present in the training set: N (S) =

|S \ Dtr | . |S|

(27)

The benchmark also considers the percentage of novel graphs S \ Dtrain that are also valid (Valid and Novel) and the percentage of generated graphs in S with no edges, formally graphs where T = ∅ (Empty Graphs). We included additional metrics from the graph generation literature (Thompson et al. 2022) to evaluate how well the generative model captures the distribution of the data. These are based on the Maximum Mean Discrepancy (MMD) between two sets of graphs, computing pairwise kernel functions k(·, ·) on features extracted from graphs using a feature extractor f . MMD is defined as: MMD2 (p, q) = EG,G′ ∼p [kf (G, G′ )]+ + EG,G′ ∼q [kf (G, G′ )] − 2EG∼p,G′ ∼q [kf (G, G′ )].

(28)

As features, we consider the node degrees (Degree), the clustering coefficients (Clustering), and the eigenvalues of the graph Laplacian (Spectre). As kernel, we use the radial basis function.

7.2

Implementation Details

We apply LTN-guidance to DiGress (Vignac et al. 2023), a state-of-the-art graph diffusion model. Because DiGress was originally implemented for undirected graphs, we reimplemented parts of the model and Graph Transformer (Dwivedi and Bresson 2020) to avoid symmetries in the adjacency matrix, e.g., removing matrix symmetrization operations AA⊤ . for duplicates. For example, the syn-types dataset contains KGs with 10 triples each, but graph conversion shows that roughly the 76.25% of the sets actually have 10 triples, while the remaining 23.75% have less than 10 triples. 2 We would like to point out that we found a discrepancy between the rules implemented in the checker and those presented in the paper. For example, the wd-movies dataset contains a rule stating that all KGs should have at least a genre. Yet, it is not present in the checker, and many KGs of the dataset do not contain any genre. Thus, we use the implemented checker in our methodology.

7.3

Results and Discussion

(RQ1) Improving validity on dataset. We use LTNguidance to integrate the rules used to check the validity. Our technique increases validity where the unconditional model violates constraints, while preserving near-perfect validity on the other datasets. The results are presented in Table 1 where, although some metrics and datasets might be redundant, we chose to keep them for the completeness of the benchmark. It can be seen that DiGress, even without guidance, achieves very good results in all datasets, producing practically perfect results on syn-paths and syn-tipr. In syn-types and wd-movies, we observe that unconditional DiGress is outperformed by the ProvCreator baseline. For the former, we find that the source of error is the cardinality constraint of the dataset. In fact, the validity reached by DiGress is very close to the percentage of triples set of length 10 without duplicates in the dataset. The inclusion of the cardinality constraint in Eq. 24 improves its satisfaction, leading to the very high validity of 95.70%. In wd-movies, LTNguidance also improves results over vanilla DiGress with an average validity of 97.37%, outperforming ProvCreator. Still, classifier guidance did not show substantial improvements on wd-articles, the most challenging dataset. In particular, the most unsatisfied constraint entails having no gaps in the paper author positions. Near the final denoising steps, the unconditional transition becomes sharply concentrated, and the chosen guidance strength is insufficient to change the model’s predictions. Increasing the weights was insufficient, so a more complex weighting scheme is needed. Regarding distributional metrics, we observe that guidance does not substantially skew the distribution compared to the unconditional models. This means that the technique does not sacrifice sample quality for validity. (RQ2) How LTN-guidance acts during denoising. We generated a batch of N = 1000 graphs from the model trained on the syn-types dataset, collecting the trajectories, i.e., the intermediate graphs during denoising, in batches St = {Gt,1 , . . . , Gt,N }. Then, we plotted the validity of all St along time, together with the rate of modification of graphs

Graph rate (%)

100

Unconditional validity Unconditional 1 - modified-graph rate Guided validity Guided 1 - modified-graph rate

75 50 25 0

0

100

200 300 Reverse denoising step (0 = final graph)

400

500

(a) Average validity and 1 − R(S0 , St ) 11

Number of triples

This allows DiGress to be used for the generation of directed graphs. We compare DiGress against ComplEx (Trouillon et al. 2016), the best KG embedding baseline of IntelliGraphs, and ProvCreator (Wang et al. 2025), an LLM-based model. Specialized constrained generation methods are not applicable to this setup, e.g., ConStruct (Madeira et al. 2024) only handles minor-hereditary properties, which do not have any overlap with the benchmark. We note that these baselines directly use the triples format, while we use their labeled graph transformation. Furthermore, ComplEx receives the correct entity set, which is not true for other methods. For our guided models, we used standard LTN values for p, while the guidance strength was split into λx for nodes and λe for edges gradients, and their validity-optimizing value per dataset was found through grid search in the range [10−5 , 1]. All experiments were conducted on a single A40 GPU. More details on the hyperparameter search and selected values can be found in Appendix A of the supplementary material.

60

10

40

9

Unconditional Guided 0

20

40

60

20 0

0

100

200 300 Reverse denoising step (0 = final graph)

400

500

(b) Average number of triples |T | (with zoom-in). Target is |T | = 10. Shaded area represents the standard deviation.

Figure 2: Comparison of unconditional and guided denoising processes in the syn-types dataset across 3 seeds. Gt with respect to the final G0 , computed as: N

R(S0 , St ) =

1 X 1>0 (GED(G0,i , Gt,i )) , |S| i=1

(29)

where GED is the Graph Edit Distance with unit costs, and 1>0 is the indicator function for the positive set. The plots obtained by gathering St can be found in Fig. 2. We remark that, because the graphs in syn-types converted from triples do not all contain exactly 10 edges, the validity is not high at time t = 0. A stark difference can be seen with LTN-guidance, where validity reaches almost 100%. A key observation is that validity starts to increase many timesteps earlier compared to denoising without guidance, followed by the inverse modification rate, meaning that the final graphs are achieved much earlier. This is further confirmed by the plot in Fig. 2b, showing the trends in the number of triples |T | in the graphs throughout the denoising process. The target is |T | = 10, and the guided denoising overshoots this value, but finally converges to it with low standard deviation, while the unconditional denoising terminates at a < 10 value. (RQ3) Plugging new rules. We evaluate the capability of LTN-guidance to enforce rules not considered in the datasets in two setups: (1) support restriction, where the new rules are compatible with the current knowledge, providing an additional control signal; (2) support shift, where we introduce new conflicting rules, removing broken ones from the data rules. For example, requiring a genre for each KG in wd-movies constitutes a restriction, while changing the number of triples for syn-types to 12 is a shift, as no in-distribution KG satisfies this condition. Details on added rules can be found in Appendix B of the supplementary material. We want to remark that setup 2 is very challenging, corresponding to out-of-distribution generation, which is nontrivial for generative models. Results are shown in Fig. 3. We observe that for the support restriction task, LTN-guidance

Table 1: Results on the IntelliGraphs benchmark. Because the setup is the same, the reported values for ComplEx and ProvCreator are taken from (Thanapalasingam et al. 2023) and (Wang et al. 2025), respectively. For our method, we report mean ± std across three models trained with random seeds from 0 to 2, sampling 1,000 graphs per dataset, except for 200 graphs on wd-articles.

Dataset

Dataset

Model

%Valid↑

%Nov. & Val.↑

%Novel↑

Degree↓

Clustering↓

Spectre↓

syn-paths

ComplEx (w/ p(S|E) only) 10.10 ProvCreator 93.14 DiGress (no guid) 99.43 ± 0.31 DiGress (w/ guid) 99.40 ± 0.44

10.10 93.14 99.40 ± 0.30 99.37 ± 0.42

95.58 100.00 99.97 ± 0.06 99.97 ± 0.06

4.42 − − − 0.00 − − − 0.00 ± 0.00 1.6e-5 ± 9.17e-6 1.33e-6 ± 1.15e-6 1.6e-5 ± 9.17e-6 0.00 ± 0.00 2.13e-5 ± 1.81e-5 1.33e-6 ± 1.15e-6 2.13e-5 ± 1.81e-5

syn-tipr

ComplEx (w/ p(S|E) only) 0.00 ProvCreator 0.00 DiGress (no guid) 99.70 ± 0.36 DiGress (w/ guid) 99.70 ± 0.36

0.00 0.00 95.87 ± 1.07 95.87 ± 1.07

99.64 100.00 96.17 ± 0.71 96.17 ± 0.71

0.36 0.00 0.00 ± 0.00 0.00 ± 0.00

− − 3e-5 ± 1.74e-5 3e-5 ± 1.74e-5

− − 6.67e-7 ± 1.15e-6 6.67e-7 ± 1.15e-6

syn-types

ComplEx (w/ p(S|E) only) 1.01 ProvCreator 86.16 DiGress (no guid) 74.97 ± 0.85 DiGress (w/ guid) 95.70 ± 1.00

1.01 86.16 74.97 ± 0.85 95.70 ± 1.00

94.17 5.83 100.00 0.00 100.00 ± 0.00 0.00 ± 0.00 100.00 ± 0.00 0.00 ± 0.00

− − 1.61e-3 ± 1.7e-4 0.01 ± 1.12e-3

− − − − 4.19e-4 ± 5.85e-5 4.51e-3 ± 1.52e-4 0.02 ± 3.56e-3 0.01 ± 4.7e-4

wd-movies

ComplEx (w/ p(S|E) only) 0.41 ProvCreator 94.26 DiGress (no guid) 93.00 ± 0.95 DiGress (w/ guid) 97.37 ± 0.40

0.41 94.26 87.63 ± 1.69 91.40 ± 2.75

93.04 100.00 94.63 ± 2.40 94.03 ± 2.35

6.96 0.00 0.00 ± 0.00 0.00 ± 0.00

− − 0.05 ± 0.01 0.05 ± 0.01

− − 0.00 ± 0.00 0.00 ± 0.00

− − 0.08 ± 0.01 0.07 ± 0.01

wd-articles

ComplEx (w/ p(S|E) only) 0.00 ProvCreator 0.00 DiGress (no guid) 64.50 ± 7.00 DiGress (w/ guid) 69.50 ± 3.97

0.00 0.00 64.50 ± 7.00 69.50 ± 3.97

100.00 0.00 100.00 0.00 100.00 ± 0.00 0.00 ± 0.00 100.00 ± 0.00 0.00 ± 0.00

− − 0.16 ± 0.02 0.15 ± 0.01

− − 0.02 ± 0.03 0.01 ± 0.01

− − 0.14 ± 0.01 0.14 ± 0.01

7.4

syn-paths syn-tipr syn-types wd-movies wd-articles

Unconditional Guided 0%

20%

40% 60% %Valid

80%

100%

(a) Support restriction rules

Dataset

%Empty↓

syn-paths syn-tipr syn-types wd-movies wd-articles

Unconditional Guided

0%

20%

40% 60% %Valid

80%

100%

(b) Support shift rules

Figure 3: Validity comparison of unconditional and guided models when introducing new compatible (restriction) or conflicting (shift) rules.

is able to improve in all cases the validity with respect to the new rules, reaching almost 100% validity in all cases. This means that in-distribution conditioning is possible with LTNguidance. As mentioned previously, the support shift task is more challenging, but LTN-guidance introduces a non-zero likelihood of generating graphs satisfying the rules. Thus, the guidance signal produced by LTN-guidance may be used to produce out-of-distribution samples.

− − 3e-5 ± 1.74e-5 3e-5 ± 1.74e-5

Limitations

LTN-guidance uses a differentiable relaxation of the logical rules, which does not guarantee perfect validity. Another limitation is the requirement for a thorough search for the best guidance weight λ per dataset. This work tackles the generation of graphs with FOL constraints, on which we found a limited body of competing works and data to compare with. Thus, a broader empirical picture is left for future work.

8

Conclusion

We presented how to steer graph denoising diffusion models with FOL rules through LTN-guidance. We first defined a graph signature and consistency axioms under which FOL rules can be written; second, we proposed to interpret the rules as differentiable objective functions through LTN; finally, classifier guidance steers the denoising process with the obtained function. Thus, a pre-trained graph diffusion model can be conditioned to maximize the satisfaction of a set of FOL rules, e.g., the ontology for knowledge graphs. This exact setup has been used to evaluate our technique, showing improved validity compared to the unconditional model. We also studied the behavior during the denoising process, observing that FOL classifier guidance acts aggressively, causing samples to reach their final discrete structure earlier in denoising time. In the future, several diverse graph setups might benefit from its applications. For instance, in counterfactual generation for Graph Neural Networks (GNN) (Chen et al. 2026) one might use LTN-guidance to have control over the counterfactual distribution at inference time. In conditioned molecular generation and retrosynthesis (Qiao et al. 2025), certain elements may be prohibited, or commercially available starting materials might be required.

Acknowledgments We acknowledge the financial support of (i) the PNRR project FAIR — Future AI Research (PE00000013), under the NRRP MUR program funded by the NextGenerationEU; (ii) the Italian Ministry of University and Research (MUR) under the PRIN program — Progetti di Rilevante Interesse Nazionale — PRIN 2022 (Secretary-General’s Decree No. 1401 of 18/09/2024) — CUP C53C24000770006, project title “DEEP-GRAPH: Design and Theory of Deep Graph Learning”.

References Ansel, J.; Yang, E.; He, H.; Gimelshein, N.; Jain, A.; Voznesensky, M.; Bao, B.; Bell, P.; Berard, D.; Burovski, E.; et al. 2024. Pytorch 2: Faster machine learning through dynamic python bytecode transformation and graph compilation. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, 929–947. Austin, J.; Johnson, D. D.; Ho, J.; Tarlow, D.; and Van Den Berg, R. 2021. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34: 17981–17993. Badreddine, S.; Garcez, A. d.; Serafini, L.; and Spranger, M. 2022. Logic tensor networks. Artificial Intelligence, 303: 103649. Barwise, J. 1977. An introduction to first-order logic. In Studies in Logic and the Foundations of Mathematics, volume 90, 5–46. Elsevier. Cai, J.-Y.; Fürer, M.; and Immerman, N. 1992. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4): 389–410. Chen, L.; He, C.; Cheng, J.; Li, C.; and Guan, Q. 2026. Generating in-distribution counterfactual explanation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, 20208–20216. Cognolato, S.; Rigoni, D.; Ballarini, M.; Serafini, L.; Moro, S.; and Sperduti, A. 2026. D4: Distance diffusion for a truly equivariant molecular design. Neurocomputing, 679: 133197. Cognolato, S.; Sperduti, A.; and Serafini, L. 2026. FLAGG: Flexible Autoregressive Graph Generation. Journal of Machine Learning Research, 27(107): 1–38. Cyganiak, R.; Wood, D.; Lanthaler, M.; Klyne, G.; Carroll, J. J.; and McBride, B. 2014. RDF 1.1 concepts and abstract syntax. W3C recommendation, 25(02): 1–22. Detlovs, V.; and Podnieks, K. 2021. Herbrand’s Theorem. In Introduction to Mathematical Logic, Edition 2021, 254–260. Dhariwal, P.; and Nichol, A. 2021. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34: 8780–8794. Dwivedi, V. P.; and Bresson, X. 2020. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699.

Eijkelboom, F.; Bartosh, G.; Andersson Naesseth, C.; Welling, M.; and van de Meent, J.-W. 2024. Variational flow matching for graph generation. Advances in Neural Information Processing Systems, 37: 11735–11764. Falcon, W. A. 2019. Pytorch lightning. GitHub, 3. Fey, M.; and Lenssen, J. E. 2019. Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds. Gruber, T. R. 1993. A translation approach to portable ontology specifications. Knowledge Acquisition, 5(2): 199–220. Ho, J.; Jain, A.; and Abbeel, P. 2020. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33: 6840–6851. Hogan, A.; Blomqvist, E.; Cochez, M.; D’amato, C.; Melo, G. D.; Gutierrez, C.; Kirrane, S.; Gayo, J. E. L.; Navigli, R.; Neumaier, S.; Ngomo, A.-C. N.; Polleres, A.; Rashid, S. M.; Rula, A.; Schmelzeisen, L.; Sequeda, J.; Staab, S.; and Zimmermann, A. 2021. Knowledge Graphs. ACM Comput. Surv., 54(4). Huang, H.; Sun, L.; Du, B.; and Lv, W. 2023. Conditional diffusion based on discrete graph structures for molecular graph generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 4302–4311. Jo, J.; Lee, S.; and Hwang, S. J. 2022. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, 10362–10383. PMLR. Lin, T.-Y.; Goyal, P.; Girshick, R.; He, K.; and Dollár, P. 2017. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, 2980–2988. Liu, Q.; Allamanis, M.; Brockschmidt, M.; and Gaunt, A. 2018. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, 31. Madeira, M.; Vignac, C.; Thanou, D.; and Frossard, P. 2024. Generative Modelling of Structurally Constrained Graphs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. Peng, C.; Xia, F.; Naseriparsa, M.; and Osborne, F. 2023. Knowledge graphs: Opportunities and challenges. Artificial intelligence review, 56(11): 13071–13102. Qiao, A.; Wang, Z.; Rao, J.; Yang, Y.; and Wei, Z. 2025. Advancing retrosynthesis with retrieval-augmented graph generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, 20004–20013. Qin, Y.; Madeira, M.; Thanou, D.; and Frossard, P. 2024. Defog: Discrete flow matching for graph generation. arXiv preprint arXiv:2410.04263. Rigoni, D.; Navarin, N.; and Sperduti, A. 2020. Conditional constrained graph variational autoencoders for molecule design. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI), 729–736. IEEE. Rigoni, D.; Navarin, N.; and Sperduti, A. 2025. RGCVAE: relational graph conditioned variational autoencoder for molecule design. Mach. Learn., 114(2): 47.

Thanapalasingam, T.; van Krieken, E.; Bloem, P.; and Groth, P. 2023. IntelliGraphs: Datasets for Benchmarking Knowledge Graph Generation. arXiv preprint arXiv:2307.06698. Thompson, R.; Knyazev, B.; Ghalebi, E.; Kim, J.; and Taylor, G. W. 2022. On Evaluation Metrics for Graph Generative Models. In International Conference on Learning Representations. Trouillon, T.; Welbl, J.; Riedel, S.; Gaussier, É.; and Bouchard, G. 2016. Complex embeddings for simple link prediction. In International conference on machine learning, 2071–2080. PMLR. Valiant, L. G. 1979. The complexity of enumeration and reliability problems. siam Journal on Computing, 8(3): 410– 421. Van den Broeck, G.; Taghipour, N.; Meert, W.; Davis, J.; De Raedt, L.; and Walsh, T. 2011. Lifted probabilistic inference by first-order knowledge compilation. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence, 2178–2185. AAAI Press/International Joint Conferences on Artificial Intelligence; Menlo . . . . Vignac, C.; Krawczuk, I.; Siraudin, A.; Wang, B.; Cevher, V.; and Frossard, P. 2023. DiGress: Discrete Denoising diffusion for graph generation. In International Conference on Learning Representations. Wang, T.; Klancher, S.; Mukherjee, K.; Wiedemeier, J.; Chen, F.; Kantarcioglu, M.; and Jee, K. 2025. Provcreator: Synthesizing complex heterogenous graphs with node and edge attributes. arXiv preprint arXiv:2507.20967. Wang, Y.; Pu, J.; Wang, Y.; and Kuzelka, O. 2024. Lifted algorithms for symmetric weighted first-order model sampling. Artificial Intelligence, 331: 104114. Yadan, O. 2019. Hydra—A Framework for Elegantly Configuring Complex Applications. GitHub. Yao, L.; Peng, J.; Mao, C.; and Luo, Y. 2025. Exploring Large Language Models for Knowledge Graph Completion. In ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 1–5.

Table 2: Selected LTN-guidance hyperparameters and corresponding maximum validity (%). Dataset syn-paths syn-tipr syn-types wd-movies wd-articles

A

Max. validity

λx

λe

99.71 99.71 97.07 98.83 86.00

−4

−3

5 · 10 5 · 10−4 5 · 10−3 5 · 10−4 1

10 5 · 10−5 1 10−2 10−3

Hyperparameters and Implementation Details

In this section we report the per-dataset hyperparameter search we performed for LTN-guidance, the values we chose, implementation and experimental details. As mentioned in the main text, we split the guidance weight λ into node and edge components λx and λe . We selected their values through a grid search for each dataset. For both hyperparameters, we evaluated the values in the set: {0, 10−5 , 5 · 10−5 , 10−4 , 5 · 10−4 , 10−3 , 5 · 10−3 , 10−2 , 5 · 10−2 , 10−1 , 5 · 10−1 , 1},

(30)

and run the generation of 1000 graphs for all datasets, and 50 graphs for wd-articles for feasibility due to the large size its graphs. All experiments are run with the model obtained from seed 0. Figure 4 reports the resulting validity for each dataset. We then selected the configuration attaining the maximum validity for each dataset, as summarized in Table 2. The implementation uses PyTorch (Ansel et al. 2024), PyTorch Lightning (Falcon 2019), Hydra (Yadan 2019), and PyTorch Geometric (Fey and Lenssen 2019). All experiments were run on a Linux system using one NVIDIA A40 GPU, five CPU cores, and 20 GB of RAM. The detailed list of architecture hyperparameters, and the list of libraries and their versions are provided in the supplementary code, in the complete Conda environment specification and hydra configurations. The code will be made publicly available upon acceptance of the paper.

B

Additional Rules for Support Restriction and Shift

Let ϕD denote the original conjunction of validity rules for dataset D. Then the set of valid graphs is: M(ϕD ) = {G : ϕD (G) = 1}.

(31)

comp Then, a compatible rule ψD for D is such that: comp M(ϕD ) ∩ M(ψD ) ̸= ∅,

(32)

conf while a conflicting rule ψD for D is such that: conf M(ϕD ) ∩ M(ψD ) = ∅.

(33)

conf Then, a shifted ruleset ϕ′D is obtained from ϕD such that ψD

is not conflicting with it, for example, by removing a rule from

conf ϕD that is in conflict with ψD . Then, we are interested in comp sampling, with LTN-guidance, from pθ (G|ϕD ∧ ψD ) and ′ conf pθ (G|ϕD ∧ ψD ), which are the conditional distributions of graphs under support restriction and support shift, respectively. The former contains a subset of the structures found in the data distribution, while the latter contains graphs out of the data distribution. The objective is, for these models, to maximize the probability of sampling valid graphs. In the main text we reported the results of the experiments for the five datasets, and here we provide the FOL formulas for the additional rules used in the support restriction and shift experiments. For the detailed rule sets of each dataset, see Section 7.4 of the IntelliGraphs paper (Thanapalasingam et al. 2023).

syn-paths. For support restriction, we retain the original three-edge path and root rules and require the relations to occur exactly in the order cycle_to, drive_to, and train_to from root to leaf: ∃x, y, z, w root(x) ∧ cycle_to(x, y) (34) ∧ drive_to(y, z) ∧ train_to(z, w). For support shift, we remove the path and root rules and replace them with a directed three-cycle. The three nodes are pairwise distinct: ∃x, y, z x ̸= y ∧ y ̸= z ∧ z ̸= x ∧ edge(x, y) ∧ edge(y, z) (35) ∧ edge(z, x). syn-tipr. For support restriction, we retain the canonical five-triple schema and require every tenure to last at least ten years: ∀x, y, z end_year(x, y) ∧ start_year(x, z) (36) → bef ore_10_years(y, z). Here y and z are year nodes and are identified with their numerical year values in the comparison. For support shift, we retain the five-triple schema but replace the original temporal-order rule with its strict reverse: ∀x, y, z end_year(x, y) ∧ start_year(x, z) (37) → af ter(y, z), meaning that z must come after y. syn-types. For support restriction, we retain all original typing rules and the ten-edge constraint, and require the composition of three spoken_in, three could_be_part_of , and four same_type_as edges: ϕcard,3 (spoken_in) ∧ ϕcard,3 (could_be_part_of ) (38) ∧ ϕcard,4 (same_type_as) ∧ ϕcard,10 (edge). For support shift, we replace the ten-edge constraint with twelve edges, using four edges of each relation, while retaining the original typing rules: ϕcard,4 (spoken_in) ∧ ϕcard,4 (could_be_part_of ) (39) ∧ ϕcard,4 (same_type_as) ∧ ϕcard,12 (edge).

98.6

99.3

99.1

98.4

98.6

99.5

99.2

1 × 10 2

99.3

99.2

99.3

99.5

99.0

99.2

98.9

99.4

99.4

99.3

99.2

99.2

5 × 10 3

99.0

99.1

99.4

99.3

99.0

98.6

99.2

99.1

99.3

99.0

99.0

99.4

1 × 10 3

99.4

99.2

98.7

99.2

99.7

99.3

99.6

99.3

98.7

99.1

99.0

99.3

5 × 10 4

99.4

98.9

99.5

99.1

99.0

98.7

99.4

99.1

99.6

99.5

99.1

99.4

1 × 10 4

98.8

99.1

99.4

99.1

99.4

99.5

99.2

99.1

99.7

99.2

98.9

99.0

5 × 10 5

99.3

99.4

99.3

98.8

99.4

99.2

98.9

99.1

99.4

99.0

99.5

99.3

1 × 10 5

99.6

99.1

99.7

99.5

99.5

99.1

99.2

99.3

99.2

99.2

99.4

98.6

0

99.5

99.2

99.1

99.3

99.0

99.4

99.3

99.1

99.2

99.2

99.2

99.1

5×

1×

97 96 95 94 93

99.5

99.0

99.0

99.5

99.0

99.0

99.2

98.9

98.7

99.1

99.4

98.9

98.5

99.6

98.6

99.4

98.6

98.7

99.7

98.9

99.0

99.4

99.5

98.9

1 × 10 1

99.2

99.4

99.7

99.3

99.2

99.5

98.5

99.1

99.3

99.1

99.2

98.9

5 × 10 2

99.7

99.4

99.0

99.4

99.2

99.2

99.0

98.6

98.8

99.4

99.3

99.1

1 × 10 2

99.1

99.1

99.0

98.7

99.3

98.9

99.0

98.5

98.7

99.2

98.9

99.2

5 × 10 3

99.3

99.0

99.1

98.5

99.2

98.8

98.9

99.3

98.9

99.7

98.9

98.5

1 × 10 3

99.5

98.7

99.3

98.9

99.3

99.0

98.9

99.3

99.5

99.2

98.9

99.1

5 × 10 4

99.3

99.2

99.3

99.1

98.7

98.5

98.9

99.0

99.4

99.1

99.4

99.0

1 × 10 4

98.9

99.1

99.6

99.2

98.8

99.2

99.4

99.1

99.4

99.2

99.2

98.9

5 × 10 5

98.2

99.2

99.2

99.3

99.7

99.2

99.3

99.3

99.0

99.0

98.9

99.5

1 × 10 5

99.3

98.7

99.1

99.1

99.3

99.3

99.2

99.4

99.5

99.2

99.1

98.7

0

99.4

98.3

99.7

99.0

99.5

98.9

99.6

99.1

99.2

99.1

98.8

99.4

95.097.5 Max Val.

43.5

52.0

52.8

53.5

61.4

82.6

80.4

80.9

5 × 10 2

55.8

56.2

52.3

54.1

48.9

47.1

56.5

71.8

78.9

77.8

80.5

78.8

1 × 10 2

78.9

78.5

79.2

77.8

79.1

76.3

76.0

77.0

79.0

77.8

78.6

79.8

1 × 10 2

98.6

97.8

98.2

98.3

98.8

98.8

98.1

98.8

98.7

98.8

98.4

98.4

5 × 10 3

5 × 10 3

76.7

76.1

77.6

75.4

75.4

78.2

77.8

76.6

80.3

78.5

79.0

75.3

1 × 10 3

76.0

76.0

80.0

79.3

75.9

79.6

75.9

76.9

76.9

77.2

77.4

77.0

97.8

97.4

97.8

98.5

97.8

98.8

98.2

98.0

97.8

98.0

97.2

98.2

1 × 10 3

95.3

94.7

95.5

93.5

95.4

96.1

96.0

96.3

94.8

96.6

94.7

96.2

5 × 10 4

77.3

76.1

79.8

78.7

78.2

77.4

78.2

79.5

78.2

77.5

78.5

77.7

5 × 10 4

94.7

92.9

95.8

93.5

94.2

95.0

94.1

95.0

94.4

94.6

94.8

94.4

1 × 10 4

93.5

93.3

94.6

92.7

93.1

92.3

93.4

92.9

94.0

93.2

93.7

93.5

80.0

5 × 10 5

92.2

94.1

93.5

93.7

93.3

94.5

93.2

93.0

93.8

94.2

92.5

93.8

79.1

78.8

77.5

78.0

76.2

77.8

76.2

75.7

75.2

78.6

79.4

76.0

78.1

78.9

76.7

77.5

1 × 10 5

93.7

94.0

94.7

94.1

94.0

92.3

93.8

93.4

93.5

93.8

93.2

93.5

0

93.8

93.8

93.1

92.9

92.9

92.2

93.2

93.8

93.2

92.4

94.1

92.1

87.5 85.0 82.5

75.0

80 90 Max Val.

5×

1

76.8

75.8

1

77.8

75.9

10

75.0

76.6

1

78.9

77.7

10

78.7

0

2

1 × 10 5

10

80.7

2

78.2

79.3

3

78.6

75.8

10

77.0

79.6

10

76.7

79.7

3

76.1

77.4

10

77.6

80.5

4

75.4

77.2

10

78.5

78.4

4

76.3

76.2

10

77.2

76.8

5

78.7

77.7

5

78.0

5 × 10 5

10

1 × 10 4

90.0

Node guidance weight x

98.8 98.6 98.4 99.499.6 Max Val.

90 80 70 60 50 40 30 20 50 100 Max Val.

(d) wd-movies

85 80

58.0

54.0

68.0

58.0

58.0

5 × 10 2

54.0

66.0

70.0

72.0

62.0

74.0

70.0

66.0

66.0

66.0

78.0

68.0

1 × 10 2

62.0

72.0

78.0

78.0

66.0

68.0

78.0

76.0

74.0

72.0

76.0

74.0

5 × 10 3

78.0

82.0

70.0

68.0

74.0

82.0

68.0

76.0

74.0

78.0

80.0

76.0

1 × 10 3

76.0

78.0

64.0

78.0

64.0

74.0

66.0

74.0

80.0

74.0

74.0

86.0

5 × 10 4

60.0

82.0

80.0

78.0

80.0

76.0

68.0

78.0

66.0

70.0

82.0

64.0

1 × 10 4

70.0

76.0

64.0

84.0

70.0

84.0

74.0

78.0

76.0

76.0

74.0

64.0

5 × 10 5

86.0

72.0

72.0

72.0

78.0

82.0

78.0

74.0

76.0

74.0

72.0

76.0

1 × 10 5

66.0

62.0

82.0

72.0

76.0

74.0

70.0

74.0

72.0

76.0

74.0

74.0

0

76.0

80.0

66.0

70.0

80.0

78.0

68.0

72.0

78.0

74.0

70.0

64.0

5×

1×

5×

1×

5×

1×

5×

1×

5×

1×

Node guidance weight x

85 80 75 70 Validity (%)

68.0

1

60.0

1

68.0

1

58.0

10

66.0

2

66.0

10

72.0

2

1 × 10 1

10

60.0

3

54.0

54.0

10

60.0

46.0

10

70.0

52.0

4

60.0

60.0

3

76.0

64.0

10

58.0

62.0

4

64.0

68.0

10

60.0

56.0

5

68.0

64.0

10

64.0

72.0

10

64.0

62.0

5

62.0

10

1 5 × 10 1

0

Edge guidance weight e

Max Val.

(c) syn-types

5×

82.6

79.6

1×

83.2

78.8

1

38.3

1

30.3

1

29.1

10

36.2

2

37.4

10

39.3

2

92.5

36.1

10

51.2

1 × 10 1

3

50.3

40.8

10

80.6

81.0

1×

43.9

34.0

5×

82.0

81.5

5×

34.3

31.0

3

83.3

78.4

1×

29.9

18.9

10

83.6

81.2

5×

23.8

18.3

1×

82.3

79.9

1×

18.3

19.1

10

79.7

78.6

5×

18.2

20.7

1×

82.4

80.5

1×

25.0

30.3

4

81.3

81.0

5×

28.8

34.3

10

82.7

0

31.8

33.7

5×

92.7

5 × 10 2

1×

32.6

31.8

4

93.5

1 × 10 1

Node guidance weight x

33.8

5 × 10 1

10

92.5

1 95.0

96.5

5

92.0

96.8

5

91.0

96.0

10

92.1

95.8

1×

91.1

96.6

5×

92.1

97.1

0

91.1

95.5

10

95.0

99.0

98.5 98.0

1×

92.2

95.7

99.2

Validity (%)

Max Val. 92.5

96.1

Validity (%)

91.4

96.7

10

Edge guidance weight e

5 × 10 1

96.0

99.4

(b) syn-tipr

Edge guidance weight e

Max Val.

(a) syn-paths 97 96 95 1

99.6

Node guidance weight x

5×

5×

1×

5×

1×

5×

1×

5×

0 1×

98

1 5 × 10 1

Validity (%)

99.3

99.2

99

1

99.1

99.5

1

99.4

99.2

1

99.2

98.5

1

99.3

99.0

10

98.8

98.6

2

99.2

99.0

10

99.2

99.1

2

99.6

5 × 10 2

10

1 × 10 1

3

98.6

10

97.8

10

97.8

4

97.6

3

98.0

10

98.3

4

98.0

10

98.4

5

98.5

10

97.5

5

98.0

10

98.2

10

5 × 10 1

Node guidance weight x

99.4

94.2

4

94.2

5× 10 1× 4 10 5× 3 10 1× 3 10 5× 2 10 1× 2 10 5× 1 10 1

94.0

5

92.4

10

93.4

5

94.0

10

94.2

1×

94.6

5×

93.2

0

94.2

10

93.0

99.6

1×

94.4

Validity (%)

1

Edge guidance weight e

Max Val.

99.4

Edge guidance weight e

Max Val.

99.6

65 60 55 50 75 80 85 Max Val.

(e) wd-articles

Figure 4: Grid-search validity (%) for the LTN-guidance weights λx and λe on the five datasets. The color-bar scale is set independently in each panel to emphasize differences within each dataset, so colors should not be compared across datasets.

wd-movies. For support restriction, we retain all original rules and add the requirement that the movie have at least one genre: ∃x

has_genre(existential_node, x) ∧ genre(x). (40) For support shift, we remove the mandatory-director rule, require at least one actor and one genre, and prohibit all has_director edges: ∃x has_actor(existential_node, x) ∧ person(x), ∃x has_genre(existential_node, x) ∧ genre(x), ∀x, y ¬has_director(x, y). (41) wd-articles. For support restriction, we retain all original rules and require at least one citation from the article to an IRI: ∃x

cites(article_node, x) ∧ iri(x).

(42)

For support shift, we replace mandatory authorship with mandatory citation and prohibit all has_author edges: ∃x cites(article_node, x) ∧ iri(x), ∀x, y ¬has_author(x, y).

(43)

The original subject and citation typing rules and all applicable structural rules are retained.

labels set is Lv = D and the edge labels set is Le = R. To convert the triples set T to a labeled graph G, we first collect the set of unique entities L(T ) in T : L(T ) = {s | (s, r, o) ∈ T } ∪ {o | (s, r, o) ∈ T }.

Then, we create the vertices V, and couple them to entities with a bijection Λv : V = {v1 , . . . , vn }, Λv (v) = l,

with n = |L(T )| v ∈ V, l ∈ L(T ).

Knowledge Graphs and Conversion to Labeled Graphs

Knowledge Graphs (KGs) (Hogan et al. 2021) are graphbased data representations that cover a variety of data from diverse sources. KGs represent information with nodes being entities of interest and edges being relations between them. This structure allows knowledge to evolve in a flexible manner by enabling granular management of individual entities and relations and allowing missing data. KGs alone only represent data and an ontology may be used to define the schema of the graph, i.e., the types of entities and relations, and the rules they must satisfy. An ontology can be implemented by FOL, starting from the definition of a domain of discourse D of entities, and from there defining functions and predicates. The domain is partitioned into subsets D1 , . . . , DN , each identifying an entity type. A unary predicate Pi is specified for each subset Di . The relations set R = {R1 , . . . , RM } contains subsets Rj ⊆ D × D. A binary predicate Rj is specified for each relation Rj . Thus, the triples set becomes T = {(s, r, o) : s, o ∈ D, r ∈ R}.

(44)

The Resource Description Framework (RDF) (Cyganiak et al. 2014) is a standardized model for representing KGs as a set of triples T , where each triple is of the form (s, r, o), with s being the subject entity, r the edge predicate or relation, and o the object entity, each represented by an identifier. To define a mapping between KGs in RDF format and labeled graphs, we propose to represent KG entities as node labels, and relations as edge labels. Mathematically, the node

(46) (47)

Finally, edges and their labels are defined as: E = {(v, v ′ ) | v, v ′ ∈ V, (Λv (v), r, Λv (v ′ )) ∈ T }, Λe ((v, v ′ )) = r,

(48)

if (Λv (v), r, Λv (v ′ )) ∈ T ∧ (v, v ′ ) ∈ E. (49)

To convert a graph G to triples T it is enough to collect all edges and labels into the set: T = {(Λv (v), Λe (v, v ′ ), Λv (v ′ )) | (v, v ′ ) ∈ E}.

(50)

Because in principle Λv is not assumed to be injective, it is possible to have multiple nodes having the same label. In the field of KGs, this implies having two nodes representing the same entity, implying that the set of edges connecting them to other nodes are merged once mapped to triples. Thus, we include additional constraints ∀l ∈ Lv : ∀x, y (l(x) ∧ l(y)) → x = y.

C

(45)

(51)

Reproducibility Checklist

2.3. All novel claims are stated formally (e.g., in theorem statements) (yes/partial/no) NA

Instructions for Authors: This document outlines key aspects for assessing reproducibility. Please provide your input by editing this .tex file directly. For each question (that applies), replace the “Type your response here” text with your answer.

2.4. Proofs of all novel claims are included (yes/partial/no) NA

Example: If a question appears as \question{Proofs of all novel claims are included} {(yes/partial/no)} Type your response here you would change it to: \question{Proofs of all novel claims are included} {(yes/partial/no)} yes Please make sure to: • Replace ONLY the “Type your response here” text and nothing else. • Use one of the options listed for that question (e.g., yes, no, partial, or NA). • Not modify any other part of the \question command or any other lines in this document. You can \input this .tex file right before \end{document} of your main file or compile it as a stand-alone document. Check the instructions on your conference’s website to see if you will be asked to provide this checklist with your paper or separately.

1. General Paper Structure 1.1. Includes a conceptual outline and/or pseudocode description of AI methods introduced (yes/partial/no/NA) yes 1.2. Clearly delineates statements that are opinions, hypothesis, and speculation from objective facts and results (yes/no) yes

2.5. Proof sketches or intuitions are given for complex and/or novel results (yes/partial/no) NA 2.6. Appropriate citations to theoretical tools used are given (yes/partial/no) NA 2.7. All theoretical claims are demonstrated empirically to hold (yes/partial/no/NA) NA 2.8. All experimental code used to eliminate or disprove claims is included (yes/no/NA) NA 3. Dataset Usage 3.1. Does this paper rely on one or more datasets? (yes/no) yes If yes, please address the following points: 3.2. A motivation is given for why the experiments are conducted on the selected datasets (yes/partial/no/NA) yes 3.3. All novel datasets introduced in this paper are included in a data appendix (yes/partial/no/NA) NA 3.4. All novel datasets introduced in this paper will be made publicly available upon publication of the paper with a license that allows free usage for research purposes (yes/partial/no/NA) NA 3.5. All datasets drawn from the existing literature (potentially including authors’ own previously published work) are accompanied by appropriate citations (yes/no/NA) yes 3.6. All datasets drawn from the existing literature (potentially including authors’ own previously published work) are publicly available (yes/partial/no/NA) yes 3.7. All datasets that are not publicly available are described in detail, with explanation why publicly available alternatives are not scientifically satisficing (yes/partial/no/NA) NA

1.3. Provides well-marked pedagogical references for lessfamiliar readers to gain background necessary to replicate the paper (yes/no) yes

4. Computational Experiments

2. Theoretical Contributions

If yes, please address the following points:

2.1. Does this paper make theoretical contributions? (yes/no) no If yes, please address the following points: 2.2. All assumptions and restrictions are stated clearly and formally (yes/partial/no) NA

4.1. Does this paper include computational experiments? (yes/no) yes

4.2. This paper states the number and range of values tried per (hyper-) parameter during development of the paper, along with the criterion used for selecting the final parameter setting (yes/partial/no/NA) yes 4.3. Any code required for pre-processing data is included

in the appendix (yes/partial/no) yes 4.4. All source code required for conducting and analyzing the experiments is included in a code appendix (yes/partial/no) yes 4.5. All source code required for conducting and analyzing the experiments will be made publicly available upon publication of the paper with a license that allows free usage for research purposes (yes/partial/no) yes 4.6. All source code implementing new methods have comments detailing the implementation, with references to the paper where each step comes from (yes/partial/no) yes 4.7. If an algorithm depends on randomness, then the method used for setting seeds is described in a way sufficient to allow replication of results (yes/partial/no/NA) yes 4.8. This paper specifies the computing infrastructure used for running experiments (hardware and software), including GPU/CPU models; amount of memory; operating system; names and versions of relevant software libraries and frameworks (yes/partial/no) yes 4.9. This paper formally describes evaluation metrics used and explains the motivation for choosing these metrics (yes/partial/no) yes 4.10. This paper states the number of algorithm runs used to compute each reported result (yes/no) yes 4.11. Analysis of experiments goes beyond singledimensional summaries of performance (e.g., average; median) to include measures of variation, confidence, or other distributional information (yes/no) yes 4.12. The significance of any improvement or decrease in performance is judged using appropriate statistical tests (e.g., Wilcoxon signed-rank) (yes/partial/no) no 4.13. This paper lists all final (hyper-)parameters used for each model/algorithm in the paper’s experiments (yes/partial/no/NA) yes

Related documents

• Your Discrete Graph Diffusion Model is Secretly Memorizing#1298282
• Your Discrete Graph Diffusion Model is Secretly Memorizing#1291808
• Local Diffusion Models and Phases of Data Distributions#158764
• GRIFDIR: Graph Resolution-Invariant Diffusion Models over Irregular Domains#1141530
• Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion#1324535