课程链接：CS224W: Machine Learning with Graphs
课程视频：【课程】斯坦福 CS224W: 图机器学习 (2019 秋 | 英字)

1. 什么是知识图谱（Knowledge Graph）

知识图谱可以看作是是一个图，图中的节点表示实体（entities），边表示实体之间的关系（relations）。

一些知识图谱的例子：

知识图谱的应用：

• 信息搜索（Serving information）
• 智能问答和对话（Question answering and conversation agents）

2. Knowledge Graph Completion 知识图谱补全

虽然现在已经有了很多可用的知识图谱，但是这些知识图谱都是不完备的，因为想要一步到位地构建一个完备的知识图谱是很困难的。那么，有没有什么办法可以预测知识图谱中可能存在的关系呢？（Can we predict plausible BUT missing links?）

Knowledge Graph Completion

2.1 Knowledge representation

知识图谱补全的主要任务就是预测可能存在的边及其类型。在知识图谱中，边通常通过三元组$(h,r,t)$来表示。

这些边（三元组）可以表示不同的关系类型：

• Symmetric Relations——对称关系：$r(h,t)\Rightarrow r(t,h),\forall h,t$。例如家人、室友关系，由$h$是$t$的室友可以得到$t$是$h$的室友。
• Composition Relations——组合关系：$r_1(x,y)\bigwedge r_2(y,z)\Rightarrow r_3(x,z),\forall x,z$。例如：$y$是$x$的母亲，$z$是$y$的父亲，可以推出$z$是$x$的外公。
• 1-to-N, N-to-1 relations——链式关系：$r(h,t_1),r(h,t_2),\cdots ,r(h,t_n)都为真$。例如，$t_1,t_2,\cdots ,t_n$都是$h$的学生。

那么，我们怎样在向量空间中表示这个三元组呢？我们首先明确一个基本的想法，就是假如在向量空间中，我们给定了向量$(h,r)$，得到的向量应该尽可能地接近向量$t$。那么，我们就需要解决两个问题：

• How to embed $(h,r)$ ?
• How to define closeness?

2.2 TransE

我们首先介绍第一种知识图谱的表示方法——TransE。

因为要让向量$(h,r)$尽可能地接近向量$t$，一个很直接的想法就是令$h+r=t$。那么，对于一个三元组来说，它的得分就是$h+r$和$t$之间的距离，即$f_r(h,t)=||h+r-t||$。那么，在训练过程中的cost function就是：

在课程的第七章给出了TransE的算法的伪代码：

因为这个算法非常经典，网上也有很多关于这个算法的解释，可以自己多去了解一下。

利用transE进行知识图谱中的链接预测——

TransE算法可以很好地解决Composition Relations，但是不能很好地解决Symmetric Relations和1-to-N, N-to-1, N-to-N relations。

2.3 TransR

TransR算法则是从另一个角度来进行向量表示。

TransR可以处理Symmetric Relations和1-to-N, N-to-1, N-to-N relations，但不能处理Composition Relations。

3. 基于知识图谱的查询/推理

我们能否进行多跳推理，即在一个不完整的、庞大的知识图谱上高效地回答复杂的查询呢?

我们首先来看一下基于知识图谱的查询类型：

3.1 One-hop Queries和Path Queries（ 路径查询）

我们可以链路预测问题看成一个单跳推理（查询问题）。比如：

Path Queries就是在知识图谱上的单跳查询的组合（也就是多跳查询）。（Generalize one-hop queries to path queries by adding more relations on the path.）。Path queries可以表示为
$$q=(v_a,r_1,\cdots ,r_n)$$

其中$v_a$是固定的节点，查询的结果通过$q$来返回，经过$r_1,\cdots ,r_n$序列表示的关系之后，是否能返回结果。path queries的计算图是链式结构：

Traversing Knowledge Graphs

下面是一个例子，表示在知识图谱中查询：Where did Turing Award winners graduate?（图灵奖获得者毕业于哪里？）

Step	Graph
首先，我们确定一个开始的节点$v_a$为“Turing Award”
从该节点开始，找到和该节点连接并且关系为win的节点——{“Pearl”,“Hinton”,“Bengio”}
从节点{“Pearl”,“Hinton”,“Bengio”}开始找到与这些节点相连并且关系为“Graduate”的节点，这些节点就是我们要找的答案！

但是，我们前面说到，我们现在可用的知识图谱大都是不完备的，如果知识图谱不完备，我们该怎样找到我们想要的答案呢？

我们可以先进行链路预测（补全），然后再进行路径查询么？——这是个看起来很有效的办法，但是不可能实现，因为庞大的知识图谱实际上是稠密的，因此在知识图谱上进行路经查询的算法时间复杂度非常高。

我们这里介绍一个有效的解决方案——embed queries！换句话说，我们可以将TransE推广到多跳查询中。

我们可以将查询结果看成是查询起点和关系的向量组合。那么，如果我们想知道实体$v$是不是查询结果$q$，我们只需要进行一个邻域搜索就行——

同样的，我们还是用上面的例子来整体了解一下这个过程——Where did Turing Award winners graduate?

Computation Graph	Embedding Space

3.2 Conjunctive Queries 连接查询

那么，我们能不能进行更加复杂的查询呢？例如：

在这个例子里面，我们的anchor node就不只是一个了，而是“Turing Award”和“Canada”两个。

Computation Graph	Embedding Space

我们同样可以将TransEt推广到Conjunctive Queries中，但是，这里有一个问题——How do we take intersection of several vectors in the embedding space?

我们设计一个neural intersection operator $J$ 实现。且该算子为一个排列不变量。

该算子的计算结构如下：

那么，有了这个算子之后，我们就可以继续后续的步骤了：

Computation Graph	Embedding Space

给定一个实体的向量$v$，查询的向量$q$，以及它们之间的距离$f_q(v)=||q-v||$。那么需要训练的参数有：

训练过程的策略和TransE是一样的。整个过程如下：

当然，这个方法也有局限性——Taking the intersection between two vectors is an operation that does not follow intuition. 我们在路径查询的过中，每一步都有可能产生很多实体的集合，选取这些实体的向量的intersection如果不可行，那么有没有更好地模型来表示这些集合呢（How can we better model these sets）？Can we define a more expressive geometry to embed the queries?

4. Query2Box: Reasoning with Box Embeddings

这一节的内容主要是老师的一些工作，发表在论文：Query2box: Reasoning over KGs in Vector Space using Box Embedding中。具体的可以看一下其他博客的论文解读。

这个是该论文/项目的Github地址：https://github.com/hyren/query2box

看名字论文的作者应该是跟着Jure学习的两个中国学生，如果有什么不理解或者有什么问题的话，直接到github里面的邮箱hyren@cs.stanford.edu发邮件询问，用中文的话我觉得问题应该不大。