Towards reasoning over knowledge graphs underaleatoric and epistemic uncertainty
1st Lucie Kunitomo-Jacquin

2nd Ken Fukuda

Université Paris-Saclay, CEA, List
Palaiseau, France
https://orcid.org/0000-0001-8961-3417

National Institute of Advanced Industrial Science and Technology
Tokyo, Japan
https://orcid.org/0000-0001-7366-1094

Abstract—The objective of this short article is to proposea research orientation to address the international Knowledge
Graph Reasoning Challenge (IKGRC). The IKGRC consists insolving mysterious crimes and providing a reasonable explanation
based on open knowledge graphs, which represent the case,background, and characters of some Sherlock Holmes novels.
The suggestion of this paper is to use the framework of thebelief functions, well adapted to the consideration of different
uncertainties and the management of conflicting information.
Index Terms—Knowledge Graph, Belief Functions, Treatmentof Uncertainties

I. I NTRODUCTION
Different types of uncertainty can disturb reasoning overa knowledge graph: a) aleatory uncertainty, i.e., intrinsic tothe hazard of a phenomenon, or b) epistemic uncertainty, i.e.,
resulting from a lack of knowledge or data. Let us note thatconflict between several sources is one possible cause of uncertainty. In the IKGRC1 , epistemic uncertainty can arise fromthe incompleteness of the graph, low granularity or imprecise
statements, like a partial description of the culprit in witness
testimony. On the other hand, aleatoric uncertainty arises whensome statements can be untrue. An adapted framework could
allow us to take greater advantage of information affected byuncertainty.
II. R EASONING UNDER UNCERTAINTY
In the past, several frameworks have been proposed torepresent and deal with uncertainty such as the probability
theory, the imprecise probabilities, the belief function theory,the possibilities, or the fuzzy logic. Some of these frameworks
have been used for reasoning over a knowledge graph. For
example, several works focus on reasoning over Knowledge
graphs in the presence of fuzziness, i.e., variables may be true
to a certain degree comprised in [0,1]. In [1] an approachis proposed to achieve reasoning with general terminological axioms in fuzzy description logic. On another note, [2]provides a logical query embedding framework for answering
complex logical queries on knowledge graphs. In the framework of classical probabilities, [3] presented a Markov logic
network-based approach for reasoning over uncertain temporalknowledge graphs.
1 https://ikgrc.org/2023/index.html

To our knowledge, there is not yet a knowledge graphreasoning approach proposed in the framework of the belief
functions. However, such an approach could allow for jointly
managing both types of uncertainty. Moreover, this framework
has rich literature on the subject of information fusion, andthus allows for possible ways of reasoning in the presence ofconflicting information.
Let us briefly introduce the belief functions theory, also
called Dempster Shafer theory [4], [5]. This theory has beenused in various domains including the semantic web [6], andontology [7]. Due to the additivity constraint inherent to thedefinition of a probability distribution, one cannot build aunique probability distribution when measures, observations,etc. imprecise, i.e., are affected by epistemic uncertainty.
Belief functions theory, as an extension of probability theory,
allows masses to be assigned to imprecise data or sets.
Denoting the universe by Θ, a mass function, also called basic
belief assignment (bba), is a set function m : 2Θ → [0, 1]
satisfyingXm(A) = 1.
(1)
A⊆ΘFor a set A ⊆ Θ, the quantity m(A) is interpreted as
the mass of belief allocated exactly to the set A and not tomore specific subsets of A. Let us illustrates the meaningof a mass function through an example borrowed from [8]originally inspired by [9]. We suppose that a murder has beencommitted and that there are three suspects: Peter, John, andMary. We set then Θ = {P eter, John, M ary}. We further
suppose that a witness has seen the culprit running away. Since
the witness is short-sighted, he could only testify that theculprit is a man (epistemic uncertainty). Moreover, this witness
was drunk at the time which makes this evidence true withreliability 0.8 (aleatoric uncertainty). The evidence provided
by this witness is then represented with the mass function
defined by m1 ({P eter, John}) = 0.8, m1 (Θ) = 0.2. Amass function induces two other set functions that can beused to make inference. First, the belief function Bel : 2Θ →[0, 1], which quantifies the total belief inPA as the sum of
all masses of subsets of A: Bel(A) =B⊆Θ,B⊆A m(B).
Second, the plausibility function of A, P l : 2Θ → [0, 1],
which quantifies P
the maximum mass that could be allocatedto A: P l(A) =B⊆Θ,B∩A̸=∅ m(B).

One of the most important benefits of the framework ofbelief functions is the ability to combine different informationfrom several sources. The most popular combination procedureused in the framework of belief functions is Dempster’scombination (conjunctive combination) which assumes thatall sources of information are independent and reliable andcompletely ignores the conflict between them. In order to combine two mass functions m1 , m2 , the Dempster combination,
denoted ⊕ is defined as follows

if A = ∅,0X
1m1 ⊕m2 (A) =m1 (B)m2 (C) elsewhere,1 − KB∩C=A̸=∅(2)
P
where the K =m(B)m(C)measuresofthe12B∩C=∅
amount of conflict between m1 and m2 . Let us continue theexample from [8]. Now we suppose that a blond hair was
found on the crime scene and that the room was cleaned
before the crime with a probability 0.6. This new pieceof evidence is represented by the following mass function
m2 : m2 ({John, M ary}) = 0.6, m2 (Θ) = 0.4. When
combining the two pieces of evidence with Dempster’s rule,
we obtain m({John}) = 0.48, m({P eter, John}) = 0.32,m({John, M ary}) = 0.12, m(Θ) = 0.08. Let us notethat this combination tightens the mass on the intersections(loss of imprecise information). This combination cantherefore be risky, especially when the degree of conflict isimportant. One other very used masses combination is thedisjunctive combination, which also assumes that the sourcesof information are independent, but which is suitable forsituations where at least one source of information is reliable.
Other combinations have been proposed to meet particularsituations of information sources. Let us cite the conjunctive
combination of Smets [10], the conjunctive combination ofYager [11], the disjunctive combination of Dubois [12] etc.
To benefit from the many modeling and inference tools of
the belief functions framework in the situation where sourcesof information are given by a knowledge graph, we suggest
relying on the basic theory of Uncertain Logic Processing(ULP) presented in [13]. ULP permits the management of
information given in the form of first-order logic formulas
subject to uncertainty, where the uncertainty is expressed in
the belief functions framework. In the same article, the authors
suggest a way to extend the concept of the satisfiability (SAT)
problem into ULP.
The idea for reasoning in the belief functions frameworkover knowledge graphs is the following. First, the relevant
triplets in the graph are extracted and interpreted as uncertain
first-order logic formulas. Then ULP is used to generatemass function assignments based on the uncertain first-orderlogic formulas. To do so, the uncertainty associated witheach formula should be made explicit. To us, capturing thisuncertainty directly from the knowledge graph is still an openquestion. However, one could use external knowledge such as”If the witness knows the person he/she saw, then he/she isright with a probability p” (aleatoric uncertainty). Concerning
the consideration of epistemic uncertainty, we could takeadvantage of an external ontology to capture the level ofprecision of an object or a subject.
One more global idea is to label each triplet with a source
tag like ”testimony of Helen” or ”observation at the scene ofthe crime”. Then, using the belief function framework, identify
which sources, e.g., characters, are the most in conflict withthe others or inconsistent with the facts. The labeling of thesources could be achieved by NLP or machine learning on theoriginal sentences in the novels.
III. C ONCLUSION
The idea presented in this paper is to propose an approachin the framework of belief functions allowing to represent
and manage both aleatoric and epistemic uncertainty whenreasoning on a knowledge graph.
Being able to take into account these two types of uncertainty could be useful to improve the expressiveness ofreasoning models on knowledge graphs. The IKGRC problem
is all the more adapted to this research direction, as it implies
many sources of information to be processed and confronted
to deduce the solution.
R EFERENCES[1] Y. Li, B. Xu, J. Lu, and D. Kang, “Discrete tableau algorithms for fshi,”in Proceedings of the International Workshop on Description Logics(DL), 2006.
[2] X. Chen, Z. Hu, and Y. Sun, “Fuzzy logic based logical query answeringon knowledge graphs,” in Proceedings of the AAAI Conference on
Artificial Intelligence, vol. 36, pp. 3939–3948, 2022.
[3] M. Chekol, G. Pirrò, J. Schoenfisch, and H. Stuckenschmidt, “Marrying
uncertainty and time in knowledge graphs,” in Proceedings of the AAAI
Conference on Artificial Intelligence, vol. 31, 2017.
[4] G. Shafer, A mathematical theory of evidence, vol. 42. Princeton
university press, 1976.
[5] P. Smets and R. Kennes, “The transferable belief model,” Artificial
intelligence, vol. 66, no. 2, pp. 191–234, 1994.
[6] L. Karanikola and I. Karali, “Towards a dempster–shafer fuzzy description logic—handling imprecision in the semantic web,” IEEE Transactions on Fuzzy Systems, vol. 26, no. 5, pp. 3016–3026, 2018.
[7] S. Harispe, A. Imoussaten, F. Trousset, and J. Montmain, “On theconsideration of a bring-to-mind model for computing the information
content of concepts defined into ontologies,” in 2015 IEEE International
Conference on Fuzzy Systems (FUZZ-IEEE), pp. 1–8, IEEE, 2015.
[8] L. Jiao, Q. Pan, T. Denoeux, Y. Liang, and X. Feng, “Belief rule-basedclassification system: Extension of frbcs in belief functions framework,”
Information Sciences, vol. 309, pp. 26–49, 2015.
[9] P. Smets and R. Kennes, “The transferable belief model,” in Classic
Works of the Dempster-Shafer Theory of Belief Functions, pp. 693–736,
Springer, 2008.
[10] P. Smets, “The combination of evidence in the transferable belief model,”IEEE Transactions on pattern analysis and machine intelligence, vol. 12,no. 5, pp. 447–458, 1990.
[11] R. R. Yager, “On the dempster-shafer framework and new combination
rules,” Information sciences, vol. 41, no. 2, pp. 93–137, 1987.
[12] D. Dubois and H. Prade, “Representation and combination of uncertainty with belief functions and possibility measures,” Computational
intelligence, vol. 4, no. 3, pp. 244–264, 1988.
[13] R. C. Núñez, M. N. Murthi, K. Premaratne, M. Scheutz, and O. Bueno,“Uncertain logic processing: logic-based inference and reasoning using
dempster–shafer models,” International Journal of Approximate Reasoning, vol. 95, pp. 1–21, 2018.