基于OAN的知识图谱查询研究

张玲玉，尹鸿峰

（1. 北京交通大学 计算机与信息技术学院，北京 100044；2. 北京交通大学海滨学院 计算机科学系，河北 黄骅 061199）

0 引言

大数据时代的到来，推动了以知识图谱为代表的知识工程等领域的飞速发展。知识图谱本质上是一种语义网络，其中节点代表各类实体和概念，边代表实体、概念之间的语义关系，现有的大量开放知识图谱，如 DBpedia[1]、YAGO[2]、Freebase[3]和Probase[4]等包含了数百万的实体和亿万的事实。知识图谱有丰富的语义关系，较高的质量和覆盖率，这些优势使得知识图谱在语义查询、知识问答、推荐系统等方面有了广泛的应用，这些应用也为知识图谱查询技术的研究带来了巨大的动力。

当前对于知识图谱查询算法的研究有很多，主要分为基于 RDF数据的查询[5,6]和基于图数据结构的查询[7,8,9]。然而前者多数是基于结构化查询语言XQuery[10]和SPARQL[11]等展开研究的，对于知识图谱的要求很高，难以适用于在半结构化、非结构化或者有大量噪声数据的知识图谱中查询；后者主要研究子图同构方法，分为精确匹配和近似匹配两类，其中算法如SAGA[12]、SIGMA[13]等存在结果集的用户相关度低、空间消耗比较大等问题。

为了提高查询结果中的用户相关度和查询效率，提高用户体验，本文提出一种同时考虑节点的语义相似和结构相似的算法OAN。知识图谱中每个节点存在一个所属类型的本体信息，这个信息能很好的反映节点间的语义关系，因此本文使用节点的本体信息来描述节点间的相似度。除了节点本身相似性之外，本文还考虑了节点的邻居信息，通过知识图谱的结构特点进一步提高候选节点的语义相关性。

1 相关工作

在子图匹配过程中节点相似度计算的方法有很多，其中使用最广泛的是基于节点标签的相似度度量[14,15]，即将节点属性等信息作为标签信息的方法。其中 Ness[16]中使用的节点标签是节点的名字等单一信息，并利用信息传播策略来度量节点的相似性。SMS2[17]则提出使用节点的多标签信息，将多个标签信息作为一个集合，通过集合的相似性度量来计算节点相似性。 但是由于标签信息仅代表节点本身的相关信息，所以这些方法不能很好的体现节点间的语义相关性。

基于标签相似度存在的问题，又提出了基于本体的方法，该方法在模式挖掘[18]、关键字查询[19,20]等方面都有应用，其主要是通过本体信息描述的实体类型之间的层级关系来度量相似度的。其中Ontq[21]将节点的本体信息用本体图的形式表示，然后通过本体图中两个节点之间的距离信息来确定两节点的相似度。但是其限制查询图和匹配结果必须是相同的图结构，这样使得算法没有表达结构相似性，并且构建本体图所需空间消耗比较大。

2 算法描述

给定有向目标图G=(NG,EG,TG,LG)，其中 NG为目标图的节点集合，EG为边的集合，TG为节点的类型集合，LG为边的标签集合；有向查询图Q=(NQ,EQ,TQ,LQ)，NQ和 EQ分别为查询图的节点集和边集，TQ和 LQ为节点的类型集合和边的标签集合。OAN的查询过程如图1所示。第一，过滤阶段，确定查询图的候选集，对于查询节点u和目标节点v，利用节点的本体信息来度量两个节点的类型相似性，相似度用simType(u, v)表示，得到每个查询节点的候选集；在该候选集的基础上，为了提高语义相似度，利用节点的邻居信息计算查询节点和其候选节点的结构相似度，用simNeighbor (u, v)表示，将相似度值与给定阈值比较，若大于阈值则 v为 u的候选节点，否则不是，最终获得查询图的候选集C(Q)。第二，检测阶段，结合图中边标签的信息，将候选集中不满足边匹配的节点移除。第三，同构排序阶段，在目标图中查找满足边同构的结果集，然后结合节点的标签相似度和结构相似度总和，给每个结果集打分后排序，获得最终排序后的结果集R(Q)。

图1 OAN算法查询过程Fig.1 The query processing of OAN

2.1 过滤阶段

这个阶段主要是利用节点的本体信息和邻居信息，通过查询节点和目标节点之间的相似性度量，确定查询图的候选集。其中查询图的候选集合用C(Q)表示，某一查询节点u的候选集用can(u)表示，节点u的类型集合用T(u)表示，其邻居集合用N(u)表示。

2.1.1 本体信息

本体信息作为知识图谱的组成元素，描述了知识图谱的数据模式，其强调概念和概念间的关系，如同义关系和上下位关系等。本体使用 rdfs:type 和rdfs:subClassOf 定义节点所属类的层次结构，并且允许声明类资源继承自其他类，而这些类型关系可以作为知识图谱表示的逻辑基础[22]。一个实体属于一个或多个类型，这些类型集合将构成这个节点的本体信息，可以作为对这个实体的一种语义描述。本文利用节点的本体信息来度量两个节点的相似度，这样节点间的语义度量就可以转化为计算两个节点的类型集合间的语义相似度，本文采用Jaccard方法度量集合的相似度，若相似度大于某一阈值，则为候选节点。

如图2所示，u、v、a、b、c等为节点标识，t1、t2、t3、t4等为节点所属类型，1ℓ、2ℓ、3ℓ 、4ℓ为节点间的边的标签。从图中可知，查询节点u的类型集合 T(u)={t1,t2,t3}，目标节点 v的类型集合T(v)={t1,t2,t4}，则节点u和v之间的类型相似度可表示为：

当simType(u, v)大于某一给定的阈值α时，则节点v可作为u的一个候选节点，否则v不是候选节点。

图2 过滤过程Fig.2 The filter process

2.1.2 邻居信息

通过类型相似度度量，查询图中每个节点有对应的候选集，但本文不仅考虑了节点本身的类型信息，还考虑了图的结构相似性，从而进一步过滤一些相关度低的候选集。图的结构特征可以通过节点的邻居信息来体现，因此本文引入Ness[16]提出的邻居集合，其中节点v的n-hop邻居节点集合N(v)为最多通过n步距离就可以到达v的节点。如图2所示，查询图中节点u的2-hop邻居节点集合N(u)={a,b, c}，对于目标图中节点v的2-hop邻居节点集合N(v)={a, b, c, e, f}，则查询节点u和目标节点v之间的结构相似度可用公式（2）表示：

当 simNeighbor(u, v)大于给定的阈值β时，节点v可作为u的一个候选节点，否则不是候选节点。由于节点间距离越近则节点间的相似度越高，随着距离增大相似度也变小，所以本文只考虑 2-hop邻居节点。

整个过滤过程如算法1描述。首先初始化候选集C(Q)；然后计算节点间的类型相似度（2-8），对于每一个查询节点nq，遍历目标图中每一个节点ng，计算两节点的类型集合相似度，若大于给定阈值α则ng为候选节点，加入nq的候选集can(nq)中，从而获得查询图的初始候选集；之后计算节点间的结构相似度（9-16），对于每一个查询节点nq，不是遍历整个目标图，而是遍历该查询节点的候选集中每一个节点ng，计算两节点的邻居集合相似度，若大于阈值β，则该候选节点仍有效，否则将这个节点从候选集中移除；最后获得最终的候选集合C(Q)。

算法1：Candidate输入：目标图 G=(NG,EG,TG,LG); 查询图Q=(NQ,EQ,TQ,LQ); G的邻居集合NG; Q的邻居集合NQ输出：查询图候选集C(Q)1： C(Q) ← Φ;2： for each nq ∈NQ do 3： for each ng ∈NG do 4： if simType(nq, ng) ＞α then 5： can(nq) ← { ng };6： end if 7： end for 8： end for 9： for each nq ∈NQ do 10： for each ng ∈can(nq) do 11： if simNeighbor(nq, ng)＜β then 12： can(nq) ← can(nq) { ng };13： end if 14： end for 15： C (Q) ← C (Q)∪can(nq);16：end for 17：return C (Q);

2.2 检测阶段

通过节点的类型和邻居信息相似度度量确定了查询图的候选集，但是以上候选集的计算并没有考虑边的匹配，可能存在边信息不匹配的候选节点。本文通过边信息检测来移除那些不匹配点，即判断对于一个查询节点 nq和一个目标节点 ng，其中 ng是nq的候选节点且nq有一条边(nq，nq1)，是否满足：在目标图中存在一个节点ng1，满足ng到ng1存在一条边并且ng1是nq1的候选节点。若满足条件，则ng是nq的匹配点，反之，两节点不匹配，将ng从候选集中移除。通过边检测得到最终的查询图的候选集。

2.3 同构排序阶段

获得目标子图后，对查询节点和其对应的候选节点进行子图匹配，从而获得匹配结果。本文利用Exq[23]提出的边标签同构的方法进行子图匹配，即数据图D与D′ 满足以下条件则边同构：若D中的节点到 D'中的节点有双射函数h，对于 D中的边u1→u2, D′ 中有边h(u1)ℓ→h(u2)，其中边的标签均为ℓ。从查询图的某一节点u开始，遍历节点u的每一个候选节点 v，将 v作为只包含一个节点的子图，通过边的同构对子图进行扩展从而获得满足边同构的匹配子图。即对于节点u与其每一个一步邻居节点u1连接的边，记录其边标签ℓ，在目标图中寻找v的一步邻居且边标签为ℓ 的邻居节点，然后再访问u1和其候选节点，以此不断迭代，直到整个查询节点都访问完，从而得到一个与查询图同构的结果。通过遍历u的不同的候选节点，获得多个结果，这些结果即为查询图的结果集。

由于用户想要从大量数据中获得自己期待的结果，所以对于得到的所有候选结果，本文只考虑与用户语义相关性高的前k个结果，并对这些结果集进行排序。其中结果的相关性度量由类型相似度和结构相似度共同决定，这两个相似度计算在确定候选集的时候已经完成。一个查询结果的语义相关性为所有查询节点的相关度之和，而查询节点u和匹配节点v之间的相关度可以用公式（3）表示。其中参数λ是一个0到1的数值，越接近1，代表邻居信息越重要；越接近0，代表节点的本体信息越重要。

3 实验与分析

在真实数据集上测试，通过和已有查询算法的对比，评估本文提出算法的精确度和查询效率。

3.1 实验设置

实验环境：本文使用Java1.8实现OAN算法，在32 G内存的Ubuntu16.04系统上做实验，每次实验重复5次，取其平均值为实验结果。在实验中选择与Exq算法中相同的2-hop的邻居信息，这样所需内存不大又不影响查询效果，且对数据集排序时的λ取值为0.5。

数据集：本文采用当前在知识图谱查询中常用的3个开源知识图谱。（1）Yago是一个巨大的语义知识库，整合了Wikipedia、WordNet和GeoNames等多领域的知识，目前 Yago3中事实的正确率约为95%。（2） DBpedia是一个多语言的百科知识图谱，其中的数据是从维基百科抽取出来的，多为结构化数据，包括人物、地点、机构、电影和专辑等很多领域。DBpedia中本体信息是为 8的层级结构，其中包含529个类。（3） IMDB是一个电影评分方面的数据库，里边包含电影、电视节目、传记、演员、导演、制片等在内的很多实体以及之间的关系。3个数据集中节点和边的规模如表1所示。

表1 3个数据集规模比较Tab.1 Database sizes

查询图：DBpedia作为链接数据的核心与Yago和IMDB都存在实体映射关系，且这个数据集还提供了一个实体和其属性值对应关系的 DBpedia tables，如在 http://dbpedia.org/page/Aristotle页面可以看到实体Aristotle的属性对应的各自属性值。每个table可以看作包含一个或多个<实体-关系-实体>的元组集合，对于每个table，我们将其中的实体手动映射到数据集中的节点，关系映射到数据集中的边。对于table中的元组集合，将其中一个元组作为查询图，其余剩下的元组作为这个查询图的基准集，用于计算结果的精确度。

3.2 精确度对比

对于获得的结果集，用户关心的是显示的前 k条记录是否信息准确且相关性高。在本文中，通过比较查询图的top-k结果集和其基准集，衡量对于不同的 k值得到结果集的精确度情况，其中采用P@k(Precision-at-k)值计算其精确度，即 top-k结果集在正确的基准集合中占的百分比。

OAN、Exq和NeMa算法在3个不同数据集下做实验，其中NeMa不考虑结构噪音和标签噪音，对于同一个数据集，3个算法的查询图是相同的，在k值分别为5、10、15、20、30情况下的结果集精确度如图3所示。从图3中可以看出，对于3个数据集，在不同的k值下OAN的精确度都比其他两个算法高，如在Yago数据集中，OAN的平均精确度比 Exq高 2%，比 NeMa高 4%。这是由于虽然NeMa考虑了节点标签和图的结构信息，但没有考虑边的标签信息，Exq考虑了邻居节点相关性并考虑了边标签，但没有关注节点本身的本体信息，而OAN将两者都考虑了。在每一个数据集中，三个算法都是在k为5时精确度最高，之后随着k值的增加精确度有所下降。这是由于top-k结果集是根据相似度值排序的，相关度高的在基准集中所占比重大，而随着k值增加，数据集的整体相关度变低。

图3 在3个数据集下算法的精确度对比Fig.3 The accuracy results of algorithms in three datasets

图4 在3个算法的查询时间对比Fig.4 The query time of three algorithms in three datasets

3.3 查询时间对比

这一部分考虑OAN、Exq和NeMa算法在以下三种情况下的查询效率，（1）查询图的规模固定时，查询时间随着数据集的增加的变化；（2）数据集的规模固定，查询时间随查询图的规模增加的变化，其中查询图的规模Q(|N|,|E|)是由查询节点个数|N|和查询边的个数|E|表示的；（3）数据集和查询图的规模都固定，查询时间随查询结果集的增加的变化。

实验结果如图4所示。Yago数据集中算法比较如图4（a）和（c）所示，对于4（a），在目标图从1M到150M的过程中，三个算法的查询时间都增加，但是OAN整体比其他两个算法查询效率高，并且从90M开始虽然数据集规模增加但查询时间并没有变化很大。这是由于前期寻找候选集的阶段需要遍历目标图，因此随着目标图的规模增大遍历时间也增加，但随着规模增大候选集的大小趋于稳定，使检测后的目标子图规模稳定，从而使得查询时间变化不大。NeMa由于在查询过程中需要不断迭代，每次迭代需要计算查询节点和所有候选节点的损失函数，导致查询时间明显比OAN长，几乎线性增长；而Exq更适合于边标签的频率很高的查询图，在边标签频率不高的图中剪枝效果不明显，查询时间比较长。4（c）是数据集在 1M 规模下查询图的规模从（3,2）增加到（7,6）过程中查询时间的变化情况，从中可以看出：（1）OAN的查询效率总体比Exq和NeMa高，在总过程中平均查询时间有提高15%；（2）随着查询图的规模增加，三个算法查询时间都增大，但OAN在（6,5）到（7,6）过程中查询时间变化不大，而另外两个算法的查询时间还是在增加。IMDB数据集的结果如图4（b）和（d）所示，与Yago中的结果整体一致。

评估查询结果集的增加对查询时间的影响，本文分别在6M的DBpedia和1M的Yago数据集上做实验，查询图的规模均为Q（4,3），k值从40到200过程中的查询时间变化如图4（e）和（f）所示，从图4中可以看出，随着K值增加，三个算法的查询时间都增加，但OAN更平缓一些。这是由于NeMa在计算排序时使用递归循环的方式，耗时较多；Exq中结果集的排序需要根据邻居节点重新计算两节点的结构相似度；而OAN中的类型相似度和结构相似度在过滤阶段就得到了，结果打分不需要重新计算。

4 结论

本文基于传统的知识图谱查询方法中语义相关度低、查询效率低的问题，提出了结合本体和邻居信息进行节点相似度度量的图查询方法OAN。OAN

中节点匹配利用的是节点的本体信息，用以提高节点间的语义相关性；图的结构匹配时考虑了节点的邻居节点对节点本身的重要性，利用 2-hop邻居集合计算结构相似性。在此基础上，提出边信息检测的方法，利用边标签信息的匹配，移除不满足条件的候选节点，这样很大程度上缩短了查询时间。最后在3个真实数据集上进行实验，通过与已有方法对比，本文提出的算法在3个数据集上的平均精确度有提高2%，查询效率提高15%。

[1] Auer S, Bizer C, Kobilarov G, et al. DBpedia: A Nucleus for a Web of Open Data[M]. The Semantic Web. Springer Berlin Heidelberg, 2007.

[2] Hoffart J, Suchanek F M, Berberich K, et al. YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[C]// International Joint Conference on Artificial Intelligence. AAAI Press, 2013: 3161-3165.

[3] Bollacker K, Evans C, Paritosh P, et al. Freebase: a collaboratively created graph database for structuring human knowledge. In SIGMOD, pages 1247–1250, 2008.

[4] Wu W, Li H, Wang H, et al. Probase: a probabilistic taxonomy for text understanding[C]// ACM, 2012:481-492.

[5] Le W, Li F, Kementsietsidis A, et al. Scalable Keyword Search on Large RDF Data[J]. IEEE Transactions on Knowledge &Data Engineering, 2014, 26(11): 2774-2788.

[6] Jayaram N, Khan A, Li C, et al. Querying Knowledge Graphs by Example Entity Tuples[J]. IEEE Transactions on Knowledge& Data Engineering, 2013, 27(10): 2797-2811.

[7] Wu Y, Yang S, Srivatsa M, et al. Summarizing answer graphs induced by keyword queries[J]. Proceedings of the Vldb Endowment, 2013, 6(14): 1774-1785.

[8] Ma S, Cao Y, Fan W, et al. Strong simulation: Capturing topology in graph pattern matching. TODS, 39(1): 4, 2014.

[9] Liu J, Xu B M, Xu X, et al.. A Link Prediction Algorithm Based on Label Propagation. Journal of Computational Science. 2016(16): 43-50.

[10] Chamberlin D, Clark J, Florescu D, et al. Xquery 1. 0: an xml query language[J]. Ibm Systems Journal, 2007, 41(4):597 - 615.

[11] Prud'hommeaux, Eric, Seaborne, et al. SPARQL Query Language for RDF[J]. 2008, 4.

[12] Tian Y, Santos C, States D, et al. SAGA: A Subgraph Matching Tool for Biological Graphs. Bioinfo., 2006.

[13] Mongiovi M, Natale R, Giugno R, et al. SIGMA: A SETCOVER-BASED INEXACT GRAPHMATCHING ALGORITHM[J]. Journal of Bioinformatics & Computational Biology,2010, 8(2): 199-218.

[14] Khan A, Wu Y, Aggarwal C, et al. NeMa: fast graph search with label similarity[C]// International Conference on Very Large Data Bases. 2013: 181-192.

[15] Zhu G, Iglesias C A. Computing Semantic Similarity of Concepts in Knowledge Graphs[J]. IEEE Transactions on Knowledge & Data Engineering, 2017, PP(99): 1-1.

[16] Khan A, Li N, Yan X, et al. Neighborhood based fast graph search in large networks[C]// ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens,Greece, June. DBLP, 2011: 901-912.

[17] Hong L, Zou L, Lian X, et al. Subgraph Matching with Set Similarity in a Large Graph Database[J]. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(9): 2507-2521.

[18] Cakmak A, Ozsoyoglu G. Taxonomy-superimposed graph mining[C]// International Conference on Extending Database Technology: Advances in Database Technology. ACM, 2008:217-228.

[19] Pound J, Hudek A K, Ilyas I F, et al. Interpreting keyword queries over web knowledge bases[C]// ACM International Conference on Information and Knowledge Management.ACM, 2012: 305-314.

[20] J. Pound, I. F. Ilyas, and G. Weddell. Expressive and flexible access to web extracted data: a keyword-based structured query language[C]// In SIGMOD, 2010。

[21] Wu Y, Yang S, Yan X. Ontology-based subgraph querying[C]// IEEE, International Conference on Data Engineering.IEEE, 2013: 697-708.

[22] Saarela S. Ontogator- a semantic view-based search engine service for web applications[C]// International Conference on the Semantic Web. Springer-Verlag, 2006: 847-860.

[23] Mottin D, Lissandrini M, Velegrakis Y, et al. Exemplar queries: a new way of searching[J]. Vldb Journal, 2016: 1-25.