So, uh, welcome, everyone, to the class.
Uh, today, we are going to discuss about, uh,
reasoning in knowledge graphs, uh, using embeddings.
So, um, what we learned,
uh, last week was that, uh,
we discussed knowledge graphs, and in particular,
we defined the notion of a knowledge graph as a,
uh, set of, uh,
nodes and a set of relations between them where, uh,
nodes can have, uh,
different types and also, uh,
relationships, uh, can have different types.
Um, and then we have defined, uh, a task,
uh, we call the knowledge graph completion task.
We're basically given an enormous knowledge graph.
The question is, can we complete it?
Can we predict, infer, uh,
missing, uh, relationships, uh, in the graph?
So for a given head and,
uh, for a given relation,
uh, we wanted to predict missing tails, right?
So basically, for example, we would want to, uh,
predict the genre that a particular author is writing,
uh, books about based on the rest of the structure,
uh, of the knowledge graph.
So what do we are going to do today is we are going to take this idea of,
uh, knowledge graphs, um,
and knowledge graph completion,
but we are going to generalize it and extend it to, uh,
more, uh, interesting and a more,
uh, challenging setting where basically,
what we will be doing is we are going to perform multi-hop reasoning,
um, and logical reasoning in these knowledge graphs, uh, using embeddings.
So the goal is to reason in knowledge graphs and what-
by mean- by reason is to be able to answer, uh,
multi-hop queries or in some sense,
to make complex predictions in these, uh,
knowledge graphs for arbitrary predictive queries.
Um, and we are going to talk about, uh, two approaches.
One will be how do we handle what is called path queries,
and the other one will be about talking about
conjunctive queries and a method called, uh, Query2box.
Um, and in all these cases, basically,
the idea will be how do we embed the knowledge graph?
How do we embed the relations such that we can reason and navigate,
and move around, uh,
in this, uh, in this- in this space.
Uh, that's essentially the idea.
So, um, for the rest of the lecture,
I'm going to use this simple, um,
biomedical knowledge graph that includes,
uh, the following, uh- uh,
four types of entities.
If we will have nodes for, uh, different, uh,
drugs, we are going to have nodes,
uh, for different diseases,
we are going also to have some kind of adverse events or let's say- let's say,
side effects, uh, that these diseases can cause,
and then we'll also have nodes corresponding to proteins,
um, and, uh, that are- that are in,
uh, in our bodies and basically,
proteins that regulate and are part of various kinds of biological processes,
uh, taking, uh, part in our bodies and in our, uh, cells.
So now, let's say we have this kind of miniature, uh,
knowledge graph or a small part of the knowledge graph, uh,
that basically captures how these different entities,
uh, are related, uh,
to each other and then the question would be,
can we answer interesting questions,
uh, over this knowledge graph?
So, uh, to give you, uh,
an example- for example, the question is,
how could I answer complex queries or how would I be able to make
complex predictions over incomplete and massive, uh, knowledge graphs,
and just to give you, uh,
a few examples, um,
you know, you could say what,
uh, adverse event is caused, uh,
by a drug, uh, Ful- Fulvestrant, right?
And the way you could say this is to say, "Hi,
I want to start with the entity Fulvestrant and I want a traverse relationship cause,
and I want to predict what is on the other end of the- uh,
of this- uh, um, uh, Fulvestrant-caused relation."
Uh, and this is in some sense, a one-hop query.
It's basically a knowledge graph completion-type task.
I could then also do path queries where, for example, I could say,
what protein is associated with an adverse event caused by, uh, Fulvestrant, right?
So in this case, I would say,
I want to start with entity Fulvestrant,
I need to traverse over causes relation,
and then I need to cause, uh,
traverse over a associated relation.
Whatever entity is at the end of this,
that is the answer to my, uh, question,
to my query and then we can also ask more complex queries,
uh, where we can also have various logical relations between them.
For example, I could ask,
what is the drug that treats breast cancer,
uh, and, uh, causes headache?
So I could say, uh, you know, uh,
breast cancer- I start with an entity breast cancer.
I say, uh, treated by,
so this is now the drugs treated by
breast cancer and I also want to take a migraine and say,
what are the drugs that cause, uh, migraine,
and then whatever drug, uh,
causes both, um, that's the- uh,
that's the answer to my question.
So, you know, you can write these questions in natural language,
you can write them in this kind of,
um, uh, formula, but you can also write them in terms of the rec- graph structure, right?
So in- in a sense that one-hop query says start with
an entity and make a step along a relation,
path queries say start with- start with an entity,
make a step along one relation,
and then make a step a- along the other relation like causes
and associated, and what does this say is, it
says start with breast cancer and move across the
treated by, and start with migraine and move across,
uh, the relation caused by and whatever you end up- whatever entity you end up with,
uh, that's the answer, uh, to your question.
So you can see how we can basically take this- uh,
let's say, uh, questions,
queries, write them in natural language,
write them in the- let's say,
this kind of logical formula or write them in this type of,
uh, graphical structure, uh, form.
Uh, of course, today,
we are not going to address how do we get from natural language to the formula,
we are only going to kind of discuss once you have the formula,
once you have this logical structure,
this graphical structure, how do you answer, uh, a query?
And an important point over here will be that this-
this- we want to be able to answer these queries over incomplete knowledge graphs.
So it won't be only that we say,
oh, just traverse the relation.
It will be like, the relation is missing,
you have to predict it.
And it will- it can be chains of relations that are missing,
or are not in the knowledge graph,
and we still want to be answered- uh,
able to answer these questions.
So, um, you know,
first, let's talk about one-hop queries.
We already know how to, uh, uh,
answer them because we can formulate
graph completion problems as answering one-hop, uh, queries, right?
In a- in a knowledge graph completion, basically,
what we need to be able to estimate is to say,
is there a link between a head and a tail of relation-type, uh, r?
So this is essentially the same as saying,
is there- is there an answer to the query start
with the head and move along the relation, uh, r?
So, for example, what side effects,
uh, are caused by drug Fulvestrant, right?
In this case, I start with drug Fulvestrant.
This is my h. Uh, r is the- um,
caused by- uh, and now,
I want to basically say, is this particular entity the nth
point of Fulvestrant and, uh, caused by?
So that's, uh, how basically answering
one-hop queries like simple link prediction queries is,
uh, knowledge graph completion.
Now, we can talk about how about answering path queries, right?
We want to generalize this to basically being able to chain multiple relations,
uh, one after the other, right?
So we can say that we have an n-hop path query q that is represented by a- uh,
what is called an anchor node, uh, starting entity,
and then a sequence of relations,
r-1, uh, all the way to r-n, right?
So v is- uh,
v_a is an anchor node,
this is a fixed entity like, uh,
Fulvestrant, as we talked about,
and then answers, uh,
to the query will be denoted in this notation.
So basically, um, I have these kind of double braces so whatever is- uh,
whatever elements I write in here,
these are the answers,
uh, to the, uh,
query q on a knowledge graph G. So the way we could write this in
a graphical form into this kind- in something
we are going to call query plan is basically,
we start with the entity, uh, v_a,
and then we want to traverse our relationship type 1 and the relationship type 2,
all the way across the n relationships, and whatever entities are at the end of this,
um, we are making,
uh, uh, a prediction that this is the correct answer.
So that's a notion of a path query.
Um, to give you an example,
I could ask what proteins that are associated with
adverse ev- events caused by Fulvestrant, right?
So if I write this, then I say,
Fulvestrant is my anchor entity,
my r_1 and r_2 are relation causes and associated.
So my query will be started with Fulvestrant,
go across the causes relation,
and go across an associated relation, right?
So here is my, uh, Fulvestrant.
I want to first go over the green, uh-
The green links, uh,
saying, uh, uh, uh, you know,
what is- uh, what causes, this would be the re- the re- the red links, uh, apologies.
And then from here, I wanna then,
uh, traverse over, uh, uh,
the second part of li- link associated to arrive,
uh, at a given, uh, protein.
So that would basically be the idea for,
uh, path queries, right?
So to answer- to give you an example again,
so how do I ans- how do I find the answer now?
Basically the way I find the answer is that, conceptually,
if- if the knowledge graph is complete,
I simply need to, uh,
traverse it according to this query plan.
So the idea is I start with Fulvestrant.
I- I traverse over causes relations to get to all the side effects,
uh, caused by, uh, this drug,
like headaches and, you know,
brain bleeding, and shortness of breath,
and kidney infection, and so on,
so, kind of, quite serious side effects.
And now that I have this set of entities,
now I need to traverse from them according to associated relation.
And you know why I traverse the edges,
and whatever proteins I end up with,
those are the answers,
uh, to my query.
So, uh, these are the answers to the- to the query about,
you know, what are proteins associated with
adverse events caused by the drug, uh, Fulvestrant?
So that's, uh, basically the, um,
idea how now I can formulate and
answer path-based queries directly on the knowledge graph,
assuming knowledge graph contains,
uh, all the information.
Of course, um, in some sense, this seemed easy, right?
It's just answering queries, seems easy.
You just traverse the knowledge graph according to this plan.
Uh, but the problem is that knowledge graphs are notoriously incomplete, right?
Many relations between entities are missing or are, uh, incomplete.
Uh, for example, we lack a lot of biomedical knowledge, and, you know,
kind of enumerating all facts,
uh, testing all possible side effects,
all possible associations in these graphs,
is too costly and would take far too much time,
and perhaps we will never be able to obtain the entire knowledge, uh, about biomedicine.
So the question then is,
if these graphs are notoriously incomplete, um,
right, we cannot simply hope to traverse them,
um, to get the answers, right?
So the question then is, uh, what do we do?
Um, to give you an example, right,
if I'm missing, perhaps, uh,
a relationship causes by because it's not yet known
that Fulvestrant also causes shortness of breath,
then, for example, if I'm not able to traverse this edge, then, you know, uh,
the li- there is no way for me to discover that, uh, BIRC2,
the- uh, the protein,
is actually an answer to my query, right?
Uh, I would be able to say that the CASP8 is, uh,
is an answer because I go over,
uh, brain leading to get to it.
I know that, uh, PIM1 is also,
uh, an answer because of this path through the kidney infection,
but there is no way for me to find out that this, uh,
BIRC2 protein is also the answer, uh, to my query.
So that's the problem.
So what you could do is to say,
uh, I, actually, you know,
listened previous lecture and I remember we talked about knowledge graph completion.
So let's just go and apply, uh,
knowledge graph completion so that now the graph will be complete,
and then we can simply, uh, traverse it.
The problem is that,
if you do this, then, um,
you don't know how many edges are really missing in the knowledge graph.
So you could basically go and apply your knowledge graph completion,
uh, approach to all possible,
uh, edges of the graph.
So it means that you would wanna take, for,
uh, every triple i- in the knowledge graph,
you'd wanna s- ask your pre- uh,
knowledge comple- knowledge graph completion engine to
assign a probability that that link, um, is true.
Um, the problem then will be that, now,
your graph just got a whole lot of new- this kind of probabilistic links,
and now the graph is getting denser and knowledge graph, uh,
completion or traversal, uh,
will get very expensive because,
if you think about, you know,
starting at an entity, alo- uh,
moving along a given relation,
and then, uh, getting to a set of nodes,
moving to the next relation,
uh, to a new set of nodes,
this will explode exponentially with the length of the query, right?
So with the query length is, let's say,
capital L, then if,
at every step, you have some,
um, uh, non-trivial expansion,
some non- non-trivial number of- um,
of, uh, uh, nodes that are as- that, uh,
al- that allow you to traverse to- uh,
along a given relation,
then this is going to, uh,
increase exponentially in the query length.
And, uh, having big queries,
this becomes computationally quite hard to do,
uh, over, uh, a massive, uh, knowledge graph,
especially if you think about that we have just added
a lot of new edges with different probabilities, uh,
and we nin- we need to keep track over these probabilistic imputing edges as well,
this becomes, uh, a very hard, uh, computational task.
So, uh, here is the idea how we are going to do this and formulate it.
And the way we are going to talk about this is we
are going to call it predictive queries.
And the idea is, right,
we need a way to answer
path-based- path-based queries over an incomplete, uh, knowledge graph.
Um, and we want our approach to implicitly impute
and account for the incompleteness of the knowledge graph.
So we don't want to impute the edges and then traverse.
We just like the method to take care of all this automatically.
So rather than thinking that all we have to do is just traverse the knowledge graph,
we really can think of this as making very complex predictions, right?
It's basically saying predict what entities are a- uh,
an answer to a given query.
So basically we are going to formulate these queries as predictions.
So this will now be our prediction task.
Um, and this means it will be very interesting
because we'll be able to answer any kind of query.
In so far, we talked about path queries,
we are able to answer any kind of path query.
Whatever set of relations you put on the path,
we should be able to answer it.
So it doesn't mean, at the training time,
we have to see the query,
then we train how to answer the query,
and now we are able to give the answers.
The idea is that we can obtain- we can get any query at the,
uh, test time, and we should still be able to answer it.
Uh, and then, you know, uh,
another important thing is that this method needs to be able to impute- to
implicity impute or implicitly complete the knowledge graph for the missing information,
and be, this way, robust to
the missing information or to the nois- in the knowledge graph.
And, really, another way how you can think of
this predictive queries task is that it's
a generalization of the link prediction task, right?
Uh, link prediction is simply starting with the head, uh,
moving along a relation of type R,
what is the tail?
And now we'd like to, uh,
generalize this one-step prediction task into multistep, uh, prediction task.
So this is very important.
We are really taking- reformulating this,
um, task of, uh,
answering queries as traversal over to the knowledge graph
into predicting what entities are the answer,
uh, to the query.