使用子圖推理實現知識圖譜關系預測

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

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

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

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

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

圖1 知識圖譜推理方法轉變Fig.1 Transformation of reasoning method of knowledge graph

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

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

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

1 相關工作

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

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

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

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

2 基于子圖推理的知識圖譜關系預測

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

2.1 基本定義

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

2.2 模型框架

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

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

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

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

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

2.3 子圖抽取

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

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

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

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

2.4 子圖表示

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

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

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

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

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

2.5 融合預測

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

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

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

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

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

SubGLP 模型算法

3 實驗與結果分析

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

3.1 實驗數據集

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

表1 實驗數據集Table 1 Experimental datasets

3.2 參數設置與評估指標

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

3.3 基準模型

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

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

TransR：TransR 與TransE 將實體和關系嵌入在相同空間的方法不同，TransR 分別在實體空間和關系空間構建實體和關系嵌入。

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

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

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

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

3.4 對比實驗結果與分析

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

表2 FB15K-237 數據集上的關系推理（MAP）實驗結果Table 2 Link prediction results(MAP)on FB15K-237 datasets

表3 NELL-995 數據集上的關系推理（MAP）實驗結果Table 3 Link prediction results(MAP)on NELL-995 datasets

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

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

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

3.5 消融實驗

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

表4 消融實驗結果Table 4 Ablation experiment results

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

4 總結

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