=Paper=
{{Paper
|id=Vol-3946/PhDW_paper1
|storemode=property
|title=Robust Knowledge Graph Cleaning
|pdfUrl=https://ceur-ws.org/Vol-3946/PhD-Workshop-1.pdf
|volume=Vol-3946
|authors=Maximilian K. Egger
}}
==Robust Knowledge Graph Cleaning==
https://ceur-ws.org/Vol-3946/PhD-Workshop-1.pdf
Robust Knowledge Graph Cleaning
Maximilian K. Egger1
Supervised by: Davide Mottin1 and Panagiotis Karras1,2
1
Aarhus University, Nordre Ringgade 1, 8000 Aarhus C, Denmark
2
Copenhagen University, Nørregade 10, 1172 Copenhagen, Denmark
Abstract
Data quality is needed to properly and reliably use the information represented in the dataset. The increasing volume of data renders
data preparation and cleaning increasingly difficult. Additionally, more diverse types of data structures for databases, like graphs, get
used and need to be handled differently. This leads to the necessity of robust methods to increase data integrity, scalable approaches for
finding and fixing errors, and local-oriented algorithms that can be used to pinpoint attention where needed. In my PhD project, I focus
mainly on knowledge graph structures and define and establish different tools that can be used to clean the knowledge graphs.
Keywords
Knowledge Graphs, Data Mining, Data Quality
1. Introduction the KG to support the generated answer to the user. If done
correctly, the generated answer will then contain the answer
In today’s data-driven world, information and knowledge from the KG, which is correct, given that the underlying KG
are mined, processed, and used in almost any digital setting. has no error.
With the rise of machine learning and artificial intelligence In all of the mentioned use cases, errors in the results or
in many daily applications, most individuals are affected the knowledge extracted in the KG can result in higher costs
by their reliability and accuracy in their respective tasks. in time and resources.
Therefore, it is essential that the information and data are In my PhD, I explore the notion of robustness as the abil-
factually correct, if available, or as accurate as possible. One ity of a knowledge base to work as intended even in the
framework for interacting and working with such data is presence of incomplete, erroneous, redundant, and inconsis-
Knowledge Graphs (KGs) [1]. A general KG is a network of tent data and accommodate such data in a way that reduces
heterogeneous information of entities that are connected incompleteness and eliminates errors, redundancies, and
with relationships [2]. Entities (nodes) are objects that are inconsistencies. Towards this, I aim to solve the following
either representations from real life, like people or places, or research questions:
abstract concepts. Relations describe the relationships such (RQ1) Is there a measure that provides a prior indication of
objects have with each other. Additionally, there are types the reliability of a KGE on a specific subgraph?
and categories that can be applied to entities and relations. (RQ2) Are there normal forms for graphs that can increase
A complete directed connection between two entities with the data integrity?
a specific relation is called a fact or triple. If nodes and (RQ3) Are there logical rules that can be found and utilized
relations also have properties themself, it is considered a on topic-based subgraphs?
property graph [3]. This paper presents the work done in the first two years of
KGs are applied in different disciplines of research, such my PhD as well as some ideas for my future work. The struc-
as medicine [4], social sciences [5], and drug discovery [6]. ture is as follows. Section 2 covers the related work regard-
In daily life, they are also used when searching the web ing our approaches to support knowledge graph cleaning;
via Google [7], often unbeknownst to the regular user. If Section 3 covers the main contributions; Section 4 presents
there is a box to the right of your search result page, it is future work and challenges; Section 5 concludes the paper.
a response generated by the KG of Google. These panels
provide factual information on the respective search terms.
KGs can be utilized by experts in the domain to query 2. Related Work
for specific information that they require to further their
own research. A current highly relevant use case is the drug Knowledge graph cleaning is the focus of several research
discovery process to save time and money for developing areas. Here, we restrict our focus to the immediate areas
new medicines. In these projects, it is possible to model the regarding my projects from the first two years as well as
benefits and side effects of various drug elements before my planned future work.
synthesizing them in the lab for clinical studies [8]. Knowledge graph embeddings (KGEs) are used com-
Currently, with the rise of interest in generative AI like monly for various tasks, like detecting missing triples, cor-
Chat GPT, Gemini, and Copilot, the generation of factual recting errors, or question answering [10, 11]. There are
incorrect but plausible-sounding information has become a several different KGE types and fitting examples like, Trans-
lot easier; this gives a need for factual correct answers. KGs lational embeddings (TansE [12]), Semantic embeddings (Dist-
are one possible solution to aid LLMs with the framework Mult [13]), Complex embeddings (ComplEx [14]) and Neural-
of retrieval augmented generation (RAG)[9]. This process network embeddings (ConvE [15]).
allows the respective LLM to query for a factual answer in Evaluation of embeddings is mainly done with ranking-
based measures, in particular with HITS@k and mean recip-
Published in the Proceedings of the Workshops of the EDBT/ICDT 2025 rocal rank (MRR) for head, tail, and relation prediction [10,
Joint Conference (March 25-28, 2025), Barcelona, Spain 16, 17]. These measures indicate performance globally, but
Envelope-Open maximilian.egger@cs.au.dk (M. K. Egger) so far, no measure provides local analysis capabilities.
Orcid 0009-0001-4473-4984 (M. K. Egger)
© 2025 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0
International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Italy in Italy Italy
ed
at
ed
in
loc
t
rn
in
pa
bo
located in
painted
born in
pai Leonardo
Leonardo Leonardo nte
bor d da Vinci
da Vinci da Vinci n in
loca bo
pa bo ted rn born in
in rn in
in
lo
located in
lo
t
Mona painted
ca
ed
ca
Mona in Mona
te
France
te
France France
d
d
Lisa Lisa
in
Lisa
in
located in
KG and considered edge Negative triples 𝒩 − (ℎ) Negative triples 𝒩 − (𝑡)
to compute rank 𝐻 to compute rank 𝑇
Figure 1: Constituents of ReliK on an example KG.
Functional dependencies (FDs) define directed relation- These scores are only used to create a ranking that is fed
ships between attributes in the data. Therefore they are into our measure.
used as blocks to construct keys and normal forms [18]. Specifically, two rankings are used to get the value for a
Similarly, FDs tailored to graph models are pairs of a graph triple. Figure 1 shows what is considered to be part of the re-
pattern and an implication [19, 20, 21]. spective ranking. Namely, the two negative neighborhoods
Data normalization uses normal forms (NF) to reduce data that are used to measure the triple against. The negative
redundancies in the chosen representation, like first, second, neighborhood aimed at the head (ℎ) part of the triple con-
third, and BC normal form [18] for relational databases. sists of all triples with the form (ℎ, ?, ?) that are not part
BCNF has been extended towards XML documents and their of the original KG. For the tail (𝑡), this is done in a similar
underlying tree structure [22, 23, 24] as a first step toward manner. Then, the embedding score for the neighborhoods
general graphs. A recent attempt at graph normalization and the correct triple 𝑥ℎ𝑟𝑡 is evaluated, and the ranking is
has been made that uses uniqueness constraints [25] and established. This gets put into the following formula to
graph-tailored functional dependencies [26] that target node constitute the ReliK score.
properties. This leaves a gap of NFs that handle all parts of
1 1 1
a graph and are not zoned in on the node level. ReliK(𝑥ℎ𝑟𝑡 ) = ( + ).
Rule mining in KGs finds logic rules that can be used to 2 rank 𝐻 (𝑥ℎ𝑟𝑡 ) rank 𝑇 (𝑥ℎ𝑟𝑡 )
find and fill in missing information throughout the data [27, This can also be extended to a subgraph level by taking
28]. These also provide human-readable statements that the mean of the respective ReliK scores for all triples in the
can be used for the reasoning process to fill in the graph. subgraph.
These rules are evaluated and constructed from a global Consequently, ReliK is agnostic to (1) the specific charac-
perspective, which could lead to topic-specific rules being teristics of a given KGE, (2) the particular KG in question,
overlooked that are still relevant and valid in their respective and (3) does not require any KGE retraining. Furthermore,
contexts. (4) ReliK is task-agnostic: its design principles are so broad
that it is naturally suited for a wide range of downstream
tasks for more details. Finally, (5) ReliK possesses the local-
3. Contributions ity property, allowing its computation and semantics to be
Here, we first discuss our completed work on reliability tailored to specific parts of the KG. Overall, our ReliK mea-
in knowledge graph embeddings and then introduce our sure fully meets all the aforementioned criteria. It is also
current endeavors on normal forms for graphs. In the initial important to note that ReliK can be utilized to evaluate the
project ReliK, we defined and evaluated a new metric for effectiveness of a KGE for a downstream task, even when
the local reliability of KGEs. In the second project, which is we only have access to the embeddings for privacy or other
in the process of being submitted, we looked into property reasons, rather than the original KG.
graphs and established normal forms for them to reduce ReliK is simple, intuitive, and easy to implement. Despite
data redundancy. that, its exact computation requires processing all the pos-
sible combinations of entities and relationships for every
single fact of interest. Therefore, we also introduced two
3.1. ReliK approximations to calculate a good estimate of the exact
KGEs are heavily used for a variety of downstream tasks ReliK for large KGs. One of them is a good approximation
that rely on the underlying KG being complete and the KGE in expectation, while the other is a strict lower bound of the
being well trained. Their evaluation so far has only been original ReliK if this is needed for theoretical guarantees.
done on a global scale with their respective tasks in mind. To showcase that both of these approximations work as
Therefore, an open problem is a more general metric that can expected, we present both runtime and MSE for a small
indicate behavior independent of the application while also dataset in which the calculation of the accurate ReliK is
being unprejudiced towards the chosen embedding model feasible.
or the underlying data. To verify our metric and its approximations, we have
These issues can be addressed by our measure ReliK [29], conducted an extensive study in which we evaluate against
which is a straightforward yet principled approach that measures like MRR for tail, relation, and triple classification,
assesses the reliability of a KGE’s performance on a specific as well as more complicated tasks with query answering
downstream task within a particular section of the KG, all and rule mining.
without executing the task or (re)training the KGE. ReliK The results of the experiments support that ReliK corre-
only relies on the existing embedding scores as a black box. lates with the accuracy of the prediction and classification
tasks, which provides deeper insight into the reliability of
p2: Paper
attributes directly dependent on a superkey; EGNF removes
e2: published
c2: Conference all value duplication by enforcing that every property is a
title: “Normal Forms”
venue: “SIGMOD”
year: 2024 key.
name: “SIGMOD’24” e3: published We provide algorithms that transform any property graph
publisher: “ACM”
city: “Los Angeles” into its respective GNF versions without losing any infor-
country: “USA”
mation that may be stored in the database. One example of
p3: Paper
how a graph not in 2GNF can be transformed into one can
title: “Schema”
year: 2024 be seen in Figure 2. In this small example, the attribute year
from paper nodes can be connected to the name of confer-
Q0 FD1 : Q0, {?x.name } → { ?y.year } ence nodes with the GFD FD1, which states that the publish
year of a paper is determined by the name of the conference
?x: Conference ?u: published ?y: Paper it was published in. This is a violation of the 2GNF, and in
venue: ?x.venue year: ?y.year order to remove the violation, the attribute year is moved
name: ?x.name
into the conference node. When done for all conference and
paper nodes, this reduces possible redundancy throughout
the graph and preserves information. It should be noted
p2: Paper that to query for the same piece of information, a different
e2: published
c2: Conference title: “Normal Forms”
query is needed between the original snippet and the 2GNF
venue: “SIGMOD” version of it.
name: “SIGMOD’24”
publisher: “ACM”
e3: published To show that our established GNFs do reduce data re-
city: “Los Angeles” dundancy, we perform experiments in which we count the
country: “USA”
year: 2024 p3: Paper total number of attribute values in a selection of datasets,
perform the transformations into the GNFs, and then count
Q1 title: “Schema”
in the transformed datasets. The number of attribute values
is getting lower as more GNFs are applied, thus showing
?x: Conference
that GNFs are able to increase the data integrity by reducing
venue: ?x.venue
name: ?x.name FD1’: Q1, {?x.name } → { ?x.year } redundancy in graphs. The process of transforming into
year: ?x.year the different GNFs incurs the addition of new edges and
nodes to the dataset to facilitate the changes needed for the
consolidation of information.
Figure 2: Fragments of graph satisfying 1GNF and 2GNF, with
associated patterns and GFDs.
4. Future Work
The next avenue to look into for graph cleaning for my
KGEs. Especially ReliK is able to differentiate between the PhD project is rule mining. Specifically, the problem of
correct and incorrect rule instances for complex logical rules contextual rule mining is about the possibility of rules hav-
as well as guiding the rule mining in subgraphs towards ing context and a local neighborhood of validity. So far
high-confidence rules. rule mining has been nearly exclusively done on a global
scale [27, 30, 28, 31, 32], this could lead to topic-specific
3.2. Graph normal forms rules to be overlooked in the process. Additionally focusing
on a specific area of a KG to mine rules opens up the chance
Graph databases like property graphs do have sources of
of generating higher complexity rules and structures.
redundancies like any database can have. This issue can be
Just selecting random subgraphs probably does not suf-
resolved in relational databases or XML files via the concept
fice. Such subgraphs should capture different contexts like
of normal forms (NF) and a process to transform the original
domain, temporal, or geographical areas. Therefore a new
data into that format.
method, similar to community detection, will be needed to
For graph databases, this does not exist in the same format
avoid human-heavy annotation of datasets. Especially since
yet. Still, the foundations like graph functional dependen-
topic areas will not necessarily be strongly connected to
cies [19, 20, 21] and a first attempt that focuses on nodes
communities in KGs.
have been made [26].
Another challenge is guaranteeing significance and sta-
In our project, we establish a set of five graph normal
tistical support for the rules based on a smaller search space.
forms (GNF) that use and build on top of these ideas by con-
Here, the absolute support of a rule in a subgraph will be at
sidering the complete graph in its structure. The process of
most equal to the global setting, which leads to a trade off
utilizing edges and their properties cannot be done trivially
between subgraph size and statistical significance.
from the NFs of the relational setting.
To motivate the validity of contextual rule mining, we
To define the GNFs, we use graph functional dependen-
report some preliminary experiments on a subset of the Free-
cies (GFDs) that consist of a pattern and a one-way depen-
base dataset that has six annotated domains in the graph1 .
dency between two sets of attributes. An example of such
In Table 1 we see some results of applying the rule mining
can be seen in Figure 2.
method AMIE [27] on both the complete set as well as ex-
1GNF disallows implicit links between nodes that could
clusively the respective domains. In three of these topic
be represented by regular edges and nested attributes that
area subgraphs we were able to find rules that are not found
hide data complexity. Increasing from there, the 2GNF for-
and presented in the entire set of these six domains. This
bids the replication of attribute values that are dependent on
observation supports the claim that these kinds of rules
the key of a different node; 3GNF disallows partial depen-
dencies from a key towards attributes; 4GNF only allows 1
https://people.cs.aau.dk/~matteo/notes/freebase-data-dump.html
Domain Triples Rules Dom. specific vey of approaches and applications, TKDE 29 (2017)
complete 4302875 1636 - 2724–2743.
organization 1767483 106 0 [11] S. Ji et al., A survey on knowledge graphs: Represen-
government 613575 405 17 tation, acquisition, and applications, Trans. Neural
military 260973 68 4 Netw. Learn. Syst. 33 (2021) 494–514.
business 1408406 758 11 [12] A. Bordes et al., Translating embeddings for modeling
geography 139900 5 0 multi-relational data, NeurIPS 26 (2013).
finance 112538 66 0 [13] B. Yang et al., Embedding entities and relations for
Table 1 learning and inference in knowledge bases, in: ICLR,
Domain details in size and number of mined rules 2015.
[14] T. Trouillon et al., Complex embeddings for simple
exist in KGs. Further investigation of the relevance and link prediction, in: ICML, PMLR, 2016, pp. 2071–2080.
significance of rules found in this approach is needed as [15] T. Dettmers et al., Convolutional 2d knowledge graph
to how to apply this concept on datasets that do not have embeddings, in: AAAI, volume 32, 2018.
domains pre-labeled. [16] T. Safavi et al., Evaluating the calibration of knowledge
graph embeddings for trustworthy link prediction, in:
EMNLP, 2020.
5. Conclusion [17] F. Bianchi et al., Knowledge graph embeddings and
In my PhD, I study the notion of robustness in knowledge explainable ai, in: Knowledge Graphs for eXplainable
bases. Towards this I investigate the reliability of knowledge Artificial Intelligence: Foundations, Applications and
graph embeddings, eliminating redundancies in graphs, and Challenges, IOS Press, 2020, pp. 49–72.
contextual rule mining. [18] E. F. Codd, Further normalization of the data base
Specifically, ReliK (1) gives the possibility of verifying relational model, Data base systems 6 (1972) 33–64.
which areas of knowledge graph embedding can and should [19] W. Fan et al., Functional Dependencies for Graphs, in:
be used in the cleaning and knowledge completion process. SIGMOD, 2016, pp. 1843–1857.
Enforced by an intuitive metric that can be applied indepen- [20] W. Fan et al., Capturing associations in graphs, VLDB
dent of model choice. Graph normal forms (2) provide the (2020) 1863–1876.
needed reduction in data redundancy that increases data [21] W. Fan et al., Discovering association rules from big
integrity, as well as giving a standardized way to normalize graphs, VLDB (2022) 1479–1492.
the data. Finally, I present locally aware rules (3) as a future [22] M. Arenas et al., A normal form for xml documents,
project that can be used to get topic-specific rules, which TODS (2004) 195–232.
can be further used to establish correctness in applicable [23] M. Arenas et al., An information-theoretic approach
subgraphs in a nuanced approach. to normal forms for relational and xml data, JACM
(2005) 246–283.
[24] M. Arenas, Normalization theory for XML, SIGMOD
References (2006) 57–64.
[25] P. Skavantzos et al., Uniqueness constraints on prop-
[1] A. Tchechmedjiev et al., Claimskg: A knowledge graph erty graphs, in: International Conference on Ad-
of fact-checked claims, in: In The Semantic Web– vanced Information Systems Engineering, Springer,
ISWC, Springer, 2019, pp. 309–324. 2021, pp. 280–295.
[2] C. Shi et al, A survey of heterogeneous information [26] P. Skavantzos et al., Normalizing Property Graphs,
network analysis, TKDE 29 (2016) 17–37. Proceedings of the VLDB Endowment 16 (2023)
[3] R. Angles et al., Pg-schema: Schemas for property 3031–3043.
graphs, Proceedings of the ACM on Management of [27] L. A. Galárraga et al., AMIE: association rule mining
Data (2023) 1–25. under incomplete evidence in ontological knowledge
[4] L. Li et al., Real-world data medical knowledge graph: bases, in: TheWebConf, 2013, pp. 413–422.
construction and applications, Artificial intelligence [28] L. Wu et al., Rule learning over knowledge graphs
in medicine 103 (2020) 101817. with genetic logic programming, in: 2022 IEEE 38th
[5] M. Conti et al., A model to represent human social International Conference on Data Engineering (ICDE),
relationships in social network graphs, SocInfo, pages IEEE, 2022, pp. 3373–3385.
174–187 (2012). [29] M. K. Egger et al., Relik: A reliability measure for
[6] F. MacLean, Knowledge graphs and their applications knowledge graph embeddings, in: ACM Web Confer-
in drug discovery, Expert opinion on drug discovery ence, 2024, p. 2009–2019.
16 (2021) 1057–1069. [30] L. Galárraga et al., Fast rule mining in ontological
[7] H. Paulheim, Knowledge graph refinement: A survey knowledge bases with amie ++, VLDBJ 24 (2015)
of approaches and evaluation methods, Semantic web 707–730.
8 (2017) 489–508. [31] S. Ortona et al., Rudik: Rule discovery in knowledge
[8] X. Zeng et al., Toward better drug discovery with bases, VLDB (2018) 1946–1949.
knowledge graph, Current opinion in structural biol- [32] N. Ahmadi et al., Mining expressive rules in knowledge
ogy 72 (2022) 114–126. graphs, JDIQ (2020) 1–27.
[9] P. Lewis et al., Retrieval-augmented generation for
knowledge-intensive nlp tasks, Advances in Neural
Information Processing Systems 33 (2020) 9459–9474.
[10] Q. Wang et al., Knowledge graph embedding: A sur-