betaFeedback

WorksComputer Science

Logic-Guided Graph Denoising Diffusion Models

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.

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. [34]; Huang et al. [19]; Cognolato et al. 2026; Cognolato, Sperduti, and Serafini 2026) and flow-matching models (Eijkelboom et al. [13]; Qin et al. [26]) 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 [27]) 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 graphs from a subspace of elements satisfying a set of constraints, has gained traction (Liu et al. [22]; Rigoni, Navarin, and Sperduti [28]; Madeira et al. [23]).

First Order Logic (FOL) (Barwise [4]) 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 [5]). 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 [16]).

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. [34]), 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 [11]) 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. [3]) differentiable functions. A mechanism based on Focal Loss (Lin et al. [21]) 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;

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

  1. We evaluated a popular graph diffusion model, DiGress (Vignac et al. [34]), 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 LLM-based approaches. We observe an improvement in validity, achieving >95%> 95\% in most datasets.

  1. We performed generation with new rules, compatible and conflicting with the data, to evaluate the conditional in-distribution 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.

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. [22]) and Conditional CGVAE (Rigoni, Navarin, and Sperduti [27]) 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. [23]) 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. [36]), closely related to Weighted First Order Model Counting (WFOMC) (Van den Broeck et al. [33]). Lifted (i.e., polynomial) sampling algorithms exist up to the C2C^2 fragment of FOL (Wang et al. [36]), that is, allowing sentences with universal and counting existential quantifiers ∀\forall, ∃≥k\exists_{\geq k}, ∃≤k\exists_{\leq k}, ∃=k\exists_{=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. [24]); (2) using Large Language Models (LLM) (Yao et al. [38]). 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.

Preliminaries

We present a formal definition of labeled graphs. A labeled graph GG is a tuple G=(V,E,Λv,Λe)G = (V, \mathcal{E}, \Lambda_v, \Lambda_e) where VV is the set of nodes, E⊆V×V\mathcal{E} \subseteq V \times V is the set of edges, Λv:V→Lv\Lambda_v : V \to\mathcal{L}_v and Λe:E→Le\Lambda_e : \mathcal{E} \to\mathcal{L}_e are the node and edge labeling functions, where Lv\mathcal{L}_v and Le\mathcal{L}_e are the node and edge labels, respectively. Its tensor representation G=(X,E)G = (X, E) is a more generation-friendly format, where X∈Rn×DvX \in\mathbb{R}^{n \times D_v} is the node tensor, E∈Rn×n×DeE \in\mathbb{R}^{n \times n \times D_e} is the edge tensor, nn is the number of nodes and Dv=∣Lv∣D_v = |\mathcal{L}_v| and De=∣Le∣+1D_e = |\mathcal{L}_e| + 1, comprising the absence of an edge as one of the DeD_e classes.

Diffusion Models for Graphs

Diffusion models (Ho, Jain, and Abbeel 2020; Austin et al. [2]) are a class of generative models where the objective is to learn an approximation pθ(G)p_\theta(G) with parameters θ\theta of an unknown data distribution q(G)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. [34]) jointly generate nodes, edges, and their labels. Two discrete diffusion processes (Austin et al. [2]) randomly flip node and edge labels in XX and EE, potentially removing or adding connectivity, proceeding from time t=0t = 0 to t=Tt = T. The forward and trained reverse processes are defined as:

q(G1:T∣G0)=∏t=1Tq(Xt∣Xt−1)q(Et∣Et−1),(1)q(G^{1:T} \mid G^0) = \prod_{t=1}^{T} q(X^t \mid X^{t-1})q(E^t \mid E^{t-1}), \tag*{(1)}
pθ(G0:T)=p(GT)∏t=1Tpθ(Gt−1∣Gt).(2)p_\theta(G^{0:T}) = p(G^T) \prod_{t=1}^{T} p_\theta(G^{t-1} \mid G^t). \tag*{(2)}

We adopt the discrete graph diffusion formulation of DiGress (Vignac et al. [34]), which corrupts node and edge labels through categorical transitions and learns the reverse transition pθ(Gt−1∣Gt)p_\theta(G^{t-1} \mid G^t). Our method leaves training unchanged and modifies this transition only at inference time.

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)\Sigma= (\mathcal{C}, \mathcal{F}, \mathcal{P}), \tag*{(3)}

where C\mathcal{C} is a set of constant symbols, F\mathcal{F} is a set of function symbols, and P\mathcal{P} is a set of predicate symbols. An interpretation I\mathcal{I} over Σ\Sigma maps each constant cc to a specific individual I(c)\mathcal{I}(c) in a domain of discourse D\mathcal{D}, function symbols ff to functions I(f):Dn→D\mathcal{I}(f) : \mathcal{D}^n \to\mathcal{D} of arity nn, and predicate symbols PP to relations I(P)⊆Dn\mathcal{I}(P) \subseteq\mathcal{D}^n of arity nn. Formulas ϕ\phi are strings composed of variables symbols (e.g., xx, yy, zz), non-logical symbols contained in the signature Σ\Sigma, 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}\{0,1\} (false and true), while fuzzy logic also considers intermediate values in [0,1][0,1]. A sentence, i.e., a formula with no unquantified variables, is satisfied by an interpretation I\mathcal{I} if applying I\mathcal{I} to symbols in Σ\Sigma evaluates to true given the semantics of the logic.

Problem Definition

Generating labeled graphs GG with constraints ϕ\phi 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)\phi(G), which is 11 if the graph GG satisfies the constraints, 00 otherwise.

  1. To generate with a model pθ(G)p_\theta(G) graphs that satisfy ϕ\phi.

Given an existing knowledge base in FOL, defining rules over graphs can be easily done when there exists a 1 ⁣: ⁣11\!:\!1 correspondence between nodes and the individuals in DD of the signature Σ\Sigma. However, if Lv=D\mathcal{L}_v = D, e.g., the entities in a knowledge graph, this assumption is broken by Λv\Lambda_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)p_\theta(G) depending on constraints ϕ\phi, leading to a conditioned distribution pθ(G∣ϕ)p_\theta(G \mid\phi). 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)p_\theta(\phi(G)=1) be the marginal probability of generated graphs satisfying ϕ\phi. In probabilities, we will also use ϕ\phi as a shorthand to indicate the event {ϕ(G)=1}\{\phi(G)=1\}.

Constrained graph generation entails sampling from a conditional distribution on graphs pθ(G∣ϕ)p_\theta(G \mid\phi) such that ϕ(G)=1\phi(G)=1 for all the graphs in its support. The optimal solution pθ∗(G∣ϕ)p_\theta^*(G \mid\phi) to the constrained graph generation problem can be trivially found by applying the Bayes theorem:

pθ∗(G∣ϕ)=p(ϕ∣G)pθ(G)∑Wp(ϕ∣W)pθ(W)=ϕ(G)pθ(G)∑Wϕ(W)pθ(W).(4)p_\theta^*(G \mid\phi)=\frac{p(\phi\mid G)p_\theta(G)}{\sum_W p(\phi\mid W)p_\theta(W)}=\frac{\phi(G)p_\theta(G)}{\sum_W \phi(W)p_\theta(W)}. \tag*{(4)}

Computing Eq. (4) is infeasible, as it amounts to solving Weighted First Order Model Counting (WFOMC) (Van den Broeck et al. [33]), which has computational complexity #P\#\mathsf{P} [32]. 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.

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,E,Lv∪Le∪P∪R),(5)\Sigma(G) = (\mathcal{V}, \mathcal{E}, \mathcal{L}_v \cup\mathcal{L}_e \cup\mathcal{P} \cup\mathcal{R}), \tag*{(5)}

where the constants are all the vertices, no functions are considered, and the predicates are Lv\mathcal{L}_v and Le\mathcal{L}_e for node and edge labels, and P\mathcal{P} and R\mathcal{R} for additional predicates over nodes and edges. Predicates in Lv\mathcal{L}_v and P\mathcal{P} are unary, while those in Le\mathcal{L}_e and R\mathcal{R} are binary. The Herbrand interpretation [10] I\mathcal{I} is defined as follows:

I(v)=v∀v∈VI(lv)={v∣v∈V,Λv(v)=lv}∀lv∈LvI(le)={e∣e∈E,Λe(e)=le}∀le∈LeI(P)⊆V∀P∈PI(R)⊆E∀R∈R\begin{aligned} \mathcal{I}(v) &= v && \forall v \in\mathcal{V}\\ \mathcal{I}(l_v) &= \{v \mid v \in\mathcal{V}, \Lambda_v(v)=l_v\} && \forall l_v \in\mathcal{L}_v\\ \mathcal{I}(l_e) &= \{e \mid e \in\mathcal{E}, \Lambda_e(e)=l_e\} && \forall l_e \in\mathcal{L}_e\\ \mathcal{I}(P) &\subseteq\mathcal{V} && \forall P \in\mathcal{P}\\ \mathcal{I}(R) &\subseteq\mathcal{E} && \forall R \in\mathcal{R} \end{aligned}

With this signature and interpretation, it is now possible to evaluate sentences ϕ\phi in FOL over labeled graphs. We denote the formula given a graph GG as ϕ(G)\phi(G), which, when evaluated in FOL, returns values in {0,1}\{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 ϕ\phi:

∀x ⋁lv∈Lv(lv(x)∧¬(⋁lv′∈Lv∖{lv}lv′(x))),(6)\forall x\ \bigvee_{l_v \in\mathcal{L}_v}\left(l_v(x) \land\neg\left(\bigvee_{l'_v \in\mathcal{L}_v \setminus\{l_v\}} l'_v(x)\right)\right), \tag*{(6)}
∀x,y ⋁le∈Le(le(x,y)∧¬(⋁le′∈Le∖{le}le′(x,y))).(7)\forall x,y\ \bigvee_{l_e \in\mathcal{L}_e}\left(l_e(x,y) \land\neg\left(\bigvee_{l'_e \in\mathcal{L}_e \setminus\{l_e\}} l'_e(x,y)\right)\right). \tag*{(7)}

Informally, these axioms state that each node and edge must have one and only one label. When unary and binary predicates P,R\mathcal{P},\mathcal{R} are defined on subset of labels, e.g., a node vv with label horror (v)(v) being a genre (v)(v), axioms can be added to the set of rules, of the form:

∀x(P(x)↔⋁lv∈LPlv(x)),(8)\forall x\left(P(x)\leftrightarrow\bigvee_{l_v\in\mathcal{L}_P}l_v(x)\right), \tag*{(8)}
∀x,y(R(x,y)↔⋁le∈LRle(x,y)),(9)\forall x,y\left(R(x,y)\leftrightarrow\bigvee_{l_e\in\mathcal{L}_R}l_e(x,y)\right), \tag*{(9)}

where LP⊆Lv\mathcal{L}_P\subseteq\mathcal{L}_v and LR⊆Le\mathcal{L}_R\subseteq\mathcal{L}_e 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.

FOL-Constrained Graph Generation

For FOL constrained graph generation, we leverage classifier guidance to steer a pretrained graph diffusion model towards satisfying a formula ϕ\phi. Classifier guidance requires a differentiable objective function for gradient computation, so we turn to Logic Tensor Networks (LTN) to interpret ϕ\phi in fuzzy logic. The contributions from each sentence in ϕ\phi are reweighted through a mechanism based on the Focal Loss. An overview of LTN-guidance can be found in Figure 1.

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)p_{\theta}(G^{t-1}\mid G^t); (bottom) LTN interprets the given FOL rules ϕ\phi as the differentiable function fϕf_{\phi}, over which the gradient on GtG^t is computed, producing an approximation of p(ϕ∣Gt−1)p(\phi\mid G^{t-1}). Classifier guidance (right) combines the two with element-wise product, returning the conditional probabilities pθ(Gt−1∣Gt,ϕ)p_{\theta}(G^{t-1}\mid G^t,\phi).

Classifier guidance (Dhariwal and Nichol [11]) 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⊤∇Glog⁡p(ϕ(Gt)=1∣Gt))pθ(Gt−1∣Gt),(10)\begin{aligned} p_{\theta}(G^{t-1}\mid G^t,\phi) \propto p(\phi\mid G^{t-1})p_{\theta}(G^{t-1}\mid G^t) \\ &\approx\exp\left(\lambda G^{t-1\top}\nabla_G\log p(\phi(G^t)=1\mid G^t)\right)p_{\theta}(G^{t-1}\mid G^t), \tag*{(10)} \end{aligned}

where pθ(Gt−1∣Gt)p_{\theta}(G^{t-1}\mid G^t) is the unconditional model denoising transition from Eq. (2), and λ\lambda is the guidance strength, tunable as a hyperparameter. The approximation comes from the first order Taylor approximation of p(ϕ∣Gt−1)p(\phi\mid G^{t-1}) evaluated at GtG^t. For a general proof, see Vignac et al. [34]. In classic FOL, p(ϕ(Gt)=1∣Gt)p(\phi(G^t)=1\mid G^t) is not differentiable, as it is equivalent to ϕ(Gt)\phi(G^t), taking values only in {0,1}\{0,1\}. Thus, we propose the use of fuzzy logic, and in particular Logic Tensor Network (LTN) (Badreddine et al. [3]), to provide differentiable fuzzy interpretations of the formulas. We implement log⁡pϕ(ϕ(Gt)=1∣Gt)\log p_{\phi}(\phi(G^t)=1\mid G^t) as a differentiable function fϕ(Gt)f_{\phi}(G^t).

Logic Tensor Network (Badreddine et al. [3]) provides differentiable fuzzy semantics for FOL predicates, connectives, and quantifiers. Fuzzy logic allows to specify the semantic SS of logical operators to return values in the range [0,1][0,1]. These functions behave exactly the same as the classical FOL semantics in the case of inputs in {0,1}\{0,1\}, but allow intermediate values, usually representing a degree of truth. In the following, we define LTN applied to a tensor graph GG. We start from the base case of generic unary and binary

predicates PiP_i and RjR_j:

SG(Pi(v))=∑l∈PiXvl,(11)S_G(P_i(v))=\sum_{l\in\mathcal{P}_i}X_{v_l}, \tag*{(11)}
SG(Rj(v,v′))=∑l∈RjEv′vl.(12)S_G(R_j(v,v'))=\sum_{l\in\mathcal{R}_j}E_{v'v_l}. \tag*{(12)}

where we remark that V\mathcal{V} is both the set of nodes in GG and the constants of the signature Σ(G)\Sigma(G). We continue recursively with the semantics of logical connectives in product logic:

SG(ϕ∧ψ)=SG(ϕ)SG(ψ),(13)S_G(\phi\land\psi)=S_G(\phi)S_G(\psi), \tag*{(13)}
SG(ϕ∨ψ)=1−(1−SG(ϕ))(1−SG(ψ)),(14)S_G(\phi\lor\psi)=1-(1-S_G(\phi))(1-S_G(\psi)), \tag*{(14)}
SG(¬ϕ)=1−SG(ϕ),(15)S_G(\neg\phi)=1-S_G(\phi), \tag*{(15)}

and all quantifiers with the following aggregation functions from Badreddine et al. [3]:

SG(∀xϕ(x))=1−(1∣V∣∑v∈V(1−SG(ϕv))p)1p,(16)S_G(\forall x\phi(x))=1-\left(\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}(1-S_G(\phi_v))^p\right)^{\frac{1}{p}}, \tag*{(16)}
SG(∃xϕ(x))=(1∣V∣∑v∈V(SG(ϕv))p)1p.(17)S_G(\exists x\phi(x))=\left(\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}(S_G(\phi_v))^p\right)^{\frac{1}{p}}. \tag*{(17)}

In the case of quantification over 2 variables, it is sufficient to aggregate the p-mean over all pairs (vi,vj)∈V×V(v_i,v_j)\in\mathcal{V}\times\mathcal{V}.

Some setups (Thanaplasingam 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 kk edges. This type of constraint can be implemented as a FOL rule for fixed kk:

ϕcard,k:∃x1,y1,…,xk,yk(⋀i=1kR(xi,yi)\phi_{\mathrm{card},k}:\exists x_1,y_1,\ldots,x_k,y_k\left(\bigwedge_{i=1}^{k}R(x_i,y_i) \right.
∧⋀i≠j¬(xi=xj∧yi=yj)\left. \land\bigwedge_{i\ne j}\neg(x_i=x_j\land y_i=y_j) \right.
∧∀x,y(R(x,y)→⋁i=1k(x=xi∧y=yi))),(18)\left. \land\forall x,y\left(R(x,y)\to\bigvee_{i=1}^{k}(x=x_i\land y=y_i)\right)\right), \tag*{(18)}

but will require the introduction of k+1k+1 pairs of variables, making checks computationally expensive. Thus, we implement a custom and easy to compute differentiable function for cardinality constraints:

SG(ϕcard,k)=exp⁡(−∣∑v,v′∈V,l∈LEEvv′l−kp∣σ)(19)S_G(\phi_{\mathrm{card},k})=\exp\left(-\frac{\left|\sum_{v,v'\in V,l\in L_E}E_{vv'l}-k^p\right|}{\sigma}\right) \tag*{(19)}

where σ\sigma is a positive temperature parameter, and pp is the same exponent used for the quantifiers.

With LTN, a sentence ϕ\phi can now be translated to a differentiable function fϕ(G)=SG(ϕ)f_\phi(G)=S_G(\phi). Still, the overall constraint may be a conjunction of multiple sentences ϕ1,…,ϕm\phi_1,\ldots,\phi_m. Let ϕ\phi be their conjunction. To each sentence ϕi\phi_i corresponds its fuzzy interpretation fϕif_{\phi_i}. To aggregate the rules into a single differentiable function, we apply an adaptive reweighting method based on the Focal Loss ([21]):

fϕ(G)=∑i=1m(1−fϕi(G))log⁡(fϕi(G)).(20)f_\phi(G)=\sum_{i=1}^{m}(1-f_{\phi_i}(G))\log(f_{\phi_i}(G)). \tag*{(20)}

When a sentence is satisfied, i.e., fϕi(G)≈1f_{\phi_i}(G)\approx1, then the contribution of log⁡(fϕi(G))\log(f_{\phi_i}(G)) disappears, leaving unsatisfied sentences to steer the generative model. To apply LTN-guidance it is enough to replace ∇Glog⁡pϕ(y∣Gt)\nabla_G\log p_\phi(y|G_t) with ∇Gfϕ(Gt)\nabla_G f_\phi(G_t).

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?

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. [35], and the amount of available data is substantially larger than existing generic graph datasets (Huang et al. [19]). Graphs in the datasets are in Resource Description Framework (RDF) (Cyganiak et al. [9]) format, i.e., triples T={(s,r,o):s,o∈D,r∈R}T=\{(s,r,o):s,o\in D,r\in R\} where ss is the subject entity, rr the edge predicate or relation, oo the object entity, and DD and RR are the entity and relation sets, respectively. To make them compatible with our generative model, we converted1 all of them to graphs GG. A detailed 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\phi(G)=1) in a batch of samples SS is:

V(ϕ,S)=1∣S∣∑G∈Sϕ(G).(21)V(\phi,S)=\frac{1}{|S|}\sum_{G\in S}\phi(G). \tag*{(21)}

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 SS and training set Dtr\mathcal{D}_{\mathrm{tr}} as the percentage of sampled graphs not present in the training set:

N(S)=∣S∖Dtr∣∣S∣.(22)N(S)=\frac{|S\setminus\mathcal{D}_{\mathrm{tr}}|}{|S|}. \tag*{(22)}

The benchmark also considers the percentage of novel graphs S∖DtrainS\setminus\mathcal{D}_{\mathrm{train}} that are also valid (Valid and Novel) and the percentage of generated graphs in SS with no edges, formally graphs where T=∅\mathcal{T}=\varnothing (Empty Graphs).

We included additional metrics from the graph generation literature (Thompson et al. [30]) 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(⋅,⋅)k(\cdot,\cdot) on features extracted from graphs using a feature extractor ff. MMD is defined as:

MMD⁡2(p,q)=EG,G′∼p[k(f(G),f(G′))]+EG,G′∼q[k(f(G),f(G′))]−2EG∼p,G′∼q[k(f(G),f(G′))].(23)\operatorname{MMD}^{2}(p,q)=\mathbb{E}_{G,G'\sim p}[k(f(G),f(G'))]+\mathbb{E}_{G,G'\sim q}[k(f(G),f(G'))]-2\mathbb{E}_{G\sim p,G'\sim q}[k(f(G),f(G'))]. \tag*{(23)}

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.

Implementation Details

We apply LTN-guidance to DiGress (Vignac et al. [34]), 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 [12]) to avoid symmetries in the adjacency matrix, e.g., removing matrix symmetrization operations AATAA^{\mathsf{T}}.

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.

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.

This allows DiGress to be used for the generation of directed graphs. We compare DiGress against ComplEx [31], the best KG embedding baseline of IntelliGraphs, and ProvCreator [35], an LLM-based model. Specialized constrained generation methods are not applicable to this setup, e.g., ConStruct [23] 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 pp, while the guidance strength was split into λx\lambda_x for nodes and λe\lambda_e for edges gradients, and their validity-optimizing value per dataset was found through grid search in the range [10−5,1][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 § 9 of the supplementary material.

Results and Discussion

(RQ1) Improving validity on dataset. We use LTN-guidance 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. (19) improves its satisfaction, leading to the very high validity of 95.70%. In wd-movies, LTN-guidance 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.

DatasetModel%Valid↑\uparrow%Nov. & Val.↑\uparrow%Novel↑\uparrow%Empty↓\downarrowDegree↓\downarrowClustering↓\downarrowSpectre↓\downarrow
syn-pathsComplEx (w/ p(S∣E)p(S|E) only)10.1010.1095.584.42———
syn-pathsProvCreator93.1493.14100.000.00———
syn-pathsDiGress (no guid)99.43 ±\pm 0.3199.40 ±\pm 0.3099.97 ±\pm 0.060.00 ±\pm 0.001.6e−5±9.17e−61.6\mathrm{e}{-5} \pm9.17\mathrm{e}{-6}1.33e−6±1.15e−61.33\mathrm{e}{-6} \pm1.15\mathrm{e}{-6}1.6e−5±9.17e−61.6\mathrm{e}{-5} \pm9.17\mathrm{e}{-6}
syn-pathsDiGress (w/ guid)99.40 ±\pm 0.4499.37 ±\pm 0.4299.97 ±\pm 0.060.00 ±\pm 0.002.13e−5±1.81e−52.13\mathrm{e}{-5} \pm1.81\mathrm{e}{-5}1.33e−6±1.15e−61.33\mathrm{e}{-6} \pm1.15\mathrm{e}{-6}2.13e−5±1.81e−52.13\mathrm{e}{-5} \pm1.81\mathrm{e}{-5}
syn-tiprComplEx (w/ p(S∣E)p(S|E) only)0.000.0099.640.36———
syn-tiprProvCreator0.000.00100.000.00———
syn-tiprDiGress (no guid)99.70 ±\pm 0.3695.87 ±\pm 1.0796.17 ±\pm 0.710.00 ±\pm 0.003e−5±1.74e−53\mathrm{e}{-5} \pm1.74\mathrm{e}{-5}6.67e−7±1.15e−66.67\mathrm{e}{-7} \pm1.15\mathrm{e}{-6}3e−5±1.74e−53\mathrm{e}{-5} \pm1.74\mathrm{e}{-5}
syn-tiprDiGress (w/ guid)99.70 ±\pm 0.3695.87 ±\pm 1.0796.17 ±\pm 0.710.00 ±\pm 0.003e−5±1.74e−53\mathrm{e}{-5} \pm1.74\mathrm{e}{-5}6.67e−7±1.15e−66.67\mathrm{e}{-7} \pm1.15\mathrm{e}{-6}3e−5±1.74e−53\mathrm{e}{-5} \pm1.74\mathrm{e}{-5}
syn-typesComplEx (w/ p(S∣E)p(S|E) only)1.011.0194.175.83———
syn-typesProvCreator86.1686.16100.000.00———
syn-typesDiGress (no guid)74.97 ±\pm 0.8574.97 ±\pm 0.85100.00 ±\pm 0.000.00 ±\pm 0.001.61e−3±1.7e−41.61\mathrm{e}{-3} \pm1.7\mathrm{e}{-4}4.19e−4±5.85e−54.19\mathrm{e}{-4} \pm5.85\mathrm{e}{-5}4.51e−3±1.52e−44.51\mathrm{e}{-3} \pm1.52\mathrm{e}{-4}
syn-typesDiGress (w/ guid)95.70 ±\pm 1.0095.70 ±\pm 1.00100.00 ±\pm 0.000.00 ±\pm 0.000.01 ±1.12e−3\pm1.12\mathrm{e}{-3}0.02 ±3.56e−3\pm3.56\mathrm{e}{-3}0.01 ±4.7e−4\pm4.7\mathrm{e}{-4}
wd-moviesComplEx (w/ p(S∣E)p(S|E) only)0.410.4193.046.96———
wd-moviesProvCreator94.2694.26100.000.00———
wd-moviesDiGress (no guid)93.00 ±\pm 0.9587.63 ±\pm 1.6994.63 ±\pm 2.400.00 ±\pm 0.000.05 ±\pm 0.010.00 ±\pm 0.000.08 ±\pm 0.01
wd-moviesDiGress (w/ guid)97.37 ±\pm 0.4091.40 ±\pm 2.7594.03 ±\pm 2.350.00 ±\pm 0.000.05 ±\pm 0.010.00 ±\pm 0.000.07 ±\pm 0.01
wd-articlesComplEx (w/ p(S∣E)p(S|E) only)0.000.00100.000.00———
wd-articlesProvCreator0.000.00100.000.00———
wd-articlesDiGress (no guid)64.50 ±\pm 7.0064.50 ±\pm 7.00100.00 ±\pm 0.000.00 ±\pm 0.000.16 ±\pm 0.020.02 ±\pm 0.030.14 ±\pm 0.01
wd-articlesDiGress (w/ guid)69.50 ±\pm 3.9769.50 ±\pm 3.97100.00 ±\pm 0.000.00 ±\pm 0.000.15 ±\pm 0.010.01 ±\pm 0.010.14 ±\pm 0.01

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 [35], respectively. For our method, we report mean ±\pm 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.

(RQ2) How LTN-guidance acts during denoising. We generated a batch of N=1000N = 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}S_t = \{G_{t,1}, \ldots, G_{t,N}\}. Then, we plotted the validity of all StS_t along time, together with the rate of modification of graphs

GtG_t with respect to the final G0G_0, computed as:

R(S0,St)=1∣S∣∑i=1N1>0(GED⁡(G0,i,Gt,i)),(24)R(S_0,S_t) = \frac{1}{|S|}\sum_{i=1}^{N} \mathbb{1}_{>0}\left(\operatorname{GED}(G_{0,i},G_{t,i})\right), \tag*{(24)}

where GED is the Graph Edit Distance with unit costs, and 1>0\mathbb{1}_{>0} is the indicator function for the positive set. The plots obtained by gathering StS_t can be found in Figure 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=0t = 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 Figure 2b, showing the trends in the number of triples ∣T∣|\mathcal{T}| in the graphs throughout the denoising process. The target is ∣T∣=10|\mathcal{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< 10 value.

Figure 2. (a) Average validity and 1−R(S0,St)1 - R(S_0,S_t)

(b) Average number of triples ∣T∣|\mathcal{T}| (with zoom-in). Target is ∣T∣=10|\mathcal{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.

(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 § 10 of the supplementary material. We want to remark that setup 2 is very challenging, corresponding to out-of-distribution generation, which is non-trivial for generative models. Results are shown in Figure 3. We observe that for the support restriction task, LTN-guidance 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 LTN-guidance. 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.

(a) Support restriction rules

(b) Support shift rules

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

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 λ\lambda 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.

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) [6] one might use LTN-guidance to have control over the counterfactual distribution at inference time. In conditioned molecular generation and retrosynthesis [25], 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”.

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 λ\lambda into node and edge components λx\lambda_x and λe\lambda_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,\left\{0,10^{-5},5\cdot10^{-5},10^{-4},5\cdot10^{-4},10^{-3},\right.
5⋅10−3,10−2,5⋅10−2,10−1,5⋅10−1,1},(25)\left.5\cdot10^{-3},10^{-2},5\cdot10^{-2},10^{-1},5\cdot10^{-1},1\right\}, \tag*{(25)}

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.

DatasetMax. validityλx\lambda_xλe\lambda_e
syn-paths99.715⋅10−45 \cdot10^{-4}10−310^{-3}
syn-tipr99.715⋅10−45 \cdot10^{-4}5⋅10−55 \cdot10^{-5}
syn-types97.075⋅10−35 \cdot10^{-3}11
wd-movies98.835⋅10−45 \cdot10^{-4}10−210^{-2}
wd-articles86.001110−310^{-3}

Table 2. Selected LTN-guidance hyperparameters and corresponding maximum validity (%).

Figure 4. Grid-search validity (%) for the LTN-guidance weights λx\lambda_x and λe\lambda_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.

The implementation uses PyTorch [1], PyTorch Lightning [14], Hydra [37], and PyTorch Geometric [15]. 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.

Additional Rules for Support Restriction and Shift

Let ϕD\phi_D denote the original conjunction of validity rules for dataset DD. Then the set of valid graphs is:

M(ϕD)={G:ϕD(G)=1}.(26)\mathcal{M}(\phi_D)=\{G:\phi_D(G)=1\}. \tag*{(26)}

Then, a compatible rule ψDcomp\psi_D^{\mathrm{comp}} for DD is such that:

M(ϕD)∩M(ψDcomp)≠∅,(27)\mathcal{M}(\phi_D)\cap\mathcal{M}(\psi_D^{\mathrm{comp}})\ne\varnothing, \tag*{(27)}

while a conflicting rule ψDconf\psi_D^{\mathrm{conf}} for DD is such that:

M(ϕD)∩M(ψDconf)=∅.(28)\mathcal{M}(\phi_D)\cap\mathcal{M}(\psi_D^{\mathrm{conf}})=\varnothing. \tag*{(28)}

Then, a shifted ruleset ϕD′\phi'_D is obtained from ϕD\phi_D such that ψDconf\psi_D^{\mathrm{conf}} is not conflicting with it, for example, by removing a rule from ϕD\phi_D that is in conflict with ψDconf\psi_D^{\mathrm{conf}}. Then, we are interested in sampling, with LTN-guidance, from pθ(G∣ϕD∧ψDcomp)p_\theta(G|\phi_D\wedge\psi_D^{\mathrm{comp}}) and pθ(G∣ϕD′∧ψDconf)p_\theta(G|\phi'_D\wedge\psi_D^{\mathrm{conf}}), 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,wroot(x)∧cycle_to(x,y)∧drive_to(y,z)∧train_to(z,w).(29)\exists x,y,z,w\quad root(x)\wedge cycle\_to(x,y) \wedge drive\_to(y,z)\wedge train\_to(z,w). \tag*{(29)}

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,zx≠y∧y≠z∧z≠x∧edge(x,y)∧edge(y,z)∧edge(z,x).(30)\exists x,y,z\quad x\ne y\wedge y\ne z\wedge z\ne x \wedge edge(x,y)\wedge edge(y,z) \wedge edge(z,x). \tag*{(30)}

syn-tipr. For support restriction, we retain the canonical five-triple schema and require every tenure to last at least ten years:

∀x,y,zend_year(x,y)∧start_year(x,z)→before_10_years(y,z).(31)\forall x,y,z\quad end\_year(x,y)\wedge start\_year(x,z) \to before\_10\_years(y,z). \tag*{(31)}

Here yy and zz 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,zend_year(x,y)∧start_year(x,z)→after(y,z),(32)\forall x,y,z\quad end\_year(x,y)\wedge start\_year(x,z) \to after(y,z), \tag*{(32)}

meaning that zz must come after yy.

syn-types. For support restriction, we retain all original typing rules and the ten-edge constraint, and require the composition of three spoken_inspoken\_in, three could_be_part_ofcould\_be\_part\_of, and four same_type_assame\_type\_as edges:

ϕcard,3(spoken_in)∧ϕcard,3(could_be_part_of)∧ϕcard,4(same_type_as)∧ϕcard,10(edge).(33)\phi_{\mathrm{card},3}(spoken\_in) \wedge\phi_{\mathrm{card},3}(could\_be\_part\_of) \wedge\phi_{\mathrm{card},4}(same\_type\_as) \wedge\phi_{\mathrm{card},10}(edge). \tag*{(33)}

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)∧ϕcard,4(same_type_as)∧ϕcard,12(edge).(34)\phi_{\mathrm{card},4}(spoken\_in) \wedge\phi_{\mathrm{card},4}(could\_be\_part\_of) \wedge\phi_{\mathrm{card},4}(same\_type\_as) \wedge\phi_{\mathrm{card},12}(edge). \tag*{(34)}

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).(35)\exists x\ \operatorname{has\_genre}(\operatorname{existential\_node},x) \land\operatorname{genre}(x). \tag*{(35)}

For support shift, we remove the mandatory-director rule, require at least one actor and one genre, and prohibit all has_director⁡\operatorname{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).(36)\begin{aligned} \exists x\ \operatorname{has\_actor}(\operatorname{existential\_node},x) \land\operatorname{person}(x),\\ \exists x\ \operatorname{has\_genre}(\operatorname{existential\_node},x) \land\operatorname{genre}(x),\\ \forall x,y\ \neg\operatorname{has\_director}(x,y). \tag*{(36)} \end{aligned}

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).(37)\exists x\ \operatorname{cites}(\operatorname{article\_node},x) \land\operatorname{iri}(x). \tag*{(37)}

For support shift, we replace mandatory authorship with mandatory citation and prohibit all has_author⁡\operatorname{has\_author} edges:

∃x cites⁡(article_node⁡,x)∧iri⁡(x),∀x,y ¬has_author⁡(x,y).(38)\begin{aligned} \exists x\ \operatorname{cites}(\operatorname{article\_node},x) \land\operatorname{iri}(x),\\ \forall x,y\ \neg\operatorname{has\_author}(x,y). \tag*{(38)} \end{aligned}

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

Knowledge Graphs and Conversion to Labeled Graphs

Knowledge Graphs (KGs) [18] are graph-based 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\mathcal{D} of entities, and from there defining functions and predicates. The domain is partitioned into subsets D1,…,DN\mathcal{D}_1,\ldots,\mathcal{D}_N, each identifying an entity type. A unary predicate PiP_i is specified for each subset Di\mathcal{D}_i. The relations set R={R1,…,RM}\mathcal{R}=\{\mathcal{R}_1,\ldots,\mathcal{R}_M\} contains subsets Rj⊆D×D\mathcal{R}_j\subseteq\mathcal{D}\times\mathcal{D}. A binary predicate Rj\mathcal{R}_j is specified for each relation Rj\mathcal{R}_j. Thus, the triples set becomes

T={(s,r,o):s,o∈D,r∈R}.(39)\mathcal{T}=\{(s,r,o):s,o\in\mathcal{D},r\in\mathcal{R}\}. \tag*{(39)}

The Resource Description Framework (RDF) [9] is a standardized model for representing KGs as a set of triples T\mathcal{T}, where each triple is of the form (s,r,o)(s,r,o), with ss being the subject entity, rr the edge predicate or relation, and oo 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 labels set is Lv=D\mathcal{L}_v=\mathcal{D} and the edge labels set is Le=R\mathcal{L}_e=\mathcal{R}. To convert the triples set T\mathcal{T} to a labeled graph GG, we first collect the set of unique entities L(T)\mathcal{L}(\mathcal{T}) in T\mathcal{T}:

L(T)={s∣(s,r,o)∈T}∪{o∣(s,r,o)∈T}.(40)\mathcal{L}(\mathcal{T})=\{s\mid(s,r,o)\in\mathcal{T}\}\cup\{o\mid(s,r,o)\in\mathcal{T}\}. \tag*{(40)}

Then, we create the vertices V\mathcal{V}, and couple them to entities with a bijection Λv\Lambda_v:

V={v1,…,vn},with n=∣L(T)∣(41)\mathcal{V}=\{v_1,\ldots,v_n\},\qquad\text{with }n=\lvert\mathcal{L}(\mathcal{T})\rvert \tag*{(41)}
Λv(v)=l,v∈V, l∈L(T).(42)\Lambda_v(v)=l,\qquad v\in\mathcal{V},\ l\in\mathcal{L}(\mathcal{T}). \tag*{(42)}

Finally, edges and their labels are defined as:

E={(v,v′)∣v,v′∈V, (Λv(v),r,Λv(v′))∈T},(43)\mathcal{E}=\{(v,v')\mid v,v'\in\mathcal{V},\ (\Lambda_v(v),r,\Lambda_v(v'))\in\mathcal{T}\}, \tag*{(43)}
Λe((v,v′))=r,if (Λv(v),r,Λv(v′))∈T∧(v,v′)∈E.(44)\Lambda_e((v,v'))=r,\quad\text{if }(\Lambda_v(v),r,\Lambda_v(v'))\in\mathcal{T}\land(v,v')\in\mathcal{E}. \tag*{(44)}

To convert a graph GG to triples T\mathcal{T} it is enough to collect all edges and labels into the set:

T={(Λv(v),Λe(v,v′),Λv(v′))∣(v,v′)∈E}.(45)\mathcal{T}=\{(\Lambda_v(v),\Lambda_e(v,v'),\Lambda_v(v'))\mid(v,v')\in\mathcal{E}\}. \tag*{(45)}

Because in principle Λv\Lambda_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\forall l\in\mathcal{L}_v:

∀x,y (l(x)∧l(y))→x=y.(46)\forall x,y\ (l(x)\land l(y))\to x=y. \tag*{(46)}

Reproducibility Checklist

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.

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.

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

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

Theoretical Contributions

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

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

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

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

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 satisfying (yes/partial/no/NA) NA

Computational Experiments

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

If yes, please address the following points:

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 single-dimensional 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

References

  1. [1]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.DOI
  2. [2]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.arxiv.org/abs/2107.03006
  3. [3]Badreddine, S.; Garcez, A. d.; Serafini, L.; and Spranger, M. 2022. Logic tensor networks. Artificial Intelligence, 303: 103649.DOI
  4. [4]Barwise, J. 1977. An introduction to first-order logic. In Studies in Logic and the Foundations of Mathematics, volume 90, 5–46. Elsevier.DOI
  5. [5]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.
  6. [6]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.
  7. [9]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.
  8. [10]Detlovs, V.; and Podnieks, K. 2021. Herbrand’s Theorem. In Introduction to Mathematical Logic, Edition 2021, 254–260.
  9. [11]Dhariwal, P.; and Nichol, A. 2021. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34: 8780–8794.
  10. [12]Dwivedi, V. P.; and Bresson, X. 2020. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699.arxiv.org/abs/2012.09699
  11. [13]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.arxiv.org/abs/2406.04843
  12. [14]Falcon, W. A. 2019. Pytorch lightning. GitHub, 3.DOI
  13. [15]Fey, M.; and Lenssen, J. E. 2019. Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds.arxiv.org/abs/1903.02428
  14. [16]Gruber, T. R. 1993. A translation approach to portable ontology specifications. Knowledge Acquisition, 5(2): 199–220.DOI
  15. [18]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, N.-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).
  16. [19]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.
  17. [21]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.
  18. [22]Liu, Q.; Allamanis, M.; Brockschmidt, M.; and Gaunt, A. 2018. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, 31.arxiv.org/abs/1805.09076
  19. [23]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.arxiv.org/abs/2406.17341
  20. [24]Peng, C.; Xia, F.; Naseriparsa, M.; and Osborne, F. 2023. Knowledge graphs: Opportunities and challenges. Artificial intelligence review, 56(11): 13071–13102.arxiv.org/abs/2303.13948
  21. [25]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.
  22. [26]Qin, Y.; Madeira, M.; Thanou, D.; and Frossard, P. 2024. Defog: Discrete flow matching for graph generation. arXiv preprint arXiv:2410.04263.arxiv.org/abs/2410.04263
  23. [27]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.arxiv.org/abs/2009.00725
  24. [28]Rigoni, D.; Navarin, N.; and Sperduti, A. 2025. RGC-VAE: relational graph conditioned variational autoencoder for molecule design. Mach. Learn., 114(2): 47.
  25. [30]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.arxiv.org/abs/2201.09871
  26. [31]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.arxiv.org/abs/1606.06357
  27. [32]Valiant, L. G. 1979. The complexity of enumeration and reliability problems. siam Journal on Computing, 8(3): 410–421.DOI
  28. [33]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 . . . .DOI
  29. [34]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.arxiv.org/abs/2209.14734
  30. [35]Wang, T.; Klancher, S.; Mukherjee, K.; Wiedemeier, J.; Chen, F.; Kantarcioglu, M.; and Jee, K. 2025. Provcreator: Synthesizing complex heterogeneous graphs with node and edge attributes. arXiv preprint arXiv:2507.20967.arxiv.org/abs/2507.20967
  31. [36]Wang, Y.; Pu, J.; Wang, Y.; and Kuzelka, O. 2024. Lifted algorithms for symmetric weighted first-order model sampling. Artificial Intelligence, 331: 104114.DOI
  32. [37]Yadan, O. 2019. Hydra—A Framework for Elegantly Configuring Complex Applications. GitHub.
  33. [38]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.arxiv.org/abs/2308.13916

Paper details

vlnc:W_d9qzr65p
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents