知識圖譜的候選實體搜索與排序①

沈航可, 祁志衛, 張子辰, 岳 昆

(云南大學 信息學院, 昆明 650500)

1 引言

知識圖譜(Knowledge Graph, KG)[1]作為實體關系的語義網絡, 在相關實體搜索的應用中至關重要, 是搜索引擎的重要支撐技術[2].基于KG的相關實體搜索旨在根據給定的實體, 在KG中搜索與此實體相關的候選實體集合, 并按照候選實體與查詢實體間的相關度對候選實體進行排序并返回結果, 以提高用戶的搜索體驗.事實上, 隨著互聯網的高速發展, Web文檔快速產生, 反映了現實世界不斷演化的知識, 與KG中的知識共同描述了實體間的相關關系.因此, 如何有效地表示實體在KG和Web文檔中的關系信息, 進而準確地搜索與給定實體相關的候選實體, 并對候選實體進行排序, 對提升相關實體搜索的準確性具有重要意義.雖然現有方法能夠有效地獲取相關實體, 減少用戶搜索時需要過濾的無用信息, 但仍存在如下挑戰:

(1) 與實體相連的不同關系能夠表示實體不同的語義[3,4], 因此, 需要一種能夠有效表示不同關系中實體的語義并準確搜索候選實體的方法.

(2) 由于Web文檔與KG共同描述了實體間的相關關系, 為了準確地對候選實體進行打分排序, 需要一種能夠根據實體在Web文檔與KG中的關系信息來計算候選實體與查詢實體間相關度的方法.

針對挑戰(1), 現有方法主要根據查詢實體的鄰居節點來搜索候選實體, 如Huang等[5]使用與查詢實體直接相連的實體作為候選實體集, Reinanda等[4]獲取以查詢實體為中心的k階子圖, 并基于子圖的路徑信息搜索候選實體.上述方法在小規模KG中表現尚可,而當KG規模較大時, 需要搜索的候選實體會出現在查詢實體的鄰居實體集外, 導致無法正確搜索到候選實體.對此, 現有的表示學習方法[5-7]將高維、復雜的KG映射到低維的向量空間中, 進而降低在大規模KG上的計算開銷.為了更加有效地搜索候選實體, 本文基于TransH模型[7]提出候選實體搜索算法, 首先去除對查詢實體不重要的關系, 降低搜索的時間代價.然后通過KG的嵌入向量計算出實體在各關系對應超平面上的投影, 作為不同關系下實體的語義表示.由于候選實體與查詢實體有共同的語義特征[2], 因此, 為了有效地搜索候選實體, 我們根據實體的語義相似度對各超平面中的投影進行聚類, 進而得到與查詢實體有共同語義特征的候選實體.

針對挑戰(2), 現有方法大多基于KG來計算實體相關度, 例如, Milne等[8]提出了WLM方法, 基于KG中實體所對應Wikipedia頁面的超鏈接完成實體間的相關度計算.Ponza等[9]提出了TSF (Two-Stage Framework)方法, 利用KG實體間的連接關系構建帶權有向圖, 并基于CoSimRank算法[10]來計算實體間的相關度.這些算法能反映KG中實體間的相關性, 但由于現有KG的知識仍不完整[11], 導致計算結果不夠準確.對此, Yamada等[12]通過將描述實體的詞匯和KG中的實體共同映射到向量空間, 以計算實體間的相關性.該方法雖能將詞匯與KG相結合來發現實體間的相關性,但在映射過程中會損失KG實體間的關系信息, 導致計算結果不夠準確.因此, 為了更準確地計算查詢實體與候選實體間的相關度, 我們提出實體無向帶權圖模型(Entity Undirected Weighted Graph, EUWG).首先,以查詢實體與候選實體作為圖中節點, 基于查詢實體與候選實體間的相關關系來構造無向邊.然后, 通過量化實體在KG向量空間和Web文檔中體現出的相關性, 計算EUWG邊上的權重, 得到查詢實體與候選實體相互間的相關度, 并基于該模型提出一個候選實體打分函數, 通過遍歷EUWG中實體間的路徑計算候選實體的分數, 完成候選實體的排序.

最后, 使用Wikidata數據集, 對所提出的方法進行了實驗測試和性能分析, 與現有的候選實體搜索算法和實體相關度計算模型進行比較, 驗證了本文提出方法的有效性.

2 候選實體搜索

2.1 查詢實體關系選擇

定義1.KG是由實體和關系組成的有向圖, 表示為Gkg=(E,R), 其中,E={e1,e2,…,en}為實體集合,R={r1,r2,…,rm}為關系集合, 任意一條有向邊表示一個三元組(h,r,t) (h,t∈E和r∈R).Gkg也可看作三元組集合.

首先, 將給定的查詢實體記為eq, 為了增加搜索候選實體的效率, 本文提出從全局重要度和局部重要度兩方面來度量關系r對eq的語義表示能力, 去除對eq語義表示能力弱的關系, 減少需計算的關系數量.

(1) 全局重要度, 即關系r在KG中的重要程度.r在Gkg中出現的頻率越高, 其對eq的特殊性就越小, 重要性也就越小.按以下方式計算r對eq的全局重要度:

其中,r′為r在Gkg中出現的次數.

(2) 局部重要度, 即關系r在以查詢實體eq為中心的局部子圖中的重要程度.將KG中與eq直接相連的邊構成的集合記為R′(eq),r在R′(eq)中出現的次數越多, 說明eq通過r連接的實體越多, 進而r對eq就越重要.r在R′(eq)中出現的次數與其重要程度成反比,計算公式如下:

其中,r"為關系r在R′(eq)中出現的次數, |R′(eq)|為R′(eq)中三元組的個數.

然后, 使用超參數α來平衡上述因素對關系r語義表示能力的貢獻.為了統一I1(eq,r)和I2(eq,r)的取值區間, 使用最大最小歸一化函數(Min-Max Scaling)[13]對全局重要度和局部重要度進行處理, 計算公式如下:

其中,α∈[0,1], 為衡量各因素貢獻比重的超參數,Nor(·)為最大最小歸一化函數.

最后, 為了提高候選實體搜索的效率, 通過式(3)計算KG中各關系對查詢實體eq的語義表示能力并對各關系進行排序, 選擇其中得分最高的前k個關系, 記為集合S.

2.2 查詢實體關系選擇

首先, 將KG中的實體通過訓練嵌入到向量空間中, 得到對應的實體向量集E={e1,e2,…,en}, 其中,ej∈E(1≤j≤n)是實體ej的向量表示.將與關系集合S對應的超平面法向量集記為D={d1,d2,…,dk}, 將與集合D中第i個法向量對應的關系記為ri∈R(1≤i≤k).使用式(4)計算實體ej在ri對應超平面上的投影, 如圖1所示.

圖1 實體在各超平面中的投影

然后, 為了正確地在各超平面中搜索候選實體, 將每一個實體向量ej在超平面di(1≤i≤k)上的投影作為該實體在ri對應超平面中的語義表示, 并根據實體在不同超平面中的語義表示, 將具有共同語義特征的實體劃分為一類.具體而言, 由于K-means++算法[14]的效率高、能夠高效地對海量實體進行劃分[15], 因此, 通過投影向量間的余弦相似度表示對應實體在ri下的語義相似度, 使用K-means++對D中各超平面上的實體投影進行聚類, 將與同屬一類的投影所對應的實體作為di上與eq有共同語義特征的實體.選擇每個超平面中都與eq同屬一類的實體, 作為候選實體搜索的結果,計算公式如下:

其中,M(eq)表示候選實體搜索的結果.

算法1.候選實體搜索算法輸入: eq: 給定的查詢實體; Gkg: KG; S: 對eq影響最大的前k種關系集合輸出: M(eq): 候選實體集1.使用TransH將Gkg嵌入到向量空間中, 獲得實體向量集E和與S對應的超平面法向量集D={d1, d2,…, dk}2.for i=1 to k do 3.Ni←? 4.for each ej in E do images/BZ_52_1390_1682_1570_1732.png5.// ej在第i個超平面的投影 images/BZ_52_1429_1737_1454_1787.png images/BZ_52_1992_1737_2017_1787.png6.將 添加到集合Ui中, 將第i個超平面中 與ej的映射關系添加到Ni中7.end for 8.K-means++(Ui) //對Ui中的實體投影進行聚類 images/BZ_52_1631_1944_1656_1994.png9.找到聚類結果中與 同屬一類的投影在Ni中對應的實體, 將實體添加到集合Mi中10.end for 11.M(eq)=M1∩M2∩…∩Mi∩…∩Mk 12.return M(eq)

算法1主要的時間代價是在k個超平面中對實體投影進行聚類, 假設聚類類別數為n′, 每一次聚類的時間復雜度為O(n′n)[14], 因此, 算法1的時間復雜度為O(kn′n).

3 相關實體排序模型

3.1 EUWG模型

將需構造的無向帶權圖記為Geg,V是Geg中的節點, 由查詢實體eq與候選實體組成, 使用V′表示V中除eq外的實體集合.由于查詢實體與各候選實體相關,因此, 先在Geg中構造eq與V′各實體間的無向邊, 然后, 通過計算各候選實體對應向量間的余弦相似度來構建候選實體間的無向邊.將V′中任意兩實體記為vi和vj, 若vi和vj對應向量間的余弦相似度為正, 則在Geg中構造一條vi到vj的無向邊, 表示vi與vj相關.下面給出EUWG模型的定義:

定義2.EUWG模型是一個無向帶權圖, 表示為Geg=(V,L,M), 其中,V=M(eq)∪{eq}為節點集合,L={l1,l2,…,lt}為邊的集合,W={w(vi,vj)|1≤i,j≤s,vi,vj∈V,i≠j}為EUWG邊上的權重集合,w(vi,vj)表示vi和vj間無向邊上的權重.

為了計算Geg中邊上的權重, 并描述節點間的相關程度, 我們考慮以下兩個方面:

(1) 向量相關度.各實體在向量空間中的語義相關度決定其向量間的相關度, 使用實體向量間的余弦相似度來度量.余弦相似度越高, 結構相關度越大.計算方法如下:

其中,Sim(·)表示實體向量間的余弦相似度.

(2) Web文檔相關度, 即Geg中任意兩個節點在Web文檔中共現頻率反映的相關度[3].我們統計Geg中任意兩個節點在Web文檔中共同出現的次數, 次數越多, 相關度越大.將Web文檔集合記為H=(h1,h2,…,hc),計算方法如下:

其中, 若實體vi與vj共同出現在hx(1≤x≤c)中, 則g(hx,vi,vj)為1, 否則為0.

使用超參數β來平衡上述因素對Geg邊上權重的貢獻.為了統一y1(vi,vj)和y2(vi,vj)的取值區間, 使用最大最小歸一化函數對其進行處理:

3.2 候選實體打分排序

Geg中任意兩個節點間有多條路徑, 不同的路徑決定了節點間不同的相關程度.因此, 通過獲取查詢實體eq與候選實體vi∈V′在Geg中的所有路徑來計算每條路徑上權重的平均值, 將其中的最大值作為候選實體vi的分數, 并基于該分數對候選實體進行排序, 計算方法如下:

其中,Zi表示查詢實體eq到候選實體vi所有的路徑集合,zj表示第j條路徑需要經歷的所有實體集合,表示第j條路徑中的第a個實體.

算法2.基于EUWG模型的候選實體排序輸入: eq: 給定的查詢實體; V: 候選實體集M(eq)與查詢實體eq的并集; L: Geg中邊的集合輸出: B: 實體排序結果1.i←1, j←1, tmp_B←?, B←? 2.for each v in V-{eq} do 3.Z←BFS(L, e, eq) //使用廣度優先算法獲取Geg中實體eq到v的所有路徑4.score←0 5.for each z in Z do 6.weight←0 7.for a=0 to |z|-1 do 8.weight←weight+w(za, za+1)9.end for 10.if weight/|z|＞score then //將各路徑權重平均值的最大值作為候選實體分數11.score←weight/|z|12.end for 13.tmp_B←tmp_B∪{(v, score)} //tmp_B保存候選實體v及其分數score組成的二元組(v, score)14.end for 15.根據tmp_B中候選實體的分數, 對實體進行排序, 將排序結果保存在B中16.return B

在算法2中, 假設Geg的節點數為s, 算法主要的時間代價是對s-1個候選實體進行廣度優先搜索,Geg采用鄰接矩陣存儲, 每一次搜索的時間復雜度為O(s2).因此, 算法2的時間復雜度為O(s3).

4 實驗結果

4.1 實驗設置

(1) 數據集與測試環境

為了測試本文提出方法的效果, 使用Wikidata(http://dumps.wikimedia.org/wikidatawiki/entities)作為測試數據集, 并從Wikidata中分別隨機抽取部分三元組, 記為KB50K和KB500K, 統計信息如表1所示.使用KORE[16]與ERT[17]數據集作為驗證數據集, 這兩個數據集均使用人工處理的方法給出了涉及IT、明星、游戲、電視劇、音樂與電影領域的多組查詢實體與候選實體間的相關度, 統計信息如表2所示.同時, 為了構造EUWG模型, 分別使用KORE與ERT數據集中各領域的查詢實體作為關鍵詞搜索Web文檔, 統計信息如表3所示.

表1 測試數據集

表2 驗證數據集

表3 Web文檔數據集

實驗使用E5-2650v3 2.3 GHz處理器, 2080Ti GPU,128 GB內存, 用Python作為編程語言, 并使用Spark和TensorFlow框架作為編程框架.

(2) 測試指標

使用準確率(Precision,P)、召回率(Recall,R)以及F1分值來評價算法1的有效性, 計算方法如下:

其中,TP為被正確搜索到的候選實體數,FP為被錯誤搜索到的候選實體數,FN為未被搜索到的候選實體數.

為了驗證EUWG模型的有效性, 使用皮爾遜相關系數(Pearson Correlation Coefficient,PCC)、斯皮爾曼等級相關系數(Spearman Correlation Rank Coefficient,SCRC)以及調和均值(Harmonic Mean,HM)來評價排序結果.其中PCC表示測試結果與驗證數據集中相關度分數的一致性,SCRC表示測試結果與驗證數據集實體排序的一致性,HM表示測試結果與驗證數據集之間的綜合一致性.計算方法如下:

其中,X為測試結果中的候選實體分數集,Y為驗證數據集中各候選實體的分數集,AC為候選實體數,bi為第i個實體在測試結果中的位置與驗證數據集中位置的差值,PCC、SCRC和HM的值越接近1, 說明結果越好.

4.2 候選實體搜索有效性測試

為了測試實體數量對算法1的影響, 分別在KORE與ERT上測試了候選實體搜索的準確率、召回率和F1值, 如圖2所示.可以看出, 隨著實體數量的增加,各項指標都有所下降.當實體數量從1×105增加到5×105時, 實體數量增加了5倍, 但召回率僅降低了10%.原因在于, 實體數量的增加使得TransH的學習結果更加準確, 并能夠更有效地表示實體的語義, 進而使算法1在大規模的KG上也表現優異.

圖2 實體數對候選實體搜索的影響

然后, 測試了不同聚類類別數對算法1的影響.在各KG中選擇5×105個實體, 取不同的聚類類別數進行測試, 如圖3所示.可以看出, 隨著聚類數的增加, 準確率和F1值都有所上升, 原因在于類別數越多, 候選實體集中被錯誤召回的實體數量所占的比例越小, 進而候選實體搜索的準確性就越高.

圖3 聚類類別數對候選實體搜索的影響

另外, 將本文提出的候選實體搜索算法記為TCES(TransH-based Candidate Entity Search), 從各KG中選擇5×105個實體, 設置聚類類別數為170, 與REFH[4]和LTRC[5]算法進行對比, 如表4所示.可以看出, 算法1在FB50K和FB500K數據集上效果更好, 且在Wikidata上準確率和F1值也高于其他兩種方法.原因在于, 算法1從KG所有實體中尋找候選實體, 搜索范圍更大,進而被正確召回的實體數目更多.

表4 不同KG的候選實體搜索結果

4.3 EUWG模型有效性測試

為了測試KG規模對候選實體排序的影響, 選擇4.5×105個Web文檔, 測試算法2在不同三元組數量下的PCC、SCRC和HM, 如圖4所示.可以看出, 隨著三元組數量增加,PCC、SCRC和HM都有所上升.當三元組數量達到5×106時, 各指標平均增加了29%、17%和25%.原因在于隨著三元組數量的增加, KG中蘊含的知識更加完整, TransH能夠更有效地對KG進行表示, 使得EUWG模型中向量相關度的計算更加準確,進而排序效果有所提升.

圖4 KG規模對候選實體排序的影響

另外, 為了測試不同Web文檔數對相關實體排序的影響, 從各KG中分別選擇5×106個三元組, 測試算法2在不同Web文檔數下的PCC, SCRC和HM, 如圖5所示.可以看出, 隨著Web文檔數增加, 各指標也隨之上升, 當數據量為4.5×105時, 各指標平均提升了41%、30%和34%.原因在于隨著Web文檔數的增加, 其中的知識也隨之增加, 對實體相關性的描述信息也更加豐富, 使得EUWG模型對實體在Web文檔中相關性的量化更加準確, 進而提升了排序效果.

圖5 Web文檔數對候選實體排序的影響

最后, 我們從KG中分別選擇5×106個三元組, 并使用4.5×105個Web文檔和不同領域的查詢實體進行測試, 與 WLM[8]、TSF[9]和 Wikipedia2Vec[12]模型進行比較, 如圖6和圖7所示.可以看出, 本文提出的EUWG模型在實體排序任務中表現較好, 其中, EUWG模型比其他3種方法的PCC高了18%.原因在于Wikipedia2Vec模型在將KG映射為向量時會發生實體和詞匯的匹配錯誤.同時, WLM與TSF模型主要根據KG來計算實體間的相關度, 但KG無法及時地反映真實世界不斷演化的知識, 因此計算結果不夠準確, 而EUWG使用Web文檔和KG共同描述實體間的相關關系, 使得計算結果更加客觀, 進而候選實體的排序結果更好.

圖6 基于FB50K的候選實體排序結果

圖7 基于FB500K的候選實體排序結果

5 結束語

本文提出了基于表示學習的相關實體搜索算法, 通過對向量空間中不同關系超平面上的實體投影進行聚類, 獲得與查詢實體相關的候選實體, 并使用實體帶權無向圖模型對候選實體進行排序.實驗結果表明, 本文提出的方法能夠正確地從KG中搜索候選實體, 同時有效地對候選實體進行排序.但在候選實體排序任務中使用的數據源仍有待進一步擴展.因此, 在未來工作中考慮加入Web應用中與實體相關的圖片數據, 更加客觀全面地描述實體間的關系信息, 提高相關實體搜索的準確性.