Probabilistic Reasoning on Knowledge Graphs

KNOWLEDGE GRAPHS & REASONING

Using a knowledge graph without reasoning is like having an inviting cake and leave it there to admire it: aesthetically fascinating but a waste of yummy ingredients and, in the long run, pointless!

Reasoning enables the ‘knowledge part’ of a knowledge graph which, without it, can be viewed more like a database than a knowledge model.

Here’s the difference in a nutshell.

While a relational database has its central point in modeling reality with relations, storing into tables, and querying in SQL a domain of interest, a knowledge graph is more about graph-like data (but not only data as in a graph database).

With a knowledge graph, you can model a reality of interest for which you have graph-like data (the so-called ground extensional component). You can abstractly describe how such reality works, that is: what are the rules of the underlying business, what are the things humans know, but neither programs nor databases do. Finally, through the reasoning process, you can generate new knowledge in the form of new nodes and edges for your graph, namely, the derived extensional component, a.k.a. reasoning component [1].

For a straightforward example of reasoning on knowledge graphs, you can check it out here on Medium.

So far, so good.

But the reality is uncertain, data are uncertain, the domain knowledge is uncertain, and even our human brain inferential processes are, by design, uncertain. Therefore, reasoning needs to include and handle all kinds of uncertainty.

So, if you want to make cutting-edge reasoning on knowledge graphs and if you want a more reasonable and reliable representation of reality and not a kind of robot/puppet version of human reasoning, you need to consider uncertainty and incorporate it in your reasoning.

How to cook probabilistic reasoning on KGs

In probabilistic reasoning with KGs, we need to perform the ‘probabilistic part’ of course. Still, the bad news is that if we want to achieve it wisely, we also need to satisfy at the same time, the standard requirements for reasoning on KGs [2].

We don’t want to be able to, for example, handle null values but not be able to traverse the graph, right? So we need FOUR CRITICAL INGREDIENTS for the basic recipe here:

Full recursion

If you want to explore graph structures, at least, you will expect to traverse these graphs! Of course not only to traverse: you want to explore graph data with a multitude of algorithms, where the extent and the form of the paths are not known a priori.

With graph databases, you may be used to pattern-matching languages like in Neo4J. Here the world is different: knowledge graphs don’t usually do pattern matching, but rely on a way more powerful tool: recursion.

So, I am sorry to inform you that since you want to reason on a kg, you need recursion.

And it must be full, in the sense that we cannot get away with many existing forms of partial recursion, as we want a complete choice of the graph algorithm we can write.

Let’s take a basic graph problem like st-connectivity (the decision problem asking in a directed graph, if t is reachable from s). It is expressible via left recursion. But there are a lot of fundamental but non-trivial problems that are impossible to state, not even with linear recursion. That’s why full recursion is a must.

I think knowing about recursion is never enough, so if you agree with me, also read [[this](https://www.springer.com/gp/book/9783642839542)](https://medium.com/swlh/tree-through-the-eyes-of-recursion-e5c8e19b8e02) or this, or come back to the first year of computer science and reread a brilliant book like this!

2. Induction (no, it is not the recursion again… read also ingredient 2!)

A language, or if you want to be more informal and breezy, a system aiming at reasoning (on knowledge graphs) and that wants to be ready for probabilistic reasoning must be able to express non-ground inductive definitions [3,4].

An inductive definition is a definition given in terms of itself, and it must be sound. There must be one or more non-recursive base cases + one or more recursive cases that eventually lead back to the base case.

Very well-known examples of inductive definitions are the Fibonacci series and the factorial. Probably the plainest example of an inductive definition is transitive closure. If a system can’t even do a non-ground (only with the base case) transitive closure of a binary relation. And it is of the essence for reasoning since:

if a system can’t even work out a transitive closure, you can be sure it won’t help you with reasoning!

3. Semantics

The reasoning process must be traced back to a specific semantic, the ingredient that gives meaning to the intensional component and to query answers.

You have a lot of different choices for semantics at your disposal, in this case, language semantics: stable-model semantics, well-founded semantics, least-model semantics, and all their variants, etc. They offer a more or less efficient reasoning process in terms of performance.

A reasonable choice, in this case, is the use of well-founded semantics.

Let’s take the answer to a conjunctive query. With the stable-model semantics, the construction of the solution needs to consider the facts appearing in all the possible interpretations that satisfy your intensional component and the query. On the contrary, in well-founded semantics, a correct answer to the query contains all the facts of whatever true interpretation. The saving is self-evident in terms of performance.

This and other theoretical underpinnings [5] are such that you can develop faster reasoners using well-founded semantics, and therefore it is a better choice!

4. Ontological reasoning

We’re talking about reasoning ok, but it is a bit vague, which kind of reasoning? I would like to have a powerful version of reasoning, of course, one that allowed me to query my knowledge graph for having unexpected, new, and significant insights!

So, at least we would like to have ontological reasoning that in philosophical terms can be seen as the ability of reasoning ‘on the existing’. While in mathematical terms implies the presence of specific operators like inclusion, universal and existential quantification, etc.

In computer science, ontological reasoning is often made to correspond to the ability of a system to support SPARQL (to query language) under the reasoning rules, known as ‘entailment regime’, of OWL 2 QL profile (a complex of concepts and reasoning rules in a well-known language of the semantic web community).

This ‘profile’ is a kind of toolbox with all the essentials of reasoning: just think that it includes symmetric, reflexive, and irreflexive properties, disjoint properties or, simply define classes and sub-classes.

Ontological reasoning under this profile also offers excellent performance, with a nice trade-off between expressive power and computational complexity; for example, being in the AC0 complexity class when the query is assumed to be fixed.

Preparation:

Photo by Aarón Blanco Tejedor on Unsplash

The four ingredients we just saw are for the basic recipe: reasoning. But for the advanced recipe, probabilistic reasoning, you will need the joint effort of the all ‘fabulous five’. You will need at least another crucial ingredient, THE FIFTH INGREDIENT: now, you must decide how you wish to manage uncertainty.

Scientists have conceived the most different approaches to cope with the most various situations involving imperfect or unknown information: probability theory, fuzzy logic, subjective logic, evidence theory, etc.

If we keep it to the ground and refer to probability theory for uncertainty, what kind of models/systems can we use to perform probabilistic reasoning on KGs?

Well, a lot of people are working on probabilistic reasoning. So many people are involved that there exist at least three main related research areas: probabilistic logic programming, probabilistic programming languages, and statistical relational learning.

It takes me a while just to dive into the different branches of science attempting to this goal. And definitely, a lot of time to truly understand what the heck the state of the art has to offer for probabilistic reasoning on knowledge graphs. And now I can report to you what I’ve found.

PROBABILISTIC LOGIC PROGRAMMING is a group of very nice languages that allows you to define very compact and elegantly simple logic programs. More, they use Sato semantics, a straightforward and compact way to define the semantics.

PROBABILISTIC PROGRAMMING LANGUAGES are elegant because they let you treat all the statistical distributions natively, and this is so attractive and comfortable for statisticians.

STATISTICAL RELATIONAL LEARNING allows us to use Probabilistic Graphical Models like Markov Logic Networks, so all competencies people have in a machine learning environment can be immediately put to use (for example, probabilistic inference in PGM). You can create PGMs that are very close to your reality of interest and model entities and relationships with minimal effort.

All pleasant and positive points and no drawbacks! So, what should I go for?

All these techniques have focused only on the fifth ingredient of the recipe: HOW TO MANAGE UNCERTAINTY. But they almost completely avoid the other four.

In other words, they provided a specific way to cope with uncertainty but without all the other fundamentals features for reasoning on knowledge graphs.

They are not applicable to probabilistic reasoning on knowledge graphs.

It is as if they studied and developed the best masala (the curry powder) for a curry recipe, forgetting the vegetables or the chicken or even the fire sometimes. How can you cook your curry then?

Image: Photo by Enrico Mantegazza on Unsplash

Having noted this, I have tried to provide my contribution to cooking probabilistic knowledge graphs, making an extra effort, studying what is necessary, and going to groceries for all the required ingredients. This is my curry recipe for probabilistic reasoning on knowledge graphs.

I’m eager to listen to yours!

CONCLUSIONS

Without reasoning, knowledge graphs are half-cooked (read more about it here), and handling uncertainly for principled reasoning is paramount. Yet, there are five fundamentals for doing this, the ‘fabulous five’. They are full recursion, induction, semantics, ontological reasoning, and probability theory. More of the existing approaches neglect most of these fabulous five and focus only on one of these ‘ingredients’. Yet some attempts have been made: here there have been used all ‘fabulous five’.

If you want to read more about probabilistic reasoning on knowledge graphs with a real case from the financial intelligence industry: