基于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.