使用子圖推理實現(xiàn)知識圖譜關(guān)系預(yù)測

于慧琳，陳 煒，王 琪，高建偉，萬懷宇

北京交通大學 計算機與信息技術(shù)學院，北京100044

知識圖譜作為一種結(jié)構(gòu)化的語義表示，可以對現(xiàn)實世界中的實體、概念、屬性以及它們之間的關(guān)系進行建模。通常知識圖譜中的知識并不是完整的，存在實體或者關(guān)系缺失等問題，如圖1（a）中，實體Charlotte Bronte 與Writer 之間缺失Profession關(guān)系。面對知識圖譜中的信息缺失問題，需要通過現(xiàn)有的知識推導出潛在的實體或關(guān)系，完善知識圖譜中的知識，為許多下游任務(wù)提供知識支持，例如問答系統(tǒng)、推薦系統(tǒng)、信息檢索等。

知識圖譜關(guān)系推理旨在從現(xiàn)有數(shù)據(jù)中識別和推斷出新的關(guān)系。知識圖譜關(guān)系推理可以分為單步推理和多步推理。單步推理主要是基于表示學習的方法如TransE、TransR等，通過距離打分函數(shù)來度量向量化后的實體與關(guān)系進而預(yù)測實體間的關(guān)系。由于實體向量和關(guān)系向量缺乏明確含義，基于表示學習的方法存在可解釋性較差的問題。為了解決這一問題，研究者們提出了基于路徑的多步推理方法，如推理鏈、PathRNN等，此類方法主要通過神經(jīng)網(wǎng)絡(luò)挖掘?qū)嶓w之間的路徑關(guān)系進行關(guān)系推理。近年來，一些研究者將強化學習融入到路徑推理中，如Deep-Path、MINERVA等，通過提升關(guān)系路徑構(gòu)建的準確性來提高推理效果。雖然基于路徑的方法具有更好的可解釋性，但它們往往只考慮所選取的單條路徑對關(guān)系的影響，忽視了多條路徑上的實體信息和節(jié)點之間的相關(guān)性。同時，基于強化學習的路徑推理方法在遇到選取路徑錯誤的情況時，還會出現(xiàn)誤差累積的問題，產(chǎn)生不理想的推理結(jié)果。如圖1（a）所示，若只選取路徑Charlotte Bronte→HasFather→Patrick Bronte→Profession→Writer，就會推理出關(guān)系Charlotte Bronte→Profession→Writer，這意味著使用父親的職業(yè)來直接推測兒子的職業(yè)，顯然是不合理的。由于單條路徑所包含的語義信息不足，常常無法有效地推理出實體間的關(guān)系。

針對上述問題，本文考慮多條路徑包含的豐富信息，提出了基于子圖的關(guān)系預(yù)測方法SubGLP（subgraph link prediction）。如圖1（b）所示，將多條路徑構(gòu)建成子圖，使用子圖推理預(yù)測實體之間的關(guān)系，不僅可以解決表示學習的可解釋性問題，還能緩解路徑推理的誤差累積問題，進而完成穩(wěn)定高效的關(guān)系推理。具體而言，本文方法首先基于實體對構(gòu)建節(jié)點子圖，獲取實體間結(jié)構(gòu)化的實體和關(guān)系信息；然后使用高階圖神經(jīng)網(wǎng)絡(luò)（-GNNs）更新子圖表示，以此來獲取子圖的高階特征；最后通過聚合操作將子圖表示作為實體之間的關(guān)系特征，完成實體間關(guān)系的推理。本文的主要貢獻總結(jié)如下：

圖1 知識圖譜推理方法轉(zhuǎn)變Fig.1 Transformation of reasoning method of knowledge graph

（1）提出了基于子圖推理的知識圖譜關(guān)系預(yù)測方法SubGLP，該方法結(jié)合表示學習與路徑推理的優(yōu)勢，使用具有豐富信息的子圖結(jié)構(gòu)獲取實體對的鄰域結(jié)構(gòu)信息，實現(xiàn)實體之間的關(guān)系預(yù)測。

（2）分別從實體層面和關(guān)系層面出發(fā)，構(gòu)建節(jié)點子圖和關(guān)系子圖，并使用圖神經(jīng)網(wǎng)絡(luò)來融合節(jié)點子圖和關(guān)系子圖的高階特征信息，從而獲得更豐富的實體關(guān)系特征。

（3）在兩個廣泛使用的基準數(shù)據(jù)集FB15K-237和NELL-995 上分別對SubGLP 模型進行了評估，實驗結(jié)果表明，SubGLP 模型明顯優(yōu)于現(xiàn)有的單步推理和多步推理的方法，同時驗證了模型在大規(guī)模知識圖譜推理任務(wù)上的有效性。

1 相關(guān)工作

傳統(tǒng)的知識圖譜關(guān)系推理的方法主要是基于人工制定的規(guī)則進行的，如一階歸納學習方法（first order inductive learner，F(xiàn)OIL），從一個關(guān)系表示派生出一組特征的一階推理方法（kernel first order inductive learner，kFOIL）等。隨著深度學習的發(fā)展，許多神經(jīng)網(wǎng)絡(luò)模型在解決關(guān)系推理問題上也取得了很好的效果，它們大致可以被分為單步推理和多步推理。其中，單步推理主要利用表示學習方法中的距離打分函數(shù)來預(yù)測實體間的關(guān)系，多步推理則利用實體間路徑作為特征來預(yù)測實體間的關(guān)系。

早期的基于表示學習的方法是Bordes 等人于2013 年提出的知識表示學習模型TransE，該模型將知識圖譜中的實體與關(guān)系映射到低維向量空間中，得到實體與關(guān)系的向量表示，并使用頭尾實體的向量差來表示關(guān)系。由于TransE 模型在處理一對多、多對一、多對多復雜關(guān)系時具有一定的局限性，一些研究者后來相繼提出TransH、TransR和TransD等模型來解決這一問題。基于表示學習的方法雖然具備較強的可擴展性，但實體向量和關(guān)系向量都缺乏明確的含義，存在可解釋性弱的缺點。多步推理主要是通過挖掘知識圖譜中路徑的語義信息來進行實體間的關(guān)系預(yù)測。例如Neelakantan 等利用隨機游走的方法來生成路徑，并通過遞歸神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）來實現(xiàn)多跳關(guān)系推理。但是，這些方法并不能很好地識別實體之間的關(guān)鍵路徑信息。

為了提高基于路徑推理中路徑查找的準確性，研究者們開始嘗試將強化學習應(yīng)用到路徑推理中。Xiong 等人提出了一種新的DeepPath 框架，采用強化學習方法進行路徑查找，以此來解決多跳推理問題。隨后，Das 等人提出了一種優(yōu)化的強化學習方法MINERVA，使用長短期記憶網(wǎng)絡(luò)（long short-term memory，LSTM）來學習歷史狀態(tài)的表示。近年來，MARLPaR（multi-agent and reinforcement learning based method for path reasoning）、M-Walk、RLH（reasoning like human）等方法紛紛將不同的強化學習策略應(yīng)用到路徑推理中，取得了效果上的提升。雖然基于路徑的推理在一定程度上解決了表示推理存在的問題，但基于路徑的方法尤其是結(jié)合強化學習的路徑推理過分依賴于單一路徑，無法綜合利用多條路徑的豐富信息，對關(guān)系特征的捕獲并不全面。

為了解決上述基于路徑推理中存在的路徑選取單一和誤差累積等問題，本文將基于路徑的推理轉(zhuǎn)化為基于子圖的推理，綜合考慮多條路徑上的節(jié)點以及節(jié)點之間的關(guān)系等更豐富的語義信息，從而更有效地進行實體間的關(guān)系推理。

2 基于子圖推理的知識圖譜關(guān)系預(yù)測

本章首先對知識圖譜關(guān)系預(yù)測問題進行形式化定義，并介紹相關(guān)概念的符號表示，最后詳細介紹SubGLP 的整體框架與細節(jié)描述。

2.1 基本定義

將知識圖譜定義為有向圖G=(,)，其中和分別表示圖中的節(jié)點和邊的集合。知識圖譜G 由許多三元組(,,)構(gòu)成，其中、分別表示頭、尾實體，表示實體間的關(guān)系。知識圖譜關(guān)系預(yù)測的目標就是在給定頭實體、實體的條件下，預(yù)測出實體間的關(guān)系，即解決實體間的關(guān)系推理(,?,)問題。

2.2 模型框架

本文提出的模型框架如圖2 所示，該框架主要包含以下三部分：

圖2 SubGLP 模型框架圖Fig.2 Framework of SubGLP

（1）子圖抽取模塊：基于實體對(,)，使用雙向?qū)挾葍?yōu)先搜索（breath first search，BFS）策略，分別構(gòu)建實體對的節(jié)點子圖S和邊子圖S，并使用TransR預(yù)訓練整個知識圖譜得到實體和關(guān)系的嵌入表示l、l，然后將子圖結(jié)構(gòu)S、S與實體表示l、關(guān)系表示l組合得到具有節(jié)點向量表示的兩個子圖()和()。

（2）子圖表示模塊：將具有向量表示的節(jié)點子圖() 和邊子圖() 分別輸入高階圖神經(jīng)網(wǎng)絡(luò)-GNNs 進行訓練，并進行多段池化，得到節(jié)點子圖和邊子圖的向量表示L和L，從而捕獲子圖中的實體和關(guān)系結(jié)構(gòu)等多層次信息。

（3）融合預(yù)測模塊：融合所得到的子圖特征，進行非線性激活后計算關(guān)系存在的概率(|,)，實現(xiàn)實體間的關(guān)系推理。

2.3 子圖抽取

首先根據(jù)給定的實體對，在知識圖譜中查找實體之間連通路徑。由于實體之間路徑眾多，為了提高搜索效率，分別從頭、尾實體出發(fā)進行雙向廣度優(yōu)先搜索，以此來完成實體對路徑的查找。為了獲取更加豐富和完整的路徑信息，本文將反向關(guān)系也添加到了知識圖譜中，即針對每個三元組(,,)，增加了反向三元組(,,)，并允許在路徑中對節(jié)點進行多次訪問。

假設(shè)在實體對(,)間找到了條路徑，將第條路徑表示為p，即路徑p從頭實體出發(fā)，經(jīng)過路徑→→…到達尾實體：

在路徑構(gòu)建完成后，分別將節(jié)點路徑和關(guān)系路徑組合成節(jié)點子圖S與邊子圖S：

處理后的S與S包含各自的圖結(jié)構(gòu)信息。同時，為了將知識圖譜中的實體、關(guān)系轉(zhuǎn)化為可訓練的向量表示，本文使用TransR對整個知識圖譜進行預(yù)訓練，分別得到實體和關(guān)系的向量表示l、l。

2.4 子圖表示

圖神經(jīng)網(wǎng)絡(luò)（graph neural networks，GNN）是一種專門處理圖結(jié)構(gòu)信息的神經(jīng)網(wǎng)絡(luò)模型，它主要是通過聚合圖中節(jié)點的鄰居節(jié)點特征，并結(jié)合節(jié)點自身特征信息來完成節(jié)點更新。用()表示知識圖譜中節(jié)點的鄰居節(jié)點集合，以節(jié)點子圖為例，使用()代表具有預(yù)訓練表示的節(jié)點子圖(S,l)。使用GNN更新節(jié)點信息的計算公式如下：

通過定義→R以及與有且僅有-1 個公共節(jié)點的鄰居子圖()，以便于-GNNs 在建模時可以獲取更多的高階信息。使用-GNNs 更新子圖節(jié)點表示方法如下：

更新節(jié)點特征后，使用Top-池化進行下采樣，來縮小圖規(guī)模，獲取關(guān)鍵特征，再將全局平均池化（global average pooling，GAP）結(jié)果與全局最大池化（global max pooling，GMP）結(jié)果拼接，求和作為子圖特征：

其中，H為下采樣后的子圖，L為拼接后的節(jié)點子圖S的表示向量。

使用同樣的方法，得到邊子圖的表示向量L。

2.5 融合預(yù)測

將節(jié)點子圖表示L與邊子圖表示L輸入到雙層感知機中，通過非線性變換得到壓縮節(jié)點子圖表示g與邊子圖表示g，同樣以節(jié)點子圖為例：

為了能夠準確表示實體信息與實體之間的關(guān)系情況，將節(jié)點子圖表示g與邊子圖表示g拼接得到完整子圖表示，然后送入Softmax 分類器中計算實體對(,)中關(guān)系存在的概率(|,)：

接著，采用交叉熵損失函數(shù)優(yōu)化模型：

其中，表示模型的所有參數(shù)，為實體對的標簽。(|,,)表示實體對(,)預(yù)測關(guān)系為的概率。

SubGLP 算法的整體流程如算法1 所示，由于各個模塊在上文進行了詳細解釋，這里進行簡要概括。

SubGLP 模型算法

3 實驗與結(jié)果分析

為了驗證SubGLP 模型的有效性，本文在兩個基準數(shù)據(jù)集上分別進行了實驗，并與基于表示的方法和基于路徑的方法進行了對比分析。

3.1 實驗數(shù)據(jù)集

本文在FB15K-237 數(shù)據(jù)集與NELL-995 數(shù)據(jù)集上分別進行測試以驗證SubGLP 模型的有效性。其中FB15K-237 是Freebase 的子集，包含237 種關(guān)系、14 000 種實體和310 000 組三元組，從中抽取10 種關(guān)系進行測試，關(guān)系類型包括出生地、國籍、首都、導演、編劇等。NELL-995 是卡內(nèi)基梅隆大學發(fā)布的數(shù)據(jù)集，包含200 種關(guān)系、75 000 種實體和154 000 組三元組，同樣從中抽取10 種關(guān)系進行測試，關(guān)系類型包含出生地、歸屬地區(qū)、雇傭關(guān)系等，如表1 所示。

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets

3.2 參數(shù)設(shè)置與評估指標

對于每個關(guān)系推理任務(wù)，設(shè)置雙向BFS 查找路徑數(shù)=5，預(yù)訓練后的實體和關(guān)系向量的維度=100，劃分=128，-GNNs 維度128。在池化部分設(shè)置Top-池化比率為0.8，非線性變換維度=256，=128，=64，=2，dropout 比例為0.5，模型學習率=0.000 5。實驗采用平均精度均值（mean average precision，MAP）作為評價指標，訓練集、測試集劃分比例為7∶3。

3.3 基準模型

本文將模型與六種關(guān)系推理方法進行比較，其中前兩種模型（TransE 和TransR）使用單步推理，即基于表示學習的方法，后四種模型（DeepPath、MINERVA、M-Walk 和RLH）使用多步推理，即基于路徑的方法。

TransE：一種經(jīng)典表示學習模型，它將知識圖譜中的實體與關(guān)系映射到同一個低維向量空間中，使用頭尾實體的向量差來預(yù)測關(guān)系。

TransR：TransR 與TransE 將實體和關(guān)系嵌入在相同空間的方法不同，TransR 分別在實體空間和關(guān)系空間構(gòu)建實體和關(guān)系嵌入。

DeepPath：一種用于學習多跳關(guān)系路徑的強化學習框架，使用強化學習自動探索路徑，并設(shè)計考慮準確性、多樣性和效率的獎勵函數(shù)，來解決知識圖譜中的多跳推理問題。

MINERVA：一種將查詢條件引入到強化學習路徑搜索中的方法，將推理問題形式化為一個馬爾可夫決策過程，使用LSTM 表示觀察序列和歷史決策序列，解決知識圖譜的問答問題。

M-Walk：在DeepPath 的基礎(chǔ)上使用蒙特卡洛樹（Monte-Carlo tree search，MCTS）策略幫助代理在圖中搜索路徑，從而嘗試在稀疏獎勵的環(huán)境下提升路徑搜索的準確性。

RLH：一個基于分層強化學習的知識圖譜推理模型，用于解決知識圖譜多跳推理過程的多語義問題。

3.4 對比實驗結(jié)果與分析

表2 和表3 展示了不同算法的實驗結(jié)果，從中可以看出，基于強化學習的路徑推理方法（DeepPath、MINERVA、M-Walk 和RLH）整體效果要優(yōu)于基于表示學習的方法（TransE 和TransR）。這表明路徑中可以包含更加豐富的語義信息，通過挖掘?qū)嶓w之間的路徑信息能有效地提高關(guān)系推理的準確性。而本文提出的SubGLP 模型優(yōu)于基于路徑的推理方法，在兩個數(shù)據(jù)集上比效果次好的RLH 模型的MAP 平均值分別高出0.060 與0.017，且比TransE 的MAP 平均值分別高出0.199 與0.190，這也驗證了實體間的子圖比實體間的單一路徑具備更豐富的語義特征，有助于獲取實體之間的關(guān)系特征，提升關(guān)系推理效果。

表2 FB15K-237 數(shù)據(jù)集上的關(guān)系推理（MAP）實驗結(jié)果Table 2 Link prediction results(MAP)on FB15K-237 datasets

表3 NELL-995 數(shù)據(jù)集上的關(guān)系推理（MAP）實驗結(jié)果Table 3 Link prediction results(MAP)on NELL-995 datasets

在分析路徑與子圖的區(qū)別時，也注意到由于基于路徑的方法使用的信息量較少，當某些關(guān)系可以使用單條路經(jīng)來明確指向時，如NELL-995 數(shù)據(jù)集上的athletePlaysInLeague 關(guān)系使用關(guān)系路徑athletePlays-ForTeam →teamPlaysInLeague 會產(chǎn)生很好的推理結(jié)果，使得基于路徑的方法的實驗結(jié)果也相對較好。

為了分析SubGLP 模型在兩個數(shù)據(jù)集上的效果差異，分別統(tǒng)計了兩個數(shù)據(jù)集上子圖的平均節(jié)點數(shù)與邊數(shù)，統(tǒng)計結(jié)果如圖3 所示。可見FB15K-237 數(shù)據(jù)集中的子圖規(guī)模更小，NELL-995 數(shù)據(jù)集的子圖則包含了更多節(jié)點和邊，這解釋了模型在NELL-995 數(shù)據(jù)集上效果更好、更穩(wěn)定的原因，也說明了內(nèi)容越豐富的子圖對于關(guān)系推理具有更加積極的作用。

圖3 兩種數(shù)據(jù)集抽取的子圖信息比較Fig.3 Subgraph statistics comparison of two datasets

3.5 消融實驗

為了進一步驗證模型的有效性，通過消融實驗來證明各個模塊的作用，探究實體與關(guān)系對關(guān)系預(yù)測的不同影響。在實驗中，刪除了完整模型中的子圖拼接模塊，分別使用節(jié)點子圖和邊子圖來表示預(yù)測實體之間的關(guān)系。其中，僅使用節(jié)點子圖的方法稱為SubGLP-nod，僅使用邊子圖的方法稱為SubGLPedg，實驗結(jié)果如表4 所示。從表中可以看出，不論是節(jié)點子圖還是邊子圖，都能帶來實驗效果的提升，其中節(jié)點子圖在兩個數(shù)據(jù)集上分別比RLH 的MAP 值平均高出0.041 與0.015，邊子圖在兩個數(shù)據(jù)集上分別比RLH 的MAP 平均值高出0.032 與0.003，這也驗證了基于子圖的關(guān)系推理的優(yōu)勢。

表4 消融實驗結(jié)果Table 4 Ablation experiment results

此外，從消融實驗中還可以看出節(jié)點子圖的效果比邊子圖的效果好，且在數(shù)據(jù)集FB15K-237 上的filmWrittenBy 關(guān)系和NELL-995 上的athletePlaysSport與athletePlaysForTeam 關(guān)系上，單獨的節(jié)點子圖具有比融合兩個子圖更好的效果，這說明實體信息對關(guān)系推理具有更重要的作用。同樣地，從消融實驗中還可以看出本文提出的SubGLP 方法與單獨使用節(jié)點子圖或邊子圖相比，MAP 值均有提升，這也說明模型使用融合兩種子圖信息的方法可以捕獲實體間的更多鄰域信息，這對于解決關(guān)系推理問題是更有效的。

4 總結(jié)

本文將圖神經(jīng)網(wǎng)絡(luò)與知識圖譜推理相結(jié)合，提出了基于子圖推理的知識圖譜關(guān)系預(yù)測方法SubGLP。為了獲取實體間更豐富的信息，采取了先分別構(gòu)建節(jié)點子圖和邊子圖，然后使用圖神經(jīng)網(wǎng)絡(luò)獲取子圖高階語義特征，最后融合兩個子圖的語義特征來預(yù)測實體之間關(guān)系的方法。在兩個基準數(shù)據(jù)集上的實驗結(jié)果驗證了本文方法優(yōu)于現(xiàn)有的基于單步推理與多步推理的關(guān)系預(yù)測方法。