Knowledge Graph Introduction

知识图谱，简单的介绍一下吧，之前也零零散散的提到了一些，现在好好的看看其中会用到的那些算法和概念

Introduction

所谓的知识图谱就是将知识按照图的情况进行排列，和其余的图的网络的结构非常的类似，甚至可以说没有什么本质的区别，只是在这里会更加强调Node之中所存在的那些Attributes.每一个在自然界之中的Entity是网络之中的一个Node，而他们的关系Relationship则以Edge的形式在网络之中呈现。

现有的成熟的知识图谱有FreeBase,Wikidata,Dbpedia,YAGO,NELL等等，一般都是大公司做出来然后开源给大家使用的，这种开源的东西自然是非常好的，节省了我们大量的时间，但是其中也存在非常多的问题，比如两个最突出的问题就是Massive和Incomplete，大公司的数据自然是大数据，这也就导致我们普通人处理起来就显得力不从心，比如说我自己搞到了一个知识图谱，大小大概是8G还是9G，我可怜的MacBook处理起来确实是难办.还有一个问题就是之中的数据是并不完全的，比如说在图谱之中，那些大公司或者是比较有影响力的实体的数据还好，但是如果是一些相比起来没有那么出名的实体，可能就会有很多的边的缺失。

Knowledge Graph Completion

所以我们需要对于那些缺失的边进行补全，我将这个计划称为是 图谱补完计划(Graph Instrumentality Project) .那么首先要获得一个对于知识图谱的表达的方法，我们所选择的方法是使用一个三元组进行表示$(h,r,t)$,分别代表Head,Realtion,Tail.Head 与Tail自然不需多言，就是自然界之中的实体，但是对于Relation还是有一些可以说的，在网络之中存在三种特别的Relation

1. Symmetric Relations：也就是其关系是对称的关系，我是我室友的室友，我室友的室友是我，这就是一种对称的关系
   $$r(h,t) \to r(t,h)$$
2. Composition Relations:可以相加的关系，比如说大家的小时候的儿歌，妈妈的姐妹叫阿姨，这就是一种可以相加的关系，想不到吧，其实中华文化博大精深，在儿童的启蒙教育之中就已经包含了知识图谱
   $$r_{1}(x,y) \cap r_{2}(y,z) \to r_3(x,z)$$
3. 1 to N / N to 1:关系自然不是对等的，比如说渣男一口气谈很多的女朋友，这就是一种一对多的关系
   $$r(h,t_{1}),r(h,t_{2}), \cdots ,r(h,t_{n})$$

好了掌握了基本知识之后，我们就要开始处理知识图谱。要有效的处理知识图谱乃至于有效的处理任何的一个非结构化数据，我们首先的要做的一点就是将他们转成形式化的数据，换言之：Embedding，使用在之前就学过的TransE算法可以处理这个Embedding吗？

我们再Recap一下这个算法，对于任何的一个三元组$(h,r,t)$我们所希望得到的结果是$h +r = t$,那么目标函数就非常容易得到了，直接用相差的距离就行了

$$f_{r} (h,t) = ||h+r-t||$$

具体的训练还是使用负采样的方法简化，这里就不赘述了，大家想要看细节的话看我之前的Note – Graph Representation Learning之中有细致的讲解。

并且有一个非常棒的一点就是，TransE可以处理上面的那种Composition的关系，

但是也很可惜，TransE对于其他的两种关系就有些束手无策了，所以这时候我们也提出了改进的算法也就是称为TransR，首先看看原来的TransE为什么不满足我们的要求，其根源就是训练的时候默认关系和实体是在同一个向量空间里面的，这就导致了关系的表达的形式受到了极大的限制，所以我们把实体和关系映射到不同的空间之中

定义一个矩阵$M_r \in R^{k\times d}$作为投影矩阵，对于Entity Vector进行如下的操作

$$h^* = M_r h , \quad t^* = M_{r}t$$

所以我们的目标函数也变成了

$$f_{r}(h,t)  =||h^* + r – t^*||$$

为什么处理节点不直接处理关系呢？因为网络之中的关系的数量比节点的数量大得多的多。通过这样的一个矩阵，我们也就可以处理Symmetric的关系了

通过矩阵操作，将这两个实体映射到关系空间里的相同的位置。

同理，对于一对多或者是多对一的关系也可以进行这样的操作，使得$t^* = M_r t_1  = M_r t_2$.

而在这样的情况下，我们无需保证$t_1 = t_2$.

简单的总结一下，可以形成下图

Queries

如何使用知识图谱呢？换言之，如何Query呢？我们可以将Query分成如下的不同的类型

One hop Query

最简单的形式，所要做的事情其实就是判断$t$是不是接近于$h +r$的组合，通过NER找到里面的实体和关系，相加，然后寻找与他们相加之后的结果最接近的那个实体就可以了。

Path Queries

也很简单，和上面的思路类似，只不过在上面是增加一个关系，而在这里将多种关系叠加起来了而已

形成一条Query Chain就可以搞定Path Queries的问题了。

Conjunctive Queries

也就是进行混合的查询，同时满足两种要求的条件的Query，比如说

“Where did Canadian citizens with Turing Award graduate?”

如果形式化的表达就是

然后选择Bengio和Hiton作为搜索的结果，再寻找他们的毕业的学校即可。

但是两个还好，如果多个Query的条件一起来怎么办呢？凡是我们思考的有些困难的问题，上神经网络试试基本没啥大问题，最起码可以搞出个能用的模型。

将当前的Query的Embedding记作是$q_1,\cdots,q_{m}$，然后经过一个神经网络之后，得到Intersection的Query Embedding记作是$q$.

这里使用了一个Permutation的操作增加Robust.然后训练就完事了。

Box Embedding

对于Box Embedding，我单独开了一篇论文笔记来讲，是2020年的ICLR的文章，链接在这【QUERY2BOX: REASONING OVER KNOWLEDGE G RAPHS IN VECTOR SPACE USING BOX EMBEDDINGS】是Jure老师的文。