Organizations: LIPADE, Université Paris Cité, Paris, France · Qatar Computing Research Institute, HBKU, Doha, Qatar · Universität zu Lübeck, Germany · TU Bergakademie Freiberg, Germany · Université de Toulouse, IRIT, France · IPAL-CNRS, Singapore
Knowledge Graphs (KGs) are widely used to represent structured knowledge, yet their automatic construction, especially with Large Language Models (LLMs), often results in incomplete or noisy outputs. Knowledge Graph Completion (KGC) aims to infer and add missing triples, but most existing methods either rely on structural embeddings that overlook semantics or language models that ignore the graph's structure and depend on external sources. In this work, we present OMNIA, a two-stage approach that bridges structural and semantic reasoning for KGC. It first generates candidate triples by clustering semantically related entities and relations within the KG, then validates them through lightweight embedding filtering followed by LLM-based semantic validation. OMNIA performs on the internal KG, without external sources, and specifically targets implicit semantics that are most frequent in LLM-generated graphs. Extensive experiments on multiple datasets demonstrate that OMNIA significantly improves F1-score compared to traditional embedding-based models. These results highlight OMNIA's effectiveness and efficiency, as its clustering and filtering stages reduce both search space and validation cost while maintaining high-quality completion.
Figures & tables
Fig. 1 : Example of a missing triple in a LLM-generated knowledge graph.
Fig. 2 : Example of the Clustering-based triple candidate generation.
Fig. 3 : Overview of OMNIA with its two main steps
Fig. 4 : Example of Entity Clustering
Fig. 5 : Triple-based scenario with its three prompting cases for LLM-based validation
Dataset
Relations
Entities
Triples
Socio-economic
17,175
33,563
64,417
CoDEx-M
49
16,759
60,000
FB15K-237
29
12,993
59,270
WN18RR
11
40,943
93,003
Covid-Fact
28
1416
908
TABLE I : Statistics of the datasets used in our experiments
dataset
UE_O
UE_G
UR_O
UR_G
nb_candidates
nb_missings
TP
nb_miss_brut
nb_gen_brut
CoDEx-M
16759
16431
49
48
9047869
11996
70.65%
95.98%
12958932528
Socio-economic
33563
29860
17175
14710
6494589
12347
9.6%
55.76%
13115724316000
FB15K237
12993
12610
29
29
4885007
11854
49.08%
96.12%
4611350900
TABLE II : Comparison of dataset statistics and generation performance. U: unique , E: entities , R: relations , O: original dataset size, G: Left for generation , TP_OMNIA: % of missing triples successfully generated by OMNIA, TP_brut:% of missing triples successfully generated by an exhaustive search, gen_brut: Total number of candidate triples generated by exhaustive search.
Dataset
Red. Ratio
Missing
TC
TCF
CoDEx-M
71.08%
11997
8476
5024
Socio-economic
70%
12347
1186
607
FB15K237
41.76%
11854
5818
3836
TABLE III : Filtering performance over different datasets
Category
Model
FB15k-237
CoDEx-M
WN18RR
Socio-Economic
KGE
TransE
0.74
0.682
0.68
0.72
DistMult
0.6709
0.674
0.77
0.737
ComplEx
0.6661
0.665
0.67
0.66
RotatE
0.7285
0.662
0.75
0.717
PLM-based
KG-Bert
0.57
0.542
0.62
0.727
LLM-based
MuKDC
0.192
0.273
0.229
0.224
TABLE IV: Performance (F1-score) comparison of OMNIA against baselines across four datasets. Bold indicates the best per dataset; underlined indicates the second-best. OMNIA (with its different variants) performs the best across all datasets with a big margin (12 percentage points for FB15k-237, 23.6 for CoDEx-M, and 10 for WN18RR) except ”Socio-Economic”, where it ranks third.
Method
Valid trans.
Valid trans. ratio
Simple prompt
462
0.92
Explicit prompt
500
1
TABLE V : Results of simple and explicit prompts for sentence transformation on 500 candidates triples from CoDEx-M dataset
Fig. 6 : Scores for different top-K on FB15K-237, WN18RR, CoDEx-M and Socio-economic
OMNIA’s step
Sample Size (in thousands)
10
20
30
40
50
Candidate generation
6.08
26.47
72.42
160.24
304.83
Embedding filtering
13.59
15.16
19.47
24.30
30.53
TABLE VI : Average execution time (in seconds) of each step across different sample sizes (in thousands).
LLM Scenario
Sample Size
50
100
250
500
Triple-based Evaluation
Zero-shot
85.18
181.87
532.52
1014.35
In-context
138.59
264.61
672.2
1481.35
RAG
567.76
687.24
987.33
1489.83
Sentence-based Evaluation
TABLE VII : Average execution time (in seconds) of LLM-based evaluation for different sample sizes.