知识图谱概论（三）

此节主要描述用于得到更多信息的知识归纳技术

3 归纳知识

归纳推理将从输入观察到的模式进行概括，生成一些新颖但可能不准确的预测。例如，从地理和航班信息的图表中，我们可以观察到几乎所有国家的首都都有国际机场为其服务，因此可以预测，由于圣地亚哥是首都，它可能有一个国际机场为其服务;然而，一些首都(如瓦杜兹)没有国际机场。因此，预测可能有一定程度的可信度;例如，如果我们看到195个首都中有187个拥有国际机场，那么我们可以为使用该模式做出的预测分配0.959的置信度。然后，我们将归纳获得的知识称为归纳知识（inductive knowledge），它既包括编码模式的模型，也包括由这些模型做出的预测。

归纳知识可以通过有监督或无监督的方法从图中获得。
监督式方法学习一个函数(也称为模型)，将一组示例输入映射到它们的标记输，然后，该模型可以应用于未标记的输入。为了避免标记太过于浪费时间，一些监督方法可以从未标记的输入自动生成输入输出对，然后将其馈送到监督过程中以学习模型。在这里，我们把这种方法称为自我监督。另外，无监督过程不需要标记的输入-输出对，而是应用预定义的函数(本质上通常是统计函数)将输入映射到输出。

在Fig.14中，我们概述了通常应用于知识图谱的归纳技术。在无监督方法的情况下，有大量关于图分析（graph analytics）的工作，其中众所周知的算法用于检测图中的社区或集群，找到中心的节点和边等。另外，知识图谱嵌入（knowledge graph embeddings）使用自我监督来学习知识图元素的低维数值模型。图的结构也可以通过图神经网络（graph neural network）直接用于监督学习。

最后，符号学习（symbolic learning）可以学习符号模型。也就是说，规则或公理形式的逻辑公式可以从图中以自监督的方式得到。现在我们依次讨论前面提到的每一种技术。

3.1 图分析（Graph Analytics）

图分析是将分析算法应用于图。这种算法通常分析图的拓扑结构，即节点和组是如何连接的。在本节中，我们简要概述了一些适用于知识图谱的流行图算法，然后讨论了可以实现这些算法的图处理框架。

3.1.1 图算法（Graph Algorithms）

不同的图算法可以运用在不同的地方，在这里我们简要介绍五类在实践中经常使用的算法。

首先，中心分析（centrality analysis）旨在识别图中最重要的中心节点或边。具体的衡量节点中心性的因素包括度（degree）、中间度（betweenness）、接近度（closeness）、特征向量（Eigenvector）、PageRank、HITS、Katz等。中间度也可以应用于边。

在Fig.15中，节点中心性度量将允许预测最繁忙的交通枢纽，而边中心性将允许我们找到许多最短路线所依赖的边，以预测交通。

其次，社区检测（community detection）旨在识别内部连接比图的其余部分更密集的子图(社区)。社区检测算法包括最小分割（minimum-cut）算法、标签传播（label propagation）、Louvain modularity等。例如，应用于Fig.15的社区检测可能检测到图左边(指智利北部，图左边的节点地名位于智利北部)、图右边(指智利南部，图右边的节点地名位于智利南部)，也可能检测到图中心(指有机场的城市)的社区。

第三，连通性分析（connectivity analysis）旨在估计图的连接程度和弹性。具体技术包括测量图密度（graph density）或k-连通性（k-connectivity），检测强连通分量和弱连通分量，计算生成树（spanning trees）或最小分割（minimum cuts），等等。在Fig.15的上下文中，这样的分析可能会告诉我们，到Grey Glacier和Piedras Rojas的路线是最“脆弱”的，如果两条$bus$路线中的一条出现故障，就会与主要枢纽断开连接。

第四，节点相似性（node similarity）旨在通过节点在其邻居的连接方式找到与其他节点相似的节点。节点相似性度量可以使用结构等价（structural equivalence）、随机游走（random walks）、扩散核（diffusion kernels）等来计算。这些方法提供了如何连接节点以及它们在哪些方面相似的理解。在Fig.15中，这样的分析可能会告诉我们Calama和Arica是相似的节点，因为它们都有飞往Santiago的返程航班和前往San Pedro的返程巴士。

第五，图摘要（graph summarisation）旨在从图中提取高级结构，通常基于商图（quotient graphs）。图摘要时，输入图中的节点被合并但保留输入节点之间的边。这些方法有助于提供大规模图的概览。

Fig.16提供了一个商图的例子，它总结了Fig.15的图，这样，如果在输入图中有一条边 s –$p$–> o，那么在s∈S和o∈O的商图中就有一条边 S –$p$–> O。在这种情况下，商图的节点是根据输出边标签定义的，我们可以从左到右检测到它们分别代表岛屿、城市和城镇/景点。

3.1.2 图处理框架（Graph Processing Frameworks）

针对大规模图形处理，已经提出了许多图形并行框架（graph parallel frameworks），包括Apache Spark (GraphX)、GraphLab、Pregel、Signal-Collect、Shark等。这些框架中的计算是迭代的，在每次迭代中，每个节点读取通过向内边（类似于入度）接收的消息(可能还有它自己以前的状态)，执行计算，然后使用结果通过向外边（类似于出度）发送消息。

为了说明这一点，假设我们希望计算Fig.15中最容易到达(或最不容易到达)的位置。衡量这一点的一个好方法是使用中心性，我们选择PageRank。它计算旅游者随机遵循图中所示路线在给定数量的“跳数”后到达特定地点的概率。我们可以使用图并行框架在大图上实现PageRank。在Fig.17中，我们为Fig.15的子图提供了一个PageRank迭代示例。

3.2 知识图谱嵌入（Knowledge Graph Embeddings）

机器学习可以直接用于提炼知识图谱，或者使用知识图进行下游任务，如推荐、信息提取、问答、查询松弛[、查询近似等。然而，机器学习技术通常采用向量表示，与通常表示图的方式不同。那么，如何对图进行数字编码以用于机器学习呢?

使用向量表示图的第一次尝试是使用one-hot编码，为每个节点生成长度为$|L|\cdot |V|$的向量，其中$|V|$表示输入图中的节点数，$|L|$表示边标签数。在向量相应的索引处置1，表示图中相应边的存在，否则为零。然而，这样的表示通常会导致大而稀疏的向量，这对大多数机器学习模型都是不利的。

知识图谱嵌入技术的主要目标是在连续的低维向量空间中创建图的密集表示(即嵌入图)，然后可用于机器学习任务。嵌入的维数$d$是固定的，通常很低(例如，50≥$d$≥1000)。图嵌入由每个节点的实体嵌入（entity embedding）组成：一个具有$d$维的向量，我们用 $e$ 表示；以及每个边标签的关系嵌入（relation embedding）:我们用 $r$ 表示O($d$) 维向量。

这些向量的总体目标是抽象和保留图中的潜在结构。有许多方法可以实例化嵌入的概念最常见的是，给定一条边 s –$p$–> o，一种特定的嵌入方法定义了一个评分函数（scoring function），该函数接受 $e_s$ (节点 s 的实体嵌入)，$r_p$(边标签 p 的关系嵌入)和$e_o$(节点 o 的实体嵌入)，并计算边的可信度（plausibility）：它是真的可能性有多大。
给定一个数据图，目标是根据给定的评分函数计算维度 $d$ 的嵌入，使正边(通常是图中的边)的合理性最大化，并使负例(通常是图中节点或边标签改变的边，使它们不再在图中)的合理性最小化。由此产生的嵌入可以被视为通过自我监督学习的模型，该模型对图的潜在特征进行编码，将输入边映射到输出合理性分数。

广泛的知识图谱嵌入技术已经被提出，我们总结了其中最突出的。首先，我们讨论平移模型（translational models），其中关系被视为将主体实体转换为客体实体。然后我们描述张量分解模型（tensor decomposition models），提取接近图结构的潜在因素。然后，我们讨论了神经网络模型（neural models basedon neural networks）。最后，我们讨论了基于词嵌入技术的语言模型（language models based on word embedding techniques）。

3.2.1 平移模型（translational models）

平移模型将边标签解释为从主节点(即源或头部)到对象节点(即目标或尾部)的转换。例如，边 San Pedro –$bus$–> Moon Valley，边标签$bus$被视为转换San Pedro为Moon Valley，同样也适用于其他$bus$边。

一种开创性的方法是TransE，在所有正边s –$p$–> o 上，TransE 对$e_s$、$r_p$、$e_o$ 进行学习，使$e_s$+ $r_p$尽可能接近 $e_o$。相反，如果边是负的，TransE 会使$e_s$+ $r_p$尽可能远离 $e_o$。
Fig.18提供了一个由TransE计算的二维($d$ = 2)实体和关系嵌入的简单示例。

对于初始图中的任意边 s –$p$–> o，将向量$e_s$、$r_p$相加应该近似于 $e_o$。在这个简单的例子中，向量精确地对应。例如，将 Licantén ($e_L$)和$westof$($r_{wo}$)的向量相加，得到一个与 Curico ($e_C$)对应的向量。我们可以使用这些嵌入来预测边。例如，要预测图中哪个节点最有可能满足Antofagasta (A.)–$westof$-> ，通过计算$e_A$+$r_{wo}$，我们发现结果向量图18($c$)中的虚线最接近$e_T$，因此预测Toconao (T.)是最可信的节点。

除这个示例之外，TransE可能过于简单。例如，在Fig.15中，$bus$ 不仅将San Pedro转换为Moon Valley，还将Arica转换为Calama，其中TransE将尝试为所有目标位置提供类似的向量，这可能对于其他边来说是不可行的。为了解决这些问题，人们研究了TransE的许多变体，通常对每种类型的关系使用不同的超平面(例如TransH)或向量空间(例如TransR ， TransD)。

3.2.2 张量分解模型（tensor decomposition models）

获得图嵌入的第二种方法是应用基于张量分解的方法。张量是一个多维数值域，它将0维张量，1维张量，2维张量（标量、向量、矩阵）推广到任意维。张量分解包括将张量分解为更多的“元素”张量(例如，低阶张量)，原始张量可以通过固定的基本操作序列重新组合(或近似)。这些元素张量可以看作是捕捉原始张量中的潜在因素。张量分解有很多方法，现在我们将简要介绍秩分解（rank decompositions）背后的主要思想。

先不考虑图，考虑一个二阶张量（即a × b矩阵）$C$，其中每个元素$C_{ij}$表示智利第$i$个城市在一年中的第$j$个月的平均温度。由于智利是一个长而窄的国家，横跨了亚极地气候和沙漠气候，我们可以将$C$分解为两个表示潜在因素的向量$x,y$。$x$中有a个元素，对纬度较低的城市给出较低的值；$y$中有b个元素，对温度较低的月份给出较低的值。那么计算两个向量的外积就可以得到$C$的近似，即$x\otimes y\approx C$。如果存在这样的 x x