2024年5月31日发(作者：闳哲圣)
word格式文档
path ranking algorithm调研报告
1. 引言
近两年来，随着Linking Open Data等项目的全面展开，语义Web数据源的
数量激增，大量RDF数据被发布。互联网正从仅包含网页和网页之间超链接的文
档万维网(Document Web)转变成包含大量描述各种实体和实体之间丰富关系的
数据万维网(Data Web)。在这个背景下，Google、百度和搜狗等搜索引擎公司纷
纷以此为基础构建知识图谱，如Knowledge Graph、知心和知立方等，用以改进
搜索质量，从而拉开了语义搜索的序幕。
正如Google的辛格博士在介绍知识图谱时提到的：“The world is not made
of strings , but is made of things.”，知识图谱旨在描述真实世界中存在
的各种实体或概念。其中，每个实体或概念用一个全局唯一确定的ID来标识，
称为它们的标识符(identifier)。每个属性-值对(attribute-value pair，又称
AVP)用来刻画实体的内在特性，而关系(relation)用来连接两个实体，刻画它们
之间的关联。知识图谱亦可被看作是由一张巨大的图组成，图中的节点表示实体
或概念，而图中的边则由属性或关系构成，我们需要构建并使用这张图。
大规模知识图谱的构建与应用需要多种智能信息处理技术的支持，其中主要
包括：实体链指（Entity Linking）、关系抽取（Relation Extraction）、知
识表示（Knowledge Representation）、知识推理（Knowledge Reasoning）等。
在知识推理方面，利用推理规则实现关系抽取的经典方法之一就是Path
Ranking Algorithm算法，由Lao & Cohen与2010年提出。该方法将每种不同
的关系路径作为一维特征，通过在知识图谱/Knowledge Base中统计大量的关系
路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取
效果，成为近年来的关系抽取的代表方法之一。但目前这种基于关系的统计的方
法，只能在连通图上使用，对于那些出现频率低的关系有严重的数据稀疏问题，
且代价高昂。针对这样的问题，现今也出现了许多针对该算法的改进研究。
专业整理
word格式文档
2. Path Ranking Algorithm
2.1 Random Walk and Restart
Random walk with restart (RWR)是最初提出的图像分割算法，也叫
Personalized Page Rank。它迭代地探讨了网络的全局结构，估计两个节点之间
的接近（亲和度得分）。在一个节点上，在每个步骤中，面临两个选择：要么移
动到一个随机选择的邻居，或跳回到起始节点。该算法仅包含一个固定参数R
称为“重启的概率（1−R移动到一个邻居的概率）。迭代后达到稳定，稳定的
概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量可
以被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足
式(1):
R=(1-d)u+dWr (1)
其中，d是继续游走概率，(1-d)为重启概率，u是启动节点，Wr是网络过
渡矩阵。随机游走(RWR)实际是一个简单的迭代过程：
R
t
=(1-d)u+dWr
t-1
（2）
式(2)表示了这样一个迭代的过程：算法从图中顶点u出发，沿图中的边随
机游走。在任意点上，算法以一定的概率d随机地选择与该顶点相邻的边，沿这
条边移动到下一个顶点，或以(1-d)概率直接回到出发点u，这是这个重启概率
可有效的防止由于随机游走的不确定性而进入一条权值很小的路径。在第t-1
步时移动带下一个顶点时，就开始了以这个点新出发点的第t步随机游走，其中
Wr
t-1
表示的是在t-1步游走时从一个节点游走到另一个节点概率。经过若干次随
机游走过程，可以到达图中每一个顶点的概率值达到平稳分布，即再次迭代也不
改变图中的概率分布值时，就可以得到的R值来对所求任务进行排序。比如讲
RWR运用在下图做图像分割时：
专业整理
2024年5月31日发(作者：闳哲圣)
word格式文档
path ranking algorithm调研报告
1. 引言
近两年来，随着Linking Open Data等项目的全面展开，语义Web数据源的
数量激增，大量RDF数据被发布。互联网正从仅包含网页和网页之间超链接的文
档万维网(Document Web)转变成包含大量描述各种实体和实体之间丰富关系的
数据万维网(Data Web)。在这个背景下，Google、百度和搜狗等搜索引擎公司纷
纷以此为基础构建知识图谱，如Knowledge Graph、知心和知立方等，用以改进
搜索质量，从而拉开了语义搜索的序幕。
正如Google的辛格博士在介绍知识图谱时提到的：“The world is not made
of strings , but is made of things.”，知识图谱旨在描述真实世界中存在
的各种实体或概念。其中，每个实体或概念用一个全局唯一确定的ID来标识，
称为它们的标识符(identifier)。每个属性-值对(attribute-value pair，又称
AVP)用来刻画实体的内在特性，而关系(relation)用来连接两个实体，刻画它们
之间的关联。知识图谱亦可被看作是由一张巨大的图组成，图中的节点表示实体
或概念，而图中的边则由属性或关系构成，我们需要构建并使用这张图。
大规模知识图谱的构建与应用需要多种智能信息处理技术的支持，其中主要
包括：实体链指（Entity Linking）、关系抽取（Relation Extraction）、知
识表示（Knowledge Representation）、知识推理（Knowledge Reasoning）等。
在知识推理方面，利用推理规则实现关系抽取的经典方法之一就是Path
Ranking Algorithm算法，由Lao & Cohen与2010年提出。该方法将每种不同
的关系路径作为一维特征，通过在知识图谱/Knowledge Base中统计大量的关系
路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取
效果，成为近年来的关系抽取的代表方法之一。但目前这种基于关系的统计的方
法，只能在连通图上使用，对于那些出现频率低的关系有严重的数据稀疏问题，
且代价高昂。针对这样的问题，现今也出现了许多针对该算法的改进研究。
专业整理
word格式文档
2. Path Ranking Algorithm
2.1 Random Walk and Restart
Random walk with restart (RWR)是最初提出的图像分割算法，也叫
Personalized Page Rank。它迭代地探讨了网络的全局结构，估计两个节点之间
的接近（亲和度得分）。在一个节点上，在每个步骤中，面临两个选择：要么移
动到一个随机选择的邻居，或跳回到起始节点。该算法仅包含一个固定参数R
称为“重启的概率（1−R移动到一个邻居的概率）。迭代后达到稳定，稳定的
概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量可
以被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足
式(1):
R=(1-d)u+dWr (1)
其中，d是继续游走概率，(1-d)为重启概率，u是启动节点，Wr是网络过
渡矩阵。随机游走(RWR)实际是一个简单的迭代过程：
R
t
=(1-d)u+dWr
t-1
（2）
式(2)表示了这样一个迭代的过程：算法从图中顶点u出发，沿图中的边随
机游走。在任意点上，算法以一定的概率d随机地选择与该顶点相邻的边，沿这
条边移动到下一个顶点，或以(1-d)概率直接回到出发点u，这是这个重启概率
可有效的防止由于随机游走的不确定性而进入一条权值很小的路径。在第t-1
步时移动带下一个顶点时，就开始了以这个点新出发点的第t步随机游走，其中
Wr
t-1
表示的是在t-1步游走时从一个节点游走到另一个节点概率。经过若干次随
机游走过程，可以到达图中每一个顶点的概率值达到平稳分布，即再次迭代也不
改变图中的概率分布值时，就可以得到的R值来对所求任务进行排序。比如讲
RWR运用在下图做图像分割时：
专业整理