Knowledge Graph Reasoning

1. 简介

1.1 Def

KG Reasoning is to infer new knowledge from the given KG.
Classification:
- Logical reasoning 主要介绍
- Statistical reasoning

1.2 Logical Reasoning include:

Deductive Reasoning determines whether the truth of a conclusion can be determined for that rule, based solely on the truth of the premises. 推导结论
Inductive Reasoning attempts to support a determination of the rule. 学习规则
Abductive reasoning selects a cogent set of preconditions.寻找前提

Example:

pre-condition: it rains

rule: if it rains, then the grass gets wet

conclusion: the grass gets wet
Deductive Reasoning: If it rains, then the grass gets wet. Since today is raining, the grass is wet. 若下雨，则草地会变湿。因为今天下雨了，所以今天草地是湿的。
Inductive Reasoning: The grass is wet each time when it rains. Thus, if it rains, then the grass gets wet. 每次下雨，草地都是湿的。所以下雨会使草地变湿。
Abductive Reasoning: If it rains, then the grass gets wet. The grass is wet because it is raining. 若下雨，草地会变湿。之所以草地是湿的，因为正在下雨。

1.3 Classification:

Forward reasoning
Backward reasoning

2. Forward reasoning

2.1 Def

starts with the available data and uses inference rules to extract more data until a goal is reached.利用已有的规则不断获取新的知识，直到知识产生，注：目标并不是明确的
- An inference engine using forward chaining searches the inference rules until it finds one where the antecedent 先前的 (If clause) is known to be true.
- When such a rule is found, the engine can conclude, or infer, the consequent (Then clause), resulting in the addition of new information to its data. 归纳新知识
- The forward chaining approach is often employed by expert systems.

2.2 Materialization 实体化

Materialization is to compute all implicit（隐式） statements by applying rules on assertions.

Example1:

Example2:

So what type of Endocarditis is?

2.3 Classification

Example1:

Classification is to compute all implicit subclass relations by applying rules on a TBox.

利用TBox的规则计算所有子类的依赖关系

Example2:

Highvalue_Company ⊑ ∃beInvestedBy. Investment_Company
高价值公司由投资公司投资。
Investment_Company ⊑ Financial_Institute
投资公司属于金融机构
∃beInvestedBy. Financial_Institute ⊑ Solvent_Company
借助金融机构投资的公司都是具备偿还能力的企业。

Answer:

Highvalue_Company ⊑ ∃beInvestedBy. Financial_Institute
Highvalue_Company ⊑ Solvent_Company

3. Backward Reasoning

Backward reasoning (Backward chaining) is an inference method described colloquially as working backward from the goal.
- It is often used in entailment（蕴含） checking or query answering in KG.
- It uses the rules to rewrite the query in several ways and the initial query is entailed if a rewritten query maps to the initial facts.
有目标，QA——真或假

Example1:

Rule: If you are human, then you are mortal.
Human(x)→Mortal(x)
Question: Is Socrates a mortal?
Solution: Check whether Mortal(Scorates) or Human(Scorates) is true.

Example2:

Query: Find all patients with heart diseases, i.e., Heart_Disease(x)
Rewriting: Endocarditis(x) ⋁ Miocardial_Infarction(x) ⋁ Coronary_disease(x)
可以理解成重写问题

Exercize：

Find all sports players with the following KG, i.e., rewrite the query Sports_Player(x).

Query: Find all sports players
Rewriting: SportsPlayer(x) ⋁ BasketballPlayer(x) ⋁ FootballPlayer(x) ⋁ TennisPlayer(x)

Other Tasks in Logical Reasoning: Inconsistency Checking

Incoherent不一致 ontology: ontology with at least one unsatisfiable concept 至少有一个不可满足概念的本体（空集）

Example:

PhDStudent ⊑ Student,
PhDStudent ⊑ Employee,
Student ⊑ ¬ Employee
- 以上最终可以退出Student和Employee都是空集，所以找不到一个model
- Inconsistent ontology: ontology without a model.

Example:

PhDStudent ⊑ Student,
PhDStudent ⊑ Employee,
Student ⊑ ¬ Employee,
PhDStudent(John)
- 这里则产生了矛盾

Example: DICE ontology:

Brain $\subseteq$ CentralNervousSystem п $\exists$systempart.NervousSystem ח BodyPart п $\exists$ region.HeadAndNeck п $\forall$ region.HeadAndNeck
CentralNervousSystem $\subseteq$ NervousSystem
BodyPart $\subseteq \neg$ NervousSystem or DisjointWith(BodyPart,NervousSystem)
- Reasoning:
  - Brain $\subseteq$ Bodypart $\subseteq$ $\neg$ NervousSystem
  - Brain $\subseteq$ CentralNervousSystem $\subseteq$ NervousSystem
  - Brain = $\emptyset$
- Brain是空集

Example from Foaf:

Person(timbl)
Homepage(timbl, http://w3.org/)
Homepage(w3c, http://w3c.org/)
Organization(w3c)
InverseFunctionalProperty(Homepage) (Homepage的domain只有一个值，所以矛盾)
DisjointWith(Organization, Person)

Example from OpenCyc:

ArtifactualFeatureType(PopulatedPlace)
ExistingStuffType(PopulatedPlace)
DisjointWith(ExistingobjectType,ExistingStuffType)
ArtifactualFeatureType $\subseteq$ ExistingObjectType
ExistingObjectType与ExistingStuddType不相交，但是却拥有相同的实例，所以矛盾

Exercise：
The following ontology is inconsistent, and remove one axiom or assertion in it to make it consistent.

$\begin{aligned} &\operatorname{Ph} D_{\text {student }} \sqcup \text { Undergraduatge }_{\text {student }} \sqsubseteq \text { Student, } \\ &\text { Student } \sqsubseteq \neg \text { Employee } \\ &\text { PhD }_{\text {student }} \text { (John), } \\ &\text { Employee(John), } \\ &\text { Marriedto(John, Lisa), } \\ &\text { Undergraduate(Jack) } \end{aligned}$

$\text { Student } \sqsubseteq \neg \text { Employee }$ or $\text { Employee(John)}$ or $\text { PhD }_{\text {student }} \text { (John) }$

4. Summary

In logical reasoning, we mainly focus on deductive reasoning, i.e., leveraging rules and preconditions to infer new knowledge.
Deductive reasoning including forward reasoning and backward reasoning.
Forward reasoning actually gets as much knowledge as possible before application. 相当于补全知识
Backward reasoning starts from the target/ application and can quickly get the result. 不考虑补全，专注于找到结果，实用性

5. Logical Reasoning in Practice

Datalog is a declarative声明式 logic programming language, which is designed for knowledge base and database.
Datalog has similar expressive ability with OWL.
Datalog supports recursion, and rule editing (more freely) for reasoning. 可以自定义规则，来做推理

OWL与Datalog相交的语言

Datalog syntax:

Atom: $𝑝(𝑡_1,𝑡_2,…,𝑡_𝑛)$ , predicate(谓语): p, variable or constant: t

Example: $\text{has_child}(𝑋,𝑌) $
Rule: $𝐻:−𝐵_1,𝐵_2,…,𝐵_𝑚,$
- head (an atom): H,
- body (one atom or the AND of more atoms): 𝐵1,𝐵2,…,𝐵𝑚 (body 可以理解为解释，即可以由body推出head)
Example: $\text{has_child}(𝑋,𝑌):−\text{has_son}(𝑋,𝑌)$
Fact: $𝐹(𝑐_1,𝑐_2,…,𝑐_𝑛):−$ , constant: $c$ , without body or variable

Example: $\text{has_child}(Alice,Bob):−$

6. Datalog program:

%%Facts
friend(joe,sue) .
friend(ann,sue) .
friend(sue,max) .
friend(max,ann) .

%% Rules
fof(X,Y) :- friend(X,Y)
fof(X,Z) :- friend(X,Y), fof(Y,Z)

%%Quiery 1
query(X) :- fof(X,ann)

%%Answer:
fof(sue,ann) .
fof(max,ann) .
fof(joe,ann) .
fof(ann,ann) .

Datalog Rule Operators:

Intersection: $Q(x_1, x_2, ⋯ , x_n) :- R(x_1, x_2, ⋯ , x_n) , S(x_1, x_2, ⋯ ,x_n) $

Example:
- $\text{smart_phone(x)} :- \text{cell_phone(x)}, \text{intelligent_device(x)}$
Union: $Q(x_1, x_2, ⋯, x_n) :- R(x_1, x_2, ⋯ ,x_n) , Q(x_1, x_2, ⋯, x_n) :- S(x_1, x_2 , ⋯ , x_n) $

Example:
- $human(x) :- woman(x) $
- $human(x) :- man(x) $
Difference: $Q(x_1, x_2, ⋯ ,x_n) :- R(x_1, x_2, ⋯, x_n) , \text{not} S(x_1, x_2, ⋯ , x_n)$

Example:
- $younger_brother(x, y) :- brother(x, y), not elder_brother(x, y)$

Exercise

Rule：fatherinlawOf(X,Z) :- wifeOf(X,Y), fatherOf(Y,Z)
Fact： wifeOf (YaoMing，YeLi)
Fact： fatherOf (YeLi，YeFa)

Who is the father-in-law of Yao Ming？
fatherinlawOf(YaoMing, YeFa)