Conceptio › Archive › arXiv CS

arXiv CSopen access

One Pass for All: A Discrete Diffusion Model for Knowledge Graph Triple Set Prediction

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

artificialintelligence knowledgerepresentation reasoning

artificial intelligence, reasoning, knowledge representation

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

One Pass for All: A Discrete Diffusion Model for Knowledge Graph Triple Set Prediction

arXiv:2604.18344v1 [cs.AI] 20 Apr 2026

Jihong Guan, Jiaqi Wang, Wengen Li, Hanchen Yang, Yichao Zhang, Shuigeng Zhou.

Abstract—Knowledge Graphs (KGs) are composed of triples, and the goal of Knowledge Graph Completion (KGC) is to infer the missing factual triples. Traditional KGC tasks predict missing elements in a triple given one or two of its elements. As a more realistic task, the Triple Set Prediction (TSP) task aims to infer the set of missing triples conditioned only on the observed knowledge graph, without assuming any partial information about the missing triples. Existing TSP methods predict the set of missing triples in a triple-by-triple manner, falling short in capturing the dependencies among the predicted triples to ensure consistency. To address this issue, we propose a novel discrete diffusion model termed DiffTSP that treats TSP as a generative task. DiffTSP progressively adds noise to the KG through a discrete diffusion process, achieved by masking relational edges. The reverse process then gradually recovers the complete KG conditioned on the incomplete graph. To this end, we design a structure-aware denoising network that integrates a relational context encoder with a relational graph diffusion transformer for knowledge graph generation. DiffTSP can generate the complete set of triples in a one-pass manner while ensuring the dependencies among the predicted triples. Our approach achieves state-of-the-art performance on three public datasets. Code: https://github.com/ADMIS-TONGJI/DiffTSP. Index Terms—knowledge graph completion, triple set prediction, discrete diffusion model

I. I NTRODUCTION Knowledge Graphs (KGs), which represent factual information as a collection of (head entity, relation, tail entity) triples, have become a cornerstone of modern AI systems [1], [2], powering applications from web search [3] to question answering [4]–[6] and recommendation systems [7]. Despite their widespread applications, a fundamental and persistent problem is their inherent incompleteness. Real-world KGs usually exhibit extensive incompleteness, with a significant proportion of valid facts missing [8]. To solve this problem, Knowledge Graph Completion (KGC) has emerged as an important research topic [9], [10]. Existing KGC tasks, such as link prediction [11]–[13] and instance completion [14], have made significant strides. However, they operate under a strong and often impractical assumption that some elements of the missing triples are known in advance [15]. For example, link prediction aims to find a missing entity or relation given the other two elements, e.g., (h, r, ?) where h is the head entity and r is one certain relation [16]. In many real-world scenarios, we lack such prior Jihong Guan, Jiaqi Wang, Wengen Li, Hanchen Yang and Yichao Zhang are with the School of Computer Science and Technology, Tongji University, Shanghai, China (jhguan, wangjq, lwengen, neoyang, [email protected]). Shuigeng Zhou is with the School of Computer Science, Fudan University, Shanghai, China ([email protected]). Wengen Li is the corresponding author.

(a) Independent Triple-by-Triple Prediction

(b) DiffTSP: One-Pass Generation

Incomplete KG

Pass 1 Score Model

Pass 2 Score Model

Triple 1 √

Triple 2 × … Triple N √

…

Pass N Score Model

Generative Model

One Pass

… (𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐴𝐴, 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖, 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐶𝐶) (𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐴𝐴, 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖, 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐶𝐶)

…

(𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐵𝐵, 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖, 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐶𝐶) Predicted Set

conflict

(𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐴𝐴, 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖, 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐶𝐶) (𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐶𝐶, 𝑖𝑖𝑖𝑖𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆, 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝐴𝐴) dependency

…

Fig. 1. Independent triple set prediction vs DiffTSP. (a) Independent prediction scores each triple separately, and may result in conflicts in the predicted set. (b) DiffTSP (our model) generates triples in one pass, and could capture their joint distribution and preserve inter-triple dependencies.

knowledge. The ultimate goal of automatic KGC is not just to fill in a blank triple by triple, but to discover entirely new and complete factual triples from the incomplete KG. Therefore, a more practical formulation for KGC is the Triple Set Prediction (TSP) task that directly predicts the entire set of missing factual triples, given only the incomplete knowledge graph as input [17]. Despite its importance, TSP faces a critical challenge, i.e., maintaining the dependency among predicted triples. The triples in a KG are not independent, but interconnected and constrained. For example, if a model predicts the triple (person A, isFatherOf, person B), it should be more likely to also predict the symmetric triple (person B, isSonOf, person A). Conversely, predicting (person A, isFatherOf, person C) should preclude the prediction of (person A, isMotherOf, person C). Existing methods for TSP, as depicted in Figure 1(a), score triples individually and select those with scores exceeding a certain threshold to obtain the final predicted set. Such an isolated approach fails to capture crucial inter-triple dependencies, often resulting in a set of triples that lacks accuracy and consistency. Therefore, to effectively address the TSP task, we must move beyond independent triple scoring, and instead model the joint distribution of the triple set. This calls for a generative framework, where the prediction of each triple is conditioned on the others, thereby producing outputs that faithfully capture inter-triple dependencies and maintain internal consistency. Diffusion models [18] have become exceedingly popular for their powerful capabilities in image [19], [20] and text generation [21], [22], which inspires us to leverage diffusion models’ generative strength for TSP. Although some existing studies, such as KGDM [23], FDM [24] and LLM-DR [25] have applied diffusion models to knowledge graphs [25]–[27], they

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

focus on the link prediction task and score triples individually, struggling to capture inter-triple dependencies. Furthermore, most of these approaches are based on continuous diffusion models which are not well-suited to handle the inherently sparse and structural characteristics of KGs. In this work, we introduce DiffTSP, a novel discrete diffusion model designed to overcome the challenge of capturing inter-triple dependency in the TSP task. As depicted in Figure 1(b), DiffTSP operates via a unified ”One-Pass Generation” process, where all the missing triples are generated holistically rather than as a sequence of independent predictions. The core idea of DiffTSP is to capture the intertriple dependencies that are critical for generating a coherent triple set. Therefore, we aim to learn the joint probability distribution of all triples, rather than scoring them in isolation. To this end, we model the joint distribution of the triple set via stepwise denoising, where each triple is predicted in the context of other triples in the evolving graph, naturally enforcing inter-triple dependencies. To learn the dependencies effectively, we design a structureaware denoising network. Specifically, it consists of two synergistic modules: a Relational Context Encoder (RCE) and a Relational Graph Diffusion Transformer (RelDiT). The RCE performs relation-guided message passing to capture local structural dependencies among entities. It aggregates neighbor information conditioned on relation types, providing entity representations that reflect the local relational context. Built upon the entity representations, the RelDiT further models global structural dependencies via relational attention mechanisms. This module enables the denoising network to capture long-range dependencies among entities during the diffusion process. DiffTSP is composed of three key modules. First, a forward process systematically corrupts a graph by progressively masking its relational edges. Subsequently, our structure-aware denoising network is trained to reverse this corruption by predicting the original clean graph given a noisy graph and the incomplete graph as a condition. Finally, we employ an iterative sampling process to generate a complete and internally consistent set of triples. In sum, our contributions are threefold: 1) We propose a novel discrete diffusion model for the triple set prediction task on KGs, establishing a new paradigm for generative knowledge graph completion. 2) We propose a structure-aware denoising network that integrates a relational context encoder with a relational graph diffusion transformer to capture the inter-triple dependency in knowledge graph generation. 3) Through extensive experiments on three public datasets, we demonstrate the superiority of our approach against multiple strong baselines, as well as the effectiveness and necessity of specific designs in DiffTSP.

II. R ELATED W ORKS Our work is positioned at the intersection of knowledge graph completion and generative diffusion models for graphs. We thus review relevant literature in both areas.

A. Knowledge Graph Completion KGC aims to address the incompleteness issue of KGs by inferring missing facts [28]. This task has been formulated in different ways, e.g., Link Prediction, Instance Completion, and Triple Set Prediction [15]. Specifically, link prediction is the most widely studied KGC task. Given a triple with one missing element, either the head entity (?, r, t), tail entity (h, r, ?), or relation (h, ?, t), the goal is to predict the missing element. A representative approach for link prediction in KGs is to learn low-dimensional embeddings for entities and relations (e.g., TransE [29], RotatE [30], HAKE [31], PairE [32]), and use a scoring function to rank candidate entities or relations. There are also some methods using graph networks (e.g., RGCN [33], CompGCN [34], MorsE [35], AstarNet [36], and ULTRA [37] ). While these models are powerful, they score each candidate entity or relation independently, which is insufficient for capturing the dependency among predicted triples. Instance completion [14] predicts all missing relation-tail pairs (?, ?) for a given head entity h. This formulation moves from single-element prediction to a one-to-many completion setting, but still requires the head entity to be specified beforehand. Triple Set Prediction is the most general and challenging formulation for the KGC task, and aims to predict the whole set of missing factual triples given only the existing incomplete graph. Existing methods [15], [17] for TSP usually adapt from a triple-by-triple prediction pipeline, which fail to model intertriple dependencies well. Our work confronts this limitation by reframing TSP as a generative task to produce the whole set of missing triples in one pass.

B. Generative Diffusion Models for Graph Generation Diffusion models [18] are a type of powerful deep generative models, achieving excellent performance in image [19] and language generation [21], [22]. They progressively add noise to data in a forward process, and then learn a neural network to reverse this process, i.e., starting from pure noise to generate new data samples. Applying diffusion models to discrete and structured data like graphs presents unique challenges. Some recent studies [38] have made significant progress in this direction. DiGress [39] defines a new discrete diffusion process over graphs. GraphDiT [40] further advanced this line of research by incorporating the Dit [41] architecture into the denoising network, demonstrating that attention-based mechanisms are crucial for modeling global graph properties in a diffusion model. However, a limitation in all existing graph generation models is that they are designed for generating generic graphs rather than semantic knowledge graphs. They typically assume a small set of node types and edge types, and cannot effectively handle the heterogeneity of realworld KGs that feature hundreds of relation types and tens of thousands of entities. Adapting these generative models to produce semantically rich KG structures remains an open challenge. Our work advances this direction by tailoring a new diffusion paradigm specifically for completing large-scale heterogeneous KGs.

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

III. P RELIMINARIES Each KG is a directed multi-relational graph G = (V, R, T ), where V is the set of entities, R is the set of relations, and T is the set of factual triples. Each triple (h, r, t) ∈ T consists of a head entity h ∈ V, a relation r ∈ R, and a tail entity t ∈ V, representing a link from h to t via r. Formally, given an incomplete KG Gtrain = (V, R, Ttrain ) as input, the goal of the TSP task is to predict the set of missing triples Tpred (Tpred ∩ Ttrain = ∅). We use Ttest as the set of true triples in the test set to evaluate the model. For clarity and ease of reference, we summarize the key mathematical notations used throughout this paper in Table I. TABLE I S UMMARY OF N OTATIONS Symbol

into a support set T s and a query set T q . We use parameter ρ ∈ (0, 1) to specify the proportion of triples allocated to T s . This yields a support graph Gs = (V, R, T s ) and a query graph Gq = (V, R, T q ). To mitigate the bias towards frequently occurring relations and ensure balance, we design a relation-balanced split strategy. It ensures that the probability distribution of relations in T s and T q mirrors that of the original graph T. Let P (r|T ) represent the probability of a relation r in a set of triples T . For any relation r ∈ R, we have: P (r|T s ) ≈ P (r|T q ) ≈ P (r|T ). (1) This process is repeated Ns times for G to generate a collection of (Gs , Gq ) pairs. This ensures that DiffTSP is trained in a variety of combinations of support and query graphs, thereby achieving robust graph generalization.

Description KG Basics

G = (V, R, T ) b Ttrain , Tpred Gs , G q T s, T q ρ, NS

KG with entities V, relations R, and triples T Number of relation types Observed triples, and predicted triples Support graph, and query graph Triple sets in the support and query graphs Ratio for support/query split, and repeat times

T, t Gqt , E q etijk

Total diffusion steps and current timestep t Noisy query graph at step t, and adjacency tensor State of edge between entities i, j with relation k at step t Mask state representing the absence of an edge Transition matrices for the forward process Noise schedule parameter at timestep t The learnable reverse transition distribution The forward diffusion transition distribution The structure-aware denoising network Predicted edge existence probability by fθ (·) Number of RelDiT blocks Hidden state vector for entity i, and relation r Variational Lower Bound and the simplified training loss

Diffusion Model

M Qt , Qt αt pθ (Gqt−1 |Gqt , Gs ) q(Gqt |Gqt−1 ) fθ (·) pE θ,ijk NDit hi , R r LV LB , Lsimple

C. Forward Diffusion Process We add structured noise into the query graph Gq and subsequently perform denoising to recover the original structure. The support graph Gs serves as a condition during the denoising phase. For clarity in the following discussion, we denote the relations among n entities as an adjacency tensor E q ∈ Rn×n×b×2 , where b is the number of relation types. For q each relation type k between entities i and j, the edge Eijk is a one-hot vector that indicates its existence ([1, 0]) or absence ([0, 1]). The goal of the TSP task is to complete the KG by inferring missing edges between a fixed set of entities. This allows the diffusion process on the graph Gq to be simplified to operate directly on its adjacency tensor E q . The assumption of fixed entities is reasonable [39]. If an entity is altered or deleted, any model-generated edges connected to it would also become invalid. The forward diffusion process is a fixed Markov chain that incrementally adds noise to the adjacency tensor E0q (= E q ). The transition at each step t is defined by a categorical distribution (Cat): q q q(Gqt |Gqt−1 ) = q(Etq |Et−1 ) = Cat(Etq ; Et−1 Qt ),

IV. M ETHODOLOGY A. Overview of DiffTSP As depicted in Figure 2, the training process of DiffTSP involves a relation-balanced learning task generation to create meta-learning tasks, each with a support graph and a query graph. Then, DiffTSP corrupts the query graph by masking relational edges in the forward diffusion process. After that, a structure-aware denoising network is optimized via a specific training objective to reverse this corruption. Finally, during the sampling process, DiffTSP uses the trained network to sample the final triple set. We introduce these modules in detail below. B. Relation-Balanced Learning Task Generation We employ a meta-learning framework to explicitly train DiffTSP to generate query triple sets from support sets. For the given graph G = (V, R, T), multiple training tasks are generated. For each task, the set of triples T is partitioned

(2)

Etq

Here, is the noisy adjacency tensor at timestep t. The q operation Et−1 Qt involves an independent matrix multiplication for each potential edge to update its state probability. Qt ∈ R2×2 defines the transition probabilities of a relational edge from timestep t − 1 to timestep t. The entry [Qt ]i,j specifies the probability of transitioning from state i to j for a specific edge. Denoting the absence of an edge as state M, the transition matrix Qt is defined as:   1    1 − αt|t−1 [Qt ]i,j = αt|t−1   0

if i = j = M, if j = M, i ̸= M, if i = j ̸= M, otherwise.

(3)

where the noise schedule parameter αt|t−1 ∈ (0, 1) is a function decreasing with t. This formulation ensures that, at each step, a relational edge either remains its current state (with probability αt|t−1 ) or transitions to the absence state (with probability 1 − αt|t−1 ). Actually, we can sample Etq directly from E0q :

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

Fig. 2. The training process and sampling process of DiffTSP .

q(Gqt |Gq0 ) = Cat(Etq ; E0q Q̄t ),

with

Q̄t =

t Y

(4)

i=1

  1   1 − α t [Q̄t ]i,j =  α t   0

if i = j = M, if j = M, i ̸= M, if i = j ̸= M, otherwise.

(5)

Qt where αt = i=1 αi|i−1 . When t approaches infinity, Gqt will only have entity nodes and no edges. D. Structure-Aware Denoising Network Our structure-aware denoising network, denoted as fθ (Gqt , Gs , t), takes the noisy query graph Gqt , the support graph Gs , and the timestep t as input. As depicted in Figure 3, to learn the inter-triple dependencies effectively, our denoising network consists of a relational context encoder and a relational graph diffusion transformer, which capture local relational structures and global structural dependencies, respectively. To effectively leverage the structural information from the support graph, we fuse Gs with the query graph Gqt . The fusion is performed by taking the union of their relational edge sets. In this case, an edge is included in the fused graph if it appears in either Gs or Gqt . The fused graph is then used as the input of the denoising network. In the RCE module, we maintain a learnable relation embedding matrix R ∈ R2nr ×a , where nr is the number of relation types and a is the embedding dimension. This matrix stores embeddings for each relation type and its corresponding inverse, allowing the model to differentiate edge directions. (0) The initial feature vector hi for an entity i is computed by averaging the embeddings of all its adjacent relations:

Fig. 3. Overview of the structure-aware denoising network.

(0) hi =

 1  X di

 Rr +

(i,r,j)∈T

Rr−1  .

(6)

(j,r,i)∈T

Here, T represents the triples in the graph, di is the total degree of entity i, and Rr and Rr−1 are the learnable embeddings for relation r and its inverse, respectively. The (l+1) entity representation hi for entity i at layer l+1 is updated as below. 

 (l+1)

= σ

X X r∈R j∈Nir

1 ci,r

(l)

Wr(l) hj + W0 hi  ,

(7)

where σ is an activation function, Nir is the set of neighbors of (l) (l) entity i under relation r, Wr and W0 are learnable weights at layer l, and ci,r is a normalization constant. In the RelDiT module, the entity features Hx ∈ Rn×a are initialized using the final entity representations from the RCE, and the edge features He ∈ Rn×n×b are initialized

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

using the multi-hot encoding from the fused graph. These features are fused through a linear projection, i.e., H(0) = Linear(Hx , He ). Following [40], the scalar timestep t is encoded by a sinusoidal embedding τ . In each RelDiT block, the time embedding is injected via adaptive layer normalization (adaLN). Specifically, the k-th block is defined as

The inequality follows from Jensen’s inequality and yields a variational lower bound on the log-likelihood. b) Decomposition of the variational lower bound.: Taking expectation over the data distribution, the variational objective becomes Eq [L] = Eq [log pθ (Gq0:T |Gs ) − log q(Gq1:T |Gq0 )] .

(k,attn) (k)

(k−1)

(k,attn)

+ AdaLN(RelAttn(H + AdaLN(MLP(H

(k−1)

(k,attn)

), τ ),

), τ ).

(8)

The attention layer RelAttn(·) operates on the representation H(k−1) . Let hi and hj denote the representations of entities i and j in H(k−1) . Unlike standard graph transformers that treat relations only as edge channels, we incorporate relational information into the attention computation through a relationaware attention bias. Formally, the attention score between entity i and entity j is computed as

Using the Markov factorization of the reverse and forward diffusion processes, and Bayes’ rule to each forward transition term q(Gqt |Gqt−1 ), we have " Eq [L] = Eq log p(GqT |Gs ) +

RelAttn(i, j) = Softmax

(hi WQ )(hj WK ) √ d

+ Bij

−

E. Reverse Process The structure-aware denoising network fθ is trained to reverse the forward diffusion process, i.e., predicting the clean graph Gq0 from its noisy version Gqt under the condition Gs . Formally, this corresponds to learning the conditional reverse process pθ (Gqt−1 | Gqt , Gs ) such that samples drawn from the reverse diffusion chain recover the data distribution. a) Variational formulation of the reverse process.: To learn the reverse process, we aim to maximize the conditional log-likelihood of the data, log pθ (Gq0 |Gs ). However, directly optimizing this likelihood is intractable due to the marginalization over all latent diffusion states. Following the standard diffusion formulation [18] and inspired by recent works [39], [42], [43], we instead optimize a variational lower bound (VLB) of the log-likelihood. Specifically, the objective is derived as follows: Z log pθ (Gq0 |Gs ) = log pθ (Gq0:T |Gs ) dGq1:T Z pθ (Gq0:T |Gs ) = log q(Gq1:T |Gq0 ) dGq1:T q(Gq1:T |Gq0 ) pθ (Gq0:T |Gs ) q q ≥ Eq(G1:T |G0 ) log (denoted as L) q(Gq1:T |Gq0 )

(10) (11) (12)

(14)

t=1

(9)

where Bij denotes the relation-aware attention bias that reflects the relational dependency between Pbthe two entities. Specifically, the bias is defined as Bij = k=1 Pt (i, k, j) rk , where Pt (i, k, j) ∈ [0, 1] represents the probability that relation type k exists between entities i and j at timestep t, b is the total number of relation types, and rk is a learnable embedding associated with relation k. After stacking multiple RelDiT blocks, the final representation Hfinal provides a purified representation of the latent graph structure. We then apply a reconstruction decoder to predict the probabilities n×n×b of the clean relational adjacency tensor: pE = θ ∈ R Linear(MLP(Hfinal )).

log pθ (Gqt−1 |Gqt , Gs )

log q(Gqt |Gqt−1 )

= Eq log p(GqT |Gs ) +

T X t=1

T X

(13)

T X

log pθ (Gqt−1 |Gqt , Gs )

t=1

−

T X

# log q(Gqt−1 |Gqt , Gq0 ) − log q(GqT |Gq0 )

(15)

t=1

= Eq [log pθ (Gq0 |Gq1 , Gs )] " T # X q q s q q q + Eq log pθ (Gt−1 |Gt , G ) − log q(Gt−1 |Gt , G0 ) t=2

+ Eq [log p(GqT |Gs ) − log q(GqT |Gq0 )] = Eq [log pθ (Gq0 |Gq1 , Gs )] −

T X

(16)

Eq [DKL (q(Gqt−1 |Gqt , Gq0 )||pθ (Gqt−1 |Gqt , Gs ))]

t=2

− DKL (q(GqT |Gq0 )||p(GqT |Gs ))

(17)

Consequently, the negative log-likelihood is upper bounded by the negative variational lower bound: −Eq [log pθ (Gq0 |Gs )] ≤ −Eq [L] =: LV LB .

(18)

c) From VLB to the simplified training objective.: We show how LV LB can be reduced to the simplified objective Lsimple used in practice. First, we denote LT = DKL (q(GqT |Gq0 ) ∥ p(GqT |Gs )).

(19)

Since q(GqT |Gq0 ) converges to a standard prior independent of Gq0 , and p(GqT |Gs ) is set to the same prior, LT is approximately constant and does not depend on the model parameters fθ . Therefore, it can be safely ignored during training. Next, for each t ∈ [2, T ], we define Lt−1 = Eq DKL q(Gqt−1 |Gqt , Gq0 ) ∥ pθ (Gqt−1 |Gqt , Gs ) .

(20)

As shown in [18], when the reverse model fθ is parameterized to predict the original data, minimizing this KL divergence is equivalent to minimizing the discrepancy between the predicted graph and the ground-truth graph Gq0 , up to constant weighting coefficients. For relational edges with binary states, this discrepancy is naturally measured using Binary CrossEntropy (BCE). Thus, each KL term can be approximated as Lt−1 ≈ Eq [BCE(Gq0 , fθ (Gqt , Gs , t))] .

(21)

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

Finally, we denote L0 = −Eq [log pθ (Gq0 |Gq1 , Gs )].

(22)

This term corresponds to a reconstruction loss measuring the ability of the model to recover Gq0 from Gq1 . Since fθ directly predicts Gq0 , this term also reduces to a BCE loss: L0 = Eq [BCE(Gq0 , fθ (Gq1 , Gs , 1))] .

(23)

To handle the sparse and imbalanced relation types of KGs, we treat non-existent edges between two entities as an additional relation type. The non-existent edge type is never noised in the forward diffusion process because there is nothing to mask. We design a weighted Binary Cross-Entropy (BCEw ) loss function to assign weights to each relation type based on its inverse frequency, thus effectively mitigating the imbalance caused by the abundance of non-existent edges and the varying counts of other relations. The final training objective is to optimize the BCEw loss between the true adjacency tensor of Gq0 and the prediction by our model fθ (Gqt , Gs , t), i.e., By aggregating all terms from t = 1 to T as in DDPM [18], we obtain the simplified training objective Lsimple = Et,(Gq0 ,Gs ),Gqt [BCEw (Gq0 , fθ (Gqt , Gs , t))] .

(24)

where eijk ∈ {0, 1} is the ground-truth value of the edge of relation type k between entities i and j. We denote pE θ = fθ (Gqt , Gs , t) ∈ Rn×n×b , and pE θ,ijk ∈ [0, 1] is the predicted existence probability for edge (i, j, k). In practice, to ensure that the model learns to generate unknown relational edges in Gq0 rather than the known edges in Gs and Gqt , we exclude the relational edges in Gs and Gqt from the loss computation. F. Sampling Process Although the denoising network is trained to directly predict the final graph Gq0 , the sampling process remains iterative, spanning T steps as illustrated in Figure 2. The process is initialized with two inputs, i.e., the support graph GS from the training data, and the noisy query graph GqT that contains the same set of entities as GS but has no edges. Assuming that the transitions of each relational edge in Gq are conditionally independent given the state at time t, as formulated in standard discrete diffusion models [39], [44], the probability of graph Gqt−1 given Gqt and GS can be expressed as a product over all possible edges: pθ (Gqt−1 |Gqt , GS ) =

q S pθ (et−1 ijk |Gt , G ),

(25)

i,j,k

q S where pθ (et−1 ijk |Gt , G ) represents the reverse transition probability for the edge of relation type k between entities i and j. To derive this probability, we first consider the true posterior distribution conditioned on the initial state. By Bayes’ rule, we have (for brevity, we define Et = Etq ):

q(Et−1 |Et , E0 ) =

q(Et |Et−1 )q(Et−1 |E0 ) q(Et |E0 )

Et Q⊤ t ⊙ E0 Qt−1 = Cat Et−1 ; p = E0 Qt Et⊤

! . (26)

Substituting the formulation for Q into Eq. (26), we obtain the specific transition probabilities for an edge state et : αt−1 (1 − αt|t−1 ) αt−1 − αt = , 1 − αt 1 − αt 1 − αt−1 q(et−1 = M|et = M, e0 = 1) = , 1 − αt (27) q(et−1 = 1|et = M, e0 = 1) =

where et denotes the state of an edge in the timestep t. In our practical implementation, et = 1 means the existence of the edge, while et = M = 0 indicates its absence. This is equivalent to the one-hot encoding of [1,0] for existence and [0,1] for absence, as described in the main text. During the sampling process, the initial state e0ijk is unknown. Therefore, to sample et−1 ijk at timestep t − 1, we comS pute the posterior probability pθ (et−1 ijk |Gt , G ) by marginalizing over the unknown initial state using the denoising network’s prediction. The network outputs the predicted probability of existence pE θ,ijk ∈ [0, 1]. The final transition probability is thus a weighted average of the tractable posteriors for the two hypotheses (e0ijk = 1 and e0ijk = 0): 0 E S t−1 t pθ (et−1 ijk |Gt , G ) = q(eijk |eijk , eijk = 1)pθ,ijk t 0 E + q(et−1 ijk |eijk , eijk = 0)(1 − pθ,ijk )  t 1, etijk ̸= M, et−1  ijk = eijk ,   1 − αt−1 −αt pE , et = M, et−1 = M, θ,ijk ijk ijk 1−αt = αt−1 −α t−1 t E t  p , e = M, e θ,ijk ijk  1−αt ijk ̸= M,   0, otherwise. (28)

This distribution is used to sample a discrete graph Gqt−1 , serving as the input for the next denoising step. We ensure the sampling process is constrained to generate relational edges that are not present in the support graph GS . G. Training and Sampling Algorithms The overall diffusion training and sampling processes are shown in Algorithm 1 and Algorithm 2, respectively. Since we treat the non-existent edge as an additional relation type b during training, for the probability distribution pE θ,ij ∈ R over relations between entities i and j, we first check if the maximum probability corresponds to the “non-existent” type. If it does, we set the other b − 1 relation types to zero. Otherwise, following LLaDA [21], we proceed with the sampling process based on the posterior distribution. In the experiments, we have sampling threshold γ = 0.999 and sampling steps T = 20. Algorithm 1 Training Process of DiffTSP Input: A query graph Gq = (X q , E q ) and a support graph Gs ▷ X q is entity feature, E q is adjacency tensor 1: Sample t ∼ U(1, . . . , T ) q 2: Sample Gt ∼ E q Q̄t ▷ Sample a noisy graph q E 3: pθ ← fθ (Gt , Gs , t) 4: optimizer.step(Lsimple (Gq , pE ▷ BCEw loss θ ))

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

Algorithm 2 Sampling Process of DiffTSP Input: A graph GS from the training data, sampling threshold γ, sampling steps T q 1: Sample GT = (V S , RS , ∅) ▷ GqT consists of the same S entities as G but with no edges 2: for t = T to 1 step 1 do q S 3: pE θ ← fθ (Gt , G , t) 4: for (i, j) = (1, 1) to (n, n) do 5: if arg maxk′ ∈{1,...,b} pE θ,ijk′ = b then 6: et−1 ← 0 ▷ If the last dim ij[1:b−1] (“non-existent edge” type) has max probability, set b − 1 relation types to 0 7: else ▷ Sampling for b − 1 relation types 8: for k = 1 to b − 1 do t 9: if etijk ̸= 0 then et−1 ijk ← eijk 10: else t−1 t−1 11: With probability 1−α 1−αt , set eijk ← 0. −αt t−1 E With probability αt−1 1−αt , set eijk ← 1(pθ,ijk > γ). 12: end if 13: end for 14: end if 15: end for 16: end for 17: return G0

V. T HEORETICAL A NALYSIS : M ODELING I NTER -T RIPLE D EPENDENCIES Here, we provide a theoretical justification for why the diffusion model framework is inherently suited to capturing the inter-triple dependencies crucial for generating consistent knowledge graphs. Our argument is that by training the model to approximate the true reverse process, we implicitly train it to replicate the complex joint distribution of the data. Theorem 1 (Perfect Denoising Recovers the True Data Distribution). Let pdata (G0 ) be the true distribution of the complete graph (represented by their adjacency tensors E0 ). If the learned denoising network pθ (Gt−1 | Gt ) perfectly matches the true reverse distribution q(Gt−1 | Gt ) for all timesteps t, then the distribution of generated graphs pθ (G0 ) is identical to the true data distribution, i.e., pθ (G0 ) = pdata (G0 ). Proof. The proof is a standard result in diffusion literature. The generative Q process is defined by the Markov chain T pθ (G0:T ) = p(GT ) t=1 pθ (Gt−1 | Gt ). If pθ (Gt−1 | Gt ) perfectly mimics the true posterior q(Gt−1 | Gt ), the joint distribution of the generative process matches that of the forward process in reverse. Marginalizing over the latent variables G1:T yields the desired result that the model’s marginal pθ (G0 ) recovers the data distribution pdata (G0 ). Implication for Dependencies: Since pdata (G0 ) contains only valid graphs from the training set, it implicitly encodes all inter-triple dependencies. By recovering this distribution, a perfect model would generate graphs with the same statistical and logical integrity. The following theorems show how our training objective works towards this ideal.

Theorem 2 (Minimizing the VLB Controls Conflict Probability). Let C be the set of all possible graphs that contain logical contradictions. Assume the true data is consistent, i.e., Ppdata (C) = 0. The probability of the model generating a contradictory graph is then upper-bounded by the total variation distance between the model and data distributions: Ppθ (C) ≤ TV(pθ , pdata ).

(29)

Furthermore, Pinsker’s inequality relates this bound to the Kullback-Leibler (KL) divergence, which is minimized by the Variational Lower Bound (VLB) objective of our diffusion model: q (30) Ppθ (C) ≤ 12 DKL (pdata ∥ pθ ). Proof. By definition, the total variation distance is TV(pθ , pdata ) = supA |Ppθ (A) − Ppdata (A)|. Letting A = C and using the assumption that Ppdata (C) = 0, we get |Ppθ (C)| ≤ TV(pθ , pdata ), which gives the inequality in Eq. (29). The second inequality in Eq. (30) is a direct application of Pinsker’s inequality, noting that the VLB objective in our diffusion model is designed to minimize an upper bound on DKL (pdata ∥ pθ ): DKL (pdata ∥pθ ) = Epdata − log pθ (G0 ) − H(pdata ) (31) ≤ LVLB − H(pdata ),

(32)

where H(pdata ) denotes the entropy of the data distribution (a constant). Combining the above, we obtain q 1 (33) Ppθ (C) ≤ 2 LVLB − H(pdata ) .

Synthesis. These theorems provide a formal basis for our claim. Theorem 1 shows that a perfect model recovers the data’s inherent dependencies. Theorem 2 shows that minimizing the VLB provably tightens an upper bound on the probability of generating inconsistent triples. Therefore, by training our model to minimize the VLB loss, we are provably tightening the bound on generating contradictory or structurally incomplete triple sets, thus inherently promoting consistency. VI. E XPERIMENT A. Datasets and Evaluation Metrics To ensure the reproducibility and fairness of the evaluation, we conduct experiments on three widely recognized benchmark datasets: Wiki79k, Wiki143k, and CFamily, where Wiki79k and Wiki143k are used under the Relation Similarity-based Partial-Open-World Assumption (RS-POWA) and Closed-World Assumption (CWA), and CFamily is used under the Closed-World Assumption (CWA). It is worth noting that all these datasets, along with their ground truth, are directly sourced from GPHT [15]. We strictly adhere to the original data partitions and definitions provided by GPHT, which guarantees that our results are directly comparable with existing methods. To make our approach tractable, we use the graph partitioning strategy from the recent work of GPHT [15] on the TSP task. This method divides the full knowledge

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

graph into a set of smaller, overlapping subgraphs. Our model, DiffTSP, is then trained and evaluated on these subgraphs. The final set of predicted triples is the union of the predictions from all subgraphs. Table II shows the details of the three datasets. Wiki79k and Wiki143k are subsets extracted from Wikidata. As they are inherently incomplete, they are usually used to evaluate model performance under the RS-POWA, a realistic setting for real-world KGs. CFamily is a smaller and synthetically completed dataset focused on family relationships. Its relative completeness makes it ideal for evaluating model performance under the CWA, where any triples not present in the graph can be considered false. TABLE II S TATISTICS OF DATASETS IN EXPERIMENTS . Datasets

Entity

Relation

Train

Valid

Test

Wiki79k Wiki143k CFamily

7,983 13,928 2,378

85 109 12

57,033 103,415 16,549

6,337 14,190 1,839

15,843 28,727 4,598

To ensure a fair and comprehensive comparison, we use the evaluation metrics, i.e., Joint Precision (JP recision), Squared Test Recall (ST Recall), and TSP Score (FT SP ), proposed for the TSP task in GPHT [15], where FT SP is the harmonic mean of JP recision and ST Recall. Higher values indicate better outcomes for these metrics. Joint Precision (JP recision) measures the precision of the predicted set while accounting for the size of the set itself. Squared Test Recall (ST Recall) measures the percentage of test triples successfully recovered by the model. TSP Score (FT SP ) is the harmonic mean of JP recision and ST Recall. In CWA, we have: CW A+ = Tpred ∩ Ttest , Tpred

CW A+ CW A− , = Tpred − Tpred Tpred

CW A CW A+ CW A− Tpred = Tpred ∪ Tpred = Tpred

(34)

In RS-POWA, we have: P OW A+ Tpred = Ttest ∩ Tpred ,

P OW A P OW A+ P OW A− Tpred = Tpred ∪ Tpred (35)

P OW A− Tpred = {(h, r, t)|(h, r, t) ∈ Tpred , (h, r, t) ∈ / Ttest ,

∃r′ ∈ R (h, r′ , t) ∈ (Ttrain ∪ Ttest ) ∧ sim(r, r′ ) < θ}

(36)

Finally, JP recision, ST Recall and FT SP in RSPOWA and CWA are calculated as follows (W A ∈ {P OW A, CW A}): 1 JP recision = 2 ST Recall = FT SP =

W A+ |Tpred |

W A+ |Tpred | + WA |Tpred | |Tpred | !1 W A+ |Tpred | 2 , |Ttest |

hyperparameters are tuned on the validation set. We set the relation-balanced partitioning ratio ρ = 0.8, repeat times Ns = 100, embedding dimension a = 16, sampling steps T = 20, and the number of Dit blocks NDit = 3. We apply a linear noise schedule function αt = 1 − t/T , and use the Adam optimizer with an initial learning rate of 1e-3. The model is trained for up to 50 epochs, with early stopping triggered if the FT SP score on the validation set does not improve for 10 consecutive epochs. C. Baselines We select both link prediction methods and TSP methods as baselines. The representative link prediction methods, including TensorLog [45], HAKE [31], PairRE [32], RGCN [33], CompGCN [34], AstarNet [36] and ULTRA [37], are modified for TSP by scoring all candidate triples in the graph and selecting those above a threshold as the predicted results. The threshold is determined through grid search on the validation set to achieve the best performance. The latest TSP methods, such as GPHT [15] and LLMTSP [17], are also included. DiGress [39] and GraphDit [40] are not selected since they are tailored to small graphs and simple conditioning, while our task involves large knowledge graphs and complex supportgraph conditioning that they cannot accommodate. D. Main Results According to the main results in Tables III and IV, DiffTSP outperforms all baselines in terms of FT SP which is highlighted in gray, demonstrating its superiority. Our results are based on 3 runs with different seeds, following the baselines’ setup for fair comparison. Concretely, in Wiki79k and Wiki143k, we calculate the RS-POWA and CWA metrics, where CWA is calculated using the average value of Tpred and P OW A+ Tpred . DiffTSP achieves SOTA performance in terms of both RS-POWA and CWA metrics. In CFamily, our model also achieves SOTA performance on JP recision and FT SP . Though RGCN shows higher ST Recall, its low JP recision results in a poor FT SP score. This indicates that its high recall is achieved by retaining a large but often false set of triples. We observe that the traditional knowledge graph embedding method HAKE achieves the second-best results in terms of FT SP , which could be attributed to the relative simplicity of the CFamily dataset, i.e., most of the head and tail entities in the triples to be predicted are within two hops. E. Ablation Studies

! ,

2 × (ST Recall × JP recision) ST Recall + JP recision

(37)

B. Settings The implementation is based on PyTorch and trained on one NVIDIA GeForce RTX 4090 GPU. For our proposed model,

We conduct ablation studies to verify the effectiveness of each module in DiffTSP. w/o RCE removes the RCE in the denoising network and uses random embedding Hrand x as entity initialization features. w/o Attention replaces the attention in RelDiT with an MLP. w/o BCEw uses unweighted BCE loss instead of weighted BCE loss for training. w/o Exinput loss calculates loss including the edges in Gqt and Gs during training. w/o Rsplit replaces relation-balanced split with random support-query graph sampling. According to Table V, removing RCE or attention causes about 2% performance

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

TABLE III P OW A+ P OW A IS THE TRIPLE T HE RESULTS ON W IKI 79 K AND W IKI 143 K DATASETS , WHERE Tpred IS THE CORRECT TRIPLE SET IN TEST DATA , AND Tpred SET THAT CAN BE CONFIDENTLY JUDGED UNDER THE RS-POWA ASSUMPTION . T HE BEST RESULTS ARE IN BOLD , AND THE SECOND - BEST RESULTS ARE UNDERLINED . T HE RESULTS WITH † ARE FROM GPHT [15]. Datasets

Models

Number of Triples in

Wiki143k

CWA Metrics

Tpred

P OW A+ Tpred

JP recision

ST Recall

FT SP

JP recision

FT SP

HAKE† PairRE† AstarNet ULTRA GPHT(HAKE)† GPHT(PairRE)†

9188±0 125±87 29742±105 5689±287 9743±0 209±47 12392±3813

1319±0 119±83 10217±51 1750±116 2945±0 191±47 5866±1262

1292±0 30±7 2901±7 1328±52 1062±0 44±8 2018±332

0.560±0 0.246±14.8% 0.191±0.1% 0.496±0.8% 0.235±0% 0.220±8% 0.253±1.6%

0.128±0 0.044±0.4% 0.428±0.0% 0.289±1.1% 0.258±0% 0.053±0.4% 0.357±2.8%

0.208±0 0.075±0.3% 0.264±0.2% 0.365±0.2% 0.246±0% 0.085±1.1% 0.296±0.4%

0.141 0.240 0.097 0.233 0.109 0.210 0.162

0.134 0.074 0.158 0.258 0.153 0.084 0.224

DiffTSP

7472±103

4355±51

3472±87

0.630±1.2%

0.468±0.4%

0.537±0.5%

0.464

0.466

TensorLog† HAKE† PairRE† AstarNet ULTRA GPHT(HAKE)† GPHT(PairRE)†

24392±0 22215±1283 19228±2075 6001±231 3844±0 17702±7935 3011±233

2570±0 6182±43 3313±722 2589±129 1349±0 4709±60 1954±191

2299±0 3044±72 1191±77 2275±31 692±0 2700±681 909±34

0.494±0 0.315±0.2% 0.211±3% 0.581±0.8% 0.346±0% 0.363±4.8% 0.384±1.9%

0.127±0 0.326±0.3% 0.204±0.7% 0.281±0.3% 0.155±0% 0.307±4.2% 0.178±0.3%

0.201±0 0.32±0.3% 0.207±1% 0.379±0.2% 0.214±0% 0.333±4.6% 0.243±0.1%

0.094 0.137 0.061 0.113 0.180 0.152 0.302

0.108 0.193 0.095 0.179 0.166 0.204 0.224

DiffTSP

10162±530

6804±275

4543±105

0.557±0.3%

0.397±0.4%

0.464±0.6%

0.447

0.420

TensorLog† Wiki79k

RS-POWA Metrics

P OW A Tpred

TABLE IV CW A+ CW A = T † T HE RESULTS ON CFAMILY DATASET, WHERE Tpred IS THE CORRECT TRIPLE SET, AND Tpred pred . T HE RESULTS WITH ARE FROM GPHT [15] AND THE RESULTS WITH * ARE FROM LLMTSP [17]. Models

TensorLog† HAKE† PairRE† RGCN† CompGCN† AstarNet ULTRA GPHT(HAKE)† GPHT(PairRE)† LLMTSP(GPT-3.5)* LLMTSP(GPT-4o)* DiffTSP

Number of Triples in

CWA Metrics

Tpred

CW A Tpred

CW A+ Tpred

JP recision

ST Recall

FT SP

911±0 3186±543 5732±2062 30608±3443 38931±3745 2075±360 32761±0 1896±149 3739±593 3403±158 1276±147

572±0 1788±321 1747±694 3026±137 2599±47 911±187 763±0 1222±58 1471±187 96±12 179±17

0.628±0 0.561±1.8% 0.305±1.8% 0.093±6.0% 0.062±4.8% 0.439±1.7% 0.023±0% 0.645±2.6% 0.393±1.3% 0.028±0.3% 0.14±0.5%

0.158±0 0.624±5.9% 0.616±13.7% 0.704±0.5% 0.598±0.3% 0.445±4.6% 0.407±0% 0.516±1.2% 0.566±3.4% 0.168±0.8% 0.374±0.7%

0.252±0 0.591±3.1% 0.408±4.9% 0.163±5.2% 0.114±1.7% 0.442±3.3% 0.044±0% 0.573±0.4% 0.464±0.7% 0.049±0.4% 0.204±0.7%

2453±35

1657±18

0.675±0.2%

0.600±0.3%

0.635±0.2%

loss on FT SP , showing the importance of structure-aware denoising network. Since w/o Exinput loss includes these edges in Gs and Gqt , the model may learn a bad mapping from input to output, causing about 8% performance drop. Using unweighted BCE loss causes the largest drop (about 30%). The non-existence edges in the KG create an extreme class imbalance, and the unweighted BCE loss could mislead the model to achieve a low loss by predicting all edges as absence. Though this minimizes the loss, it prevents the model from learning meaningful patterns, thus leading to poor performance. In contrast, the weighted BCE loss introduces relation class balancing to properly guide the learning process. F. Sampling Process Visualization Figure 4 visualizes DiffTSP’s sampling process on a subgraph from the CFmaliy dataset. We run 20 denoising steps and show the snapshots at steps 4, 8, 12, 16 and 20. The first

TABLE V A BLATION STUDIES ON CFAMILY DATASET. Method

CFamily JP recision

ST Recall

FT SP

w/o RCE w/o Attention w/o BCEw w/o Exinput loss w/o Rsplit

0.602 0.665 0.369 0.700 0.637

0.623 0.573 0.308 0.485 0.605

0.612 0.616 0.336 0.573 0.621

DiffTSP

0.675

0.600

0.635

frame is the subgraph Ggi in training data, the last frame is the ground-truth subgraph from test data, and the middle five frames show the sampling process. Surprisingly, although the initial denoising steps predict some incorrect edges (shown in red), the errors do not accumulate. Instead, the model still

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

is_sister_of is is_nephew_of is_sister_of is_a _u _nunc ience t_lefo is_uncle_o _of f is_ is_aunt_is_fatheis_ is_n is_sister_ofbrother_o of r_one f ep is_nephe is_aisunt f phew is_mo is_nephew is_n_uep_of is_ne w_of phew_of _of hew_o ther_o is nchele _of is_brother_of f rother _niece ece_of is_bis_b f w_o_of is_is_ni unis_n cle _of _o ephew_of isroth f is_aunt_of _ne er_ofis_aunt_ is_aunt_o f _of is_un f of is_un ister_o cle_ofis_s ph is_wife_of f is_nephew_of cle_o ew is_brother_of _of is_f da is_u _nnc is_hugusb hter is_uncle_of is_un iecele isis_un _of_of and is_acle_of _of _daucle_o is_a f is gh un is_ is__aunug ter_ t_of un is_aunt_of is_ueph t_ is_n is_brother_of aunt_o da is_br t_o of is_siothe ncle ster_r_of _of ew_ f ofhter_of of f of is_nephew is_a _of un is_sis is_un is_u is_aucle_o nt_off t_o ter_o ncle f is_a is_aunt_of f _of is_au unt_of is_ni is_ntau_of is_un ece_ is_u nt_o cle_o _nnc of ie f f is_a cele_of is_father_of unt_ is_uncle_of is_aunt_o of f is_a is_brother_o funt_of is_sister_of

is_aunt_

is_niece_of

fce_of er_o ce_o roth

_fa is _b 68 60 th f is f 69 53 er_of 62_uncle_o is_sis _aunt_o _of cle56 76other 5 is_nephew_of is_ne is_br 2is _ofis_unclete_ofr_isof _of isis_d_m phew 77is_un is_siste is_ni of of45 auot ce_ece_ r_of of nier_of _of is_iste _of ghheter_r_ is_ne ce_ cle 66 nieis_s 67 offn_of 93 is_ ofauf is_un phew is_b is_so hew 63 nd_o 24 ife_o ep nt 35 _of is_niece_of 59 usba _of roth is_his_w 20 is_n 28 f 52 er_ 91 r_o 51 e _of 55 is_nephew_of e of 31 19 th _o cl f aunt f is_bro is_un is_bro 6429 ther_o f unis_t_of ther_o is_husband_of is_bro other_o92 58 is_a 43 f r_o_off is_br isteher is_srot is_b 44 is 61 f _b f 50 83 is_u is_uncle_o16 17 of rothunce t_ce_oof_o f 54 ncl is_nephew_6 isis_n _nieeier_ _a 70 is is 18 e_of 36_oof f _fath of er_ 12thteerr_ off is_au r_ont_o 84 65 isis_b_srois f is_urothe 37 40 ncle 42 46 71 is_b75 of t_of_of ter_ 30 _of is_aun 47 of sis13 is_ is_a hew 73 ce_ unt_ _oepf is_nie is_a of 7 thiser_n un _bro8 t_iso 90 94 74 is_b roth 49 is_n f er_o 8889 f 11 ephew_of4815 is_bro ther_ois_neph 41 14 f 72ew _of 87 is_aunt_of 38 9 is_niece_of 85 39 86 10

_nie

is_da is_faught ther_er_o of f

is_sister_of is_nephew_of is_sister_of is_nephew_of is_sister_of is_n is_bro iece is_aunt_ is_n ther_o _of is of is_neph is_nieceis_nie f is is_n _unnis_a ephew_o _of ce__uofn ew_o eisp_nhew f cle is_neph ccllee_ount is_brother_of is_n f iece_of is_u _of is_niece_of _off _of iencle _ofof _of ceew_ is_a is_aunt_off unt_of is_un _of is_aunt_o cle_ of is_niece_of is_au is_uncle_of is_u nt_of niscl_a is_un u e cle _onft_ is_husband_of of is_a _of is_au is_niece_of unt_ is_ueph nt is_n ncle _of of _ofof ew_ is_n iece is_uncle_o is_ni is_u _of f ece_ ncle of is_brot is_aunt _of is_au _of her_o isnt is_unf _a_o unft_ is_u cle_o of f ncl e_o f is_brother_o f

is_niece_of is_uncle_of

is_a unt_ is_uncle_o fof

is_niece_of

is_sister_of is_nephew_of

is_sister_of is_nephew_of is_sister_of is_nephew_of is_sister_of is_n is_bro iece is_aunt_ is_n ther_o _of is of is_neph is_nieceis_nie f is is_n _unis_a ephew_o _of ce__uofn ew_o eisp_nhew f cle is_neph cle unt is_brother_of is_n f iece_of is_u _of is_niece_of _o _of iencle _ofof _of ceew_ is_a f is_aunt_of is_un _of is_aunt_o f unt_of cle_ of is_niece_of is_au is_uncle_of is_u nt_of ncl is_un cle_o e_o is_husband_of f f is_au is_niece_of is_uncle nt_o _of f is_n iece is_uncle_o is_u _of f ncle is_br is_aunt _of is_au othe _of nt_o is_r_o f unfcle is_u _of ncl e_o f is_brother_o f

is_niece_of is_uncle_of

is_uncle_of

is_aunt_

is_niece_of

is_brother_o

is_u n

is_aunt_ is_n is of is_neph is_nieceis_niece_ isis_n _unis_a ephew_o _of _uofn ew_o eisp_nhew f cle is_neph cle unt is_brother_of is_n f iece_of is_u _of _o _of iencle is_niece_of _ofof _of ceew_ is_a f is_aunt_of is_un _of is_aunt_o f unt_of cle_ of is_niece_of is_au is_uncle_of is_u nt_of n is_un cl cle_o e_o f f is_au is_niece_of is_uncle nt_o _of f is_n iece is_uncle_o is_u _of f ncle is_br _of is_au othe nt_o is_r_o f unfcle _of

is_niece_of

is_brother_o

is_uncle_of

is_sister_of

nis_a cle unt_of is_n is_ueph _o nclew_ e_ofof is_aun f is_u t_of ncle _of is_au is_uncle_of nt_of

cle _of

ncl is_br e_of othe is_r_o unfcle _of

nt_o f

is_au

is_au is_niece_of nt_o f is_uncle_o f is_u

_of

is_uncle

is_brother_o

is_u ncl is_br e_of othe is_r_o unfcle _of

is_u

is_uncl e_of ncle _of is_au is_uncle_of nt_of

is_u

_of

is_aunt

cle _of

_of

w_o

he ep

is_n

ce_of f nt_ is_ofnie er_o is_au roth is_b

ce_of f nt_ is_ofnie er_o roth is_b

is_au

_of

ce nt_ is_ofnie

is_au

is_uncle

_of ncle is_u is_aunt_of

is_u n

_of

is_uncle

is_aunt_of

is_niece_of is_niece_of is_sister_of

is_uncle_of

is_nie ce_ e_of of

57 25

is_niece_of f e_o is_niec is_niece_of f w_o of he ece_ ep is_ni is_n _of ff is_uncle f f cle ew_o_o _ounph is_niece_of ncle_o ifeis_ne is_u is_aunt_of is_wis_ is_niece_of is_aunt_of f _o ncle f is_u _of is_aunt_of w_o phew is_aunt_of ephe f is_mother_of is_n e_of is_ne erf_o is_niece_o is_niece_of ncl _of _o_o ff roth r_of of unfcleof ntife is_u is_bis_siste is__o unt_ is_w phew ter_ is_au is_a is_ne is_sis ce_of f nt_ is_ofnie of er_o_of is_au ephew_ is_nr_of is_brothe roth er _of is_b_broth is_nephew is_aunt_of is cle_of f nt_of is_niece_of is_un w_ois_au r_of ephe is_aunt_of is_brothe _oisf _n is_brother_of fis_sister_of iece er_of cle_o is_nis_broth is_un is_sister_of is_h

niec 6968 60 62is_ is_s _of cle56 76other 5 2 _ofis_unclistee_or_of is_br 77is_un is_ni off of45 ce_ece_ nier_of is_iste 66 is_sois_n_of is_neis_s is_n 93 phis_ew is_b brot67 24 uncle 35 ie 63 _ofher_o ceis_niece_of is_niece_of 59 _of roth 28 _of 20 f 52of f 55 er_ 91 51 e_ of of 1931 cl _o r_of is_bro is_un phise_uw n 6429 unt_ ther_o_ne cle is_brothe 92 is_a _of is f 43 58 44 is 61 _of f _bro ncle17 50is_aun83 16 54of is_u ce_ole_of t_of eier_ is_nephew_6 is isth_nis_unc 70 _fa of 18 36 the 12 is_nie r_ooff ce_r_ 84 65 is_ is_urothe of 37 brothe _b nc 42 464071 r_of is 75le_of of f ter_ is 30 sis13 w_o _un 47 of is_ cle_ ephe 73 is_niece_ of is_n 7 f 90 94 74 ew_o 8 49is_neph 48 le_of 8889 is_unc 11 15 41 14 72 87 85 38 9 39 86 10

78 23 1 333422 is_bro ofaunt_of ce_is_ is_nie 4 ther_of is_mo 26 57 ther_o 81 2182 3 f 27 25 is_nie f

d_of sban is_niece_of is_hu f iece_ois_niece_of is_aunt_of unt_of f is_ais_n ter_o f is_sis hew_o f _of niece ep hew_o is_aunt_of is_ is_nephew_of is_n_nep is_niece_of is f f _oe_f_oofew_o _of is_niece_of le_of is_wife_of niifeeccle un neph is_uncle of _unc of _of _of er_ is_son_of isis__wis_ is_mother_ son is_mothis is_aunt_ is_ ece_of ew is_ni is_niece_ofis_aunt_of eph of ather_ is_aunt_of is_n is_f f f of f _o f is_uncle_o f w_o thteerr_ wep_ohe f f is_brohether_o on_o _srois _n is_mother_of _of f isis_b is_s phew _nepis ncle_o is_ne _of _of r_of r_of w_o _ofis f phew _u e r_of w is_siste he _o ife is is_siste of is_ne ep ephe _fath r_ofofphewister_ is_w is_n is her_ne is_n of ce_of otte is_ is_s nt_ of is_ofnie f f er_ of is_is_brsis cle_ois_n r_of ephew_ is_au er_o roth f is_brothe _of r_o unt_ e_of is_un is_niecle_of is_unc _of aunt the roth is_b is_a is_is_ is_aunt is_b ter_broof cle_of is_unis_sis ter_of r_of is_sis is_aunt_off is_aun is_niece_o f is_aunt_of t_of t_of brothe ce_of hew_o is_aun is_nep is_ fis_sister_of ie r_o_off isteher cle_o is_nis_broth er_ofsband_ofis_b is_srot is_hu is_un is_sister_of f on_of is_uncle_ois_s is_father_of

usba

is_aunt_of

is_niece_of f e_o is_niec is_niece_of

le_o

e_o

ncl

is_u

is_niece_of is_niece_of is_sister_of

_of ncle of is_aunt_

f e_o

is_u

ncl

of ephew_ is_nr_of is_brothe _of is_nephew is_aunt_of is_niece_of r_of brothe ce_of is_ fis_sister_of ie cle_o is_nis_broth er_of is_un

nc is_u

_of

is_aunt_of

_of _o_o ff is_unr_cleof au_wntife iste is_ is is_s

is_u

is_niece_of

of is_aunt_

f e_o

f her_o brot is_ is_sister_of is_brother_of

ncl

ephew_ of is_n is_nephew_ is_aunt_of

is_niece_of

is_niece_of f e_o is_niec is_niece_of

_o r_of aunt iste is_ is_s

is_aunt_of

is_niece_of

_of is_uncle

is_u

is_brother_of

ephew_ of is_n is_nephew_ is_aunt_of

isis_d _fauat is_d is_un is_f gh is_s heter_ is_f ni aug athe ath on_ hte er_r_of ofr_o is_his of fecclee__ooff isis_n is_b r_ofis_brot is_sroth isteer_o of is_nep r_ofis_son_o _w usisba is_uncl her_of _uepn is_sister_of is_sister_of hew_o er_of fis_siste is_ne e_of f fr_of is_aunt_of is_moth ife_nis_ phew neis_au nt_o_of is_sister_of auphnt_ is_brother_of hclee ew_of is_aunt_ofis_neph nd f _oieis_ is_uncle is_nephew_of is_aunt is_uncle_of is_n is_u ew _of fce _ois_nephe of_of ncle w_o_o_of is_nephew_of is_uncle_of _ofw_of ew_ is_nephew feph _o of is_ne is_un is_ni is_unphew isis_m ff ece_ cle_ooffisis_f_sa_of cle_o is_of is_ is_is_nephew thonef is_uncle_of _a_sf is_n is_ne_o is_ _or_fo is is_sis is_aep _of otunonhet__or_ is_is_ne sister is_is_ auph is_da nie is_ neauph is_ is_b ter nt_ is_ neug is_n f is_ ew is_ne ph _m ce mis_ is_n unso un is_ is _of is f of is_a of un n_ ne ew ph he isfroth _of of is_ phew _o is is_n is_ is_ er_o ot eph nt_ _n_nis_a is_neunph isis_n unt_ of_o _nph t_is_ _of ew _mis_uothe he f _of cleau ew_ htcle ne au wof_of is_nie is_u unt _o _of of ew_ of is_fis_ err_o _o is_u e eph ncle _of auewceof_of phnt_o _aeispuu_ahnnt_ entfpew_ois_ f au cle is_un is_ is_sois_sooth ncle ncle is_ _ofof ew_o fphcleew is_un ew_ cle_o fun heph iece ni_of athe nt_ is_neph he_of ne au et_uwoof _oiefpis_n cle_o of is_brother_of is_oof_afncle_of ff ntew_o n_ofne_o is_r_of cfeeis_bro _off f is_ ec _of is_is_un is_u _of f _of is_n nt w is_sis un nie nie is_s ew_of au w e_ r_ ther_ _o ter_o n_ot_f f is_neph eph _o is_aunt is_nephe nt_ ce _ofof cle_ ceis_uncle_ _ow_of of f ister_r_o isisis_ _ofcle is_aunt_oisfisoisf_bf_s ew_of _of of of f uunc of of _of f is_soffiste is_u is_n nt_ew_ of is_n fe_o isis_ ncl iece is_nephew is_nir_of is_ _broisisrothte _ofis_ne is_nephew _u _of _n_b_sbrnierosis is_nephew_o _off _of ofle_of isotthteteher_o is_b hew_o isis_diece_of isis_husband_of f phew is_nep is_niece r_o ec is_nep is_ is_aun e is_ _n clce r_ is f e th _a r_ _n hew_o ro _m _of f e_ t_of r_oof is_is_ne ni _of au e_or_oof _uepn ofis_au f is_uncle_of a ther fis isieuer_u _n isis_brother_of is_sister is_is_ne isisau is_au auec _nph phntnte_ gthhe nt_ois_mo _o_ooff uo_of is_n _a t__onie_ofcloce f f is_nephew_of hclewis_nephew_of is_uncle_of fis_so fffe nt_of _a_nieunce ew ieun is_ae is_n_o f is_n_of _u _nnt_ is_nie is_au ter_r_ is_nie ew cece is_ iece _o _o ce_ f nt_of ther_ ce_o n_of t_ nc ie is of _o is_ne _o _o f fa is_au f of puhne n of ce of o ff ie_ncet__oieois_w phew ther nt_o f _o le_of is_niece_of of f _of f nephis is_ne is_sisis_ t_wo_ois_n is_au f phew nt_of_of is_m ife_ _ofceece_ is_n ewnc teris_of _u _n is_n f fis_aeph is_a untew_of eph _ocelef is_ni unt_ fis_o_shef offof ieis_ is_uncle_of is_niece_of ew_ ot _n is_f _of is_ is is_aunt_of of is_s ep is_brot of ath nie is_ au ep on_ _n_aie is_smothe _o nt_ is unt_ is_a ce_ is_n her_of ofis_ niusb r_ofe_of is_niec is_his_w heis_siste is_n ecer_o unce w r_of ofof r_teiece of is_aeph e_ofoff heiste w_oof ife_ r_ofo _of is_nephew_o ew_ and unt_ is_u t__oo is_ of _of _ofr_of f is _nisun f nie f is_nep is is_aun f _n f cle n ie hew_o _aun isis_n_a e _nis_aclecece t_of is_bro is_au fis_sis _of is_siste r_of isis_n_a is_nie ce_of is_is_br is_n is_ni ter_of is_neotunis_s ieunce phfe t_of _oece_ peunt_of is_u ofis_uncle_of ther_o is_n is_u is_a ncle ph epiece t__oof w_o hecleew is_niec nceist_is_o_d_m hnet_wfo is_nephew_of untieu_of is_ote is_ r_o e_ofis_neph he _of is_n offauotgh _of f _off r_f ofbris_ nc is_ is_n iec f ieceis_is_ wncl is_aunt_of is_nie is_ni f is_ niephce_ is_u aunt_ otne _of e_o le_o f heteis_mo he ce_ofof ew_of is_ aunce_ ece_ is_nie n_of unc nie r_oewof r_is_sother_ t_ooff _ofaunt ofiste is_ is_sroth le_of f _of ce_ isis_b_sis_ is_auf _of is_n r_ofof is_b is_n er_o r_of f niecofe_ is_aep roisthtenie ce_o eph of _offis_ unhet_ err_nt is_ni is_au _o ofnt_o ece_ eisisw_b_s wof_o f offis_fatsohen_r_o _oroisf th ofis_ne f f phew is_nis_daughter_of teerr_ is_da is_moughte is_niece_of is_brother_o epf he is_uncle_of ther_r_of _of _o of f of is_nie is_aun is_niece_of ce_of w is_brother_of is_sister_oft_of is_sister_of _of is_sister_of is_ne is is_au phew _u _n nt_of_of nc iecele is_uncle_of _of

79 80

r_ iste

r_of

57 25

niec 6968 60 62is_ is_s _of cle56 76other 5 2 _ofis_unclistee_or_of is_br 77is_un is_ni off of45 ce_ece_ nier_of 66 is_son_of is_sis_is_iste 67 is_n 93 is_b br ot ie 63 is_niece_of 24 35 28 20 52of 55her_of ce_of rother_ 91 59 51 e_ of of 1931 cl r_of is_bro is_un is_un 6429 unt_ ther_o cle is_brothe 92 is_a f _of 43 58 44 is 61 _of f _bro ncle17 50is_aun83 _o 54of is_u 16 this_unc iece le_of t_of ephew_6 70 is_fis_ner_o 18 is_n36 ath f e 12 is_nie r_ooff ce_r_ 84 65 is_ is_urothe of 37 brothe _b nc 42 464071 r_of is 75le_of 3013 is_un cle_ 73 47 of 7 f 90 94 74 ew_o 8 49is_neph 48 le_of 8889 is_unc 11 15 41 14 72 87 85 38 9 39 86 10

333422 ce_is_aof unt_of23 1 is_nie 4 26 81 2182 3 27_of is_uncle_of

is_nie ce_ e_of of

79 80

is_niece_of f e_o is_niec is_niece_of f w_o of he ece_ ep is_ni is_n _of ff is_uncle f f cle ew_o_o _ounph is_niece_of ncle_o ifeis_ne is_u is_aunt_of is_wis_ is_niece_of is_aunt_of _of ncle is_u _of is_aunt_of phew is_aunt_of f _of is_mother_of is_ne er e_o f is_niece_o is_niece_of ncl _of _o_o ff roth r_of of is_u is_bis_siste is_uncleof ntife au r_ _w unt_ iste is_ is is_a ce_of f is_s nt_ is_ofnie of er_o_of is_au ephew_ is_nr_of is_brothe roth er _of is_b_broth is_nephew is_aunt_of is cle_of f nt_of is_niece_of is_un w_ois_au r_of ephe is_aunt_of is_brothe _oisf _n is_brother_of fis_sister_of iece er_of cle_o is_nis_broth is_un is_sister_of

57 25

is_uncle_of

e_of

True_Graph 0 95 nodes, 238 edges

Result 0 95 nodes, 154 edges

23 1 333422 4is_aunt_of 26 81 27 2182 3

niec 6968 60 62is_ is_s _of cle56 76other 5 2 _ofis_unclistee_or_of is_br 77is_un f is_ni ece_ ce_of of45 66 is_son_of is_is_brnieot67 is_n 93 is_b ie 63 24 35 28 20 52of 55her_of ce_of rother_ 91 59 51 e_ of 1931_uncl 6429 is 92 is_aunt_of 58 43 44 is 61 _of f _bro ncle17 50is_aun83 _o 54of is_u 16 th iece t_of ephew_6 70 is_ner_o 18 is_n36 f 12 f r_o 84 65 is_ 37 is_urothe brothe _b nc 42 464071 r_of is 75le_of 3013 is_un cle_ 73 47 of 7 f 90 94 74 ew_o 8 49is_neph 48 le_of 8889 is_unc 11 15 41 14 72 87 85 38 9 39 86 10

is_aunt_of

ff is_uncle f cle ew_o_o _ounph ifeis_ne is_wis_ is_niece_of is_aunt_of

57 25

niec 6968 62is_ 60 is of cle_56 762ther_ is_u_snclister_o 5 is_bro 77is_un e_off of is_ni ece_of45 ce_of is_nie 66 is_br 67 93 is ot 63 _b 24 35 59 roth 28 20 52 her_of er_ 91 51 of 1931_uncle_of 55 6429 is 92 is_aunt_of 58 43 44 is 61 _of _bro ncle17 50 83 16 54of is_u the is_nephew_6 70 r_ of 18 36 12 f r_o 84 65 is_ the 37 ro brothe _b 42 4640 71 r_of is 75 3013 73 47 7 f 90 94 74 ew_o 8 49is_neph 48 le_of 88 89 is_unc 11 15 41 14 72 87 85 38 9 39 86 10

79 80

23 1 333422 4 26 81 27 2182 3 is_uncle_of

is_uncle_of

is_aunt_of

e_of

_of ff is_uncle ew_o_o e_neofunphcle ifis_ is_wis_ of is_niece_ is_aunt_of

57 25

79 80

23 1 333422 4 26 81 27 2182 3

6968 62 60 is of cle_56 762 is_u_snclister_o 5 77is_un e_off 45 66 is_br 67 93 is ot 63 _b 24 35 59 roth 28 20 52 her_of er_ 91 51 of 1931_uncle_of 55 6429 is 92 is_aunt_of 58 43 44 is 61 50 83 16 546 _brothe 17 70 r_ of 18 36 12 84 65 37 42 40 46 71 75 3013 73 47 7 90 94 74 8 49 48 88 89 11 15 41 14 72 87 85 38 9 39 86 10 53

79 80 78

f cle_o is_un of is_niece_

is_uncle_of

_nf is_ of nt_of o niauect_ isis er_isr_oof is_ ter_

_b nt is_s roisth_steroisthteis_aun e__oofisf isf_sis is_o_n_a_n er_r_iso 6968 60 o is_b_s epcet_ _n cclee e_ofieun fff nc f o_u ieisce 53 isn_of 62 f _nle_bnie_once_of clt_of he_oofw f is_aun t_wo_o is_nie is_nncl is_u 32is_u iecee_o _of puhne fis_niece_of cef_o _of5 is_urofthe _aent2 is_uncle_o _of _nlencie_o _o is_aunt_of et__oof56 is is76 _n isf _u isis_niece_of is_sis isau isf is_n f r_f of of_u fter_ois_d iec _o _sis iecele77 nc ieu ncle_sisis_his_w ieis_ace _aauhe e_o eris_au _nis_s _of htisr_o f nt_ _nis_nnc e__ooffis_u is45 ceun _of ife_ois_ ter_ ugungh _of ter_usba au nie r_of is_n is_d niec fcleisis_biste is_ unt_tecle f nt_o ofis_ is_is_dafatis_ of nd f_o is_ is_uncle_of 66isis_fat ncle iece_of of 93 r_fof f f is_ fr__fau 67 ofat roth_oofer_o is_is_nephew_of is_u _sroisthte is is_u _ohe is_ her_o uncle ofis_b hegh neroth on te sis t_ er_ r_ ot is ph nc is_niece_of is_aunt_of ce 63 _u _n er_ _b _s is_uncle_of r_ 24 _o te of f 35 fis_uncle_of 59 ieunisf_m isf _o nieis_b 28 ofr_o is_husband_of is_wife_of 20 clcee _siste ew_o f of le_o r_oof ro cet__oof is_niece_of isfis_n_a cet__oofis_uncle_of 52 _of r_ _n is_son_of_of _aieun thteerr_r_of is_m f f ther_ f 91isis_n _aewieun_o_sffrois55 51 is_mother is o is_fa is is_so is_s o_o f te 31 19 is_o_bn_of on_er_ is_is_dafat isof of isther_ f oth ther_ pf his_bro ter_o isis_sis ofoffis_ ther_o niece f _o f e_o f_ofof 6429 is_hehtsisr_o unt ter_of r_ofofug _ne ncle_nieis_sis_n _or_of _niece f92 is_aiec erter r_is_br sis is te he _of on er_ r_o _o is_ f _u is_si c is_wife is he at her te _o f isf gh othe ster_r_of f isis_f_s efat _ofce _ofght 43 58 _fauat is_is_dau is__osis cle isis_n of ft_of _of nie un cle_o isis_d phew is_ is_un _uepn is_ne un of is 44 is is_n 61 is_a f ew_ _a _n eph _b is_niece_of 50 epunthew_83 isis_a17 eph hclew is_aunt_of is_nephew_of _ofof is is_niece_o le_of 16 of is_nro is_nie fe_of_o 54 ew _nep un_oce_of ce is_aofunt_ _uenc f _oof6f is_dis_isthun 70 nie heis_ni _o t_ r_cle f is_sister_of is_ece_ is_ f 18 wisis_ auer_o of36 of_of ois_brother_of f off _o ner_auph ieuncet_ ntbr_n _oot _a f isis_nte_uf pn is_ rothtetherr_gh clee_o isisew bro of_ofhef r_ois_b w_o_of is_s e12 isf_s_brois tenier_c hcl r_ the r_o 84 65 isis__sisteew_o_of f is isisis__fisf _nunroepclethise_u_nr__ofofof 37niecliscee__n_oofepisf_nheiece 40 is_bro _n 42 _of ofof is_sais_u siseph _bthiso_n_uephew is_u ew_ ofis_uncl ncle the ew_ ter 46 e_of unt_ is_u eph ne_or_nchele_o is_n _of r_o is_a is_n f fof75 71 nc r_of f f o w f _o le is_ 13 he of r_ f _o r_o _o is f f aug er_ ni_ofeccle hte 30ot _nep he _oun is_b le_o_satfon f e_ 47 is_br _of oth _ocle _f f 73 ofis_d rofnc f is_un fis_m hew phew r_o theisisof is_h neis_w _o the usbife_ eris_o_unt_ _o ew andof_of bro 7 r_is_ 90 94 74is_of_bf rois_8this_neauphis_is of is_ne is_uncle _of cle_o_of f 49 is_unis_uclencle_of 48isis__b_sfrobristhteoterr_he_oofr_of is_unphew f 8889 is_nephew_o f 11 _ofis_ 15 is_n is_ne isis_un ntew_o_of phew bro 41 phcle_o _aepuneau uncle 14 hnet_w f ther_ofis_72 is_is_ _of o_of f _of 87 is_nephew r_of 9 is_aunt_of 85 is_brothe38 39 86 10

Step_16 0 95 nodes, 134 edges

is_s

79 80

23 1 333422 4 26 81 27 2182 3

Step_12 0 95 nodes, 101 edges

iste

sba

is_nie ce_of

78 u is_h 23 333422 of 1 ce_ ofis_br is_sis nie is_bro other ter_o is_ ther_o f f _of is_aunt_4 is_ daught 26er_of 57 _of is_niece_of 81 is_uncle is_nephe 2182 3 isfis_aunt_of 27w_of is_niece_ _n ie f of ife_o ncet__ooce_o 25 is_w _aieu is_auf f

Step_8 0 95 nodes, 68 edges

is_s

79 80

f fe_o is_uncle_of is_niece_of is_uncle_of is_wi _off f ther_o e_of is_moghter is_dau is_niece_of is_niec is_uncl nclfe_ois_uncle_of is_uncl cle_ooff is_u iece_o is_nephew_of is_niofece_ is_un e_of d_of ew_of is_n is_uencl unt_ _of is_aeph sban is_n is_niece_ofaunt_of r_o is_uncle_of is_hu iecef _of _uncl le_of is_nncle is_u is_ is_siste f is nc of er_of iece_of cef _o f un is_nncle is_u er_ofof is_broth is_brother_ofd_ofis_u is_f is_aunt_of nief_ocle ter_ _o f on_ ff _o iece_of is_sath is__o fe_of roth f r_of er_o fce sban of _of nie ofof_of ceun is_wi _of e_o ew _o_ocle r_ooff is_nofeph of_sf is nie f is_hu _ofewnc unt_ auis_nt ie_ocelef er_ is_siste nclew_ le_ ncle is_b ce the eph ght hew is_a of le_of r_ is_ f _of of is_n _n _u is_u is_u unc nd mo er_r_iso is_ is_unc nie is_n nep ce_ is_husband_o te ce_o ew_ iscle is_ is_is_dau is_ unph nieiscle bais_ne is_is_sun is_neph roisthte is__husis_ ofief ephew_ofof ther_of is_brother_of is_n fis_s f of _of _of cle_o phew _o of f f f is_n is f on_ isis_b_s cle_ is_un is_ne r_is_ t_wofphew cle_of of e_mo is_un r_o is_ne he r_o is_un un clefew_o_o e_o ph teheun r_of _of thecle ncl_ofteher_o f f sis ofot _of f _of ncl of f f is_roun is_aephe is_ne ofis_aunt_ is_niece_of is_n is_nephew_o ter r_o is_is_r_bris_ f er_ofof_of sisthe hew isr_of_uofon_ew_o_o _b is_uis_brsisot bro leew_o on_ f cle is_s is_ le_ ot ath r_ f is_ of hew ph c h is is_ of _o te un of f _o ew_ unc of ne f nep unt_ heter ew_ f fof e_o eph is_is_s hew_o is_ is_br is_nep_ofau unt_of is_is_f is_a unt_ is_ nt_of is_n oth eph otgh is_nep fer _uepn_of phew is_a is_au brsis is_n neo_or_fnieccle is_ne f t_ofis_a er_o r_r_o f_of er_of _mis_sist isis_n _oun r_ole_a _dis_ ofe_of r_o _o f ff r_o f the auntisisis_ _saetho _u_n is_aunt f is_niec r_ th roth he er bro te te is_sister_of is_brother_of is is _f hew_o ot ffunt _offof is_ nc is_son_of is_uncle_of is_nephew_of sis ew_ br_of is_nepis_ _oeph w_o _b_sroisthteis_aunt_of _o is_nephew_of is_b cle_o _u er_ois_fisais is_aunt ce is_is_ew_of is_a nt fisis_aunt_of isis_uncle_of is_un f he of is_ f th_of auis_n fis_au f_o_sis_neph is_uncle_of is_uncle_of isis is_nephew is_nephew_of f is_niece_ f ofis_nie ce_of _o unt__of is_nie _o is_aiece ndisnt_of ewof le_o ro _o her_ofis_n wof_oep _b is_brot her_of f w_o is_uncle_ t_ phr_ce_ ba of is_brot nenie _o phusew f f_son ntis_ puhneis_n is_wife ofnc isis_of _u _of is_nephew band_ isis_aunt_o _ooff f f ephe is_auis_ iste is_ne_hof _of ce_of nt_ df_o is_ae is_hus ew auofcle nie nt_ _o _of r_of is_n is_s f teisr_ is_n un ph aen_o is_ _of au f _of _of h if of _o is_ _of necle ew nt_o f is_ _of of g _oothf erndr__oof rothe unt_ iece ph f f hnew is_au ncle is_ne usbroth _w is_aphew r_of f is_is_is_ ster_of_h is_n neun ew_o_ofephete hr_ewr_of_dau isteer_o isis_s w_o_o ep u ceusrot_isba f is_si is_u ie_b te is_b is_b r_unofphcle_mau_notgh is ew_isof hclee is_n_n is_a_h f of_of f f nt_of fr_or_o is_ne is_aunt_o he eph f _ofthe _d _of is otis_ _o is _of _of ce_of epn is is is_s is is_n ew t_whe of_of bro ew r_o the is_au is_nie ew _u_of unt cle heso ter_o n_phew w_of phis_ un phew_of ph bro is_br is_n un is_aeph of is_ne is_uncle_of f ephew_ofis_is_ nt_o ep _of is_ne ne neis_ _of fat phew r_oisfis_nf fean_od_f of ew_ ofis_ is_aunt_o f_n is_n is_sis f is_nephew is_au isofephe is_n is_ is_ne t__a is_uncle_of is_nephew_o _oeph isncle is_u f fis_is_n sb othe is_ wi ew _ar_un is_br f is_nephew_of is_niece_ofunt_obrothef r_o is_nephew_of is_hu f ph of otishe r_o ther_o is_aunt_of is_son_of is_father_of f fr_o f is_net_m is_ _ohte is_sister_of _of is_acleew _ofhe is_aunt_of is_brother_of is_nephew ug is_brother_of is_bro is_nephew_of _o is_sister_of is_brother_of r_o unis_ er_of unt_of dafat ph ew unis_ is_ae_of neis_ the is_ais_broth is_wif neis_ph ois_brother_of is_is_ of n_of _of cle_of hew_ _of is_un is_nep is_sother is_m f is_fatheris_fa cle_o_of is_niece_of is_uncl ew_of is_unphew is_ne is_neph

_of

Step_4 0 95 nodes, 37 edges

is_uncle_of

Support_Graph 0 95 nodes, 886 edges

Fig. 4. Sampling process visualization for one subgraph in CFamily dataset.

Metrics Value

0.66 0.64 0.62 0.60 50

100

Repeat Times Ns

150

0.675 0.650 0.625 0.600 0.575 0.550

FTSP

JPrecision

0.68

STRecall

Time

0.66 0.64 0.62 0.60 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Ratio

DIT Layer Numbers NDit

0.70

0.65

0.60

Time (seconds)

0.68

0.55 25101520

Sampling Steps T

100 0

Fig. 5. Model performance with different hyperparameter settings.

recovers a large number of correct edges (shown in green) in later steps.

G. Hyper-parameter Analysis The primary hyperparameters of DiffTSP include the ratio ρ for splitting graphs into support and query graphs, the number of repeat times Ns , the number of Dit blocks NDit , and the sampling steps. Figure 5 presents the results of DiffTSP while varying these hyperparameters. We observe that a low ratio ρ leads to a slight decrease in the FT SP score but a relatively higher ST Recall. This suggests that providing less support encourages the model to predict a broader range of possible triples. Conversely, an excessively high ratio also negatively impacts the FT SP score, likely because it hinders the model’s ability to complete missing edges comprehensively. DiffTSP demonstrates robustness regarding Ns since its performance remains consistent regardless of the value of Ns . For NDit , we observe that increasing the number of blocks generally leads to improved performance. However, to strike a balance between model efficiency and performance, we set NDit = 3. Despite DiffTSP is built on the DDPM framework, it achieves promising results with a small number of steps. This is because the model benefits from the support graph, rather than reconstructing the graph from scratch. However, as the number of steps increases, there is a slight decrease in the FT SP metric. We attribute this to the accumulation of erroneous edges during the sampling process. This issue becomes more pronounced with additional steps, leading to a decline in prediction accuracy.

H. Case Studies Table VI presents some case studies to compare the predictions of HAKE, AstarNet, and DiffTSP against the “Test Data” (the ground truth). A key observation is the presence of conflicting predictions in HAKE and AstarNet, which are notably absent in DiffTSP. For instance, in Case 1 (Head entity 35), HAKE predicts (35, is brother of, 31) and (35, is sister of, 36). This implies that entity 35 is both a brother and a sister, which is a clear logical contradiction. AstarNet also exhibits a similar pattern for entity 35, predicting (35, is daughter of, 14) and (35, is father of, 106), another type of relational conflict. In contrast, DiffTSP provides consistent predictions for entity 35: (35, is nephew of, 18), (35, is brother of, 31), and (35, is nephew of, 105), aligning well with the “Test Data” and avoiding internal contradictions. These examples highlight DiffTSP’s superior ability to maintain dependency in its predictions. I. Effectiveness Analysis of the Generative Framework To validate the effectiveness of the overall framework of DiffTSP, we also adapt the training and sampling strategies from Repaint [20] to DiffTSP, named as DiffTSP-repaint. The new training phase thus does not use the support-query learning paradigm. Instead, we train DiffTSP-repaint to denoise the entire graph. The forward process gradually adds noise to the graph Ggi rather than the query graph Gq . The loss function for training the denoising network is the same as DiffTSP. This trains DiffTSP-repaint for an unconditional graph reconstruction task, without explicitly teaching it to complete a graph from a support set. During the sampling process, we use the trained denoising network to generate

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

TABLE VI C ASE S TUDIES : * INDICATES A LOGICAL CONTRADICTION WITH OTHER PREDICTIONS FOR THE SAME HEAD ENTITY. HAKE

AstarNet

DiffTSP

Test Data (Ground Truth)

(35, is brother of, 31)* (35, is sister of, 36)*

(35, is daughter of, 14)* (35, is father of, 106)* (35, is nephew of, 105)

(35, is nephew of, 18) (35, is brother of, 31) (35, is nephew of, 105)

(35, is nephew of, 17) (35, is brother of, 31) (35, is nephew of, 105)

(87, is sister of, 88)* (87, is aunt of, 90) (87, is father of, 317) (87, is brother of, 88)*

(87, is sister of, 88)* (87, is son of, 69)* (87, is uncle of, 317) (87, is daughter of, 69)*

(87, is nephew of, 36) (87, is uncle of, 317) (87, is nephew of, 35)

(87, is brother of, 88) (87, is uncle of, 317) (87, is son of, 69)

(2630, is brother of, 2631)* (2630, is sister of, 2629)* (2630, is niece of, 481)

(2630, is sister of, 2631)* (2630, is nephew of, 57) (2630, is brother of, 2631)*

(2630, is nephew of, 147)

(2630, is brother of, 2631) (2630, is nephew of, 57)

(243, is son of, 2984)* (243, is nephew of, 2997) (243, is wife of, 239)*

(243, is wife of, 239)* (243, is son of, 2984)*

(243, is wife of, 239)

new triples, conditioned on the known graph GS . We create a binary mask m from GS to distinguish between known and unknown edges: ( 1 if (vi , rk , vj ) ∈ GS (38) m[i, j, k] = 0 otherwise The known edges are where m = 1, and the unknown edges are where m = 0. For each sampling step from t to t − 1, we perform three operations: First, we use the denoising network to predict the state of the unknown edges of the graph: Gunknown ∼ pθ (Gt−1 |Gt ). t−1

(39)

Next, for the known edges (defined by the support graph GS ), we do not use the model’s prediction. Instead, we re-introduce them by sampling from the forward process. We take the known edges from GS and add t − 1 steps of noise to them, obtaining a noisy graph: S Gknown t−1 ∼ q(Gt−1 |G ).

(40)

Finally, we combine the two parts using a binary mask m derived from GS . The complete graph for the next step Gt−1 is constructed as: unknown Gt−1 = (m ⊙ Gknown ), t−1 ) + ((1 − m) ⊙ Gt−1

(41)

where ⊙ denotes element-wise multiplication. This combined graph Gt−1 then serves as the input for the next sampling step. According to Table VII, DiffTSP-repaint exhibits a performance degradation of approximately 4% on the FT SP metric. This decline is attributed to its training methodology, which directly restores the entire graph without leveraging the support-query learning paradigm. Without using a support graph as a condition during training, the model’s capability to effectively restore incomplete graphs is compromised. J. Efficiency Analytics Figure 6 details the runtime comparison. The runtime for these methods is measured under the same experimental conditions. We specifically select GPHT and AstarNet as representative baselines for this comparison. GPHT is chosen

TABLE VII P ERFORMANCE OF D IFF TSP AND D IFF TSP- REPAINT IN CFAMILY DATASET. Method DiffTSP-repaint DiffTSP

JP recision

CFamily ST Recall

FT SP

0.508 0.675

0.704 0.600

0.590 0.635

as it is the current state-of-the-art method specialized for the TSP task. AstarNet is included as a strong and efficient representative of link prediction models adapted for TSP. The comparison reveals that DiffTSP has a notable efficiency advantage for the TSP task. VII. C ONCLUSION In this work, we treat TSP as a generative task, and propose a novel discrete diffusion model named DiffTSP which could effectively capture the interdependence among the predicted triples. In addition, we design a structure-aware denoising network to combine relation-guided message passing with global structural attention for generating knowledge graphs of high quality. Extensive experiments on multiple datasets showcase the superior performance of DiffTSP compared to strong baselines. ACKNOWLEDGMENTS This work was supported in part by the National Natural Science Foundation of China (No. 62372326). R EFERENCES [1] S. Ji, S. Pan, E. Cambria, P. Marttinen, and S. Y. Philip, “A survey on knowledge graphs: Representation, acquisition, and applications,” IEEE transactions on neural networks and learning systems, vol. 33, no. 2, pp. 494–514, 2021. [2] Y. Liu, Z. Cao, X. Gao, J. Zhang, and R. Yan, “Bridging the space gap: Unifying geometry knowledge graph embedding with optimal transport,” in Proceedings of the ACM Web Conference 2024, 2024, pp. 2128–2137. [3] Y. Wu, Y. Xu, W. Zhang, X. Xu, and Y. Zhang, “Query2gmm: Learning representation with gaussian mixture model for reasoning over knowledge graphs,” in Proceedings of the ACM web conference 2024, 2024, pp. 2149–2158.

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

Predicting Seconds

CFamily

Wiki79k

5532

1680

1500 4000

20 10

1000

2000

0 ) KE rNet fTSP T(HA Asta Dif

GPH

Wiki143k

6000

500

695

72 0 ) E tarNet iffTSP K A s H D A PHT(

135 60 0 ) t P e E S N HAK Astar DiffT PHT(

Fig. 6. The predicting time of different methods on CFamily, Wiki79k, and Wiki143k.

[4] W. Zheng, J. X. Yu, L. Zou, and H. Cheng, “Question answering over knowledge graphs: question understanding via template decomposition,” Proceedings of the VLDB Endowment, vol. 11, no. 11, pp. 1373–1386, 2018. [5] M. Yasunaga, H. Ren, A. Bosselut, P. Liang, and J. Leskovec, “Qa-gnn: Reasoning with language models and knowledge graphs for question answering,” arXiv preprint arXiv:2104.06378, 2021. [6] A. Saxena, A. Kochsiek, and R. Gemulla, “Sequence-to-sequence knowledge graph completion and question answering,” in Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, S. Muresan, P. Nakov, and A. Villavicencio, Eds. Association for Computational Linguistics, 2022, pp. 2814–2828. [7] N. Zhang, Q. Jia, S. Deng, X. Chen, H. Ye, H. Chen, H. Tou, G. Huang, Z. Wang, N. Hua et al., “Alicg: Fine-grained and evolvable conceptual graph construction for semantic search at alibaba,” in Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, 2021, pp. 3895–3905. [8] N. A. Krishnan and C. R. Rivero, “A method for assessing inference patterns captured by embedding models in knowledge graphs,” in Proceedings of the ACM Web Conference 2024, 2024, pp. 2030–2041. [9] H. Chang, J. Ye, A. Lopez-Avila, J. Du, and J. Li, “Path-based explanation for knowledge graph completion,” in Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2024, pp. 231–242. [10] H. Chang, J. Wu, Z. Tao, Y. Ma, X. Huang, and T.-S. Chua, “Integrate temporal graph learning into llm-based temporal knowledge graph model,” arXiv preprint arXiv:2501.11911, 2025. [11] T. Dettmers, P. Minervini, P. Stenetorp, and S. Riedel, “Convolutional 2d knowledge graph embeddings,” in Proceedings of the AAAI conference on artificial intelligence, vol. 32, 2018. [12] Y. Lin, Z. Liu, M. Sun, Y. Liu, and X. Zhu, “Learning entity and relation embeddings for knowledge graph completion,” in Proceedings of the AAAI conference on artificial intelligence, vol. 29, no. 1, 2015. [13] S. Pan, L. Luo, Y. Wang, C. Chen, J. Wang, and X. Wu, “Unifying large language models and knowledge graphs: A roadmap,” IEEE Transactions on Knowledge and Data Engineering, vol. 36, no. 7, pp. 3580–3599, 2024. [14] P. Rosso, D. Yang, N. Ostapuk, and P. Cudré-Mauroux, “Reta: A schema-aware, end-to-end solution for instance completion in knowledge graphs,” in Proceedings of the Web Conference 2021, 2021, pp. 845–856. [15] W. Zhang, Y. Xu, P. Ye, Z. Huang, Z. Xu, J. Chen, J. Z. Pan, and H. Chen, “Start from zero: Triple set prediction for automatic knowledge graph completion,” IEEE Transactions on Knowledge and Data Engineering, vol. 36, no. 11, pp. 7087–7101, 2024. [16] F. Shi, D. Li, X. Wang, B. Li, and X. Wu, “Tgformer: A graph transformer framework for knowledge graph embedding,” IEEE Transactions on Knowledge and Data Engineering, 2024. [17] Y. Yuan, Y. Xu, and W. Zhang, “Is large language model good at triple set prediction? an empirical study,” in 2024 IEEE International Conference on Knowledge Graph (ICKG). IEEE, 2024, pp. 470–476. [18] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” Advances in neural information processing systems, vol. 33, pp. 6840– 6851, 2020. [19] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer, “Highresolution image synthesis with latent diffusion models,” in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2022, pp. 10 684–10 695. [20] A. Lugmayr, M. Danelljan, A. Romero, F. Yu, R. Timofte, and L. Van Gool, “Repaint: Inpainting using denoising diffusion probabilistic

models,” in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2022, pp. 11 461–11 471. [21] S. Nie, F. Zhu, Z. You, X. Zhang, J. Ou, J. Hu, J. Zhou, Y. Lin, J.R. Wen, and C. Li, “Large language diffusion models,” arXiv preprint arXiv:2502.09992, 2025. [22] M. Arriola, A. Gokaslan, J. T. Chiu, Z. Yang, Z. Qi, J. Han, S. S. Sahoo, and V. Kuleshov, “Block diffusion: Interpolating between autoregressive and diffusion language models,” arXiv preprint arXiv:2503.09573, 2025. [23] X. Long, L. Zhuang, A. Li, J. Wei, H. Li, and S. Wang, “Kgdm: A diffusion model to capture multiple relation semantics for knowledge graph embedding,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 8, 2024, pp. 8850–8858. [24] X. Long, L. Zhuang, A. Li, H. Li, and S. Wang, “Fact embedding through diffusion model for knowledge graph completion,” in Proceedings of the ACM Web Conference 2024, 2024, pp. 2020–2029. [25] K. Chen, X. Song, Y. Wang, L. Gao, A. Li, X. Zhao, B. Zhou, and Y. Xie, “Llm-dr: A novel llm-aided diffusion model for rule generation on temporal knowledge graphs,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39, no. 11, 2025, pp. 11 481–11 489. [26] Y. Cao, L. Wang, and L. Huang, “Dpcl-diff: Temporal knowledge graph reasoning based on graph node diffusion model with dual-domain periodic contrastive learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39, no. 14, 2025, pp. 14 806–14 814. [27] Y. Gao, J. Bai, Y. Huang, X. Fu, Q. Sun, and Y. Song, “Unifying deductive and abductive reasoning in knowledge graphs with masked diffusion model,” arXiv preprint arXiv:2510.11462, 2025. [28] J. Wang, W. Li, Y. Shu, J. Guan, Y. Zhang, and S. Zhou, “Raker: A relation-aware knowledge reasoning model for inductive relation prediction,” ACM Transactions on Knowledge Discovery from Data, 2025. [29] A. Bordes, N. Usunier, A. Garcı́a-Durán, J. Weston, and O. Yakhnenko, “Translating embeddings for modeling multi-relational data,” in Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a Meeting Held December 5-8, 2013, Lake Tahoe, Nevada, United States, C. J. C. Burges, L. Bottou, Z. Ghahramani, and K. Q. Weinberger, Eds., 2013, pp. 2787–2795. [30] Z. Sun, Z.-H. Deng, J.-Y. Nie, and J. Tang, “RotatE: Knowledge graph embedding by relational rotation in complex space,” in 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. [31] Z. Zhang, J. Cai, Y. Zhang, and J. Wang, “Learning hierarchy-aware knowledge graph embeddings for link prediction,” in Proceedings of the AAAI conference on artificial intelligence, vol. 34, no. 03, 2020, pp. 3065–3072. [32] L. Chao, J. He, T. Wang, and W. Chu, “Pairre: Knowledge graph embeddings via paired relation vectors,” arXiv preprint arXiv:2011.03798, 2020. [33] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. Van Den Berg, I. Titov, and M. Welling, “Modeling relational data with graph convolutional networks,” in European semantic web conference. Springer, 2018, pp. 593–607. [34] S. Vashishth, S. Sanyal, V. Nitin, and P. Talukdar, “Compositionbased multi-relational graph convolutional networks,” arXiv preprint arXiv:1911.03082, 2019. [35] M. Chen, W. Zhang, Y. Zhu, H. Zhou, Z. Yuan, C. Xu, and H. Chen, “Meta-knowledge transfer for inductive knowledge graph embedding,” in SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Madrid, Spain, July 11 - 15,

JOURNAL OF LATEX CLASS FILES, VOL. 18, NO. 9, SEPTEMBER 2020

2022, E. Amigó, P. Castells, J. Gonzalo, B. Carterette, J. S. Culpepper, and G. Kazai, Eds. ACM, 2022, pp. 927–937. [36] Z. Zhu, X. Yuan, M. Galkin, L.-P. Xhonneux, M. Zhang, M. Gazeau, and J. Tang, “A* net: A scalable path-based reasoning approach for knowledge graphs,” Advances in Neural Information Processing Systems, vol. 36, pp. 59 323–59 336, 2023. [37] M. Galkin, X. Yuan, H. Mostafa, J. Tang, and Z. Zhu, “Towards foundation models for knowledge graph reasoning,” in The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. [38] J. Jo, S. Lee, and S. J. Hwang, “Score-based generative modeling of graphs via the system of stochastic differential equations,” in International conference on machine learning. PMLR, 2022, pp. 10 362– 10 383. [39] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard, “Digress: Discrete denoising diffusion for graph generation,” arXiv preprint arXiv:2209.14734, 2022. [40] G. Liu, J. Xu, T. Luo, and M. Jiang, “Graph diffusion transformers for multi-conditional molecular generation,” Advances in Neural Information Processing Systems, vol. 37, pp. 8065–8092, 2024. [41] W. Peebles and S. Xie, “Scalable diffusion models with transformers,” in Proceedings of the IEEE/CVF international conference on computer vision, 2023, pp. 4195–4205. [42] K. Sohn, H. Lee, and X. Yan, “Learning structured output representation using deep conditional generative models,” Advances in neural information processing systems, vol. 28, 2015. [43] J. Ko, I. Kong, D. Park, and H. J. Kim, “Stochastic conditional diffusion models for robust semantic image synthesis,” arXiv preprint arXiv:2402.16506, 2024. [44] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. Van Den Berg, “Structured denoising diffusion models in discrete state-spaces,” Advances in neural information processing systems, vol. 34, pp. 17 981–17 993, 2021. [45] W. W. Cohen, F. Yang, and K. R. Mazaitis, “Tensorlog: Deep learning meets probabilistic dbs,” arXiv preprint arXiv:1707.05390, 2017.

Wengen Li received the B.Eng. degree and Ph.D. degree in Computer Science from Tongji University, Shanghai, China, in 2011 and 2017, respectively. In addition, he received a dual Ph.D. degree in Computer Science from the Hong Kong Polytechnic University in 2018. He is currently an Associate Professor of the School of Computer Science and Technology at Tongji University. His research interests include multi-modal artificial intelligence, and spatio-temporal intelligence for urban computing and ocean computing. He is a member of China Computer Federation (CCF), a member of IEEE, and a member of ACM. Hanchen Yang received the Bachelor’s degree from Beijing jiaotong University, Beijing, China, in 2020. He is working toward a dual Ph.D. at the Department of Computer Science and Technology, Tongji University and Hong Kong Polytechnic University, Hong Kong, China. Also, he is currently a visiting scholar at the University of Illinois, Chicago. His research interests include spatial-temporal data mining, graph neural networks, and large foundation models. Yichao Zhang received his Ph.D degree in Computer Science and Technology from Tongji University, Shanghai, China. Currently, he is an Associate Professor at the Department of Computer Science and Technology of Tongji University, Shanghai, China. His research interests include information diffusion, link prediction, modelling of weighted networks, random diffusion on weighted networks, and evolutionary games on networks.

VIII. B IOGRAPHY S ECTION

Jihong Guan received the bachelor’s degree from Huazhong Normal University in 1991, the master’s degree from Wuhan Technical University of Surveying and Mapping (merged into Wuhan University since 2000) in 1991, and the PhD degree from Wuhan University in 2002. She is currently a professor in the School of Computer Science and Technology, Tongji University, Shanghai, China. Before joining Tongji University, she served in the Department of Computer, Wuhan Technical University of Surveying and Mapping from 1991 to 1997, as an assistant professor and an associate professor (since August 2000), respectively. She was an associate professor (2000-2003) and a professor (Since 2003) in the School of Computer, Wuhan University. Her research interests include databases, data mining, distributed computing, bioinformatics, and geographic information systems (GIS).

Jiaqi Wang received a bachelor’s degree in Computer Science and Technology with a dual degree in Mathematics from Tongji University, Shanghai, China, in 2022. He is currently pursuing a Ph.D. in Computer Science and Technology at Tongji University, Shanghai, China. His main research interests include knowledge graph and data mining.

Shuigeng Zhou is a professor of School of Computer Science, Fudan University, Shanghai, China. He received his Bachelor degree from Huazhong University of Science and Technology (HUST) in 1988, his Master degree from University of Electronic Science and Technology of China (UESTC) in 1991, and his PhD of Computer Science from Fudan University in 2000. He served in Shanghai Academy of Spaceflight Technology from 1991 to 1997, as an engineer and a senior engineer (since August 1995) respectively. He was a post-doctoral researcher in State Key Lab of Software Engineering, Wuhan University from 2000 to 2002. His research interests include big data management and analysis, artificial intelligence, and bioinformatics. He has published more than 200 papers in domestic and international journals and conferences. Currently, he is a senior member of IEEE and a member of ACM.

Record · ID 120562 · SHA-256 e01a907d59457f62
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.