于慧琳,陳 煒,王 琪,高建偉,萬懷宇
北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,北京100044
知識圖譜作為一種結(jié)構(gòu)化的語義表示,可以對現(xiàn)實(shí)世界中的實(shí)體、概念、屬性以及它們之間的關(guān)系進(jìn)行建模。通常知識圖譜中的知識并不是完整的,存在實(shí)體或者關(guān)系缺失等問題,如圖1(a)中,實(shí)體Charlotte Bronte 與Writer 之間缺失Profession關(guān)系。面對知識圖譜中的信息缺失問題,需要通過現(xiàn)有的知識推導(dǎo)出潛在的實(shí)體或關(guān)系,完善知識圖譜中的知識,為許多下游任務(wù)提供知識支持,例如問答系統(tǒng)、推薦系統(tǒng)、信息檢索等。
知識圖譜關(guān)系推理旨在從現(xiàn)有數(shù)據(jù)中識別和推斷出新的關(guān)系。知識圖譜關(guān)系推理可以分為單步推理和多步推理。單步推理主要是基于表示學(xué)習(xí)的方法如TransE、TransR等,通過距離打分函數(shù)來度量向量化后的實(shí)體與關(guān)系進(jìn)而預(yù)測實(shí)體間的關(guān)系。由于實(shí)體向量和關(guān)系向量缺乏明確含義,基于表示學(xué)習(xí)的方法存在可解釋性較差的問題。為了解決這一問題,研究者們提出了基于路徑的多步推理方法,如推理鏈、PathRNN等,此類方法主要通過神經(jīng)網(wǎng)絡(luò)挖掘?qū)嶓w之間的路徑關(guān)系進(jìn)行關(guān)系推理。近年來,一些研究者將強(qiáng)化學(xué)習(xí)融入到路徑推理中,如Deep-Path、MINERVA等,通過提升關(guān)系路徑構(gòu)建的準(zhǔn)確性來提高推理效果。雖然基于路徑的方法具有更好的可解釋性,但它們往往只考慮所選取的單條路徑對關(guān)系的影響,忽視了多條路徑上的實(shí)體信息和節(jié)點(diǎn)之間的相關(guān)性。同時(shí),基于強(qiáng)化學(xué)習(xí)的路徑推理方法在遇到選取路徑錯(cuò)誤的情況時(shí),還會出現(xiàn)誤差累積的問題,產(chǎn)生不理想的推理結(jié)果。如圖1(a)所示,若只選取路徑Charlotte Bronte→HasFather→Patrick Bronte→Profession→Writer,就會推理出關(guān)系Charlotte Bronte→Profession→Writer,這意味著使用父親的職業(yè)來直接推測兒子的職業(yè),顯然是不合理的。由于單條路徑所包含的語義信息不足,常常無法有效地推理出實(shí)體間的關(guān)系。
針對上述問題,本文考慮多條路徑包含的豐富信息,提出了基于子圖的關(guān)系預(yù)測方法SubGLP(subgraph link prediction)。如圖1(b)所示,將多條路徑構(gòu)建成子圖,使用子圖推理預(yù)測實(shí)體之間的關(guān)系,不僅可以解決表示學(xué)習(xí)的可解釋性問題,還能緩解路徑推理的誤差累積問題,進(jìn)而完成穩(wěn)定高效的關(guān)系推理。具體而言,本文方法首先基于實(shí)體對構(gòu)建節(jié)點(diǎn)子圖,獲取實(shí)體間結(jié)構(gòu)化的實(shí)體和關(guān)系信息;然后使用高階圖神經(jīng)網(wǎng)絡(luò)(-GNNs)更新子圖表示,以此來獲取子圖的高階特征;最后通過聚合操作將子圖表示作為實(shí)體之間的關(guān)系特征,完成實(shí)體間關(guān)系的推理。本文的主要貢獻(xiàn)總結(jié)如下:
圖1 知識圖譜推理方法轉(zhuǎn)變Fig.1 Transformation of reasoning method of knowledge graph
(1)提出了基于子圖推理的知識圖譜關(guān)系預(yù)測方法SubGLP,該方法結(jié)合表示學(xué)習(xí)與路徑推理的優(yōu)勢,使用具有豐富信息的子圖結(jié)構(gòu)獲取實(shí)體對的鄰域結(jié)構(gòu)信息,實(shí)現(xiàn)實(shí)體之間的關(guān)系預(yù)測。
(2)分別從實(shí)體層面和關(guān)系層面出發(fā),構(gòu)建節(jié)點(diǎn)子圖和關(guān)系子圖,并使用圖神經(jīng)網(wǎng)絡(luò)來融合節(jié)點(diǎn)子圖和關(guān)系子圖的高階特征信息,從而獲得更豐富的實(shí)體關(guān)系特征。
(3)在兩個(gè)廣泛使用的基準(zhǔn)數(shù)據(jù)集FB15K-237和NELL-995 上分別對SubGLP 模型進(jìn)行了評估,實(shí)驗(yàn)結(jié)果表明,SubGLP 模型明顯優(yōu)于現(xiàn)有的單步推理和多步推理的方法,同時(shí)驗(yàn)證了模型在大規(guī)模知識圖譜推理任務(wù)上的有效性。
傳統(tǒng)的知識圖譜關(guān)系推理的方法主要是基于人工制定的規(guī)則進(jìn)行的,如一階歸納學(xué)習(xí)方法(first order inductive learner,F(xiàn)OIL),從一個(gè)關(guān)系表示派生出一組特征的一階推理方法(kernel first order inductive learner,kFOIL)等。隨著深度學(xué)習(xí)的發(fā)展,許多神經(jīng)網(wǎng)絡(luò)模型在解決關(guān)系推理問題上也取得了很好的效果,它們大致可以被分為單步推理和多步推理。其中,單步推理主要利用表示學(xué)習(xí)方法中的距離打分函數(shù)來預(yù)測實(shí)體間的關(guān)系,多步推理則利用實(shí)體間路徑作為特征來預(yù)測實(shí)體間的關(guān)系。
早期的基于表示學(xué)習(xí)的方法是Bordes 等人于2013 年提出的知識表示學(xué)習(xí)模型TransE,該模型將知識圖譜中的實(shí)體與關(guān)系映射到低維向量空間中,得到實(shí)體與關(guān)系的向量表示,并使用頭尾實(shí)體的向量差來表示關(guān)系。由于TransE 模型在處理一對多、多對一、多對多復(fù)雜關(guān)系時(shí)具有一定的局限性,一些研究者后來相繼提出TransH、TransR和TransD等模型來解決這一問題?;诒硎緦W(xué)習(xí)的方法雖然具備較強(qiáng)的可擴(kuò)展性,但實(shí)體向量和關(guān)系向量都缺乏明確的含義,存在可解釋性弱的缺點(diǎn)。多步推理主要是通過挖掘知識圖譜中路徑的語義信息來進(jìn)行實(shí)體間的關(guān)系預(yù)測。例如Neelakantan 等利用隨機(jī)游走的方法來生成路徑,并通過遞歸神經(jīng)網(wǎng)絡(luò)(recurrent neural network,RNN)來實(shí)現(xiàn)多跳關(guān)系推理。但是,這些方法并不能很好地識別實(shí)體之間的關(guān)鍵路徑信息。
為了提高基于路徑推理中路徑查找的準(zhǔn)確性,研究者們開始嘗試將強(qiáng)化學(xué)習(xí)應(yīng)用到路徑推理中。Xiong 等人提出了一種新的DeepPath 框架,采用強(qiáng)化學(xué)習(xí)方法進(jìn)行路徑查找,以此來解決多跳推理問題。隨后,Das 等人提出了一種優(yōu)化的強(qiáng)化學(xué)習(xí)方法MINERVA,使用長短期記憶網(wǎng)絡(luò)(long short-term memory,LSTM)來學(xué)習(xí)歷史狀態(tài)的表示。近年來,MARLPaR(multi-agent and reinforcement learning based method for path reasoning)、M-Walk、RLH(reasoning like human)等方法紛紛將不同的強(qiáng)化學(xué)習(xí)策略應(yīng)用到路徑推理中,取得了效果上的提升。雖然基于路徑的推理在一定程度上解決了表示推理存在的問題,但基于路徑的方法尤其是結(jié)合強(qiáng)化學(xué)習(xí)的路徑推理過分依賴于單一路徑,無法綜合利用多條路徑的豐富信息,對關(guān)系特征的捕獲并不全面。
為了解決上述基于路徑推理中存在的路徑選取單一和誤差累積等問題,本文將基于路徑的推理轉(zhuǎn)化為基于子圖的推理,綜合考慮多條路徑上的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系等更豐富的語義信息,從而更有效地進(jìn)行實(shí)體間的關(guān)系推理。
本章首先對知識圖譜關(guān)系預(yù)測問題進(jìn)行形式化定義,并介紹相關(guān)概念的符號表示,最后詳細(xì)介紹SubGLP 的整體框架與細(xì)節(jié)描述。
將知識圖譜定義為有向圖G=(,),其中和分別表示圖中的節(jié)點(diǎn)和邊的集合。知識圖譜G 由許多三元組(,,)構(gòu)成,其中、分別表示頭、尾實(shí)體,表示實(shí)體間的關(guān)系。知識圖譜關(guān)系預(yù)測的目標(biāo)就是在給定頭實(shí)體、實(shí)體的條件下,預(yù)測出實(shí)體間的關(guān)系,即解決實(shí)體間的關(guān)系推理(,?,)問題。
本文提出的模型框架如圖2 所示,該框架主要包含以下三部分:
圖2 SubGLP 模型框架圖Fig.2 Framework of SubGLP
(1)子圖抽取模塊:基于實(shí)體對(,),使用雙向?qū)挾葍?yōu)先搜索(breath first search,BFS)策略,分別構(gòu)建實(shí)體對的節(jié)點(diǎn)子圖S和邊子圖S,并使用TransR預(yù)訓(xùn)練整個(gè)知識圖譜得到實(shí)體和關(guān)系的嵌入表示l、l,然后將子圖結(jié)構(gòu)S、S與實(shí)體表示l、關(guān)系表示l組合得到具有節(jié)點(diǎn)向量表示的兩個(gè)子圖()和()。
(2)子圖表示模塊:將具有向量表示的節(jié)點(diǎn)子圖() 和邊子圖() 分別輸入高階圖神經(jīng)網(wǎng)絡(luò)-GNNs 進(jìn)行訓(xùn)練,并進(jìn)行多段池化,得到節(jié)點(diǎn)子圖和邊子圖的向量表示L和L,從而捕獲子圖中的實(shí)體和關(guān)系結(jié)構(gòu)等多層次信息。
(3)融合預(yù)測模塊:融合所得到的子圖特征,進(jìn)行非線性激活后計(jì)算關(guān)系存在的概率(|,),實(shí)現(xiàn)實(shí)體間的關(guān)系推理。
首先根據(jù)給定的實(shí)體對,在知識圖譜中查找實(shí)體之間連通路徑。由于實(shí)體之間路徑眾多,為了提高搜索效率,分別從頭、尾實(shí)體出發(fā)進(jìn)行雙向廣度優(yōu)先搜索,以此來完成實(shí)體對路徑的查找。為了獲取更加豐富和完整的路徑信息,本文將反向關(guān)系也添加到了知識圖譜中,即針對每個(gè)三元組(,,),增加了反向三元組(,,),并允許在路徑中對節(jié)點(diǎn)進(jìn)行多次訪問。
假設(shè)在實(shí)體對(,)間找到了條路徑,將第條路徑表示為p,即路徑p從頭實(shí)體出發(fā),經(jīng)過路徑→→…到達(dá)尾實(shí)體:
在路徑構(gòu)建完成后,分別將節(jié)點(diǎn)路徑和關(guān)系路徑組合成節(jié)點(diǎn)子圖S與邊子圖S:
處理后的S與S包含各自的圖結(jié)構(gòu)信息。同時(shí),為了將知識圖譜中的實(shí)體、關(guān)系轉(zhuǎn)化為可訓(xùn)練的向量表示,本文使用TransR對整個(gè)知識圖譜進(jìn)行預(yù)訓(xùn)練,分別得到實(shí)體和關(guān)系的向量表示l、l。
圖神經(jīng)網(wǎng)絡(luò)(graph neural networks,GNN)是一種專門處理圖結(jié)構(gòu)信息的神經(jīng)網(wǎng)絡(luò)模型,它主要是通過聚合圖中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)特征,并結(jié)合節(jié)點(diǎn)自身特征信息來完成節(jié)點(diǎn)更新。用()表示知識圖譜中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合,以節(jié)點(diǎn)子圖為例,使用()代表具有預(yù)訓(xùn)練表示的節(jié)點(diǎn)子圖(S,l)。使用GNN更新節(jié)點(diǎn)信息的計(jì)算公式如下:
通過定義→R以及與有且僅有-1 個(gè)公共節(jié)點(diǎn)的鄰居子圖(),以便于-GNNs 在建模時(shí)可以獲取更多的高階信息。使用-GNNs 更新子圖節(jié)點(diǎn)表示方法如下:
更新節(jié)點(diǎn)特征后,使用Top-池化進(jìn)行下采樣,來縮小圖規(guī)模,獲取關(guān)鍵特征,再將全局平均池化(global average pooling,GAP)結(jié)果與全局最大池化(global max pooling,GMP)結(jié)果拼接,求和作為子圖特征:
其中,H為下采樣后的子圖,L為拼接后的節(jié)點(diǎn)子圖S的表示向量。
使用同樣的方法,得到邊子圖的表示向量L。
將節(jié)點(diǎn)子圖表示L與邊子圖表示L輸入到雙層感知機(jī)中,通過非線性變換得到壓縮節(jié)點(diǎn)子圖表示g與邊子圖表示g,同樣以節(jié)點(diǎn)子圖為例:
為了能夠準(zhǔn)確表示實(shí)體信息與實(shí)體之間的關(guān)系情況,將節(jié)點(diǎn)子圖表示g與邊子圖表示g拼接得到完整子圖表示,然后送入Softmax 分類器中計(jì)算實(shí)體對(,)中關(guān)系存在的概率(|,):
接著,采用交叉熵?fù)p失函數(shù)優(yōu)化模型:
其中,表示模型的所有參數(shù),為實(shí)體對的標(biāo)簽。(|,,)表示實(shí)體對(,)預(yù)測關(guān)系為的概率。
SubGLP 算法的整體流程如算法1 所示,由于各個(gè)模塊在上文進(jìn)行了詳細(xì)解釋,這里進(jìn)行簡要概括。
SubGLP 模型算法
為了驗(yàn)證SubGLP 模型的有效性,本文在兩個(gè)基準(zhǔn)數(shù)據(jù)集上分別進(jìn)行了實(shí)驗(yàn),并與基于表示的方法和基于路徑的方法進(jìn)行了對比分析。
本文在FB15K-237 數(shù)據(jù)集與NELL-995 數(shù)據(jù)集上分別進(jìn)行測試以驗(yàn)證SubGLP 模型的有效性。其中FB15K-237 是Freebase 的子集,包含237 種關(guān)系、14 000 種實(shí)體和310 000 組三元組,從中抽取10 種關(guān)系進(jìn)行測試,關(guān)系類型包括出生地、國籍、首都、導(dǎo)演、編劇等。NELL-995 是卡內(nèi)基梅隆大學(xué)發(fā)布的數(shù)據(jù)集,包含200 種關(guān)系、75 000 種實(shí)體和154 000 組三元組,同樣從中抽取10 種關(guān)系進(jìn)行測試,關(guān)系類型包含出生地、歸屬地區(qū)、雇傭關(guān)系等,如表1 所示。
表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental datasets
對于每個(gè)關(guān)系推理任務(wù),設(shè)置雙向BFS 查找路徑數(shù)=5,預(yù)訓(xùn)練后的實(shí)體和關(guān)系向量的維度=100,劃分=128,-GNNs 維度128。在池化部分設(shè)置Top-池化比率為0.8,非線性變換維度=256,=128,=64,=2,dropout 比例為0.5,模型學(xué)習(xí)率=0.000 5。實(shí)驗(yàn)采用平均精度均值(mean average precision,MAP)作為評價(jià)指標(biāo),訓(xùn)練集、測試集劃分比例為7∶3。
本文將模型與六種關(guān)系推理方法進(jìn)行比較,其中前兩種模型(TransE 和TransR)使用單步推理,即基于表示學(xué)習(xí)的方法,后四種模型(DeepPath、MINERVA、M-Walk 和RLH)使用多步推理,即基于路徑的方法。
TransE:一種經(jīng)典表示學(xué)習(xí)模型,它將知識圖譜中的實(shí)體與關(guān)系映射到同一個(gè)低維向量空間中,使用頭尾實(shí)體的向量差來預(yù)測關(guān)系。
TransR:TransR 與TransE 將實(shí)體和關(guān)系嵌入在相同空間的方法不同,TransR 分別在實(shí)體空間和關(guān)系空間構(gòu)建實(shí)體和關(guān)系嵌入。
DeepPath:一種用于學(xué)習(xí)多跳關(guān)系路徑的強(qiáng)化學(xué)習(xí)框架,使用強(qiáng)化學(xué)習(xí)自動探索路徑,并設(shè)計(jì)考慮準(zhǔn)確性、多樣性和效率的獎勵函數(shù),來解決知識圖譜中的多跳推理問題。
MINERVA:一種將查詢條件引入到強(qiáng)化學(xué)習(xí)路徑搜索中的方法,將推理問題形式化為一個(gè)馬爾可夫決策過程,使用LSTM 表示觀察序列和歷史決策序列,解決知識圖譜的問答問題。
M-Walk:在DeepPath 的基礎(chǔ)上使用蒙特卡洛樹(Monte-Carlo tree search,MCTS)策略幫助代理在圖中搜索路徑,從而嘗試在稀疏獎勵的環(huán)境下提升路徑搜索的準(zhǔn)確性。
RLH:一個(gè)基于分層強(qiáng)化學(xué)習(xí)的知識圖譜推理模型,用于解決知識圖譜多跳推理過程的多語義問題。
表2 和表3 展示了不同算法的實(shí)驗(yàn)結(jié)果,從中可以看出,基于強(qiáng)化學(xué)習(xí)的路徑推理方法(DeepPath、MINERVA、M-Walk 和RLH)整體效果要優(yōu)于基于表示學(xué)習(xí)的方法(TransE 和TransR)。這表明路徑中可以包含更加豐富的語義信息,通過挖掘?qū)嶓w之間的路徑信息能有效地提高關(guān)系推理的準(zhǔn)確性。而本文提出的SubGLP 模型優(yōu)于基于路徑的推理方法,在兩個(gè)數(shù)據(jù)集上比效果次好的RLH 模型的MAP 平均值分別高出0.060 與0.017,且比TransE 的MAP 平均值分別高出0.199 與0.190,這也驗(yàn)證了實(shí)體間的子圖比實(shí)體間的單一路徑具備更豐富的語義特征,有助于獲取實(shí)體之間的關(guān)系特征,提升關(guān)系推理效果。
表2 FB15K-237 數(shù)據(jù)集上的關(guān)系推理(MAP)實(shí)驗(yàn)結(jié)果Table 2 Link prediction results(MAP)on FB15K-237 datasets
表3 NELL-995 數(shù)據(jù)集上的關(guān)系推理(MAP)實(shí)驗(yàn)結(jié)果Table 3 Link prediction results(MAP)on NELL-995 datasets
在分析路徑與子圖的區(qū)別時(shí),也注意到由于基于路徑的方法使用的信息量較少,當(dāng)某些關(guān)系可以使用單條路經(jīng)來明確指向時(shí),如NELL-995 數(shù)據(jù)集上的athletePlaysInLeague 關(guān)系使用關(guān)系路徑athletePlays-ForTeam →teamPlaysInLeague 會產(chǎn)生很好的推理結(jié)果,使得基于路徑的方法的實(shí)驗(yàn)結(jié)果也相對較好。
為了分析SubGLP 模型在兩個(gè)數(shù)據(jù)集上的效果差異,分別統(tǒng)計(jì)了兩個(gè)數(shù)據(jù)集上子圖的平均節(jié)點(diǎn)數(shù)與邊數(shù),統(tǒng)計(jì)結(jié)果如圖3 所示??梢奆B15K-237 數(shù)據(jù)集中的子圖規(guī)模更小,NELL-995 數(shù)據(jù)集的子圖則包含了更多節(jié)點(diǎn)和邊,這解釋了模型在NELL-995 數(shù)據(jù)集上效果更好、更穩(wěn)定的原因,也說明了內(nèi)容越豐富的子圖對于關(guān)系推理具有更加積極的作用。
圖3 兩種數(shù)據(jù)集抽取的子圖信息比較Fig.3 Subgraph statistics comparison of two datasets
為了進(jìn)一步驗(yàn)證模型的有效性,通過消融實(shí)驗(yàn)來證明各個(gè)模塊的作用,探究實(shí)體與關(guān)系對關(guān)系預(yù)測的不同影響。在實(shí)驗(yàn)中,刪除了完整模型中的子圖拼接模塊,分別使用節(jié)點(diǎn)子圖和邊子圖來表示預(yù)測實(shí)體之間的關(guān)系。其中,僅使用節(jié)點(diǎn)子圖的方法稱為SubGLP-nod,僅使用邊子圖的方法稱為SubGLPedg,實(shí)驗(yàn)結(jié)果如表4 所示。從表中可以看出,不論是節(jié)點(diǎn)子圖還是邊子圖,都能帶來實(shí)驗(yàn)效果的提升,其中節(jié)點(diǎn)子圖在兩個(gè)數(shù)據(jù)集上分別比RLH 的MAP 值平均高出0.041 與0.015,邊子圖在兩個(gè)數(shù)據(jù)集上分別比RLH 的MAP 平均值高出0.032 與0.003,這也驗(yàn)證了基于子圖的關(guān)系推理的優(yōu)勢。
表4 消融實(shí)驗(yàn)結(jié)果Table 4 Ablation experiment results
此外,從消融實(shí)驗(yàn)中還可以看出節(jié)點(diǎn)子圖的效果比邊子圖的效果好,且在數(shù)據(jù)集FB15K-237 上的filmWrittenBy 關(guān)系和NELL-995 上的athletePlaysSport與athletePlaysForTeam 關(guān)系上,單獨(dú)的節(jié)點(diǎn)子圖具有比融合兩個(gè)子圖更好的效果,這說明實(shí)體信息對關(guān)系推理具有更重要的作用。同樣地,從消融實(shí)驗(yàn)中還可以看出本文提出的SubGLP 方法與單獨(dú)使用節(jié)點(diǎn)子圖或邊子圖相比,MAP 值均有提升,這也說明模型使用融合兩種子圖信息的方法可以捕獲實(shí)體間的更多鄰域信息,這對于解決關(guān)系推理問題是更有效的。
本文將圖神經(jīng)網(wǎng)絡(luò)與知識圖譜推理相結(jié)合,提出了基于子圖推理的知識圖譜關(guān)系預(yù)測方法SubGLP。為了獲取實(shí)體間更豐富的信息,采取了先分別構(gòu)建節(jié)點(diǎn)子圖和邊子圖,然后使用圖神經(jīng)網(wǎng)絡(luò)獲取子圖高階語義特征,最后融合兩個(gè)子圖的語義特征來預(yù)測實(shí)體之間關(guān)系的方法。在兩個(gè)基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法優(yōu)于現(xiàn)有的基于單步推理與多步推理的關(guān)系預(yù)測方法。